stringtranslate.com

Маршрутизация (автоматизация электронного проектирования)

В электронном проектировании прокладка проводов , обычно называемая просто маршрутизацией , является шагом в проектировании печатных плат (PCB) и интегральных схем (ИС). Он основан на предыдущем этапе, называемом размещением , который определяет расположение каждого активного элемента ИС или компонента на печатной плате. После размещения на этапе маршрутизации добавляются провода, необходимые для правильного соединения размещенных компонентов с соблюдением всех правил проектирования ИС. Вместе этапы размещения и маршрутизации при проектировании ИС называются местом и маршрутом .

Задача всех роутеров одна и та же. Им предоставляются некоторые уже существующие многоугольники, состоящие из контактов (также называемых терминалами) на ячейках, и, возможно, некоторые ранее существовавшие соединения, называемые предварительными маршрутами. Каждый из этих полигонов связан с сетью , обычно по имени или номеру. Основная задача маршрутизатора — создать такую ​​геометрию, чтобы все терминалы, назначенные одной сети, были подключены, никакие терминалы, назначенные разным сетям, не были подключены, и соблюдались все правила проектирования. Маршрутизатор может выйти из строя из-за неподключения клемм, которые должны быть подключены (обрыв), из-за ошибочного подключения двух терминалов, которые не должны быть подключены (короткое замыкание), или из-за нарушения правил проектирования. Кроме того, для правильного подключения сетей маршрутизаторы также должны убедиться, что конструкция соответствует времени, не имеет проблем с перекрестными помехами , соответствует всем требованиям к плотности металла, не страдает от антенных эффектов и так далее. Этот длинный список зачастую противоречивых целей делает маршрутизацию чрезвычайно сложной.

Известно, что почти каждая проблема, связанная с маршрутизацией, неразрешима . Простейшая задача маршрутизации, называемая проблемой дерева Штейнера , заключающаяся в поиске кратчайшего маршрута для одной сети в одном слое без препятствий и правил проектирования, как известно, является NP-полной , как в случае, когда разрешены все углы, так и в случае, когда маршрутизация разрешена. ограничивается только горизонтальными и вертикальными проводами. [1] Также было показано, что варианты маршрутизации каналов являются NP-полными, [2] а также маршрутизация, которая уменьшает перекрестные помехи , количество переходных отверстий и так далее. Поэтому маршрутизаторы редко пытаются найти оптимальный результат. Вместо этого почти вся маршрутизация основана на эвристике , которая пытается найти достаточно хорошее решение.

Правила проектирования иногда значительно различаются от слоя к слою. Например, допустимая ширина и интервалы на нижних слоях могут быть в четыре или более раз меньше, чем разрешенные ширина и интервалы на верхних слоях. Это создает множество дополнительных сложностей, с которыми не сталкиваются маршрутизаторы для других приложений, таких как проектирование печатных плат или многокристальных модулей . Особые трудности возникают, если правила не являются простыми кратными друг другу и когда переходные отверстия должны проходить между слоями с разными правилами.

Типы маршрутизаторов

Печатная плата как конструкция на компьютере (слева) и реализованная в виде сборки платы, заполненной компонентами (справа). Плата двусторонняя, со сквозным покрытием, зеленым паяльным резистом и белой надписью. Использовались как поверхностные, так и сквозные компоненты.

Самыми ранними типами маршрутизаторов EDA были «ручные маршрутизаторы»: составитель щелкал мышью по конечной точке каждого сегмента линии каждой сети. Современное программное обеспечение для проектирования печатных плат обычно предоставляет «интерактивные маршрутизаторы»: составитель выбирает контактную площадку и щелкает в нескольких местах, чтобы дать инструменту EDA представление о том, куда идти, а инструмент EDA пытается разместить провода как можно ближе к этому пути, не нарушая его. проверка правил проектирования (DRC). Некоторые более продвинутые интерактивные маршрутизаторы имеют функции «толкай и толкай» (также известные как «отталкивание» или «автоматическое перемещение») в интерактивном маршрутизаторе; инструмент EDA отодвигает другие сети, если это возможно, чтобы разместить новый провод там, где этого хочет составитель, и при этом избежать нарушения DRC. Современное программное обеспечение для проектирования печатных плат также обычно предоставляет «автотрассировщики», которые маршрутизируют все оставшиеся неразведенные соединения без вмешательства человека.

