Исследование и разработка метода планировки цепей СБИС с равномерным заполнением области трассировки
Диссертация
Практическая значимость работы. На основе разработанных алгоритмов был создан комплекс прикладного программного обеспечения для планировки цепей при проектировании топологии СБИС. Использование разработанных алгоритмов и программного обеспечения позволяет улучшать трассируемость схем путем повышения равномерности заполнения области трассировки без существенного увеличения суммарной длины цепей… Читать ещё >
Содержание
- Глава 1. Обзор алгоритмов и методов планировки цепей
- 1. 1. Этапы решения задачи трассировки
- 1. 2. Модели представления коммутационного пространства
- 1. 3. Методы планировки цепей
- 1. 3. 1. Алгоритмы лабиринтной трассировки
- 1. 3. 2. Алгоритмы трассировки многотерминальных цепей
- 1. 3. 3. Методы оптимизации множества цепей
- 1. 4. Алгоритмы планировки цепей с конкурса 1БРО
- 1. 5. Выводы
- Глава 2. Алгоритм построения множества деревьев Штейнера
- 2. 1. Необходимость разработки нового алгоритма для построения деревьев Штейнера
- 2. 2. Постановка задачи построения семейства деревьев Штейнера
- 2. 3. Алгоритм построения семейства деревьев Штейнера
- 2. 3. 1. Алгоритм построения семейства остовных деревьев
- 2. 3. 2. Алгоритм преобразования остовных деревьев к деревьям Штейнера с ортогональными ребрами
- 2. 4. Фильтрация семейства деревьев
- 2. 4. 1. Оценка близости двух деревьев
- 2. 4. 2. Фильтрация семейства деревьев Штейнера
- 2. 5. Выводы
- Глава 3. Метод планировки цепей с использованием семейств деревьев
- Штейнера
- 3. 1. Постановка задачи
- 3. 1. Выбор деревьев для равномерного заполнения области трассировки
- 3. 2. Алгоритм оптимизации с использованием семейства деревьев Штейнера
- 3. 2. 1. Целевая функция для оценки распределения загруженности области трассировки
- 3. 2. 2. Алгоритм выбора деревьев из семейства
- 3. 3. Демонстрация работы алгоритма выбора деревьев Штейнера
- 3. 5. Выводы
- Глава 4. Программная реализация метода планировки цепей и результаты тестирования
- 4. 1. Программная реализация метода планировки цепей
- 4. 1. 1. Программная реализация алгоритма генерации семейства деревьев Штейнера
- 4. 1. 2. Программная реализация алгоритма выбора деревьев Штейнера
- 4. 2. Исследование реализации алгоритмов
- 4. 2. 1. Результаты тестирования быстродействия
- 4. 2. 2. Результаты тестирования эффективности предложенных алгоритмов. 88 4.4. Выводы
- 4. 1. Программная реализация метода планировки цепей
Список литературы
- International Technology Roadmap for Semiconductors (ITRS), 2006.
- J. Cong. Challenges and opportunities for design innovations in nanometer technologies. // in SRC Design Science Concept Papers, 1997.
- Казеннов Г. Г. Основы проектирования интегральных схем и систем. М.: БИНОМ. Лаборатория знаний. 2005.
- Т. Gao and С. L. Liu. Minimum crosstalk switchbox routing. // in Proc. IEEE Int. Conf. Computer-Aided Design. 1994.
- J. Westra, P. Groeneveld, T. Yan, and P. H. Madden. Global Routing? Metrics, Benchmarks, and Tools. // in IEEE DATC Electronic Design Process, 2005.
- R. M. Karp. Complexity of computer computations. // in Reducibility Among Combinatorial Problems. New York: Plenum, 1972.
- J. Hu and S. S. Sapatnekar. A survey on multi-net global routing for integrated circuits. // Integration, the VLSI Journal, vol. 31, no. 1, 2001. pp. 1−49.
- Т. H. Cormen, С. E. Leiserson, R. L. Rivest and C. Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001.
- M. Kurant, A. Markopoulou and P. Thiran. On the bias of BFS (Breadth First Search). // International Teletraffic Congress (ITC 22), 2010.
- C. Y. Lee. An algorithm for path connection and its application. // in IRE Trans. Electronic Computer, 1961.
- E. F. Moore. The shortest path through a maze. // In Proceedings of the International Symposium on the Theory of Switching, Harvard University Press, Cambridge, 1959. pp. 285−292.
- S. Akers. A modification of lee’s path connection algorithm. // IEEE Transactions on Electronic Computers, EC-16(2): 97−98, 1967.
- S. Akers. Routing. // Vol. 1. Prentice-Hall, Englewood Cliffs, NJ, 1972.
- F. 0. Hadlock. A shortest path algorithm for grid graphs. // Networks, 7(4): 323−334, 1977.
- J. Soukup. Fast maze router. // In Proceedings of the 15th Design Automation Conference, IEEE Press, Piscataway, NJ, pp. 100−102, 1978.
- K.Mikami and K. Tabuchi. A computer program for optimal routing of printed circuit connectors. // In IFIPS Proceedings, H47: 1475−1478, 1968.
- D. W. Hightower. A solution to line-routing problems on the continuous plane. // In Proceedings of the 6th Annual Conference on Design Automation, ACM, NY, pp. 1−24, 1969.
- R.Kastner, E. Borzorgzadeh, andM. Sarrafzadeh, Predictable routing. // in Proc. IEEE Int. Conf. Computer-Aided Design, 2000.
- R. Kastner, E. Bozorgzadeh and M. Sarrafzadeh. Pattern Routing: Use and Theory for Increasing Predictability and Avoiding Coupling. // IEEE TCAD 21(7), pp. 777−790, 2002.
- J. Westra, C. Bartels, and P. Groeneveld. Probabilistic Congestion Prediction. // in Proc. Int. Symp. on Physical Design, 2004.
- J. Westra, C. Bartels, and P. Groeneveld. Is Probabilistic Congestion Estimation Worthwhile? // in Proc. System-Level Interconnect Prediction, 2005.
- M. Pan and C. Chu. Fastroute: A step to integrate global routing into placement. // In Proceedings of International Conference on Computer Aided Design, IEEE Press, Piscataway, NJ, pp. 464−471, 2006.
- Eisner, Jason. State-of-the-art algorithms for minimum spanning trees: A tutorial discussion. // Manuscript, University of Pennsylvania, April, pp 78, 1997.
- Eugene F. Krause. Taxicab Geometry. Dover. 1987.
- M. Hanan. On Steiner’s problem with rectilinear distance. // SIAM Journal of Applied Mathematics, 14:255−265, 1966.
- M. Garey and D. S. Johnson. The rectilinear Steiner problem is NP-complete. // SIAM Journal of Applied Mathematics, 32(4): 826−834, 1977.
- F. K. Hwang. On Steiner minimal trees with rectilinear distance. // SIAM Journal of Applied Mathematics, 30(1): 104−114, 1976.
- A. B. Kahng and G. Robins. On Optimal Interconnections for VLSI. Kluwer Academic Publishers, Boston, MA, 1995.
- A. B. Kahng and G. Robins. A new family of Steiner tree heuristics with good performance: The iterated 1-steiner approach. // In Proceedings of the IEEE International Conference Computer-Aided Design, pp. 428−431, Santa Clara, CA, November 1990.
- A. B. Kahng and G. Robins. On performance bounds for a class of rectilinear Steiner tree heuristics in arbitrary dimension. // IEEE Transactions Computer-Aided Design, 11(11): 1462−1465, November 1992.
- G. Robins. On Optimal Interconnections. // PhD thesis, Department of Computer Science, UCLA, Los Angeles, CA, CSD-TR-920 024, 1992.
- M. Burstein and R. Pelavin. Hierarchical Wire Routing. // IEEE Trans, on Computer-Aided Design of Integrated Circuits and Systems, vol. 2, no. 4, pp. 223−234, 1983.
- Joseph. B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. // Proceedings of the American Mathematical Society, Vol 7, No. 1 (Feb, 1956), pp. 48−50.
- R. C. Prim. Shortest connection networks and some generalizations. // Bell System Technical Journal, 36 (1957), pp. 1389−1401.
- J. M. Ho, G. Vijayan, and C. K. Wong. New algorithms for the rectilinear Steiner tree problem. // IEEE Transactions Computer-Aided Design, 9(2): 185−193, 1990.
- D. S. Richards. Fast Heuristic Algorithms for Rectilinear Steiner Trees. // Algorithmica, 4 (1989), pp. 191−207.
- M. Borah, R.M. Owens, and M. J. Irwin. A fast and simple Steiner routing heuristic. // Discrete and Applied Mathematics, 90(1−3): 51−67, 1999.
- M. Sarrafzadeh and C. K. Wong. Hierarchical Steiner tree construction in uniform orientations. // IEEE Transactions Computer-Aided Design, 11(9): 1095−1103, September 1992.
- C. J. Alpert, T. C. Hu, J. H. Huang, A. B. Kahng, and D. Karger. Prim-Dijkstra tradeoffs for improved performance-driven routing tree design. // IEEE Transactions Computer-Aided Design, 14(7):890−896, 1995.
- A. B. Kahng and G. Robins. A new class of iterative steiner tree heuristics with good performance. // IEEE Transactions Computer-Aided Design, 11(7): 893−902, July 1992.
- A. B. Kahng and G. Robins. On Optimal Interconnections for VLSI. Kluwer Academic Publishers, Boston, MA, 1995.
- F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, 1985.
- G. Georgakopoulos and C. H. Papadimitriou. The 1-Steiner tree problem. // Journal of Algorithms, 8:122−130, 1987.
- A. B. Kahng, 1.1. Mandoiu, and A. Z. Zelikovsky. Highly scalable algorithms for rectilinear and octilinear Steiner trees. // In Proceedings of the Asia and South Pacific Design Automation Conference, Yokohama, Japan, pp. 827 833, 2000.
- A. Zelikovsky. An 11/6-approximation for the network Steiner tree problem. // Algorithmica 9 (1993), pp. 463−470.
- C. Chu. FLUTE: Fast lookup table based wirelength estimation technique. // in Proc. ICCAD, 2004, pp. 696−701.
- C. C. N. Chu and Y.-C. Wong. Fast and accurate rectilinear Steiner minimal tree algorithm for VLSI design. // in Proc. ISPD, 2005, pp. 28−35.
- M. Cho and D. Z. Pan. BoxRouter: A New Global Router Based on Box
- Expansion and Progressive ILP. // in Proc. Design Automation Conf., July 2006.
- M. Pan and C. Chu. FastRoute: A step to integrate global routing into placement. // in Proc. ICCAD, 2006, pp. 464−471.
- M. Pan and C. Chu. FastRoute 2.0: A High-quality and Efficient Global Router. // In Proc. ASPDAC, pp. 250−255, 2007.
- B. S. Ting and B. N. Tien. Routing techniques for gate array. // IEEE Transactions on Computer Aided Design, CAD-2(4):301−312, October 1983.
- R. Nair, S. J. Hong, S. Liles, and R. Villani. Global wiring on a wire routing machine. // In Proceedings of the ACM/IEEE Design Automation Conference, pages 224−231, 1982.
- K. W. Lee and C. Sechen. A global router for sea-of-gate circuits. // In Proceedings of the European Design Automation Conference, p. 242−247, 1991.
- V. Betz and J. Rose. Directional bias and non-uniformity in FPGA global routing architectures. // In International Conference on Computer Aided Design, IEEE Computer Society, Washington, DC, pp. 652−659, 1996.
- V.Betz and J.Rose. VPR: A new packing, placement and routing tool for FPGAresearch. // In 7th International Workshop on Field-Programmable Logic, pp. 213−222, 1997.
- C. Ebeling, L. McMurchie, S. A. Hauck, and S. Burns. Placement and routing tools for the triptych FPGA. // IEEE Transactions on VLSI Systems, IEEE Press, Piscataway, NJ, pp. 473−482, 1995.
- M. M. Ozdal and M. D. F. Wong. Archer: A history-driven global routing algorithm. // In Proceedings of International Conference on Computer Aided Design, IEEE Press, Piscataway, NJ, pp. 488−495, 2007.
- J.A.Roy and I. L.Markov. High-performance routing at the nanometer scale. // In Proceedings of International Conference on Computer Aided
- Design, IEEE Press, Piscataway, NJ, pp. 496−502, 2007.
- M. Cho, K. Lu, and D. Z. Pan. Boxrouter 2.0: Architecture and implementation of a hybrid and robust global router. // In Proceedings of International Conference on Computer Aided Design, Press, Piscataway, NJ, pp. 503−508, 2007.
- J. D. Cho and M. Sarrafzadeh. Four-bend top-down global routing. // IEEE Transactions on Computer-Aided Design, 17(9):793−802, 1998.
- J. Hu and S. S. Sapatnekar. A timing-constrained algorithm for simultaneous global routing of multiple nets. // In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pages 99 103, 2000.
- G. Meixner and U. Lauther. A new global router based on a flow model and linear assignment. // In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pages 44−47, 1990.
- C. Albrecht. Provably good global routing by a new approximation algorithm for multicommodity flow. // In International Symposium on
- Physical Design, ACM, NY, pp. 19−25, 2000.
- C. Albrecht. Global routing by new approximation algorithms for multicommodity flow. // in IEEE Trans, on Computer-Aided Design of Integrated Circuits and Systems, vol. 20, pp. 622−632, 2001.
- D. G. Luenberger. Linear and nonlinear programming. Addison-Wesley Publishing Company, Reading, MA, 1984.
- N. Karmarkar. A new polynomial-time algorithm for linear programming. // Combinatorica, 4(4):373−395, 1984.
- P. Raghavan and C. D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. // Combinatorica, 7(4):365−374, 1987.
- A. Vannelli. An adaptation of the interior point method for solving the global routing problem. // IEEE Transactions on Computer-Aided Design, 10(2): 193−203, 1991.
- T. C. Hu and E. S. Kuh. Theory and concepts of circuit layout. In T. C. Hu and E. S. Kuh, editors, VLSI Circuit Layout: Theory and Design, pages 3−18. IEEE Press, New York, NY, 1985.
- R. W. Thaik, N. Lek, and S.-M. Kang. A new global router using zero-one integer linear programming techniques for sea-of-gates and custom logic arrays. // IEEE Transactions on Computer-Aided Design, 12(12): 1479−1494, 1992.
- J. Heisterman and T. Lengauer. The efficient solution of integer programs for hierarchical global routing. // IEEE Transactions on Computer-Aided Design, 10(6):748−753, 1991.
- ISPD 2006: http://www.sigda.org/ispd2006/contest.html
- ISPD 2008: http://www.siqda.org/ispd2QQ8/contest.html
- D. Kucar. «Partitioning and Clustering» in «The Handbook of Algorithms for VLSI Physical Design Automation,» C. 3. Alpert, D. P. Mehta, and S. S.
- Sapatnekar, editors, pp. 100−132, 2007.
- L. R. Ford, Jr. and D. R. Fulkerson. Flows in networks. Princeton University Press, Princeton, NJ, 1962.
- N. Karmarkar. A new polynomial-time algorithm for linear programming. // Combinatorica, 4(4):373−395, 1984.
- R.Tessier. Negotiated A* Routing for FPGAs. // in Proceedings of the Fifth Canadian Workshop on Field-Programmable Devices, 1998.
- P. O. Fjallstrom. Algorithms for graph partitioning: A survey. // Linkoping Electronic Articles in Computer and Information Science, 3(10), 1998.84. http://www.opencores.org
- Заглядин Г. Г., Панфилов C.B. Инфраструктура и подсистема планировки кристалла для САПР топологии ИС. // Микроэлектроника и информатика-2006, М.: МИЭТ, 2006. стр. 120.
- Заглядин Г. Г. Реализация этапа декомпозиции при создании учебно-исследовательской САПР топологии СБИС. // Микроэлектроника и информатика-2007, М.: МИЭТ, 2007. стр. 67.
- Заглядин Г. Г. Исследование реализации этапа декомпозиции при создании учебно-исследовательской САПР топологии СБИС. // Сб. науч. Трудов «Проектирование электронной компонентной базы и систем на кристалле» под ред. М. Г. Путри, М.: МИЭТ, 2007. с. 49−55.
- Заглядин Г. Г. Планировка цепей высокопроизводительных ИС. // Микроэлектроника и информатика-2008, М.: МИЭТ, 2008. стр. 72.
- Заглядин Г. Г., Многокритериальная планировка цепей СБИС. // Микроэлектроника и информатика-2009, М.: МИЭТ, 2009. стр. 85.
- Gleb Zaglyadin, Multiobjective Global Routing. // MB-JASS 2009, Москва, 2009.
- Заглядин Г. Г, Разработка метода многокритериальной глобальной трассировки СБИС. // Микроэлектроника и информатика-2010, М.:1121. МИЭТ, 2010. стр. 73.
- Заглядин Г. Г., Сырцов И. А., Школа А. В. Алгоритм синтеза множества остовных деревьев для выполнения глобальной трассировки заказных СБИС. // Известия высших учебных заведений. Электроника. № 5(85). М: МИЭТ, 2010. стр. 36−40.
- Заглядин Г. Г., Сырцов И. А. Глобальная трассировка заказных СБИС с использованием множества остовных деревьев. // Естественные и технические науки. № 4(48). М: «Спутник+», 2010. стр. 322 326.
- Заглядин Г. Г. Метод глобальной трассировки цепей субмикронных СБИС с использованием семейства деревьев Штейнера. // Проектирование систем на кристалле: тенденции развития и проблемы, М.: МИЭТ, 2010. стр. 13.