Projektowanie topografii systemów VLSI. Cz. 3. Metody analityczne

Nagórny, Z.; Kos, A.

Artykuł - szczegóły

Tytuł artykułu

Projektowanie topografii systemów VLSI. Cz. 3. Metody analityczne

Autorzy

Nagórny Z. , Kos A.

Wybrane pełne teksty z tego czasopisma

http://ijet.pl/index.php/ijet

Identyfikatory

Warianty tytułu

The sedign of the VLSI circuit layout. Part 3. Analytical methods

Języki publikacji

Abstrakty

Niniejsza praca jest trzecią częścią przeglądu metod rozmieszczania modułów, stosowanych podczas projektowania topografii układów VLSI. W pracy szczegółowo został opisany algorytm zamiany parami oraz metody analityczne. Przedstawiono liczne modyfikacje algorytmu zamiany parami, łącznie z algorytmami wykorzystującymi metody relaksacyjne. Modyfikacje algorytmu zamiany parami oraz metody relaksacyjne są stosowane w programach rozmieszczania opartych na metodach analitycznych. Następnie, opisano podstawy zastosowania programowania kwadratowego i liniowego w rozmieszczaniu modułów. Ze względu na dużą liczbę rozwiązań stosowanych w metodach analitycznych, poszczególne rozwiązania szczegółowo przedstawiono na przykładzie wybranych programów rozmieszczania. W tym celu scharakteryzowano następujące programy rozmieszczania: GORDIAN / DOMINO, KraftWerk, FastPlace, mPL, PROUD, ATLAS, FAR, mFAR, BloBB, APlace. Przedstawiono również sposób zastosowania metody relaksacyjnej w układach o topografii swobodnej oraz możliwość optymalizacji topografii układu ze względu na aspekt termiczny.

The design process of the VLSI circuits requires the use of computer aided design tools. This paper is the third part of the survey of the cell placement techniques for digital VLSI circuits. In this part of the survey, the pairwise interchange algorithm and some analytical methods are presented. The force-directed placement algorithm and some modifications of the pairwise interchange algorithm, which are used in analytical algorithms are described. Then, the nonlinear programming, quadratic programming and linear programming techniques are presented. An application of these techniques to the cell placement problem is described. Nowadays the tools used for the cell placement, which utilize the presented algorithms are characterized: GORDIAN, DOMINO, KraftWerk, FastPlace, mPL, PROUD, ATLAS, FAR, mFAR, BloBB, APlace. A force-directed placer for a building block design style is described. The principles of the multilevel optimization for the cell placement problem are presented. Applications of the flow network and branch and bound algorithm to the cell placement are characterized. Some conclusions concerning described techniques and tools are presented.

Słowa kluczowe

VLSI projektowanie topografii układu układ scalony układ Standard Cell układ Sea-of-Gates rozmieszczanie modułów algorytm zamiany parami metody relaksacyjne relaksacja sterowana siłami zamiana sterowana siłami relaksacja parami sterowana siłami algorytm Goto metody analityczne programowanie nieliniowe programowanie kwadratowe programowanie liniowe sieć przepływowa wielopoziomowa optymalizacja GORDIAN/DOMINO KraftWerk FastPlace mPL PROUD ATLAS FAR mFAR BloBB APlace

VLSI physical design process integrated circuit Standard Cell Sea-of-Gates cell placement pairwise interchange algorithm force-directed placement algorithm force-directed relaxation force-directed interchange force-directed pairwise relaxation generalized force-directed relaxation analytical methods nonlinear programming quadratic programming linear programming flow network multilevel optimization GORDIAN DOMINO KraftWerk FastPlace mPL PROUD ATLAS FAR mFAR BloBB APlace

Wydawca

Wydawnictwo Naukowe PWN SA

Czasopismo

Kwartalnik Elektroniki i Telekomunikacji

Rocznik

2006

Tom

Vol. 52, z. 4

Strony

669--695

Opis fizyczny

Bibliogr. 40 poz., rys.

Twórcy

autor

Nagórny Z.

nagorny@inieria.pl

Studium Generale Sandomiriense, Wyższa Szkota Humanistyczno-Przyrodnicza w Sandomierzu, ul. Krakowska 26, 27-600 Sandomierz

