Ключевые слова
интегральная схема
многоуровневый метод
виртуальные каналы
Как цитировать
Аннотация
Рассматривается проблема трассировки цепей интегральной схемы. Предлагается многоуровневый метод, в основу которого положены идеи редукции сетки трассировки, а также расширения коммутационных ресурсов кристалла за счет введения дополнительных каналов. Редукция сетки трассировки обеспечивает существенное сокращение времени работы известных алгоритмов трассировки. Введение дополнительных каналов дает возможность свести задачи поиска трассы в сложной топологии коммутационного пространства к задаче вытеснения построенных трасс с дополнительных (виртуальных) каналов.
Литература
Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Мир; 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.