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

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

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

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

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

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

Типы роутеров

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

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

Основные типы автотрассировщиков:

Как работают роутеры

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

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

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

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

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

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

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

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

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

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

  1. ^ а б c d е Байерс, Т. Дж. (1991-08-01). Разработка печатных плат на микрокомпьютерах (1-е изд.). Нью-Йорк, США: Intertext Publications / Multiscience Press, Inc., Книжная компания McGraw-Hill. С. 99–101. ISBN  978-0-07-009558-8. LCCN  91-72187.
  2. ^ Ричи, Ли В. (декабрь 1999 г.). «Маршрутизаторы печатных плат и методы трассировки» (PDF). Журнал PC Design. Speeding Edge (февраль 1999 г.). В архиве (PDF) из оригинала от 22.10.2018. Получено 2018-10-22.
  3. ^ Ли, Честер Ю. (сентябрь 1961 г.). «Алгоритм соединений путей и его приложения». Операции IRE на электронных компьютерах. ИС-10 (3): 346–365. Дои:10.1109 / TEC.1961.5219222.
  4. ^ а б c d е Коллипара, Равиндранатх; Tripathi, Vijai K .; Sergent, Джерри Э .; Блэквелл, Гленн Р .; Белый, Дональд; Сташак, Збигнев Ю. (2005). «11.1.3 Упаковочные электронные системы - Дизайн печатных монтажных плат» (PDF). В Whitaker, Jerry C .; Дорф, Ричард К. (ред.). Справочник по электронике (2-е изд.). CRC Press, Тейлор и Фрэнсис Групп, ООО. п. 1266. ISBN  978-0-8493-1889-4. LCCN  2004057106. В архиве (PDF) из оригинала на 2017-09-25. Получено 2017-09-25.
  5. ^ Хэдлок, Фрэнк О. (1977-12-01). «Алгоритм кратчайшего пути для сеточных графов». Сети. 7 (4): 323–334. Дои:10.1002 / нетто.3230070404.
  6. ^ Миками, Коичи; Табучи, Кинья (1968). Компьютерная программа для оптимальной разводки разъемов печатных плат. IFIPS Ход работы. H47. С. 1745–1478.
  7. ^ Хайтауэр, Дэвид У. (1969). "Решение линейной трассировки на непрерывной плоскости ". DAC'69: Материалы 6-й ежегодной конференции по автоматизации проектирования. ACM Press. С. 1–24. (NB. Это одно из первых описаний «маршрутизатора линейного пробника».)
  8. ^ а б c d Мингес, Меррилл Л. (1989). Справочник по электронным материалам: упаковка. 1. ASM International. ISBN  978-0-87170-285-2. Получено 2017-09-27.
  9. ^ Рид, Джеймс Б.; Сангиованни-Винчентелли, Альберто; Сантамауро, Мауро (1985). «Новый маршрутизатор символьных каналов: YACR2». IEEE Transactions по автоматизированному проектированию интегральных схем и систем. 4 (3): 203–219. Дои:10.1109 / TCAD.1985.1270117. [1]
  10. ^ а б c Шанкар, Рави; Фернандес, Эдуардо Б. (12 января 2014 г.). Эйнспрух, Норман Г. (ред.). СБИС и компьютерная архитектура. Наука о микроструктуре электроники СБИС. 20. Академическая пресса. ISBN  978-1-48321784-0. Получено 2018-10-22.
  11. ^ "Воспоминания о маршрутизации каналов".
  12. ^ Финч, Алан С .; Маккензи, Кен Дж .; Balsdon, G.J .; Симондс, Г. (23.06.1985). Метод бессеточной маршрутизации печатных плат (PDF). 22-я конференция ACM / IEEE по автоматизации проектирования, Лас-Вегас, Невада, США. Конференция по автоматизации проектирования, 2009. Dac '09. 46Th Acm / IEEE. Ньютаун, Тьюксбери, Глостершир, Великобритания: Racal-Redac Ltd. С. 509–515. Дои:10.1109 / DAC.1985.1585990. ISBN  0-8186-0635-5. ISSN  0738-100X. В архиве (PDF) из оригинала от 22.10.2018. Получено 2018-10-22.
  13. ^ Уэбб, Даррелл (2012-12-20). "Посвящение Алану Финчу, отцу автономной маршрутизации". В архиве из оригинала от 22.10.2018. Получено 2018-10-22.
  14. ^ Ву, Бо (апрель 1992 г.). Алгоритмы маршрутизации на основе теории графов (PDF) (Тезис). Университет Западного Мичигана. В архиве (PDF) из оригинала от 22.10.2018. Получено 2018-10-22.
  15. ^ "Computer-Partner Kiel GmbH:" Ищейка "entflechtet Leiterplatten auf 16 Lagen". Computerwoche (на немецком). 1992-03-13. В архиве из оригинала от 21.10.2018. Получено 2018-10-20.
  16. ^ Пфейл, Чарльз (2017-11-02). «Разработка печатных плат на весь срок службы: от дизайна к программному обеспечению». Сеть EDN. В архиве из оригинала от 21.10.2018. Получено 2018-10-20.
  17. ^ а б Редлих, Детлеф. «1.6. Rechnergestützter Leiterplattenentwurf - Entflechtung» (PDF). Schaltungsdesign (на немецком). Ernst-Abbe-Hochschule Jena (EAH). Архивировано из оригинал (PDF) на 2018-10-21. Получено 2018-10-20.
  18. ^ «Simplify Design Automation - новое поколение методологии проектирования».
  19. ^ Соукуп, Иржи (1979). «Глобальный маршрутизатор». Материалы 16-й конференции по автоматизации проектирования.. Сан-Диего, Калифорния, США: IEEE Press. С. 481–489.
  20. ^ Рубин, Франк (1974). «Итерационный метод печатной разводки проводов». Труды 11-го семинара по автоматизации проектирования. С. 308–13.
  21. ^ Линскер, Ральф (1984). «Система прокладки проводов, управляемая функцией штрафов итеративным улучшением» (PDF). Журнал исследований и разработок IBM. 28 (5): 613–624. Дои:10.1147 / rd.285.0613.

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

  • Scheffer, Louis K .; Лаваньо, Лучано; Мартин, Грант (2006). "Глава 8: Маршрутизация". Справочник по автоматизации проектирования электроники для интегральных схем. II. Бока-Ратон, Флорида, США: CRC Press / Тейлор и Фрэнсис. ISBN  978-0-8493-3096-4.

внешняя ссылка