Projektowanie topografii systemów VLSI. Cz. 4. Symulowane wyżarzanie, sieci neuronowe

Nagórny, Z.; Kos, A.

Artykuł - szczegóły

Tytuł artykułu

Projektowanie topografii systemów VLSI. Cz. 4. Symulowane wyżarzanie, sieci neuronowe

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 4. Simulated annealing, neural networks

Języki publikacji

Abstrakty

Niniejsza praca jest czwartą, ostatnią częścią przeglądu metod rozmieszczania modułów, stosowanych podczas projektowania topografii układów VLSI. Modułem jest fragment systemu wyodrębniony ze względu na pełnioną funkcję. Praca jest poświęcona algorytmowi symulowanego wyżarzania oraz sieciom neuronowych. Przedstawiono dokładny opis algorytmu symulowanego wyżarzania oraz sposób zastosowania algorytmu do rozmieszczania modułów. Programy wykorzystujące algorytm symulowanego wyżarzania zostały szczegółowo opisane. W tym celu scharakteryzowano następujące programy rozmieszczania: TimberWolf, MGP, MPG-MS, VPR. Następnie, opisano sposób zastosowania sieci samoorganizującej się oraz sieci Hopfielda w optymalizacji topografii układów VLSI. Przedstawiono rezultaty rozmieszczania modułów otrzymane z użyciem sieci Hopfielda. Następnie, scharakteryzowano inne metody stosowane podczas rozmieszczania modułów: algorytmy genetyczne, strategie ewolucyjne, schemat rozmieszczanie-planowanie topografii-rozmieszczanie, programy dla układów 3D VLSI oraz sprzętowe metody rozwiązania problemu rozmieszczania modułów. Porównano metody rozmieszczania modułów przedstawione w przeglądzie.

The design process of the VLSI circuits requires the use of computer aided design tools. This paper is the fourth part of the survey of the cell placement techniques for digital VLSI circuits. In this part of the survey, the simulated annealing algorithm and neural networks are presented. An application of the simulated annealing algorithm to the cell placement problem is described. Nowadays the tools used for the cell placement, which utilize the presented algorithms are characterized: TimberWolfSC, TimberWolfMC, MGP, MPG-MS, VPR. Then, applications of neural networks to the cell placement problem are described. A self-organizing network and Hopfield network for the cell placement problem are presented. Some circuit layouts generated by using the Hopfield network are presented. Applications of a genetic algorithm, evolutionary strategy, three-stage placement-floorplanning-placement flow and special purpose hardware for the cell placement are described. Tools used for the 3D VLSI cell placement are characterized. Some conclusions concerning described techniques and tools are presented.

Słowa kluczowe

VLSI physical design process integrated circuit Standard Cell Gate Array Sea-of-Gates field programmable gate array FPGA floorplanning cell placement routing pairwise interchange algorithm simulated annealing algorithm cooling schedule multilevel optimization neural networks self-organizing network Kohonen algorithm Hopfield network genetic algorithm evolutionary strategy reconfigurable system TimberWolf MGP MPG-MS VPR Parquet Gravity

Wydawca

Wydawnictwo Naukowe PWN SA

Czasopismo

Kwartalnik Elektroniki i Telekomunikacji

Rocznik

2006

Tom

Vol. 52, z. 4

Strony

697--727

Opis fizyczny

Bibliogr. 70 poz., rys.

Twórcy

autor

Nagórny Z.

nagorny@inieria.pl