Основными типами автотрассировщиков являются:

Как работают маршрутизаторы

Многие маршрутизаторы выполняют следующий общий алгоритм:

Для детальной маршрутизации наиболее распространенным методом является разрыв и перенаправление, также известный как разрыв и повтор : [3]

Этот процесс повторяется до тех пор, пока все цепи не будут разведены или пока программа (или пользователь) не сдастся.

Альтернативный подход состоит в том, чтобы рассматривать короткие замыкания, нарушения правил проектирования, препятствия и т. д. на том же основании, что и избыточную длину провода, то есть как конечные затраты, которые следует сократить (на первых порах), а не как абсолютные значения, которых следует избегать. Этот многопроходной метод маршрутизации с «итеративным улучшением» [22] описывается следующим алгоритмом:

Большинство маршрутизаторов назначают слоям проводки преимущественно направленную проводку «x» или «y», хотя существуют маршрутизаторы, которые избегают или уменьшают необходимость такого назначения. [23] У каждого подхода есть свои преимущества и недостатки. Ограниченные направления упрощают проектирование источника питания и контроль межуровневых перекрестных помех, но разрешение произвольных маршрутов может уменьшить потребность в переходных отверстиях и уменьшить количество необходимых слоев проводки.

Смотрите также

Рекомендации

  1. ^ Гэри, MR; Джонсон, DS (1977). «Задача о прямолинейном дереве Штейнера NP-полна». SIAM Journal по прикладной математике . 32 (4): 826–834. дои : 10.1137/0132071. ISSN  0036-1399.
  2. ^ Шимански, Томас Г. (1985). «Маршрутизация канала Dogleg является NP-завершенной». Сделки IEEE по автоматизированному проектированию интегральных схем и систем . 4 (1): 31–41. дои : 10.1109/tcad.1985.1270096.
  3. ^ abcde Байерс, TJ (1 августа 1991 г.). Проектирование печатных плат на микрокомпьютерах (1-е изд.). Нью-Йорк, США: Intertext Publications/Multiscience Press, Inc. , McGraw-Hill Book Company . стр. 99–101. ISBN 978-0-07-009558-8. LCCN  91-72187.
  4. ^ Ричи, Ли В. (декабрь 1999 г.). «Маршрутизаторы для печатных плат и методы маршрутизации» (PDF) . Журнал ПК-дизайна . Speeding Edge (февраль 1999 г.). Архивировано (PDF) из оригинала 22 октября 2018 г. Проверено 22 октября 2018 г.
  5. ^ Ли, Честер Ю. (сентябрь 1961 г.). «Алгоритм соединения путей и его приложения». IRE-транзакции на электронных компьютерах . ЕС-10 (3): 346–365. дои : 10.1109/TEC.1961.5219222. S2CID  40700386.
  6. ^ abcde Коллипара, Равиндранат; Трипати, Виджай К.; Серджент, Джерри Э.; Блэквелл, Гленн Р.; Уайт, Дональд; Сташак, Збигнев Ю. (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 г.
  7. ^ Хэдлок, Фрэнк О. (1 декабря 1977 г.). «Алгоритм кратчайшего пути для сеточных графов». Сети . 7 (4): 323–334. дои : 10.1002/net.3230070404.
  8. ^ Миками, Коичи; Табучи, Кинья (1968). Компьютерная программа для оптимальной разводки разъемов печатных плат . Труды ИФИПС . Том. Х47. стр. 1745–1478.
  9. ^ Хайтауэр, Дэвид В. (1969). «Решение проблем прокладки линий на непрерывной плоскости». DAC'69: Материалы 6-й ежегодной конференции по автоматизации проектирования . АКМ Пресс . стр. 1–24. дои : 10.1145/800260.809014.(Примечание. Здесь содержится одно из первых описаний «маршрутизатора линейного зонда».)
  10. ^ abcd Мингес, Меррилл Л. (1989). Электронный справочник материалов: Упаковка. Том. 1. АСМ Интернэшнл . ISBN 978-0-87170-285-2. Проверено 27 сентября 2017 г.
  11. ^ Рид, Джеймс Б.; Санджованни-Винсентелли, Альберто; Сантамауро, Мауро (1985). «Новый маршрутизатор символических каналов: YACR2». Транзакции IEEE по автоматизированному проектированию интегральных схем и систем . 4 (3): 203–219. doi : 10.1109/TCAD.1985.1270117. S2CID  17065773.[1]
  12. ^ abc Шанкар, Рави; Фернандес, Эдуардо Б. (12 января 2014 г.). Айнспрух, Норман Г. (ред.). СБИС и архитектура компьютеров. СБИС электроника микроструктура. Том. 20. Академическая пресса . ISBN 978-1-48321784-0. Проверено 22 октября 2018 г.
  13. ^ Маклеллан, Пол (23 апреля 2012 г.). «Память маршрутизации каналов». Архивировано из оригинала 18 мая 2021 г. Проверено 1 января 2022 г.
  14. ^ Финч, Алан С.; Маккензи, Кен Дж.; Болсдон, Дж.Дж.; Саймондс, Г. (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 г.
  15. ^ Уэбб, Даррелл (20 декабря 2012 г.). «Дань уважения Алану Финчу, отцу бессеточной автотрассировки». Архивировано из оригинала 22 октября 2018 г. Проверено 22 октября 2018 г.
  16. ^ Ву, Бо (апрель 1992 г.). Алгоритмы маршрутизации на основе теории графов (PDF) (Диссертация). Университет Западного Мичигана . S2CID  3357923. Архивировано из оригинала (PDF) 22 октября 2018 г. Проверено 22 октября 2018 г.
  17. ^ "Computer-Partner Kiel GmbH: "Bloodhound" entflechtet Leiterplatten auf 16 Lagen" . Computerwoche (на немецком языке). 13 марта 1992 г. Архивировано из оригинала 21 октября 2018 г. Проверено 20 октября 2018 г.
  18. ^ Пфейл, Чарльз (2 ноября 2017 г.). «Проектирование печатных плат на протяжении всей жизни: от дизайна к программному обеспечению». Сеть ЭДН . Архивировано из оригинала 21 октября 2018 г. Проверено 20 октября 2018 г.
  19. ^ аб Редлих, Детлеф. «1.6. Rechnergestützter Leiterplattenentwurf - Entflechtung» (PDF) . Schaltungsdesign (на немецком языке). Высшая школа Эрнста-Аббе Йена (EAH). Архивировано из оригинала (PDF) 21 октября 2018 г. Проверено 20 октября 2018 г.
  20. ^ «Упрощение автоматизации проектирования - новое поколение методологии проектирования» .
  21. ^ Соукуп, Иржи (1979). «Глобальный маршрутизатор». Материалы 16-й конференции по автоматизации проектирования . Сан-Диего, Калифорния, США: IEEE Press . стр. 481–489.
  22. ^ Рубин, Фрэнк (1974). «Итеративный метод прокладки печатных проводов». Материалы 11-го семинара по автоматизации проектирования . стр. 308–13.
  23. ^ Линскер, Ральф (1984). «Система маршрутизации проводов, основанная на штрафных функциях итеративного улучшения» (PDF) . Журнал исследований и разработок IBM . 28 (5): 613–624. дои : 10.1147/rd.285.0613.

дальнейшее чтение

Внешние ссылки