PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

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

Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
EN
The sedign of the VLSI circuit layout. Part 3. Analytical methods
Języki publikacji
PL
Abstrakty
PL
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.
EN
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.
Rocznik
Strony
669--695
Opis fizyczny
Bibliogr. 40 poz., rys.
Twórcy
autor
autor
  • Studium Generale Sandomiriense, Wyższa Szkota Humanistyczno-Przyrodnicza w Sandomierzu, ul. Krakowska 26, 27-600 Sandomierz, nagorny@inieria.pl
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
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.