Оптимизация топологии СБИС в иерархических моделях
Диссертация
К сожалению, ни интерактивные, ни автоматические методы в том виде, в котором они существуют и используются в современных САПР, не могут поддержать проектирование при лавинообразном увеличении сложности СБИС. Новые методы должны совмещать преимущества как интерактивных, так и автоматических методов, а именно: решать задачи синтеза с высоким качествомиспользовать иерархическое описаниесокращать… Читать ещё >
Содержание
- ГЛАВА 1. СОВРЕМЕННИКЕ МЕТОДЫ И АЛГОРИТМЫ ТОПОЛОГИЧЕСКОГО СИНТЕЗА
- 1. 1. ДЕКОМПОЗИЦИЯ ЭЛЕКТРИЧЕСКОЙ СХЕМЫ
- 1. 2. РАЗМЕЩЕНИЕ И ПЛАНИРОВКА КРИСТАЛЛА СБИС
- 1. 3. МАКРОТРАССИРОВКА ЦЕПЕЙ СБИС
- 1. 4. ДЕТАЛЬНАЯ ТРАССИРОВКА ЦЕПЕЙ СБИС
- 1. 5. СЖАТИЕ ТОПОЛОГИИ СБИС
- ВЫВОДЫ
- ГЛАВА 2. МЕТОДОЛОГИЯ ИЕРА^ЙЙЕС^ОШ СИНТЕЗА ТОПОЛОГИИ СБИС'
- 2. 1. ГЛОБАЛЬНЫЕ ПРОБЛЕМЫ ТОПОЛОГИЧЕСКОГО СИНТЕЗА
- 2. 2. МЕТОДОЛОГИЯ ИСПОЛЬЗОВАНИЯ ОБЩЕЙ ИЕРАРХИЧЕСКОЙ МОДЕЛИ
- 2. 3. ДЕКОМПОЗИЦИЯ И ОПЕРАЦИИ МАКРОСИНТЕЗА КРИСТАЛЛА
- 2. 4. ОПЕРАЦИИ ДЕТАЛЬНОГО СИНТЕЗА КРИСТАЛЛА
- ВЫВОДЫ
- ГЛАВА 3. МЕТОДЫ И АЛГОРИТМЫ ОПТИМИЗАЦИИ ИЕРАРХИЧЕСКОГО ПРОЕКТИРОВАНИЯ
- 3. 1. МЕТОД ИТЕРАЦИОННОЙ РЕКОМПОЗИЦИИ ДЕРЕВА ИЕРАРХИИ
- 3. 2. АЛГОРИТМ МАКРОТРАССИРОВКИ НА ОСНОВЕ ВЕКТОРНОЙ МОДЕЛИ
- 3. 3. ВЕКТОРНЫЙ МЕТОД ДЕТАЛЬНОЙ ТРАССИРОВКИ
- 3. 4. СИЛОВОЙ АЛГОРИТМ СЖАТИЯ
- ВЫВОДЫ
- ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ИССЛЕДОВАНИЕ АЛГОРИТМОВ ОПТИМИЗАЦИИ
- 4. 1. ОРГАНИЗАЦИЯ БАЗЫ ДАННЫХ В ИЕРАРХИЧЕСКОЙ САПР
- 4. 2. РЕАЛИЗАЦИЯ АЛГОРИТМА РЕКОМПОЗИЦИИ ДЕРЕВА ИЕРАРХИИ
- 4. 3. АДАПТАЦИЯ АЛГОРИТМА ВЕКТОРНОЙ МАКРОТРАССИРОВКИ К САПР С БИНАРНЫМ ДЕРЕВОМ ИЕРАРХИИ
- 4. 4. ОСОБЕННОСТИ РЕАЛИЗАЦИИ АЛГОРИТМОВ ДЕТАЛЬНОГО СИНТЕЗА В ИЕРАРХИЧЕСКИХ САПР
- ВЫВОДЫ
- ГЛАВА 5. ПРОЕКТИРОВАНИЕ ТОПОЛОГИИ С ИСПОЛЬЗОВАНИЕМ ИЕРАРХИЧЕСКОЙ САПР
- 5. 1. СТРУКТУРНАЯ СХЕМА СВЯЗЕЙ МЕЖДУ ПРОЦЕДУРАМИ В СИСТЕМЕ ПРОЕКТИРОВАНИЯ АИСТ
- 5. 2. НАСТРОЙКА ПАРАМЕТРОВ МАРШРУТА ПРОЕКТИРОВАНИЯ
- 5. 3. ПРОЕКТИРОВАНИЕ ПЕЧАТНЫХ ПЛАТ С ИСПОЛЬЗОВАНИЕМ ИЕРАРХИЧЕСКОЙ САПР
- ВЫВОДЫ
- ЗАКЛЮЧЕНИЕ
- СПИСОК ЛИТЕРАТУРЫ
- ПРИЛОЖЕНИЯ
Список литературы
- Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств// Львов: Вища школа,-1981, с. 167.
- Селютин В.А. Машинное конструирование электронных устройств// М., Сов. радио, 1976.
- W.Kernigan, S.Lin. An efficient heuristic procedure for partitioning graph// Bell System Technical Journal.- 49:391−307,1970.
- C.M.Fiducca, R.M.Mattheyses. A linear-time heuristics for improving network partitons// Proceeding of the 19th Design Automation Conference.-pp.175−181,1982.
- A.Chatterjee, R.Hartley. A new simultaneous circuit partitioning and chip placement approach based on simulated annealing// Proceeding of Design Automation Conference.- pp.36−39, 1990.
- Y.G. Saab, V. Rao. Stochastic evolution: A fast effective heuristic for some generic layout problems// Proceedings of Design Automation Conference.-pp.36−31,1990.
- R.Murgai, R.K.Brayton, A. Sangiovanni-Vincentelli. On clustering for minimum delay/area// Proceeding of IEEE International Conference on Computer-Aided Design.- pp.6−9, November 1991.
- K.M.Hall. An r-dimensional quadratic placement algorithm// Management Science.- 17:219−229, November 1970.
- C.Cheng, E.Kuh. Module placement based of resistive network optimization// IEEE Transactions on Computer-Aided Design.- CAD-3:218−225, July 1984.
- M.A.Breuer. A class of min-cut placement algorithms// Proc. 14th Design Automation Conference.- pp. 284−290, June 1977.
- M.A.Breuer, J. C. Lien. A methodology for the design of hierarchically testable and maintainable digital systems// Proc. 8th Digital Avionics Systems Conference (DASC).- pp. 40−47, San Jose, CA, 1988.
- T.C.Lee. A bounded 2d contour searching algorithm for floorplan design with arbitrarily shaped rectilinear and soft modules// Proceedings of the 30th Design Automation Conference.- pp.525−530, June 1993.
- M. R. Garey and D. S. Johnson. The rectilinear steiner tree problem is np-complete// SIAM Journal Applied Mathematics.- 32: 826−834., 1977.
- C. Chiang, M. Sarrafzadeh and С. K. Wong. A powerfull global routing: Based on steiner min-max trees// Proceedings of IEEE International Conference on Computer-Aided Design.- pp. 2−5, November 1989.
- M. Burstein, R. Pelavin. Hierarchical wire routing// IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems.- CAD-2 (4), pp.223−234, 1983.
- C. Sechen. Chip-planning, placement and global routing of macro/custom cell integrated circuits using simulated annealing// Proceedings of 25th ACM/IEEE Design Automation Conference.- pp.73−80,1988.
- Прим P.K. Кратчайшие связывающие сети и некотороые обобщения: пер. с англ.//Кибернетический сборник.- М, — 1974.- вып.2., с95−107.
- J. В. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem// Proceedings of the American Mathematical Society.-7(1): 48−50,1956.
- E. W. Dijkstra. A note on two problems in connexion with graphs// Numerische Mathematic.-1:269−271,1959.
- M. Marek-Sadowska, S. P. Lin. Timing driven placement// Proceeding of International Conference on Computer-Aided Design.- pp.94−97,1989.
- T.Villa, T. Kam, R.K.Brayton, and A. Sangiovanni-Vincentelli. Synthesis of FSMs: Logic Optimization, Kluwer Academic Publishers// Boston/Dordrecht/London.- 1997.
- C.Y. Lee. An algorithm for path connections and its application// IRE Trans. Electronic Computers.- EC-10, pp.346−365,1961.
- M. Marek-Sadowska. Switchbox routing: a retrospective// INTEGRATION the VLSI Jornal.- Vol.13.- pp.39−65,1992.
- M. Burstein, R. Pelavin. Hierarchical wire routing// IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems.- CAD-2 (4).- pp.223−234.-1983.
- M. Marek-Sadowska. Two-dimensional router for double layer layout// Proc. 22th Design Automation Conference.- pp.266−272,1985.
- R. Joobbani. WEAVER: An application of knowledge based expert systemws to detailed routing of VLSI circuits// Research Report. CMUCAD.- pp.85−56, June 1985.
- Щемелинин В. M., Данилин А. А. Многоуровневая модель трассировки свичбокса// Известия вузов. ЭЛЕКТРОНИКА.- № 3, — 1999. с. 65−72.
- J.P. Cohoon, P.L. Heck. BEAVER: A computational geometry based tool for switch box routing// IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems.- CAD-7 (6), June 1988.- pp.684−697.
- Широ Г. Э., Алгоритм трассировки, использующий деформацию ранее построенных проводников. В кн.: Вычислительная техника. Каунас, 1976, т.8. с. 136−139.
- Абрайтис Л.Б. Автоматизация проектирования топологии цифровых интегральных схем// М.- Радио и связь, 1985.
- A.A.Malik. An efficient algorithm for constraint graph for compaction// Proc. if IEEE. International Conference on Computer-Aided Design.- pp.130−133,1987.
- H.Shin, A.L.Sangivanni-Vincentelli and C.H.Sequin. Two-dimensional compaction by «zone-refining"// Proc. of 23rd Design Automation Conference.-pp. 115−122,1986.
- M.Shlag, Y.Z.Liao, C.K.Wong. An algorithm for optimal two-dimensional compactionof VLSI layouts//Integration.- Vol.1.- pp.179−209,1983.
- J.Williams. Sticks graphical compiler for high-level LSI design// Proc. of AFIPS.- pp.289−265, 1978.
- M.A.Breuer, K.Anshul. A Methodology for custom VLSI layout // IEEE Trans. On circuits and systems.- 1983, — Vol.1.- CAS-30,№ 6.- pp.358−364.
- Сырцов И.А., Щемелинин B.M. Оптимизация топологии СБИС с использованием иерархических моделей// Известия вузов. Электроника.- 1997.- № 6, — с.63−70.
- Гинзбург Б.Д. Алгоритм размещения модулей на плате// Обмен опытом в радиопромышленности,-1972.-№ 4, с.31−33.
- Марченко A.M., Щемелинин В. М. О классе алгоритмов плотной укладки фрагментов БИС// Автоматизация проектирования в радиоэлектронике и вычислительной технике.- М.- МДНТП.- 1987.-с.150−155.
- J.M.Ho, G. Vijayan and C.K.Wong. A new approach to the rectilinear Steiner Tree problem// IEEE Transactions on Computer-Aided Design.- 9(2).-pp.185−193, February 1985.
- Сырцов И.А., Загидуллин M.P. Векторная модель макротрассировки сигнальных цепей в иерархических системах проектирования топологии СБИС// Известия вузов. Электроника.- 1999, — № 3, с.73−80.
- Марченко A.M., Щемелиннн В. М. Алгоритм декомпозиции функционально-завершенных фрагментов БИС// Электронная техника. Серия 3. Микроэлектроника.- вып.1(121).- 1987.- с.56−61.
- К. J. Antreich, F. М. Johannes, F. Н. Kirsch. A new aproach for solving the placement problem using force models// Proceedings of the IEEE International Symposium on Circuits and Systems.- pp.481−486, 1982.
- N. R. Quinn, M. A. Breuer. A force directed component placement procedure for printed circuit boards// IEEE Trans. Circuits and Systems.- pp.377−388, June 1979.
- Сырцов И.А. Алгоритм сжатия топологии СБИС на основе силовой модели// Известия вузов. Электроника.- 1999.- № 6.
- Казеннов Г. Г., Марченко А. М., Щемелинин В. М. АИСТ подсистема автоматического иерархического синтеза топологии заказных БИС // Электронная промышленность. — 1988. — № 10. — С.49 — 50.
- Казеннов Г. Г., Марченко A.M., Щемелинин В. М. Автоматический синтез топологии заказных БИС// Электронная техника. Серия 3. Микроэлектроника.- вып.2(131).- 1989.- с.39−41.
- Сырцов И.А. Алгоритм оптимизации топологии СБИС методом плотной, компрессии// Тез. докл научно-техническая конференция студентов и аспирантов, — М., МИЭТ.- 1996.- с. 40.
- Сырцов И.А. Оптимизация топологии СБИС в иерархических системах путем перестройки дерева декомпозиции// Тез.докл. Всероссийская межвузовская научно-техническая конференция студентов и аспирантов.- М., МИЭТ, — 1998, — с. 69.
- Сырцов И.А. Иерархический синтез топологии заказных СБИС// Тез.докл. Всероссийская межвузовская научно-техническая конференция студентов и аспирантов.- М., МИЭТ.- 1999.- с. 108.
- S. B. Akers. On the use of the linear assignment algorithm in module placement// Proceedings of 18th ACM/IEEE Design Automation Conference.-pp. 137−144,1981.
- A.Mukherjee, R. Sudhakar, M. Marek-Sadowska, S.I.Long/ A Novel NonfVt1. erative Synthesis and Layout Technique// 36 Design Automation Conference// New Orleans, LA.- June 21−25,1999.- p.466.
- J.Bianks. Partitioning by probability condensation// Proceeding of Design Automation Conference// pp.758−761, 1989.
- T. Cormen, C.E. Leiserson and R. Rivest. Introduction to Algorithms. McGraw Hill, 1990.
- G. Chartrand and Lesniak. Graphs and Digraphs. Wadsworth and Brooks/Cole Inc., Monterey, 1986.
- J.Cullum, W. Donath, P.Wolfe. The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices// Mathematical Programming Study, 3:35−55,1975.
- J. P. Cohoon, W. Paris. Genetic placement// Proceedings of the IEEE International Conference on Computer-Aided Design.- pp 422−425, 1986.
- H. Chan, P. Mazumber, K. Shahookar. Macro-cell and module placement by genetic adaptive search with bitmap represented chromosome// Integration: the VLSI Journal.- 12(1): 49−77, November 1991.
- J. Cong. Pin assignment with global routing// Proceedings of International Conference on Computer-Aided Design.- pp.302−305,1989.
- W. W. Dai, B. Eschermann, E. Kuh, M. Pedram. Hierarchical placement and floorplanning in bear// IEEE Transactions on Computer-Aided Design. -8:1335−1349, Dec. 1989.
- W. E. Donath, R. J. Norman, B. K. Agrawal, S. E. Bello Sang Yong Han, J. M. Kurtzberg, P. Lowy, R. I. McMillan. Timing driven placement using complete path delays// Procee dings of 27th ACM/IEEE Design Automation Conference, pages 84−89,1990.
- W. A. Dees, P. G. Karger. Automated rip-up and reroute techniques. Proceeding of Design Automation Conference, 1982.
- Edward M. Reingold, Jurg Nivevergelt, Narsingh Deo, Combinatorial algorithms. Theory and practice// Prentice-Hall, Inc., Englewood Cliffs, New Jersey 1977.
- Y. Ogawa et. al. Efficient placement algorithms optimizing delay for highspeed eel masterslice Isi’s// Proceedings of 23rd ACM/IEEE Design Automation Conference.- pages 404−410,1986.
- C. Fowler, G. D. Hachtel, 1. Roybal. New algorithms for hierarchical place and route of custom VLSI// Proceeding of International IEEE Conference on Computer-Aided Design.- pages 273−275, 1985.
- M.K.Goldberg, M.Burstein. Heuristic improvement technique for bisection of vlsi networks// Proceeding of IEEE International Conference on Computer Design.- pages 652−657,1983.
- G. Gopal, D. Coppersmith, C. K. Wong. Optimal wiring of movable terminals//IEEE Transactions on Computers, C-32: 845−858,1983.
- R.B.Hitchcock. Partitioning of logic graphs: A theoretical analysis of pin reduction// Proceeding of Design Automation Conference.- p.54−63, 1970.
- M. Hanan, J. M. Kurtzberg. A review of placement and quadratic assignment problems// SIAMRev.- 14(2): 324−342, April 1972.
- F. Hadlock. Finding a maximum cut of a planar graph in polynomial time// SIAM Journal of Computing.- 4, no.3:221−225, September 1975.
- R.Kling, P.Bannerjee. Esp: Placement by simulated evolution// IEEE Transactions on Computer-Aided Design.- 8(3):245−256,1989.
- W.K. Luk. A greedy switch box router// VLSI Document VI58, — Carnegie Mellon University. May 1984.
- Y.L. Lin, Y.C. Hsu, F.S. Tsay. A detailed router based on simulated evolution//Proc. Int. Conf. Computer-Aided Design.- 1988. 38−41.
- F.F. Moore. The shortest path through a maze// Annals of the Harvard Computation Laboratory.- Vol.30. Pt.ll.- pp.185−192.
- R.Murgai, R.K.Brayton, A. Sangiovanni- Vincentelli. On clustering for minimum delay/area// Proceeding of IEEE International Conference on Computer-Aided Design.- pages 6−9, November 1991.
- M.C.McFarlald. Using bottom-up design techniques in the synthesis of digital hardware from abstract behavioral description.// Proceedings of the 23rd Design Automation Conference.- pages 474−480,1986.
- K. McCullen, J. Thorvaldson, D. Demaris, P. Lampin. A system for floorplanning with hierarchical placement and routing// Proceedings of European Design Automation Conference.- pages 262−265, 1990.
- T. Ohtsuki. Partitioning, Assignment and Placement//North-Holland, 1986.
- С. H. Paradimitriou and K. Steigliz. Combinatorial Optimization -Algorithms and Complexity// Prentice-Hall, Inc., 1982.
- F. Preparata and M. I. Shamos. Computational Geometry. An Introductoin. Springer- Verlag, 1985.
- N. R. Quinn, M. A. Breuer. A force directed component placement procedure for printed circuit boards// IEEE Trans. Circuits and Systems.- pp.377−388, June 1979.
- R.B. Rukc. A gridless switch box router. Proc. Int. Conf. On Custom Integrated Circuits. 1987, — pp.629−632.
- Щемелинин B.M. Метод трассировки сложных схем// Известия вузов. ЭЛЕКТРОНИКА. № 1,1997, с.66−72.
- Naveed Shervani. Algorithms for VLSI Physical Design Automation. Second Edition, Kluwer Academic Publishers, Boston/ Dordrecht /London, 1995.
- M. Sarrafzadeh and С. K. Wong. Hierarchical steiner tree construction in uniform orientations// Research report, Dept. Of Electrical Engineering and Computer Science, Northwestern University, 1990.167
- A. Shanbhad, S. Danda, N. Sherwani. Floorplanning for mixed macro block and standard cell designs// Fourth Great Lakes Symposium on VLSI, pages 80−85,1994.
- S. Sutanthavibul, E. Shargowitz, R. Lin. An adaptive timing driven placement for high performance vlsi’s// IEEE Transactions on CAD of Integrated Circuits and Systems.- 12: 1488−1498, October 1993.
- T. G. Szymanski. Dogleg channel routing is np-complete// IEEE Transactions on Computer-Aided Design, CAD-4: 31−41, January 1985.
- V. Shchemelinin, A. Danilin, The Switchbox Routing Specification Expansion Method// First International Workshop.- Multi-Architecture Low Power Design, Sept 1999, Moscow, p.89.
- Y.Wei, C.Cheng. Towards efficient hierarchical designs by ratio cut partitioning// Proceeding of IEEE International Conference on Computer Design.- pages 298−301, November 1989.
- Декан ЭКТ факультета профессор, д.т.н.
- Зав. кафедрой ПКИМС профессор, д.т.н.1. М. А. Королев Г. Г.Казеннов
- Уч.секретарь кафедры ПКИМС >«.¦ .доцент, к.т.н. рян&^о «В.Н.Целибеева