autor

Kos A.

kos@agh.edu.pl

Akademia Górniczo-Hutnicza w Krakowie, Katedra Elektroniki, Al. Mickiewicza 30, 30-059 Kraków

Bibliografia

1. M.J.S. Smith: Application-Specific Integrated Circuits, Addison Wesley Longman, 1997.
2. A. Kos: Modelowanie hybrydowych układów mocy i optymalizacja ich konstrukcji ze względu na rozkład temperatury, Kraków, Wydawnictwa AGH, 1994.
3. B.T. Preas, M.J. Lorenzetti (red.): Physical Design Automation of VLSI Systems, Menlo Park, Benjamin-Cummings, 1988.
4. T. Ohtsuki (red.): Layout Design and Verification, Elsevier Science Publishers B.V. (North-Holland), 1986.
5. M.M. Vai: VLSI Design, CRC Press, 2001.
6. C. Sechen: VLSI Placement and Global Routing Using Simulated Annealing, Boston, Kluwer Academic Publishers, 1988.
7. M. Gajęcki, A. Kos: A Problem of Optimization of Topography of VLSI Circuit, Proc. of the XIXth National Conference on Circuit Theory and Electronic Networks, Kraków-Krynica (Poland), October 1996, pp. II/307-312.
8. W. Wolf: Modern VLSI Design: a systems approach, Englewood Cliffs, New Jersey, PTR Prentice Hall, 1994.
9. K. Shahookar, P. Mazumder: VLSI Cell Placement Techniques, ACM Computing Surveys, 1991, vol. 23, pp. 143-220.
10. C.J. Alpert, G.J. Nam, P.G. Villarrubia: Effective Free Space Management for Cut-Based Placement via Analytical Constraint Generation, IEEE Transactions on Computer-Aided Design, 2003, vol. 22, pp. 1343-1353.
11. T.C. Hu, E.S. Kuh (red.): VLSI Circuit Layout: Theory and Design, New York, IEEE Press, 1985.
12. M.A. Breuer (red.): Automatyczne projektowanie maszyn cyfrowych, Warszawa, PWN, 1976.
13. S.N. Adya, M.C. Yildiz, I.L. Markov, P.G. Villarrubia, P.N. Parakh, P.H. Madden: Benchmarking for Large-Scale Placement and Beyond, IEEE Transactions on Computer-Aided Design, 2004, vol. 23, pp. 472-486.
14. O. Liu, M. Marek-Sadowska: A Study of Netlist Structure and Placement Efficiency, IEEE Transactions on Computer-Aided Design, 2005, vol. 24, pp. 762-772.
15. C.C. Chang, J. Cong, M. Romesis, M. Xie: Optimality and Scalability Study of Existing Placement Algorithms, IEEE Transactions on Computer-Aided Design, 2004, vol. 23, pp. 537-549.
16. S. Sutanthavibul, E. Shragowits, J.B. Rosen: An Analytical Approach to Floorplan Design and Optimization, IEEE Transactions on Computer-Aided Design, 1991, vol. 10, pp. 761-769.
17. S. Goto: An Efficient Algorithm for the Two-Dimensional Placement Problem in Electrical Circuit Layout, IEEE Transactions on Circuits and Systems, 1981, vol. 28, pp. 12-18.
18. W. Findeisen, J. Szymanowski, A. Wierzbicki: Teoria i metody obliczeniowe optymalizacji, Warszawa, PWN, 1977.
19. W. Grabowski: Programowanie matematyczne, Warszawa, Państwowe Wydawnictwo Ekonomiczne, 1982.
20. I. Dziubiński, T. Świątkowski (red.): Poradnik matematyczny, Warszawa, PWN, 1982.
21. J.M. Kleinhans, G. Sigl, F.M. Johannes, K.J. Antreich: GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization, IEEE Transactions on Computer-Aided Design, 1991, vol. 10, pp. 356-365.
22. G. Sigl, K. Doll, F.M. Johannes: Analytical Placement: A Linear or a Quadratic Objective Function?, Proc. of the Design Automation Conference, 1991, pp. 427-432, http://www.sigda.org/Archives/ProceedingArchives/Dac/.
23. K. Doll, F.M. Johannes, K.J. Antreich: Iterative Placement Improvement by Network Flow Methods, IEEE Transactions on Computer-Aided Design, 1994, vol. 13, pp. 1189-1200.
24. R. Sedgewick: Algorithms in C, Part 5: Graph Algorithms, Addison Wesley Professional, 2002.
25. R. Sedgewick: Algorytmy w C++. Część 5. Grafy, Warszawa, Wydawnictwo RM, 2003.
26. H. Eisenmann, F.M. Johannes: Generic Global Placement and Floorplanning, Proc. of the Design Automation Conference, 1998, pp. 269-274, http://www.sigda.org/Archives/ProceedingArchives/Dac/.
27. B. Obermeier, H. Ranke, F.M. Johannes: Kraftwerk - A Versatile Placement Approach, Proc. of the International Symposium on Physical Design, 2005, pp. 242-244, http://www.sigda.org/Archives/ProceedingArchives/Ispd/.
28. N. Viswanathan, C.C.-N. Chu: FastPlace: Efficient Analytical Placement Using Cell Shifting, Iterative Local Refinement and a Hybrid Net Model, IEEE Transactions on Computer-Aided Design, 2005, vol. 24, pp. 722-733.
29. F. Mo, A. Tabbara, R.K. Brayton: A Force-Directed Macro-Cell Placer, Proc. of the International Conference on Computer-Aided Design, 2000, pp. 177-180, http://www.sigda.org/Archives/ProceedingArchives/Iccad/.
30. T.F. Chan, J. Cong, T. Kong, J.R. Shinnerl: Multilevel Optimization for Large-Scale Circuit Placement, Proc. of the International Conference on Computer-Aided Design, 2000, pp. 177-176, http://cadlab.cs.ucla.edu/~cong/papers/iccad00_placement.pdf
31. T.F. Chan, J. Cong, T. Kong, J.R. Shinnerl, K. Sze: An Enhanced Multilevel Algorithm for Circuit Placement, Proc. of the International Conference on Computer-Aided Design, 2003, pp. 299-306, http://ballade.cs.ucla.edu/~cong/papers/mpl2.pdf.
32. C.-K. Cheng, E.S. Kuh: Module Placement Based on Resistive Network Optimization, IEEE Transactions on Computer-Aided Design, 1984, vol. 3, pp. 218-225.
33. R.-S. Tsay, E.S. Kuh, C.-P. Hsu: PROUD: A Fast Sea-Of-Gates Placement Algorithm, Proc. of the Design Automation Conference, 1988, pp. 318-323.
34. L. Sha, T. Blank: ATLAS - A Technique for Layout using Analytic Shapes, Proc. of the International Conference on Computer-Aided Design, 1987, pp. 84-87, http://www.sigda.org/Archives/ProceedingArchives/Iccad/Last20/Papers/1987/.
35. B. Hu, M. Marek-Sadowska: Multilevel Fixed-Point-Addition-Based VLSI Placement, IEEE Transactions on Computer-Aided Design, 2005, vol. 24, pp. 1188-1203.
36. A.B. Kahng, Q. Wang: Implementation and Extensibility of an Analytic Placer, IEEE Transactions on Computer-Aided Design, 2005, vol. 24, pp. 734-747.
37. H.H. Chan, I.L. Markov: Practical Slicing and Non-slicing Block-Packing without Simulated Annealing, Proc. of the Great Lakes Symposium on VLSI, 2004, pp. 282-287, http://vlsicad.eecs.umich.edu/BK/BloBBB/PAPERS/p037-chan.pdf.
38. VLSI CAD Bookshelf Slots and Entries, A.B. Kahng, I.L. Markov, http://vlsicad.eecs.umich.edu/BK/Slots/slots/BlockPacking.html.
39. VLSI CAD Bookshelf Slots and Entries, A.B. Kahng, I.L. Markov, http://vlsicad.eecs.umich.edu/BK/Slots/slots/WirelengthdrivenStandardCellPlacement.html.
40. J.-G. Kim, Y.-D. Kim: A Linear Programming-Based Algorithm for Floorplanning in VLSI Design, IEEE Transactions on Computer-Aided Design, 2003, vol. 22, pp. 584-592.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-BWA0-0016-0031