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

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

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

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

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

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

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

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

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

  • Маршрутизатор лабиринта [3] [4]
    • Маршрутизатор Ли [5] [3] [6]
    • Маршрутизатор Hadlock [7]
    • Маршрутизатор Flood [3]
  • Маршрутизатор линейно-зондового типа
    • Маршрутизатор Миками–Тахучи [8]
    • Маршрутизатор Hightower [9] [6] [10] [3]
  • Шаблонный маршрутизатор [6] [10]
  • Маршрутизатор каналов [11] [10] [6] [12]
    • Коммутатор маршрутизатор [12]
    • Речной маршрутизатор [12]
    • Фрезерный станок для стежка и окантовки [13]
  • Бессетевой маршрутизатор [14] [10] [6] [15]
    • Маршрутизатор области
    • Маршрутизатор на основе теории графов [16]
    • Топологический маршрутизатор
      • FreeStyle Router (он же SpeedWay , автотрассировщик на базе DOS для P-CAD )
      • TopoR ( автотрассировщик на базе Windows , также используемый в Delta Design компании Eremex )
      • Toporouter (маршрутизатор с открытым исходным кодом Энтони Блейка на печатной плате пакета gEDA )
      • TopRouter (топологический предварительный маршрутизатор в CadSoft / Autodesk EAGLE 7.0 и выше)
      • SimplifyPCB (топологический маршрутизатор с фокусом на маршрутизацию пучков с результатами ручной маршрутизации) [20]

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

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

  • Сначала определите приблизительный курс для каждой сети, часто путем маршрутизации по грубой сетке. Этот шаг называется глобальной маршрутизацией [ 21] и может опционально включать назначение слоев. Глобальная маршрутизация ограничивает размер и сложность следующих подробных шагов маршрутизации, которые могут быть выполнены квадрат за квадратом сетки.

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

  • Выберите последовательность, в которой будут прокладываться сети.
  • Прокладывайте каждую сеть последовательно
  • Если не все сети могут быть успешно проложены, примените любой из множества методов «очистки», при которых выбранные маршруты удаляются, порядок оставшихся сетей, подлежащих прокладке, изменяется, а оставшиеся маршруты прокладываются снова.

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

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

  • Для каждого из нескольких итеративных проходов:
  • Назначьте или отрегулируйте параметры веса «целевой функции» (имеющей значение параметра веса для каждой единицы избыточной длины провода и для каждого типа нарушения). Например, для первого прохода избыточная длина провода обычно может иметь высокую стоимость, в то время как нарушения конструкции, такие как короткие замыкания, смежность и т. д., имеют низкую стоимость. В последующих проходах относительный порядок затрат изменяется таким образом, что нарушения становятся высокостоимостными или могут быть полностью запрещены.
  • Выберите (или выберите случайным образом) последовательность, в которой сети должны быть проложены во время этого прохода.
  • «Разорвите» (если они были ранее проложены) и перенаправьте каждую сеть по очереди, чтобы минимизировать значение целевой функции для этой сети. (Некоторые из маршрутов, как правило, будут иметь короткие замыкания или другие нарушения конструкции.)
  • Переходите к следующему итеративному проходу до тех пор, пока маршрутизация не будет завершена и правильна, не прекратит улучшаться или не будет выполнен какой-либо другой критерий завершения.

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

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

