Authors B.K. Lebedev, A.A. Shashelov
Month, Year 01, 2014 @en
Index UDC 681.3.001.63
Abstract The article describes one of the most important tasks of the design of VLSI design - routing circuits task. It belongs to a class of NP-hard and difficult tasks. In this paper, we present a new multi-level down-top hybrid full-chip routing. The structure of a global routing graph is described. The principle of global routing graph partition into subgraphs in a multi-level approach is developed. General scheme of a multi-level approach is showed. Described genetic algorithm global routing basic idea is to coding alternatives of constructing the route in the vertices of the graph. Algorithm of global routing method ant colony is described. Feature of algorithm is the concept of competition colonies. The features of algorithm the implicit griddles maze detail routing is described. The structure of hybridization the global routing with detailed routing is developed. Experimental researches were spent on IBM PC. Compared with existing algorithms achieved better results.

Download PDF

Keywords Genetic algorithm; ant colony; global routing; detail routing; global rerouting; multilevel full-chip routing; optimization.
References 1. Cong J., Xie M., Zhang Y. An Enhanced Multilevel Routing System // Proc. ICCAD. – 2002. – P. 51-58.
2. Chang Y.-W., Lin S.-P. A novel framework for multilevel routing considering routability and performance // Proc. ICCAD. – 2002. – P. 44-50.
3. Tai-Chen Chen, Yao-Wen Chang. Multilevel Full-Chip Gridless Routing Considering Optical Proximity Correction // Proc. ASPDAC. – 2005. – P. 1160-1163.
4. Bozorgzadeh E., Kastner R., Sarrafzadeh M. Pattern Routing: Use and Theory for Increasing Predictability and Avoiding Coupling // Circuits and Systems. – 2002. – Vol. 21, № 7. – P. 777-790.
5. Воронин Е.И., Лебедев Б.К. Многоуровневый подход к решению задачи трассировки по всему чипу с использованием модификаций муравьиного алгоритма // Известия ЮФУ.
Технические науки. – 2009. – № 7 (120). – С. 73-80.
6. Лебедев В.Б., Шашелов А.А. Генетический алгоритм глобальной трассировки основанный на альтернативах построения маршрута // Известия ЮФУ. Технические науки.
– 2012. – № 7 (132). – С. 55-62.
7. Воронин Е.И., Лебедев Б.К. Генетический алгоритм распределения соединений по слоям при многослойной глобальной трассировке СБИС // Известия ЮФУ. Технические науки. – 2012. – № 7 (132). – С. 14-21.
8. Лебедев Б.К., Шашелов А.А. Волновой алгоритм детальной трассировки основанный на неявном графе соединений // Конгресс по интеллектуальным системам и информационным
технологиям (IS&IT’12). – М.: Изд-во “Физматлит”, 2012. – Т. 3. – С. 155-160.
9. CSE Department. Testing and Verification of Circuits (CS60089, 3-1-0). [Online]. (Дата обращения: 14.05.2013).

Comments are closed.