Projektowanie topografii systemów VLSI. Cz. 1, Style i etapy projektowania, rozmieszczanie modułów

Nagórny, Z.; Kos, A.

Artykuł - szczegóły

Tytuł artykułu

Projektowanie topografii systemów VLSI. Cz. 1, Style i etapy projektowania, rozmieszczanie modułów

Autorzy

Nagórny Z. , Kos A.

Wybrane pełne teksty z tego czasopisma

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

Identyfikatory

Warianty tytułu

The design of the VLSI circuit layout. Part 1, Styles, phases, placement

Języki publikacji

Abstrakty

Projektowanie układów VLSI wymaga stosowania systemów projektowania wspomaganych komputerowo. Niniejsza praca jest pierwszą częścią przeglądu metod rozmieszczania modułów, stosowanych podczas projektowania topografii układów VLSI. Opisano różne style topografii oraz przykłady układów dla poszczególnych stylów. Następnie, przedstawiono etapy projektowania topografii: podział, planowanie układu, rozmieszczenie, trasowanie połączeń oraz weryfikacja. Planowanie układu zostało szczegółowo omówione, ze względu na podobieństwa łączące ten etap z rozmieszczaniem. Przedstawiono problem rozmieszczania modułów. Omówiono sposoby estymacji długości połączeń. Opisano metody minimalizacji opóźnień w układzie. Przedstawiono stosowane metody rozmieszczania modułów.

The design process of the VLSI circuits requires the use of computer aided design tools. This paper the first part of the survey of the cell placement techniques for digital VLSI circuits. Design styles used in VLSI circuits are described. Layouts of Standard Cell, Gate Array, Sea-of-Gates and Field Programmable Gate Array are presented. Then the physical design flow, which includes partitioning, becouse this stage is similar to the placement problem. The cell placement problem and placement techniques are describes. VLSI cell placement phase of the physical design process. Cell placement, which is a ver difficult optimization problem, has proved to be a np. - compete. The goail of the VLSI cell placement is to arrange all the cells on a placement carrier while minimizing an objective or cost function. The most commonly used objectives of the placement are to minimize the total estimated wire length and the interconnect congestion, and to meet the timing requirements for critical nets. Commonly used wire length estimates for the cell placement are presented. The timing driven placement methods are described. The algorithms used for the cell placement are presented.

Słowa kluczowe

VLSI projektowanie topografii układu układ scalony projektowanie wspomagane komputerowo układ Standard Cell matryca bramkowa GA układ Sea-of-Gates układ FPGA podział planowanie układu rozmieszczanie modułów trasowanie połączeń estymacja długości połączeń metoda połowy obwodu graf pełny minimalizacja opóźnień metody konstrukcyjne algorytm min-cut algorytm zamiany parami wyżarzanie symulowane algorytm genetyczny metody analityczne sieć neuronowa

VLSI physical design process integrated circuit layout computer-aided design Standard Cell Gate Array Sea-of-Gates field programmable gate array FPGA partitioning loorplanning cell placament routing wire length estimation half-perimeter complete graph timing-driven placement constructive placement methods min-cut algorithm pairwise interchange algorithm simulated annealing genetic algorithms analytical methods neural network

Wydawca

Wydawnictwo Naukowe PWN SA

Czasopismo

Kwartalnik Elektroniki i Telekomunikacji

Rocznik

2006

Tom

Vol. 52, z. 3

Strony

451--468

Opis fizyczny

Bibliogr. 51 poz.

Twórcy

autor

Nagórny Z.

nagorny@interia.pl

