Маршрутизация (автоматизация электронного проектирования)
В электронном дизайне разводка проводов , обычно называемая просто разводкой , представляет собой этап проектирования печатных плат (PCB) и интегральных схем (IC). Он основывается на предыдущем шаге, называемом размещением , который определяет расположение каждого активного элемента ИС или компонента на печатной плате. После размещения на этапе трассировки добавляются провода, необходимые для правильного соединения размещенных компонентов с соблюдением всех правил проектирования ИС. Вместе этапы размещения и маршрутизации при проектировании ИС известны как место и маршрут .
Задача всех маршрутизаторов одинакова. Им даются несколько ранее существовавших полигонов, состоящих из контактов (также называемых клеммами) на ячейках, и, возможно, некоторые ранее существовавшие соединения, называемые предварительными маршрутами. Каждый из этих полигонов связан с сетью , обычно по имени или номеру. Основная задача маршрутизатора состоит в том, чтобы создать такую геометрию, чтобы все терминалы, назначенные одной сети, были соединены, терминалы, назначенные разным сетям, не были соединены, и чтобы соблюдались все правила проектирования. Маршрутизатор может выйти из строя, не подключив терминалы, которые должны быть подключены (обрыв), по ошибке подключив два терминала, которые не должны быть подключены (короткое замыкание), или создав нарушение правил проектирования. Кроме того, чтобы правильно соединить сети, можно ожидать, что маршрутизаторы будут следить за тем, чтобы конструкция соответствовала времени, не имелапроблемы с перекрестными помехами , соответствует всем требованиям по плотности металла, не страдает от антенных эффектов и т.д. Этот длинный список часто противоречащих друг другу целей делает маршрутизацию чрезвычайно сложной.
Известно, что почти каждая проблема, связанная с маршрутизацией, неразрешима . Простейшая задача маршрутизации, называемая задачей дерева Штейнера , о поиске кратчайшего маршрута для одной сети в одном слое без препятствий и правил проектирования является NP-сложной , если разрешены все углы, и NP-полной , если разрешены только горизонтальные и вертикальные провода. . Также было показано, что варианты маршрутизации каналов являются NP-полными, а также маршрутизация, которая уменьшает перекрестные помехи , количество переходных отверстий и т. д. Поэтому маршрутизаторы редко пытаются найти оптимальный результат. Вместо этого почти вся маршрутизация основана на эвристике , которая пытается найти достаточно хорошее решение.
Правила проектирования иногда значительно различаются от слоя к слою. Например, допустимая ширина и интервал на нижних слоях могут быть в четыре или более раз меньше разрешенной ширины и интервала на верхних слоях. Это вносит много дополнительных сложностей, с которыми не сталкиваются маршрутизаторы для других приложений, таких как печатная плата или конструкция многокристального модуля . Особые трудности возникают, если правила не являются простыми кратными друг другу, и когда переходные отверстия должны проходить между слоями с разными правилами.
Самые ранние типы маршрутизаторов EDA были «маршрутизаторами с ручным управлением» - разработчик щелкал мышью по конечной точке каждого линейного сегмента каждой сети. Современное программное обеспечение для проектирования печатных плат обычно предоставляет «интерактивные маршрутизаторы» - чертежник выбирает контактную площадку и щелкает несколько мест, чтобы дать инструменту EDA представление о том, куда идти, и инструмент EDA пытается разместить провода как можно ближе к этому пути, не нарушая проверка правил проектирования(ДРК). Некоторые более продвинутые интерактивные маршрутизаторы имеют функции «толкать и толкать» (также известные как «отталкивание» или «автоматическое перемещение») в интерактивном маршрутизаторе; инструмент EDA отталкивает другие цепи, если это возможно, чтобы разместить новый провод там, где этого хочет разработчик, и при этом избежать нарушения DRC. Современное программное обеспечение для проектирования печатных плат также обычно предоставляет «автотрассировщики», которые маршрутизируют все оставшиеся неразведенные соединения без вмешательства человека.
