Keywords
integrated circuit
multistage method
virtual channels
How to Cite
Abstract
The study solves the problem of circuit routing in ICs. We propose a multistage approach based on interconnection mesh reduction. It expands the chip interconnecting capability by introducing extra channels. The interconnection mesh reduction significantly accelerates the existing routing algorithms. The introduction of more channels makes it possible to reduce the routing problem in a complex interconnect space topology by removing the new routes from the extra (virtual) channels.
References
Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Мир; 1982. 584 с.
Mikami K., Tabuchi K. A Computer Program for Optimal Routing of Printed Circuit Conductors. Proc. IFIP Congress. 1968:1475–1478.
Hightower D. W. A Solution to Line-Routing Problems on the Continuous Plane. Proc. 6th Annual Design Automation Conference (DAC ’69). 1969:1–24.
Hadlock F. O. A Shortest Path Algorithm for Grid Graphs. Networks. 1977;7(4):323–334.
Lee C. Y. An Algorithm for Path Connections and Its Applications. IRE Transactions on Electronic Computers. 1961;EC–10(3):346–365.
Hama T., Etoh H. Topological Routing Path Search Algorithm with Incremental Routability Test. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1999;Feb:142-150.
Старостин Н. В., Балашов В. В. Использование гиперграфов для решения задачи ортогональной трассировки больших интегральных схем с нерегулярной структурой. Радиотехника и электроника. 2008;53(5):618-623.
Батищев Д. И., Старостин Н. В., Филимонов А. В. Двухуровневая эволюционно-генетическая трассировка электрических цепей на графовой модели. Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). 2008;1:61-64.
Батищев Д. И., Старостин Н. В., Филимонов А. В. Многоуровневый генетический алгоритм решения задачи декомпозиции гиперграфа. Известия СПбГЭТУ ЛЭТИ. 2007;1:3-13.