Studium Generalne Sandomiriense, Wyższa Szkoła Humanistyczno-Przyrodnicza, 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. Lorenzelli (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. D.F. Wong, H.W. Leong, C.L. Liu: Simulated Annealing for VLSI Design, Kluwer Academic Publishers, 1988.
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. V. Betz, J. Rose: VPR: A New Packing, Placement and Routing Tool for FPGA Research, Proc. of the 7th International Workshop on Field Programmable Logic and Applications, London, 1997, pp. 213-222, http://www.eecg.toronto.edu/~vaughn/papers/fpl97.pdf.
11. 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.
12. M. Mogaki, C. Miura, H. Terai: Algorithm for Block Placement with Size Optimization Technique by the Linear Programming Approach, Proc. of the IEEE International Conference on Computer Aided Design, 1987, pp. 80-83.
13. Y.T. Lai, S.M. Leinwand: Algorithms for Floorplan Design Via Rectangular Dualization, IEEE Transactions on Computer Aided Design, 1988, vol. 7, pp. 1278-1289.
14. S. Wimer, I. Koren, I. Cederbaum: Optimal Aspects Ratios of Building Blocks in VLSI, IEEE Transactions on Computer Aided Design, 1989, vol. 8, pp. 139-145.
15. K. Chong, S. Sahni: Optimal Realisations of Floorplans, IEEE Transactions on Computer Aided Design, 1993, vol. 12, pp. 193-801.
16. G.K.H. Yeap, M. Sarrafzadeh: A Unified Approach to Floorplan Sizing and Enumeration, IEEE Transactions on Computer Aided Design, 1993, vol. 12, pp. 1858-1867.
17. W. Shi: A Fast Algorithm for Area Minimization of Slicing Floorplans, IEEE Transactions on Computer Aided Design, 1996, vol. 15, pp. 1525-1532.
18. P.S. Dasgupta, S. Sur-Kolay, B. Bhattacharya: A Unified Approach to Topology Generation and Optimal Sizing of Floorplans, IEEE Transactions on Computer Aided Design, 1998, vol. 17, pp. 126-135.
19. P. Pan, C.L. Liu: Area Minimization for Floorplans, IEEE Transactions on Computer Aided Design, 1995, vol. 14, pp. 123-132.
20. H. Murata, K. Fujiyoshi, S. Nakatake, Y. Kajitani: VLSI Module Placement Based on Rectangle - Packing by the the Sequence - Pair IEEE Transactions on Computer Aided Design, 1996, vol. 15, pp. 1518-1524.
21. H. Murata, K. Fujiyoshi, M. Kanenko: VLSI/PCB Placement with Obstacles Based on Sequence - Pair, IEEE Transactions on Computer Aided Design, 1998, vol. 17, pp. 60-68.
22. K. Fujiyoshi, H. Murata: Arbitrary Convex and Concave Rectilinear Block Packing Using Sequence - Pair, IEEE Transactions on Computer Aided Design, 2000, vol. 19, pp. 224-233.
23. S. Nakatake, K. Fujiyoshi, H. Murata, Y. Kajitani: Module Packing Based on the BSG - Structure and IC Layout Applications IEEE Transactions on Computer Aided Design, 1998, vol. 17, pp. 519-530.
24. E.F.Y. Young, C.C.N. Chu, Z.C. Shen: Twin Binary Sequences: A Nonredundant Representation for General Nonslicing Floorplan, IEEE Transactions on Computer Aided Design, 2003, vol. 22, pp. 457-469.
25. Y. Feng, D.P. Mehta, H. Yang: Constrained Floorplanning Using Network Flows, IEEE Transactions on Computer Aided Design, 2004, vol. 23, pp. 572-580.
26. D. Sitaram, Y. Zheng, K.L. Shepard: Full - Chip Three - Dimensional Shapes - Based RLC Extraction, IEEE Transactions on Computer Aided Design, 2004, vol. 23, pp. 711-727.
27. A. Kos, Z. Nagórny: Estymacja długości połączeń w układach VLSI, IV Krajowa Konferencja Elektroniki, Darłówko Wschodnie, czerwiec 2005, pp. 159-164.
28. M.A. Breuer (red.): Automatyczne projektowanie maszyn cyfrowych, Warszawa, PWN, 1976.
29. D.S. Rao, J.D. Provence: An integrated approach to routing and via minimization, Information Processing Letters, 1991, vol. 39, pp. 257-263.
30. T.C. Hu, E.S. Kuh (red.): VLSI Circuit Layout: Theory and Design, New York, IEEE Press, 1985.
31. A.E. Dunlop, B.W. Kernighan: A Procedure for Placement of Standard - Cell VLSI Circuits, IEEE Transactions on Computer Aided Design, 1985, vol. 4, pp. 92-98.
32. P.R. Suaris, G. Kedem: An Algorithm for Quadrisection and Its Application to Standard Cell Placement, IEEE Transactions on Circuits and Systems, 1988, vol. 35, pp. 294-302.
33. A.E. Caldwell, A.B. Kahng, I.L. Markov: Can Recursive Bisection Alone Produce Routable Placements?, Design Automation Conference, 2000, pp. 477-482, http://www.eecs.umich.edu/~imarkov/pubs/conf/c015.pdf.
34. A.E. Caldwell, A.B. Kahng, I.L. Markov: Optimal Partitioners and End Case Placers for Standard Cell Layout, IEEE Transactions on Computer Aided Design, 2000, vol. 19, pp. 1304-1313.
35. M. Wang, X. Yang, M. Sarrafzadeh: Dragon2000: Standard - Cell Placement Tool for Large Industry Circuits, International Conference on Computer Aided Design, 2000, pp. 260-263, http://er.cs.ucla.edu/Dragon/papers/dragon.pdf.
36. A.R. Agnihotri, S. Ono, C. Li, M.C. Yildiz, A. Khatkhate, C.K. Koh, P.H. Madden: Mixed Block Placement via Fractional Cut Recursive Bisection, IEEE Transactions on Computer Aided Design, 2005, vol. 24, pp. 748-761.
37. M.C. Yildiz, P.H. Madden: Improved Cut Sequences for Partitioning Based Placement, Design Automation Conference, 2001, pp. 776-779, http://vlsicad.cs.binghamton.edu/pubs/Yildiz01dac.pdf.
38. P.H. Madden: Reporting of Standard Cell Placement Results, IEEE Transactions on Computer Aided Design, 2002, vol. 21, pp. 240-247.
39. S.N. Adya, M.C. Yildiz, I.L. Markov, P.G. Vil1arrubia, 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.
40. X. Yang, B.K. Choi, M. Sarrafzadeh: Timing - Driven Placement using Design Hierarchy Guided Constraint Generation, International Conference on Computer Aided Design, 2002, pp. 177-184, http://er.cs.ucla.edu/Dragon/papers/timingdragon.pdf.
41. R. Nair, C.L. Berrman, P.S. Hauge, E.J. Yoffa: Generation of Performance Constraints for Layout, IEEE Transactions on Computer Aided Design, 1989, vol. 8, pp. 860-874.
42. H. Youssef, R.B. Lin, E. Shragowitz: Bounds on Net Delays for VLSI Circuits, IEEE Transactions on Circuits and Systems, 1992, vol. 39, pp. 815-824.
43. H. Ren, D.Z. Pan, D.S. Kung: Sensitivity Guided Net Weighting for Placement - Driven Synthesis, IEEE Transactions on Computer Aided Design, 2005, vol. 24, pp. 711-721.
44. Q. Liu, B. Hu, M. Marek Sadowska: Individual Wire Length Prediction With Application to Timing - Driven Placement, IEEE Transactions on VLSI Systems, 2004, vol. 12, pp. 1004-1014.
45. T. Łuba, K. Jasiński, B. Zbierzchowski: Specjalizowane układy cyfrowe w strukturach PLD i FPGA, Warszawa, Wydawnictwa Komunikacji i Łączności, 1997.
46. T. Łuba, B. Zbierzchowski: Komputerowe projektowanie układów cyfrowych, Warszawa, Wydawnictwa Komunikacji i Łączności, 2000.
47. S. Sutanthavibul, E. Shragowitz, J.B. Rosen: An Analytical Approach to Floorplan Design and Optimization, IEEE Transactions on Computer Aided Design, 1991, vol. 10, pp. 761-769.
48. 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/BloBB/PAPERS/p037 -chan.pdf.
49. 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/.
50. R. Sedgewick: Algorithms in C, Part 5: Graph Algorithms, Addison Wesley Professional, 2002 .
51. R. Sedgewick: Algorytmy w C++. Część 5. Grafy, Warszawa, Wydawnictwo RM, 2003.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-BWA9-0002-0010