Studium Generale Sandomiriense, Wyższa Szkoła 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. S. Osowski: Sieci neuronowe w ujęciu algorytmicznym, Warszawa, WNT, 1996.
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, (dostępna w bibliotece WA 290).
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. 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. S. Kirkpatrick, C.D. Gelatt, Jr., M.P. Vecchi: Optimization by Simulated Annealing, Science, 1983, vol. 220, no 4598, pp. 671-680.
13. D.T. Pham, D. Karaboga: Intelligent Optimisation Techniques, Springer-Verlag London Limited, 2000.
14. J. Mańdziuk: Sieci neuronowe typu Hopfielda. Teoria i przykłady zastosowań, Warszawa, Akademicka Oficyna Wydawnicza EXIT, 2000.
15. J.A. Freeman, D.M. Skapura: Neural networks: algorithms, applications, and programming techniques, Addison-Wesley Publishing Company, 1991.
16. T. Khanna: Foundations of neural networks, Addison-Wesley Publishing Company, 1990.
17. C. Sechen, A. Sangiovanni-Vincentelli: The TimberWolf Placement and Routing Package, IEEE Journal of Solid-State Circuits, 1985, vol. 20, pp. 510-522.
18. C. Sechen, K.-W. Lee: An Improved Simulated Annealing Algorithm for Row-Based Placement, Proc. of the International Conference on Computer-Aided Design, 1987, pp. 478-481, http://www.sigda.org/Archives/ProceedingArchives/Iccad/.
19. C. Sechen D. Braun, A. Sangiovanni-Vincentelli: ThunderBird: A Complete Standard Cell Layout Package, IEEE Journal of Solid-State Circuits, 1988, vol. 23, pp. 410-420.
20. W. Swartz, C. Sechen: New Algorithms for the Placement and Routing of Macro Cells, Proc. of the International Conference on Computer-Aided Design, 1990, pp. 336-339, http://www.sigda.org/Archives/ProceedingArchives/Iccad/
21. W.-J. Sun, C. Sechen: Efficient and Effective Placement for Very Large Circuits, IEEE Transactions on Computer-Aided Design, 1995, vol. 14, pp. 349-359.
22. Strona internetowa firmy InternetCAD.com, http://www.internetcad.com.
23. C.-C. Chang, J. Cong, Z. Pan, X Yuan: Multilevel Global Placement With Congestion Control, IEEE Transactions on Computer-Aided Design, 2003, vol. 22, pp. 395-409.
24. 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.
25. C.-C. Chang, J. Cong, X. Yuan: Multi-level Placement for Large-Scale Mixed-Size IC Design, Proc. of the Asia and South Pacific Design Automation Conference, 2003, pp. 325-330, http://cadlab.cs.ucla.edu/~cong/papers/aspdac03.pdf.
26. V. Betz, J. Rose: VPR: A New Packing, Placement and Routing Tool for FPGA Research, Proc. 7th International Workshop on Field Programmable Logic and Applications, London, 1997, pp. 213-222, http://www.eecg.toronto.edu/~vaughn/papers/fpl97.pdf.
27. A. Marquardt, V. Betz, J. Rose: Timing-Driven Placement for FPGAs, Proc. International Symposium on FPGA, 2000, pp. 203-213, http://www.sigda.org/Archives/ProceedingArchives/Compendiums/papers/fpga/confsym.htm.
28. P. Maidee, C. Ababei, K. Bazargan: Timing-Driven Partitioning-Based Placement for Island Style FPGAs, IEEE Transactions on Computer-Aided Design, 2005, vol. 24, pp. 395-406.
29. VLSI CAD Bookshelf Slots and Entries, A.B. Kahng, I.L. Markov, http://vlsicad.eecs.umich.edu/BK/Slots/slots/FPGALayout.html.
30. H. Murata, K. Fujiyoshi, S. Nakatake, Y. Kajitani: VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair, IEEE Transactions on Computer-Aided Design, 1996, vol. 15, pp. 1518-1524.
31. 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.
32. 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.
33. 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.
34. 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.
35. 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.
36. F. Balasa, S.C. Maruvada, K. Krishnamoorthy: On the Exploration of the Solution Space in Analog Placement With Symmetry Constraints, IEEE Transactions on Computer-Aided Design, 2004, vol. 23, pp. 177-191.
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/BloBB/PAPERS/p037-chan.pdf.
38. J.J. Hopfield, D.W. Tank: "Neural" computation of decisions in optimization problems, Biological Cybernetics, 1985, vol. 52, pp. 141-152.
39. R. Tadeusiewicz: Sieci neuronowe, Warszawa, Akademicka Oficyna Wydawnicza, 1993.
40. J. Hertz, A. Krogh, R.G. Palmer: Wstęp do teorii obliczeń neuronowych, Warszawa, WNT, 1995.
41. J. Żurada, M. Marski, W. Jędruch: Sztuczne sieci neuronowe, Warszawa, Wydawnictwo PWN, 1996.
42. M. Glesner, W. Pöchmüller: Neurocomputers, London, Chapman & Hall, 1994.
43. C.-X. Zhang, D.A. Mlynski: Mapping and Hierarchical Self-Organizing Neural Networks for VLSI Placement, IEEE Transactions on Neural Networks, 1997, vol. 8, pp. 299-314.
44. A. Hemani, A. Postula: Cell Placement by Self-Organisation, Neural Networks, 1990, vol. 3, pp. 377-383.
45. P. Bratek, A. Kos: Complex Optimisation of Topology of VLSI Circuits with Self-Organising Neural Nets, Proc. of the MIXDES Mixed Design of Integrated Circuits and Systems, Łódź (Poland), June 1996, pp. 78-83.
46. P. Bratek, A. Kos: Self-Organising Neural Computations for Optimisation of IC Topography in Thermal Aspect, Proc. of the XIXth National Conference on Circuit Theory and Electronic Networks, Kraków-Krynica (Poland), October 1996, pp. II/627-632.
47. Y. Takefuji, K.-C. Lee, H. Aiso: An artificial maximum neural network: a winner-take-all neuron model forcing the state of the system in a solution domain, Biological Cybernetics, 1992, vol. 67, pp. 243-251.
48. H. Mączka, P. dziurdzia, A. Kos: Neural Algorithm for Minimisation of Total Length of Connections in VLSI Circuits, Proc. of the XIXth National Conference on Circuit Theory and Electronic Networks, Kraków-Krynica (Poland), October 1996, pp. II/319-324.
49. A. Kos, Z. Nagórny: Minimalizacja długości połączeń w układach elektronicznych z wykorzystaniem sieci Hopfielda, Kwartalnik Elektroniki i Telekomunikacji, 2005, tom 51, z. 1, pp. 55-72.
50. Z. Nagórny , A. Kos: Optymalizacja z wykorzystaniem zmodyfikowanej sieci Hopfielda, Kwartalnik Elektroniki i Telekomunikacji, 2005, tom 51, z. 2, pp. 255-275.
51. A. Kos, Z. Nagórny: A Modified Hopfield Neural Network for VLSI Placement, Proc. of the MIXDES 2005 Mixed Design of Integrated Circuits and Systems, Kraków (Poland), June 2005, vol. 1, pp. 33-38.
52. 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.
53. A. Kos, Z. Nagórny: Estymacja długości połączeń w układach VLSI, Elektronika, 2005, rok 46, nr 11, pp. 47-49.
54. K. Shahookar, P. Mazumder: A Genetic Approach to Standard Cell Placement Using Meta-Genetic Parameter Optimization, IEEE Transactions on Computer-Aided Design, 1990, vol. 9, pp. 500-511.
55. R.M. Kling, P. Banerjee: ESP: Placement by Simulated Evolution, IEEE Transactions on Computer-Aided Design, 1989, vol. 8, pp. 245-256.
56. S.N. Adya, I.L. Markov: Fixed-Outline Floorplanning: Enabling Hierarchical Design, IEEE Transactions on VLSI Systems, 2003, vol. 11, pp. 1120-1135.
57. S.N. Adya, I.L. Markov: Consistent Placement of Macro-Blocks Using Floorplanning and Standard-Cell Placement, Proc. of the International Symposium on Physical Design, 2002, pp. 12-17, http://www.sigda.org/Archives/ProceedingArchives/Ispd/.
58. VLSI CAD Bookshelf Slots and Entries, A.B. Kahng, I.L. Markov, http://vlsicad.eecs.umich.edu/BK/Slots/slots/BlockPacking.html.
59. S.T. Obenaus, T.H. Szymański: Gravity: Fast Placement for 3-D VLSI, ACM Transactions on Design Automation of Electronic Systems, 2003, vol. 8, pp. 298-315.
60. M.G. Wrighton, A.M. DeHon: Hardware-Assisted Simulated Annealing with Application for Fast FPGA Placement, Proc. International Symposium on FPGA, 2003, pp. 33-42, http://www.sigda.org/Archives/ProceedingArchives/Compendiums/papers/fpga/confsym.htm.
61. K. Wiatr: Akceleracja obliczeń w systemach wizyjnych, Warszawa, WNT, 2003
62. 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.
63. S.N. Adya, M.C. Yildizz, 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.
64. VLSI CAD Bookshelf 2, A.B. Kahng, I.L. Markov, http://vlsicad.eecs.umich.edu/BK/.
65. Strona internetowa firmy Synopsys, http://www.synopsys.com.
66. Strona internetowa firmy Cadence, http://www.cadence.com.
67. Cadence Design Systems: Envisia Silicon Ensemble Place-and-Route Reference, 2000.
68. Strona internetowa firmy Mentor Graphics, http://www.mentor.com.
69. Strona internetowa firmy Xilinx, http://www.xilinx.com.
70. Strona internetowa firmy Altéra, http://www.altera.com.

Typ dokumentu

Bibliografia

Identyfikator YADDA

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