Projektowanie topografii systemów VLSI. Cz. 2, Algorytm min-cut

Nagórny, Z.; Kos, A.

Artykuł - szczegóły

Tytuł artykułu

Projektowanie topografii systemów VLSI. Cz. 2, Algorytm min-cut

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. 2, Min-cut algorithm

Języki publikacji

Abstrakty

Niniejsza praca jest drugą częścią przeglądu metod rozmieszczania modułów, stosowanych podczas projektowania topografii układów VLSI. W pracy szczegółowo został opisany algorytm min-cut. Przedstawiono algorytm Kernighana i Lina, który jest stosowany w algorytmie min-cut. Opisano algorytm podziału Fiduccia i Mattheysesa. Przedstawiono modyfikacje algorytmu min-cut. Podany został sposób zastosowania algorytmu min-cut dla topografii swobodnej. Omówiono wielopoziomowy algorytm podziału hMETIS. Scharakteryzowano obecnie stosowane programy, które wykorzystują algorytm min-cut: Capo, Dragon, Feng Shui, QUAD.

The design process of the VLSI circuits requires the use of computer aided design tools. This paper is the second part of the survey of the cell placement techniques for digital VLSI circuits. In this part of the survey, the min-cut algorithm is presented. The Kernighan-Lin algorithm and its modifications, which are the base of the min-cut algorithm are described. Then, the Fiduccia-Mattheyses algorithm is described. The computation time of the Fiduccia-Mattheyses algorithm increases only slightly more than linearly with the number of logic cells in the circuit. It is a very important improvement. Some modifications of the min-cut algorithm are presented. The terminal propagation and the quadrisection algorithm are described. The application of the min-cut algorithm for the building block design style is presented. The principles of the multilevel circuit partitioning algorithm are described. Two multilevel circuit partitioning algorithms are characterized: hMETIS and hMETIS-Kway. Nowadays the tools used for the cell placement, which utilize the presented algorithms are characterized Capo, Dragon, Feng Shui, QUAD. Some conclusions concerning described techniques and tools are presented.

Słowa kluczowe

VLSI projektowanie topografii układu układ scalony projektowanie wspomagane komputerowo układ Standard Cell rozmieszczanie modułów podział układu algorytm Kernighana-Lina algorytm Fiduccia-Mattheysesa algorytm min-cut wielopoziomowy podział układu algorytm hMETIS Capo Dragon feng shui quad

VLSI physical design process integrated circuit layout computer-aided design Standard Cell cell placement circuit partitioning Kernighan-Lin algorithm Fiduccia-Mattheyses algorithm min-cut algorithm multilevel circuit partitioning hMETIS algorithm Capo Dragon Feng Shui QUAD

Wydawca

Wydawnictwo Naukowe PWN SA

Czasopismo

Kwartalnik Elektroniki i Telekomunikacji

Rocznik

2006

Tom

Vol. 52, z. 3

Strony

469--488

Opis fizyczny

Bibliogr. 36 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, Z. Nagórny: Estymacja długości połączeń w układach VLSI, IV Krajowa Konferencja Elektroniki, Darłówko Wschodnie, czerwiec 2005, ss. 159-164.
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.A. Breuer (red.): Automatyczne projektowanie maszyn cyfrowych, Warszawa, PWN, 1976.
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. T.C. Hu, E.S. Kuh (red.): VLSI Circuit Layout: Theory and Design, New York, IEEE Press, 1985.
11. 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.
12. B. Krishnamurthy: An Improved Min-Cut Algorithm for Partitioning VLSI Networks, IEEE Transactions on Computers, 1984, vol. 33, pp. 438-446.
13. 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.
14. 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.
15. A.E. Caldwell, A.B. Kahng, I.L. Markov: Design and Implementation of Move-Based Heuristics for VLSI Hypergraph Partitioning, ACM Journal of Experimental Algorithmics, 2000, vol. 5, artykuł 5, http://www.eecs.umich.edu/~imarkov/pubs/jour/j004.pdf.
16. C.J. Alpert, J.H. Huang, A.B. Kahng: Multilevel Circuit Partitioning, IEEE Transactions on Computer Aided Design, 1998, vol. 17, pp. 655-667.
17. G. Karypis, R. Aggarwal, V. Kumar, S. Shekhar: Multilevel Hypergraph Partitioning: Applications in VLSI Domain IEEE-Transactions on VLSI Systems, 1999, vol. 7, pp. 69-79.
18. G. Karypis, V. Kumar, : Multilevel k-way Hypergraph Partitioning, Design Automation Conference, 1999, pp. 343-348, http://www.users.cs.umn.edu/~karypis/publications/Papers/PDF/khmetis.pdf.
19. University of Minnesota, USA; George Karypis's Home Page, http://www.users.cs.umn.edu/~karypis/metis/hmetis/download.html
20. 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.
21. A.E. Caldwell, A.B. Kahng, I.L. Markov: Improved Algorithms for Hypergraph Bipartitioning, Asia and South Pacific Design Automation Conference, 2000, pp. 661-666, http://www.eecs.umich.edu/ imarkov/pubs/conf/c0l3.pdf.
22. A.E. Caldwell, A.B. Kahng, I.L. Markov: Iterative Partitioning with Varying Node Weights,VLSI Design, 2000, vol. 11, pp. 249-258, http://www.eecs.umich.edu/~imarkov/pubs/jour/j006.pdf.
23. 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.
24. 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.
25. A.R. Agnihotri, S. Ono, C. Li, M.C. Yildiz, A. Khatkhate, CK. Koh, P.H. Madden: Mixed Block Placement via Fractional Cut Recursive Bisection, IEEE Transactions on Computer Aided Design, 2005, vol. 24, pp. 748-761.
26. 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/Yildiz0ldac.pdf.
27. M.C. Yildiz, P.H. Madden: Global Objectives for Standard-Cell Placement, Great Lakes Symposium on VLSI, 2001, pp. 68-72, http://vlsicad.cs.binghamton.edu/pubs/Yildiz0l0068.pdf.
28. A. Agnihotri, M.C. Yildiz, A. Khatkhate, A. Mathur, S. Ono, P.H. Madden: Fractional Cut: Improved Recursive Bisection Placement, International Conference on Computer Aided Design, 2003, pp. 307-310, http://vlsicad.cs.binghamton.edu/pubs/Agnihotri03.pdf.
29. D.J.H. Huang, A.B. Kahng: Partitioning-Based Standard-Cell Global Placement with an Exact Objective, International Symposium on Physical Design, 1997, pp. 18-25, http://citeseer.ist.psu.edu/71921.html.
30. VLSI CAD Bookshelf Slots and Entries, A.B. Kahng, I.L. Markov, http://vlsicad.eecs.umich.edu/BK/Slots/slots/WirelengthdrivenStandardCellPlacement.html
31. P.H. Madden: Reporting of Standard Cell Placement Results, IEEE Transactions on Computer Aided Design, 2002, vol. 21, pp. 240-247.
32. 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.
33. 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.
34. 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-548.
35. 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.
36. 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.

Typ dokumentu

Bibliografia

Identyfikator YADDA

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