Канальный маршрутизатор

Рисунок 1: Проблема маршрутизации канала. Пронумерованные контакты сверху и снизу канала должны быть соединены. Сети, указанные слева и справа от канала, должны быть доведены до этого конца канала.

Канальный маршрутизатор — это особая разновидность маршрутизатора для интегральных схем . Обычно при использовании двух слоев межсоединения необходимо соединить указанные контакты сверху и снизу канала. Указанные сети также необходимо выводить слева и справа от канала, но можно выводить в любом порядке. Высота канала не указана — роутер сам вычисляет, какая высота нужна.

Рисунок 2. Решение проблемы маршрутизации каналов, показанной выше. Решения не уникальны, и это лишь одно из многих возможных.

Плотность внутри канала , канала, определенная для каждого x представляет собой количество сетей, которые появляются как слева, так и справа от вертикальной линии в этом x . Максимальная плотность является нижней границей высоты канала. «Циклическое ограничение» возникает, когда два вывода встречаются в одном и том же столбце (но с разным порядком) как минимум в двух столбцах. В показанном примере сети 1 и 3 страдают от циклических ограничений. Эту проблему можно решить только с помощью «изгибающихся ног», как показано в сети 1 примера.

Канальные маршрутизаторы были одной из первых форм маршрутизаторов для интегральных схем . ^[1] и активно использовались в течение многих лет, с YACR ^[2] пожалуй, самая известная программа. Однако современные чипы имеют гораздо больше двух слоев межсоединений. Хотя были предприняты усилия по расширению маршрутизаторов каналов на большее количество уровней, ^[3]^[4] этот подход никогда не был очень популярен, поскольку он плохо работал при маршрутизации внутри ячейки, где контакты неподвижны. В последние годы локальные маршрутизаторы на смену им пришли .

Ссылки

^ Феллер, А. 1976. Автоматическая компоновка недорогих быстродействующих нестандартных LSI-устройств со случайной логикой . В материалах 13-й конференции по автоматизации проектирования (Сан-Франциско, Калифорния, США, 28–30 июня 1976 г.). ЦАП '76. ACM Press, Нью-Йорк, Нью-Йорк, 79–85.
^ Рид, Дж., Санджованни-Винсентелли, А., Сантомауро, М.; Новый маршрутизатор символьных каналов: YACR2 , Компьютерное проектирование интегральных схем и систем, IEEE Transactions, том 4, выпуск 3, июль 1985 г. Страницы: 208–219
^ Браун, Д., Бернс, Дж., Давадас, С., Ма, Х.К., Маярам, К., Ромео, Ф. и Санджованни-Винсентелли, А. 1986. Хамелеон: новый многоуровневый канальный маршрутизатор . В материалах 23-й конференции ACM/IEEE по автоматизации проектирования (Лас-Вегас, Невада, США). Ежегодная конференция ACM IEEE по автоматизации проектирования. IEEE Press, Пискатауэй, Нью-Джерси, 495-502.
^ Фанг С., Фэн В. и Ли С. 1992. Новый эффективный подход к проблеме маршрутизации многоуровневых каналов . В материалах 29-й конференции ACM/IEEE по автоматизации проектирования (Анахайм, Калифорния, США, 8–12 июня 1992 г.). Ежегодная конференция ACM IEEE по автоматизации проектирования. Издательство IEEE Computer Society Press, Лос Аламитос, Калифорния, 579–584.

[1] Феллер, А. 1976. Автоматическая компоновка недорогих быстродействующих нестандартных LSI-устройств со случайной логикой . В материалах 13-й конференции по автоматизации проектирования (Сан-Франциско, Калифорния, США, 28–30 июня 1976 г.). ЦАП '76. ACM Press, Нью-Йорк, Нью-Йорк, 79–85.

[2] Рид, Дж., Санджованни-Винсентелли, А., Сантомауро, М.; Новый маршрутизатор символьных каналов: YACR2 , Компьютерное проектирование интегральных схем и систем, IEEE Transactions, том 4, выпуск 3, июль 1985 г. Страницы: 208–219

[3] Браун, Д., Бернс, Дж., Давадас, С., Ма, Х.К., Маярам, К., Ромео, Ф. и Санджованни-Винсентелли, А. 1986. Хамелеон: новый многоуровневый канальный маршрутизатор . В материалах 23-й конференции ACM/IEEE по автоматизации проектирования (Лас-Вегас, Невада, США). Ежегодная конференция ACM IEEE по автоматизации проектирования. IEEE Press, Пискатауэй, Нью-Джерси, 495-502.

[4] Фанг С., Фэн В. и Ли С. 1992. Новый эффективный подход к проблеме маршрутизации многоуровневых каналов . В материалах 29-й конференции ACM/IEEE по автоматизации проектирования (Анахайм, Калифорния, США, 8–12 июня 1992 г.). Ежегодная конференция ACM IEEE по автоматизации проектирования. Издательство IEEE Computer Society Press, Лос Аламитос, Калифорния, 579–584.

[1]

[2]

[3]

[4]