7.7. Программа автоматической трассировки specctra

Рассмотренные алгоритмы имеют общей чертой наличие координатной сетки. Принципиально отличными от них являются бессеточные алгоритмы программы SPECCTRA.

SPECCTRA — коммерческая программа автоматической трассировки печатных плат от компании Cadence Design Systems. Современное название Allegro PCB Router. SPECCTRA успешно трассирует платы большой сложности благодаря применению нового принципа представления графических данных — так называемой ShapeBased-технологии. В отличие от известных ранее пакетов, в которых графические объекты представлены в виде набора точек-координат, в этой программе используются более компактные способы их математического описания. За счёт этого повышается эффективность трассировки печатных плат с высокой плотностью расположения компонентов, обеспечивается автоматическая трассировка одной и той же цепи трассами разной ширины и др.

SPECCTRA использует адаптивные алгоритмы, реализуемые за несколько проходов трассировки. На первом проходе выполняется соединение абсолютно всех проводников без обращения внимания на возможные конфликты, заключающиеся в пересечении проводников на одном слое и нарушении зазоров. На каждом последующем проходе автотрассировщик пытается уменьшить количество конфликтов, разрывая и вновь прокладывая связи (метод ripup-and-retry) и проталкивая проводники, раздвигая соседние (метод push-and-shove).

Программа совместима с большинством современных систем проектирования печатных плат, благодаря использованию стандартного промышленного формата DSN для описания проектов и Do-файлов для задания стратегии трассировки.

В заключении необходимо отметить следующее:

1. Ни один алгоритм трассировки не гарантирует 100% трассировку, поэтому необходимо предусмотреть доработку топологии. В связи с этим, алгоритмы трассировки не обязательно должны обеспечивать максимальное число разведенных соединений, но, главное, достаточно простую конфигурацию трасс.

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

8. Графо-теоретический подход к синтезу топологии

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

Графо-теоретический подход к синтезу топологии состоит из следующих этапов.

1. Построение графовой модели схемы.

2. Анализ планарности графа.

3. Планаризация графа.

4. Реализация непланарных соединений.

5. Построение плоского чертежа схемы.

6. Синтез геометрии схемы.

Одной из основных топологических задач проектирования коммутации является возможность разложения соединений на плоскости без пересечений. Эта задача связана с определением планарности графа. Среди критериев планарности графа наиболее известен критерий Понтрягина-Куратовского (Kazimierz Kuratowski):

Граф G(X, U) – планарен тогда и только тогда, когда он не содержит подграфов гомеоморфных полному графу K₅ или полному двудольному графу K_3,3.

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

Критерий Бадера (W. Bader). Граф G(X,U) планарен, если его граф пересечений G^' является бихроматическим (двудольным) графом. Критерий справедлив для графов, имеющих гамильтонов цикл.