Маршрутизация (автоматизация электронного проектирования)
В электронном проектировании прокладка проводов , обычно называемая просто маршрутизацией , является шагом в проектировании печатных плат (PCB) и интегральных схем (ИС). Он основан на предыдущем этапе, называемом размещением , который определяет расположение каждого активного элемента ИС или компонента на печатной плате. После размещения на этапе маршрутизации добавляются провода, необходимые для правильного соединения размещенных компонентов с соблюдением всех правил проектирования ИС. Вместе этапы размещения и маршрутизации при проектировании ИС называются местом и маршрутом .
Задача всех роутеров одна и та же. Им предоставляются некоторые уже существующие многоугольники, состоящие из контактов (также называемых терминалами) на ячейках, и, возможно, некоторые ранее существовавшие соединения, называемые предварительными маршрутами. Каждый из этих полигонов связан с сетью , обычно по имени или номеру. Основная задача маршрутизатора — создать такую геометрию, чтобы все терминалы, назначенные одной сети, были подключены, никакие терминалы, назначенные разным сетям, не были подключены, и соблюдались все правила проектирования. Маршрутизатор может выйти из строя из-за неподключения клемм, которые должны быть подключены (обрыв), из-за ошибочного подключения двух терминалов, которые не должны быть подключены (короткое замыкание), или из-за нарушения правил проектирования. Кроме того, для правильного подключения сетей маршрутизаторы также должны убедиться, что конструкция соответствует времени, не имеет проблем с перекрестными помехами , соответствует всем требованиям к плотности металла, не страдает от антенных эффектов и так далее. Этот длинный список зачастую противоречивых целей делает маршрутизацию чрезвычайно сложной.
Известно, что почти каждая проблема, связанная с маршрутизацией, неразрешима . Простейшая задача маршрутизации, называемая проблемой дерева Штейнера , заключающаяся в поиске кратчайшего маршрута для одной сети в одном слое без препятствий и правил проектирования, как известно, является NP-полной , как в случае, когда разрешены все углы, так и в случае, когда маршрутизация разрешена. ограничивается только горизонтальными и вертикальными проводами. [ 1 ] варианты маршрутизации каналов являются NP-полными. Также было показано, что [ 2 ] а также маршрутизация, которая уменьшает перекрестные помехи , количество переходных отверстий и так далее. Поэтому маршрутизаторы редко пытаются найти оптимальный результат. Вместо этого почти вся маршрутизация основана на эвристике , которая пытается найти достаточно хорошее решение.
Правила проектирования иногда значительно различаются от слоя к слою. Например, допустимая ширина и интервалы на нижних слоях могут быть в четыре или более раз меньше, чем разрешенные ширина и интервалы на верхних слоях. Это создает множество дополнительных сложностей, с которыми не сталкиваются маршрутизаторы для других приложений, таких как проектирование печатных плат или многокристальных модулей . Особые трудности возникают, если правила не являются простыми кратными друг другу и когда переходные отверстия должны проходить между слоями с разными правилами.
Типы маршрутизаторов
[ редактировать ]
Самыми ранними типами маршрутизаторов EDA были «ручные маршрутизаторы»: составитель щелкал мышью по конечной точке каждого сегмента линии каждой сети. Современное программное обеспечение для проектирования печатных плат обычно предоставляет «интерактивные маршрутизаторы»: составитель выбирает контактную площадку и щелкает в нескольких местах, чтобы дать инструменту EDA представление о том, куда идти, а инструмент EDA пытается разместить провода как можно ближе к этому пути, не нарушая его. проверка правил проектирования (DRC). Некоторые более продвинутые интерактивные маршрутизаторы имеют функции «толкай и толкай» (также известные как «отталкивание» или «автоматическое перемещение») в интерактивном маршрутизаторе; инструмент EDA отодвигает другие сети, если это возможно, чтобы разместить новый провод там, где этого хочет составитель, и при этом избежать нарушения DRC. Современное программное обеспечение для проектирования печатных плат также обычно предоставляет «автотрассировщики», которые маршрутизируют все оставшиеся неразведенные соединения без вмешательства человека.
Основными типами автотрассировщиков являются:
- Лабиринтный маршрутизатор [ 3 ] [ 4 ]
- Линейно-зондовый маршрутизатор
- Маршрутизатор шаблона [ 6 ] [ 10 ]
- Канальный маршрутизатор [ 11 ] [ 10 ] [ 6 ] [ 12 ]
- Маршрутизатор распределительной коробки [ 12 ]
- Речной маршрутизатор [ 12 ]
- Корешок и фрезерный станок [ 13 ]
- Бессеточный маршрутизатор [ 14 ] [ 10 ] [ 6 ] [ 15 ]
- Маршрутизатор области
- Маршрутизатор на основе теории графов [ 16 ]
- Роутер «Бладхаунд» [ 17 ] [ 18 ] [ 19 ] ( CADSTAR от Racal-Redac / Zuken )
- Спектра [ 19 ] (он же Allegro PCB Router ) (без сетки, начиная с версии 10)
- Топологический маршрутизатор
- FreeStyle Router (он же SpeedWay , автотрассировщик на базе DOS для P-CAD )
- TopoR ( автотрассировщик на базе Windows , также используемый в Eremex ) Delta Design компании
- Toporouter (маршрутизатор с открытым исходным кодом Энтони Блейка на печатной плате пакета gEDA )
- TopRouter (топологический предварительный маршрутизатор в CadSoft / Autodesk EAGLE 7.0 и выше)
- SimplifyPCB (топологический маршрутизатор с упором на маршрутизацию пакетов с результатами ручной трассировки) [ 20 ]
Как работают маршрутизаторы
[ редактировать ]Многие маршрутизаторы выполняют следующий общий алгоритм:
- Сначала определите приблизительный курс для каждой сети, часто прокладывая ее по крупной сетке. Этот шаг называется глобальной маршрутизацией . [ 21 ] и может дополнительно включать назначение слоев. Глобальная маршрутизация ограничивает размер и сложность следующих детальных этапов маршрутизации, которые можно выполнять по квадрату сетки.
Для детальной маршрутизации наиболее распространенным методом является разрыв и перенаправление, также известный как разрыв и повтор : [ 3 ]
- Выберите последовательность, в которой должны быть проложены цепи.
- Последовательно проложите каждую сеть
- Если не все цепи могут быть успешно проложены, примените любой из множества методов «очистки», при которых выбранные маршруты удаляются, порядок оставшихся цепей, подлежащих трассировке, изменяется, а оставшиеся трассировки повторяются.
Этот процесс повторяется до тех пор, пока все цепи не будут разведены или пока программа (или пользователь) не сдастся.
Альтернативный подход состоит в том, чтобы рассматривать короткие замыкания, нарушения правил проектирования, препятствия и т. д. на том же основании, что и избыточную длину провода, то есть как конечные затраты, которые следует сократить (на первых порах), а не как абсолютные значения, которых следует избегать. Этот многопроходный метод маршрутизации с «итеративным улучшением». [ 22 ] описывается следующим алгоритмом:
- Для каждого из нескольких итерационных проходов:
- Прописать или настроить весовые параметры «целевой функции» (имеющей значение весового параметра для каждой единицы избыточной длины провода и для каждого вида нарушения). Например, при первом проходе избыточная длина провода обычно может стоить дорого, тогда как нарушения конструкции, такие как короткое замыкание, соседство и т. д., обходятся дешево. На более поздних этапах относительный порядок затрат изменяется так, что нарушения влекут за собой высокие издержки или могут быть полностью запрещены.
- Выберите (или произвольно выберите) последовательность, в которой цепи должны быть проложены во время этого прохода.
- «Разорвите» (если маршрут был ранее проложен) и перенаправьте каждую сеть по очереди, чтобы минимизировать значение целевой функции для этой сети. (Некоторые маршруты обычно имеют замыкания или другие конструктивные нарушения.)
- Перейдите к следующему итерационному проходу до тех пор, пока маршрутизация не будет завершена и правильна, не будет улучшена или не будет удовлетворен какой-либо другой критерий завершения.
Большинство маршрутизаторов назначают слоям проводки преимущественно направленную проводку «x» или «y», хотя существуют маршрутизаторы, которые избегают или уменьшают необходимость такого назначения. [ 23 ] У каждого подхода есть преимущества и недостатки. Ограниченные направления упрощают проектирование источника питания и контроль межуровневых перекрестных помех, но разрешение произвольных маршрутов может уменьшить потребность в переходных отверстиях и уменьшить количество требуемых слоев проводки.
См. также
[ редактировать ]- Автоматизация электронного проектирования
- Процесс проектирования (EDA)
- Разработка интегральных схем
- Место и маршрут
- Автоматическая полярность (дифференциальные пары)
- Автокроссовер (Ethernet)
Ссылки
[ редактировать ]- ^ Гэри, MR; Джонсон, DS (1977). «Проблема о прямолинейном дереве Штейнера NP-полна» . SIAM Journal по прикладной математике . 32 (4): 826–834. дои : 10.1137/0132071 . ISSN 0036-1399 .
- ^ Шимански, Томас Г. (1985). «Маршрутизация канала Dogleg является NP-завершенной» . Транзакции IEEE по автоматизированному проектированию интегральных схем и систем . 4 (1): 31–41. дои : 10.1109/tcad.1985.1270096 . S2CID 17511882 .
- ^ Jump up to: а б с д и Байерс, Ти Джей (1 августа 1991 г.). Проектирование печатных плат на микрокомпьютерах (1-е изд.). Нью-Йорк, США: Intertext Publications/Multiscience Press, Inc. , McGraw-Hill Book Company . стр. 99–101. ISBN 978-0-07-009558-8 . LCCN 91-72187 .
- ^ Ричи, Ли В. (декабрь 1999 г.). «Маршрутизаторы для печатных плат и методы маршрутизации» (PDF) . Журнал PC Design (февраль 1999 г.). Ускоренный край. Архивировано (PDF) из оригинала 22 октября 2018 г. Проверено 22 октября 2018 г.
- ^ Ли, Честер Ю. (сентябрь 1961 г.). «Алгоритм соединения путей и его приложения». IRE-транзакции на электронных компьютерах . ЕС-10 (3): 346–365. дои : 10.1109/TEC.1961.5219222 . S2CID 40700386 .
- ^ Jump up to: а б с д и Коллипара, Равиндранат; Трипати, Виджай К.; Серджент, Джерри Э.; Блэквелл, Гленн Р.; Уайт, Дональд; Сташак, Збигнев Ю. (2005). «11.1.3 Корпуса электронных систем. Проектирование печатных монтажных плат» (PDF) . В Уитакере, Джерри К.; Дорф, Ричард К. (ред.). Справочник по электронике (2-е изд.). CRC Press , Taylor & Francisco Group, LLC . п. 1266. ИСБН 978-0-8493-1889-4 . LCCN 2004057106 . Архивировано (PDF) из оригинала 25 сентября 2017 г. Проверено 25 сентября 2017 г.
- ^ Хэдлок, Фрэнк О. (1 декабря 1977 г.). «Алгоритм кратчайшего пути для сеточных графов» . Сети . 7 (4): 323–334. дои : 10.1002/net.3230070404 .
- ^ Миками, Коичи; Табучи, Кинья (1968). Компьютерная программа для оптимальной разводки разъемов печатных плат . Труды ИФИПС . Том. Х47. стр. 1745–1478.
- ^ Хайтауэр, Дэвид В. (1969). «Решение проблем прокладки линий на непрерывной плоскости». DAC'69: Материалы 6-й ежегодной конференции по автоматизации проектирования . АКМ Пресс . стр. 1–24. дои : 10.1145/800260.809014 . (Примечание. Здесь содержится одно из первых описаний «маршрутизатора линейного зонда».)
- ^ Jump up to: а б с д Мингес, Меррилл Л. (1989). Электронный справочник материалов: Упаковка . Том. 1. АСМ Интернэшнл . ISBN 978-0-87170-285-2 . Проверено 27 сентября 2017 г.
- ^ Рид, Джеймс Б.; Санджованни-Винсентелли, Альберто; Сантамауро, Мауро (1985). «Новый маршрутизатор символических каналов: YACR2». Транзакции IEEE по автоматизированному проектированию интегральных схем и систем . 4 (3): 203–219. дои : 10.1109/TCAD.1985.1270117 . S2CID 17065773 . [1]
- ^ Jump up to: а б с Шанкар, Рави; Фернандес, Эдуардо Б. (12 января 2014 г.). Айнспрух, Норман Г. (ред.). СБИС и архитектура компьютеров . СБИС электроника микроструктура. Том. 20. Академическая пресса . ISBN 978-1-48321784-0 . Проверено 22 октября 2018 г.
- ^ Маклеллан, Пол (23 апреля 2012 г.). «Память маршрутизации каналов» . Архивировано из оригинала 18 мая 2021 г. Проверено 1 января 2022 г.
- ^ Финч, Алан С.; Маккензи, Кен Дж.; Болсдон, Дж.Дж.; Саймондс, Г. (23 июня 1985 г.). Метод бессеточной трассировки печатных плат (PDF) . 22-я конференция по автоматизации проектирования ACM/IEEE, Лас-Вегас, Невада, США. Конференция по автоматизации проектирования, 2009. Dac '09. 46-я конференция ACM/IEEE . Ньютаун, Тьюксбери, Глостершир, Великобритания: Racal-Redac Ltd., стр. 509–515. дои : 10.1109/DAC.1985.1585990 . ISBN 0-8186-0635-5 . ISSN 0738-100X . Архивировано (PDF) из оригинала 22 октября 2018 г. Проверено 22 октября 2018 г.
- ^ Уэбб, Даррелл (20 декабря 2012 г.). «Дань уважения Алану Финчу, отцу бессеточной автотрассировки» . Архивировано из оригинала 22 октября 2018 г. Проверено 22 октября 2018 г.
- ^ Ву, Бо (апрель 1992 г.). Алгоритмы маршрутизации на основе теории графов (PDF) (Диссертация). Университет Западного Мичигана . S2CID 3357923 . Архивировано из оригинала (PDF) 22 октября 2018 г. Проверено 22 октября 2018 г.
- ^ «Компьютер-Партнер Киль ГмбХ: «Бладхаунд» распаковывает платы на 16 слоев» . Компьютерная неделя (на немецком языке). 13 марта 1992 г. Архивировано из оригинала 21 октября 2018 г. Проверено 20 октября 2018 г.
- ^ Пфайл, Чарльз (2 ноября 2017 г.). «Проектирование печатных плат на протяжении всей жизни: от дизайна к программному обеспечению» . Сеть ЭДН . Архивировано из оригинала 21 октября 2018 г. Проверено 20 октября 2018 г.
- ^ Jump up to: а б Честное слово, Детлеф. «1.6. Компьютерное проектирование печатных плат – разукрупнение» (PDF) . Схемотехника (на немецком языке). Университет Эрнста Аббе в Йене (EAH). Архивировано из оригинала (PDF) 21 октября 2018 г. Проверено 20 октября 2018 г.
- ^ «Упрощение автоматизации проектирования — новое поколение методологии проектирования» .
- ^ Соукуп, Иржи (1979). «Глобальный маршрутизатор» . Материалы 16-й конференции по автоматизации проектирования . Сан-Диего, Калифорния, США: IEEE Press . стр. 481–489.
- ^ Рубин, Фрэнк (1974). «Итеративный метод прокладки печатных проводов» . Материалы 11-го семинара по автоматизации проектирования . стр. 308–13.
- ^ Линскер, Ральф (1984). «Система маршрутизации проводов, управляемая штрафными функциями итеративного улучшения» (PDF) . Журнал исследований и разработок IBM . 28 (5): 613–624. дои : 10.1147/рд.285.0613 .
Дальнейшее чтение
[ редактировать ]- Шеффер, Луи К.; Лаваньо, Лучано; Мартин, Грант (2006). «Глава 8: Маршрутизация ». Справочник по автоматизации электронного проектирования интегральных схем . Том. II. Бока-Ратон, Флорида, США: CRC Press / Тейлор и Фрэнсис . ISBN 978-0-8493-3096-4 .