В электронном проектировании прокладка проводов , обычно называемая просто маршрутизацией , является шагом в проектировании печатных плат (PCB) и интегральных схем (ИС). Он основан на предыдущем этапе, называемом размещением , который определяет расположение каждого активного элемента ИС или компонента на печатной плате. После размещения на этапе маршрутизации добавляются провода, необходимые для правильного соединения размещенных компонентов с соблюдением всех правил проектирования ИС. Вместе этапы размещения и маршрутизации при проектировании ИС называются местом и маршрутом .
Задача всех роутеров одна и та же. Им предоставляются некоторые уже существующие многоугольники, состоящие из контактов (также называемых терминалами) на ячейках, и, возможно, некоторые ранее существовавшие соединения, называемые предварительными маршрутами. Каждый из этих полигонов связан с сетью , обычно по имени или номеру. Основная задача маршрутизатора — создать такую геометрию, чтобы все терминалы, назначенные одной сети, были подключены, никакие терминалы, назначенные разным сетям, не были подключены, и соблюдались все правила проектирования. Маршрутизатор может выйти из строя из-за неподключения клемм, которые должны быть подключены (обрыв), из-за ошибочного подключения двух терминалов, которые не должны быть подключены (короткое замыкание), или из-за нарушения правил проектирования. Кроме того, для правильного подключения сетей маршрутизаторы также должны убедиться, что конструкция соответствует времени, не имеет проблем с перекрестными помехами , соответствует всем требованиям к плотности металла, не страдает от антенных эффектов и так далее. Этот длинный список зачастую противоречивых целей делает маршрутизацию чрезвычайно сложной.
Известно, что почти каждая проблема, связанная с маршрутизацией, неразрешима . Простейшая задача маршрутизации, называемая проблемой дерева Штейнера , заключающаяся в поиске кратчайшего маршрута для одной сети в одном слое без препятствий и правил проектирования, как известно, является NP-полной , как в случае, когда разрешены все углы, так и в случае, когда маршрутизация разрешена. ограничивается только горизонтальными и вертикальными проводами. [1] Также было показано, что варианты маршрутизации каналов являются NP-полными, [2] а также маршрутизация, которая уменьшает перекрестные помехи , количество переходных отверстий и так далее. Поэтому маршрутизаторы редко пытаются найти оптимальный результат. Вместо этого почти вся маршрутизация основана на эвристике , которая пытается найти достаточно хорошее решение.
Правила проектирования иногда значительно различаются от слоя к слою. Например, допустимая ширина и интервалы на нижних слоях могут быть в четыре или более раз меньше, чем разрешенные ширина и интервалы на верхних слоях. Это создает множество дополнительных сложностей, с которыми не сталкиваются маршрутизаторы для других приложений, таких как проектирование печатных плат или многокристальных модулей . Особые трудности возникают, если правила не являются простыми кратными друг другу и когда переходные отверстия должны проходить между слоями с разными правилами.
Типы маршрутизаторов
Печатная плата как конструкция на компьютере (слева) и реализованная в виде сборки платы, заполненной компонентами (справа). Плата двусторонняя, со сквозным покрытием, зеленым паяльным резистом и белой надписью. Использовались как поверхностные, так и сквозные компоненты.
Самыми ранними типами маршрутизаторов EDA были «ручные маршрутизаторы»: составитель щелкал мышью по конечной точке каждого сегмента линии каждой сети. Современное программное обеспечение для проектирования печатных плат обычно предоставляет «интерактивные маршрутизаторы»: составитель выбирает контактную площадку и щелкает в нескольких местах, чтобы дать инструменту EDA представление о том, куда идти, а инструмент EDA пытается разместить провода как можно ближе к этому пути, не нарушая его. проверка правил проектирования (DRC). Некоторые более продвинутые интерактивные маршрутизаторы имеют функции «толкай и толкай» (также известные как «отталкивание» или «автоматическое перемещение») в интерактивном маршрутизаторе; инструмент EDA отодвигает другие сети, если это возможно, чтобы разместить новый провод там, где этого хочет составитель, и при этом избежать нарушения DRC. Современное программное обеспечение для проектирования печатных плат также обычно предоставляет «автотрассировщики», которые маршрутизируют все оставшиеся неразведенные соединения без вмешательства человека.
SimplifyPCB (топологический маршрутизатор с упором на маршрутизацию пакетов с результатами ручной трассировки) [20]
Как работают маршрутизаторы
Многие маршрутизаторы выполняют следующий общий алгоритм:
Сначала определите приблизительный курс для каждой сети, часто прокладывая ее по крупной сетке. Этот шаг называется глобальной маршрутизацией [ 21] и может дополнительно включать назначение уровней. Глобальная маршрутизация ограничивает размер и сложность следующих детальных этапов маршрутизации, которые можно выполнять по квадрату сетки.
Для детальной маршрутизации наиболее распространенным методом является разрыв и перенаправление, также известный как разрыв и повтор : [3]
Выберите последовательность, в которой должны быть проложены цепи.
Последовательно проложите каждую сеть
Если не все цепи могут быть успешно проложены, примените любой из множества методов «очистки», при которых выбранные маршруты удаляются, порядок оставшихся цепей, подлежащих трассировке, изменяется, а оставшиеся трассировки повторяются.
Этот процесс повторяется до тех пор, пока все цепи не будут разведены или пока программа (или пользователь) не сдастся.
Альтернативный подход состоит в том, чтобы рассматривать короткие замыкания, нарушения правил проектирования, препятствия и т. д. на том же основании, что и избыточную длину провода, то есть как конечные затраты, которые следует сократить (на первых порах), а не как абсолютные значения, которых следует избегать. Этот многопроходной метод маршрутизации с «итеративным улучшением» [22] описывается следующим алгоритмом:
Для каждого из нескольких итерационных проходов:
Прописать или настроить весовые параметры «целевой функции» (имеющей значение весового параметра для каждой единицы избыточной длины провода и для каждого вида нарушения). Например, при первом проходе избыточная длина провода обычно может стоить дорого, тогда как нарушения конструкции, такие как короткое замыкание, соседство и т. д., обходятся дешево. На более поздних этапах относительный порядок затрат изменяется так, что нарушения влекут за собой высокие издержки или могут быть полностью запрещены.
Выберите (или произвольно выберите) последовательность, в которой цепи должны быть проложены во время этого прохода.
«Разорвите» (если ранее маршрутизация была проложена) и перенаправьте каждую сеть по очереди, чтобы минимизировать значение целевой функции для этой сети. (Некоторые маршруты обычно имеют замыкания или другие конструктивные нарушения.)
Перейдите к следующему итерационному проходу до тех пор, пока маршрутизация не будет завершена и правильна, не будет улучшена или не будет удовлетворен какой-либо другой критерий завершения.
Большинство маршрутизаторов назначают слоям проводки преимущественно направленную проводку «x» или «y», хотя существуют маршрутизаторы, которые избегают или уменьшают необходимость такого назначения. [23] У каждого подхода есть свои преимущества и недостатки. Ограниченные направления упрощают проектирование источника питания и контроль межуровневых перекрестных помех, но разрешение произвольных маршрутов может уменьшить потребность в переходных отверстиях и уменьшить количество необходимых слоев проводки.
^ Шимански, Томас Г. (1985). «Маршрутизация канала Dogleg является NP-завершенной». Сделки IEEE по автоматизированному проектированию интегральных схем и систем . 4 (1): 31–41. дои : 10.1109/tcad.1985.1270096.
^ Ричи, Ли В. (декабрь 1999 г.). «Маршрутизаторы для печатных плат и методы маршрутизации» (PDF) . Журнал ПК-дизайна . Speeding Edge (февраль 1999 г.). Архивировано (PDF) из оригинала 22 октября 2018 г. Проверено 22 октября 2018 г.
^ Ли, Честер Ю. (сентябрь 1961 г.). «Алгоритм соединения путей и его приложения». IRE-транзакции на электронных компьютерах . ЕС-10 (3): 346–365. дои : 10.1109/TEC.1961.5219222. S2CID 40700386.
^ 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 г.
^ Хэдлок, Фрэнк О. (1 декабря 1977 г.). «Алгоритм кратчайшего пути для сеточных графов». Сети . 7 (4): 323–334. дои : 10.1002/net.3230070404.
^ Миками, Коичи; Табучи, Кинья (1968). Компьютерная программа для оптимальной разводки разъемов печатных плат . Труды ИФИПС . Том. Х47. стр. 1745–1478.
^ Хайтауэр, Дэвид В. (1969). «Решение проблем прокладки линий на непрерывной плоскости». DAC'69: Материалы 6-й ежегодной конференции по автоматизации проектирования . АКМ Пресс . стр. 1–24. дои : 10.1145/800260.809014.(Примечание. Здесь содержится одно из первых описаний «маршрутизатора линейного зонда».)
^ abcd Мингес, Меррилл Л. (1989). Электронный справочник материалов: Упаковка. Том. 1. АСМ Интернэшнл . ISBN978-0-87170-285-2. Проверено 27 сентября 2017 г.
^ abc Шанкар, Рави; Фернандес, Эдуардо Б. (12 января 2014 г.). Айнспрух, Норман Г. (ред.). СБИС и архитектура компьютеров. СБИС электроника микроструктура. Том. 20. Академическая пресса . ISBN978-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. ISBN0-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 г.
^ "Computer-Partner Kiel GmbH: "Bloodhound" entflechtet Leiterplatten auf 16 Lagen" . Computerwoche (на немецком языке). 13 марта 1992 г. Архивировано из оригинала 21 октября 2018 г. Проверено 20 октября 2018 г.
^ Пфейл, Чарльз (2 ноября 2017 г.). «Проектирование печатных плат на протяжении всей жизни: от дизайна к программному обеспечению». Сеть ЭДН . Архивировано из оригинала 21 октября 2018 г. Проверено 20 октября 2018 г.
^ аб Редлих, Детлеф. «1.6. Rechnergestützter Leiterplattenentwurf - Entflechtung» (PDF) . Schaltungsdesign (на немецком языке). Высшая школа Эрнста-Аббе Йена (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/rd.285.0613.
дальнейшее чтение
Шеффер, Луи К.; Лаваньо, Лучано; Мартин, Грант (2006). «Глава 8: Маршрутизация ». Справочник по автоматизации электронного проектирования интегральных схем . Том. II. Бока-Ратон, Флорида, США: CRC Press / Тейлор и Фрэнсис . ISBN 978-0-8493-3096-4.