Алгоритмы трассировки печатных плат РЭС

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

1) минимальная суммарная длина соединений;

2) минимальное число соединений, длина которых превышает заданное значение;

3) минимальное число переходов между слоями;

4) минимальное число слоев;

5) минимальные паразитные помехи;

6) максимальная удаленность трасс соединений;

7) число слоев не должно превышать заданного значения;

8) длина соединения не должна превышать заданного значения;

9) уровень помех, наводимых в каждой трассе, не должен превышать допустимого значения;

10) число соединений (паек) к одному выводу не должно превышать заданного значения.

При проектировании многослойных структур, как правило, отдельно решается задача оптимального расслоения, в которой минимизируется показатель

(1)

где г - номер слоя; z - число слоев; М - число цепей в схеме; - характери­стика степени пересечения k-й и s-й трасс;

если трассы к и s не принадлежат слою r;

если трассы к и s принадлежат слою r.

Характеристика задается различными величинами, например: пло­щадью перекрытия зон реализации цепей аr и as; числом пересечений полных подграфов цепей аr и as; числом пересечений минимальных связывающих сетей аr и as; числом выводов цепей аr и as, принадлежащих пересечению зон реализации этих цепей.

В общей проблеме автоматизации конструкторского проектирования трассировка соединений - это наиболее трудная задача, в которой прослеживается особенно тесная связь с конструктивно-технологической реализацией. Исходной информацией задачи трассировки в общем случае являются:

1) список цепей проектируемой схемы;

2) параметры конструкций элементов (форма и геометрические размеры);

3) параметры монтажного пространства (допустимые расстояния, форма соединений, число пересечений и т.п.);

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

Задача трассировки имеет метрический и топологический аспекты. Метрический аспект связан с учетом конструктивных размеров элементов, соединений и монтажного пространства (размещения). Топологический аспект связан с учетом ограничений на число допустимых пересечений, число слоев схемы и т.д., т.е. связан с пространственным расположением отдельных частей и соединений схемы. Алгоритмические методы трассировки, несмотря на их многообразие, не гарантируют проведения 100% соединений. По способу построения трасс методы трассировки разделяют на конструктивные и итерационные.

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

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

Для решения задач трассировки разработаны также алгоритмы, в которых объединены последовательные и итерационные процедуры - “мешающие” трассы деформируются или удаляются, т.е. изменяется конфигурация уже проложенных соединений или очередность прокладки трасс.

На рис.1 приведена последовательность применения методов трассировки к различным типам схем и используемые алгоритмы.

Рис. 1. Последовательность применения методов трассировки к различным типам схем и используемые алгоритмы: а - схемы регулярные, многослойные, из однотипных элементов (печатный монтаж или многослойные ИС и БИС); б - схемы нерегулярные, из разнотипных элементов (однослойный монтаж на печатных платах, гибридные ИС)

Примеры алгоритмов трассировки

Большинство известных универсальных алгоритмов трассировки осно­вывается на волновом алгоритме определения пути (трассы соединений эле­ментов), минимизирующем некоторую многомерную функцию качества этого пути. Идея волнового алгоритма иллюстрируется на рис. 2, где соединяются элементы А и В, расположенные в точках (1, 4) и (4, 7) регулярного монтажного пространства.

Рис. 2. Трассировка соединений волнового алгоритма при наличии препятствий

Цифрами 0, 1, 2, ..., 14 показаны “фронты” распространения волны от точки (1,4) - состояние 0, до тех пор пока она не достигается точки (4, 7) - состояние 14. Оптимальная трасса получается соединением точек в обратной последовательности 14-13-...-1-0, как трасса, имеющая минимальную длину, минимальное число изгибов и обеспечивающая максимальную плотность монтажа. Штрихами показаны трассы, имеющие ту же длину, но худшие по остальным критериям. Модификации волнового алгоритма направлены на повышение быстродействия и уменьшение требуемого объема памяти.

Трассировка с использованием другого эвристического алгоритма - лучевого - показана на рис. 3. Между соединяемыми точками А (6, 3) и В (5, 8) проводится луч. При переходе к следующей точке монтажного пространства определяется направление трассы, минимально отличающейся от направления луча с учетом указанного на диаграмме приоритета (нумерация направлений) и необходимости обхода препятствий, образованных занятыми позициями.

Рис. 3. Трассировка соединений лучевым алгоритмом при наличии препятствий

Штриховой линией отмечен оптимальный путь (его длина в два раза меньше первого), проложенный при проведении луча от В к А, т.е. в обратном направлении.

Следует отметить, что приведенные при рассмотрении постановки задачи трассировки критерии оптимальности вводятся не для управления процессом трассировки, а лишь для оценки качества полученного решения.

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

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

Рис. 4. Трассировка соединений с использованием каналов

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

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

Следует отметить, что при использовании САПР время проектирования топологии устройств, содержащих 20 ... 30 ИС, сокращается приблизительно на порядок, а для БИС практически нет другого способа достижения высокого качества проекта и его документации. Однако большим недостатком современных систем автоматизированного конструкторского проектирования является необходимость огромного объема исходной информации, которая может готовиться порядка нескольких недель для БИС с уже разработанной логической схемой. Для преодоления этого недостатка необходимы создание САПР, соединяющих все этапы проектирования РЭА и имеющих интегрированную базу данных, содержащую инвариантную информацию, пополняемую в процессе разработки, а также стандартизация наиболее рациональных схемотехнических и конструктивных решений.

1.