Ссылки

  1. ^ Garey, MR; Johnson, DS (1977). «Проблема прямолинейного дерева Штейнера является NP-полной». SIAM Journal on Applied Mathematics . 32 (4): 826– 834. doi :10.1137/0132071. ISSN  0036-1399.
  2. ^ Szymanski, Thomas G. (1985). «Dogleg Channel Routing is NP-Complete». Труды IEEE по автоматизированному проектированию интегральных схем и систем . 4 (1): 31– 41. doi :10.1109/tcad.1985.1270096. S2CID  17511882.
  3. ^ abcde Байерс, Т.Дж. (1991-08-01). Проектирование печатных плат с использованием микрокомпьютеров (1-е изд.). Нью-Йорк, США: Intertext Publications/Multiscience Press, Inc. , McGraw-Hill Book Company . стр.  99– 101. ISBN 978-0-07-009558-8. LCCN  91-72187.
  4. ^ Ritchey, Lee W. (декабрь 1999 г.). "PCB routers and routing methods" (PDF) . PC Design Magazine (февраль 1999 г.). Speeding Edge. Архивировано (PDF) из оригинала 2018-10-22 . Получено 2018-10-22 .
  5. ^ Ли, Честер Ю. (сентябрь 1961 г.). «Алгоритм для соединений путей и его приложения». Труды IRE по электронным компьютерам . EC-10 (3): 346– 365. doi :10.1109/TEC.1961.5219222. S2CID  40700386.
  6. ^ abcde Kollipara, Ravindranath; Tripathi, Vijai K.; Sergent, Jerry E.; Blackwell, Glenn R.; White, Donald; Staszak, Zbigniew J. (2005). "11.1.3 Упаковка электронных систем - Проектирование печатных плат" (PDF) . В Whitaker, Jerry C.; Dorf, Richard C. (ред.). The Electronics Handbook (2-е изд.). CRC Press , Taylor & Francis Group, LLC . стр. 1266. ISBN 978-0-8493-1889-4. LCCN  2004057106. Архивировано (PDF) из оригинала 2017-09-25 . Получено 2017-09-25 .
  7. ^ Хэдлок, Фрэнк О. (1977-12-01). "Алгоритм кратчайшего пути для решетчатых графов". Networks . 7 (4): 323– 334. doi :10.1002/net.3230070404.
  8. ^ Миками, Коити; Табучи, Кинья (1968). Компьютерная программа для оптимальной трассировки соединителей печатных плат . Труды IFIPS . Том H47. С.  1745–1478 .
  9. ^ Хайтауэр, Дэвид В. (1969). «Решение проблем трассировки линий на непрерывной плоскости». DAC'69: Труды 6-й ежегодной конференции по автоматизации проектирования . ACM Press . С.  1– 24. doi :10.1145/800260.809014.(Примечание. Здесь содержится одно из первых описаний «маршрутизатора линейного зонда».)
  10. ^ abcd Minges, Merrill L. (1989). Справочник по электронным материалам: Упаковка. Том 1. ASM International . ISBN 978-0-87170-285-2. Получено 27.09.2017 .
  11. ^ Рид, Джеймс Б.; Санджованни-Винчентелли, Альберто; Сантамауро, Мауро (1985). «Новый символический маршрутизатор каналов: YACR2». Труды IEEE по автоматизированному проектированию интегральных схем и систем . 4 (3): 203– 219. doi :10.1109/TCAD.1985.1270117. S2CID  17065773.[1]
  12. ^ abc Шанкар, Рави; Фернандес, Эдуардо Б. (2014-01-12). Эйнспрух, Норман Г. (ред.). СБИС и архитектура компьютеров. Наука о микроструктурах электроники СБИС. Том 20. Academic Press . ISBN 978-1-48321784-0. Получено 22.10.2018 .
  13. ^ Маклеллан, Пол (2012-04-23). ​​"Channel Routing Memories". Архивировано из оригинала 2021-05-18 . Получено 2022-01-01 .
  14. ^ Finch, Alan C.; Mackenzie, Ken J.; Balsdon, GJ; Symonds, G. (1985-06-23). ​​Метод бессеточной трассировки печатных плат (PDF) . 22-я конференция ACM/IEEE по автоматизации проектирования, Лас-Вегас, Невада, США. Конференция по автоматизации проектирования, 2009. Dac '09. 46-я конференция ACM/IEEE . Ньютаун, Тьюксбери, Глостершир, Великобритания: Racal-Redac Ltd. стр.  509– 515. doi :10.1109/DAC.1985.1585990. ISBN 0-8186-0635-5. ISSN  0738-100X. Архивировано (PDF) из оригинала 2018-10-22 . Получено 2018-10-22 .
  15. ^ Уэбб, Даррелл (2012-12-20). «Дань уважения Алану Финчу, отцу бессеточной автомаршрутизации». Архивировано из оригинала 2018-10-22 . Получено 2018-10-22 .
  16. ^ Wu, Bo (апрель 1992 г.). Graph Theory Based Routing Algorithms (PDF) (диссертация). Western Michigan University . S2CID  3357923. Архивировано из оригинала (PDF) 2018-10-22 . Получено 2018-10-22 .
  17. ^ "Computer-Partner Kiel GmbH: "Bloodhound" entflechtet Leiterplatten auf 16 Lagen" . Computerwoche (на немецком языке). 13 марта 1992 г. Архивировано из оригинала 21 октября 2018 г. Проверено 20 октября 2018 г.
  18. ^ Пфайль, Чарльз (2017-11-02). "Проектирование печатных плат на протяжении всей жизни: от проектирования до программного обеспечения". EDN Network . Архивировано из оригинала 21-10-2018 . Получено 20-10-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 Journal of Research and Development . 28 (5): 613– 624. doi :10.1147/rd.285.0613.

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

  • Шеффер, Луис К.; Лаваньо, Лучано; Мартин, Грант (2006). "Глава 8: Маршрутизация ". Electronic Design Automation For Integrated Circuits Handbook . Том II. Бока-Ратон, Флорида, США: CRC Press / Taylor & Francis . ISBN 978-0-8493-3096-4.
  • http://www.eecs.northwestern.edu/~haizhou/357/lec6.pdf
  • http://www.facweb.iitkgp.ernet.in/~isg/CAD/SLIDES/10-grid-routing.pdf
Взято с "https://en.wikipedia.org/w/index.php?title=Маршрутизация_(электронная_автоматизация_проектирования)&oldid=1210799570#Push-and-shove_router"