Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

Типы роутеров [ править ]

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

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

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

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

Как работают роутеры [ править ]

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

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

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

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

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

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

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

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

См. Также [ править ]

  • Автоматизация электронного проектирования
  • Расчетный поток (EDA)
  • Дизайн интегральной схемы
  • Место и маршрут

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

  • Scheffer, Louis K .; Лаваньо, Лучано; Мартин, Грант (2006). «Глава 8: Маршрутизация ». Справочник по автоматизации проектирования электроники для интегральных схем . 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