ОЧЕРЕДНОСТЬ ПРОКЛАДКИ СОЕДИНЕНИЙ ПЕЧАТНЫХ ПЛАТ

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

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

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

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

Рисунок 1. Различные порядки трассировки

Вопрос об эффективности различных методов упорядочения остается дискуссионным. В работе [9] дана статистическая обработка результатов трассировки для двухслойной печатной платы, выполненной при использова­нии различных тактик упорядочения, основанных на длине соединений. В качестве критерия сравнения принята сумма идеальных длин успешно завершенных соединений.

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

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

Рисунок 2. Метод прямоугольника

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

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

,

где L - полупериметр минимального прямоугольника, содержащего выводы цепи; n - количество выводов. Приоритет отдается цепям с меньшей оценкой l.

Основной недостаток всех указанных выше методов состоит в том, что упорядочение выполняется до начала трассировки. Более перспективными являются динамические методы очередности прокладки соединений. Сущность этих методов заключается в следующем. Вначале присваивается некоторая оценка и первым трассируется соединение с "наилучшей" оценкой. Затем производится пересчет оценок и процесс продолжается.

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

Список литературы:

1. Абрайтис Л.Б. Определение конфигураций соединительных деревьев ком­плексов с распределением коммутаций по слоям // Вычислительная техника.- Каунас: Каунас, политехи, ин-т, 1971,- Т.П.- С. 162 - 169.
2. Абрайтис Л.Б. Система автоматизированного монтажно-коммутационного проектирования ячеек цифровых устройств // Вычислительная техника.- Каунас: Каунас, политехи, ин-т, 1972,- Т. III.- С. 230 - 233.
3. Андреев Г.Ю., Петухов Г.А., Скородубский В.Н. Компенсирующий алгоритм поиска малоповоротных путей // Вычислительная техника. - Каунас: Каунас, политехи, ин-т, 1972,- T.III.- С. 380 - 386.
4. Бахтин Б.И. Автоматизация в проектировании и производстве печатных плат радиоэлектронной аппаратуры,- Л.: Энергия, Ленингр. отд-ние, 1979.­120 с.
5. Малышева И.И., Розанов В.А., Юрин О.Н. Автоматизация технического проектирования многослойных печатных плат // Вопросы радиоэлектрони­ки. Сер. VII.- Электронная вычислительная техника,- 1972,- Вып. 3,- С. 115 - 118.
6. Матицкас К.Л. Алгоритм определения дерева оптимальной длины с ограничением степени его вершин // Вычислительная техника,- Каунас: Каунас, политехи, ин-т, 1971,- Т.П.- С. 121 - 131.
7. Петухов Г.А. и др. Алгоритмические методы конструкторского проектиро­вания узлов с печатным монтажом / Г.А. Петухов, Г.Г. Смолич, Б.И. Юлин,- М.: Радио и связь, 1987,- 152 с.
8. Построение современных систем автоматизированного проектирования / К.Д. Жук, A.A. Тимченко, A.A. Родионов и др.- Киев: Навукова думка, 1983.-248 с.
9. Abel C.L. On the ordering of connection for automatic wire routing // IEEE Trans.- 1972,- V. C-21, № 11,- P. 1227 - 1233.