Методы и алгоритмы трассировки соединения для ДПП

30. Методы и  алгоритмы трассировки соединения  для ДПП.

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

   Однако дальнейшее распространение ДПП в разработках и производстве РЭА автоматизированными методами тормозится серьезными трудностями, связанными с автоматизацией проектных работ ио 100%-ной трассировке пе­чатных проводников. Практически все современные алгоритмы ие обеспечивают детерминированного синтеза необходимых соединений в схеме, топология которых удовлетворяет задаваемым кон- структорско-технологичеоким ограничениям. Это определяется спецификой конструкций ДПП. Задача трассировки решается на объемной модели, т. е. с допущением перехода проводников с одного слоя на другой в любом незаня­том участке конструкции ( путем создания дополнительных сквозных металлизированных отверстий). Такое допуще­ние существенным образом увеличивает размерность решаемой задачи 100%-ной трассировки. Синтез электрических соединений выполняется на фиксированных ресурсах монтажного пространства (разрешены только два слоя для трассировки). Номенклатура электрических схем, реализуемых на конструкциях ДПП, включает как цифровые, так и аналоговые схемы, что существенно расширяет множество вариантов их конструктивного исполнения — от регулярных структур размещения одвогабаригных корпусов до нерегулярных структур с исполь­зованием элементов произвольной формы. И, наконец, насыщенность конструкций ДПП радиоэлектронными элемен­тами непрерывно возрастает. Вое это существенно усложняет разработку формальных методов гарантированной 100%-ной трассировки ДПП в автоматическом режиме.

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

   Главной задачей, решаемой ори автоматизации процесса прокладки печатных проводников в ДПП, является раз­работка подходов, методов и алгооит- мов трассировки, обеспечивающих 100%-ную разводку заданных цепей ав­томатическим способом. Наибольшее распространение в практике автоматической трассировки ДПП получил подход, основу которого составляет комплексное решение следующей совокупности подзадач:

определение порядка трассировки цепей и структуры соединений в каждой Цепи, трассировка соединений.

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

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

fY

8

7

   Рассмотрим структуры электрических соединений в каждой цепи с учетом требования о минимизации числа ис­пользуемых сквозных переходов. Сформулируем задачу: требуется реализовать электрические соединения между контактами цепи, множество которых {Xjt/j}(/ = 1, 2, 3       п) представляется тремя

подмножествами: контактов первого слоя {XiWytW} (i=il, 2, 3        т), контактов второго СЛОЯ {*ft(2>(/ft((2>} (£ = = 1, 2, 3, .., I) и сквозных контактов lxtwyim). Справедливо соотношение m+l+t=n. Результирующая топология электрических соединений должна иметь минимальную суммарную длину с минимумом сквозных переходов. Очевидно, что получаемая структура электрических соединений определяется порядком трассировки контактов цепи при организации их попарного соединения.

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

6 5 А 3 2 -t

Pij = Ixj—xtl \yj—yi\ +0(йг, kj),

где (Xiyi) н (ха-г/з) — координаты пары контактов,

О, еслн номера слоев контактов ki н kj совпадают, либо одии из G (kt kj) = ннх сквозной,

So в противном случае («о — площадь одного слоя ДПП).

Алгоритм Прима.

Шаг 0. Инициализация. Помечаем все вершины графа как «невыбранные». Выбираем произвольную вершину и поме­чаем ее как «выбранную».

Шаг I. Цикл. Выполнение цикла до тех пор, пока все вершины графа не будут помечены как «выбранные». Выбрать ребро минимального веса, соединяющее вершину (U) из множества «выбранных» и вершину (V) множества «невыбранных». Выбранную вершину (V) пометить как «выбранную», соединяющее ребро между U н V включить в состав формируемого дерева. Продолжить выполнение цикла. 

   Топология дерева соединений, полученного алгоритмом Прима (таблица ребер дерева (hshe), (fesfes), (heh7), (hehl3), (h9h,), (h3h2), (feaA4), (ft3fti), суммарная длина ребер планируемого дерева 25 дискрет)

Цепь соединений. Задача о построении кратчайшей (или оптимальной) цепи, соединяющей множество заданных п контактов, эквивалентна задаче, известной в литературе как задача коммивояжера [48], который желает посетить п городов, начиная с некоторого, побывать в каждом городе по одному разу и прн этом выбрать путь минимальной протяженности из всех имеющихся. Аналогично задача формулируется и прн трассировке п контактов.

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

Удачный эвристический алгоритм решения задачи коммивояжера прн трассировке п контактов предложен . Приведем данный алгоритм.

Шаг 0. Выбрать произвольную вершину (и) в графе возможных соединений. Пометить ее как «выбранную».

Шаг I. Выполнить следующий цикл операций до тех пор, пока все вершины не будут помечены как «выбранные». Для выбранной вершины и выбрать смежную (К), имеющую соединяющее

ребро с минимальной весовой характеристикой. Пометить вершину V как «выбранную». Определить в качестве вершины и вершину V. Соединяющее ребро включить в состав формируемой цепи.

  Построение связывающей цепи *-го места сквозных переходов (порядок построения цепи: hah,, hgh,, kskt, ktk3, кгкг, k2ku Ь|йб, Ьбй7, L =32)

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

Сеть электрических соединений. Третьим видом топологии связывающих соединений для п контактов одной цепи является модель сети [60]. Задача формулируется так: необходимо соединить заданную группу из п контактов сетью соединений минимальной длины. Допускается пополнение множества нз п• контактов новыми, по мере необходимости.

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

электрических соединений, авторы избрали несколько иной путь. Построение сети выполняется в процессе реальной траосировки цепи. Суть метода заключается /в следующем: из неупорядоченного множества контактов цепн {Xjt/j} выбирается тот (xj, yj), который наиболее близко расположен к «центру тяжести» контактов:

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

   Построение связывающей сети (Г, s"=35 дискрет; *ц т<=>5.1; </цтет4.3; hs — ближайший к «центру тяжести»)

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

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

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

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

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

Переход волны с одного слоя на другой выполняется при одновременном выполнении следующих двух условий :

а) в месте перехода волиы (x<i/i) дискреты обоих слоев должны быть свободны для трассировки одновременно;

б) множества дискретов {xiyj} обоих слоев, расположенных на модели не далее чем на величину б от дискрета, в котором выполняется переход волны, должны быть также свободны для трассировки *.

Значение б рассчитывается в соответствии с выражением 5=CEIL[0,5X X [CEIL (d/k)—1 ] ], где d — значение диаметра металлизации сквозных переходов, мм; k — шаг сетки трассировки,

• Расчет величины расстояния между парой дискретов    и (xjVj) здесь выполняется

ио формуле: МАХ((*3—х()(у~ 1/()) независимо от их расположения на слоях.

мм; СЕ1Ь(х)=Л, А — целое число, большее либо равное аргументу х.

При трассировке ДПП целесообразно включение в процесс распространения волны системы «штрафных» функций за перемещение по слою в непрноритетном направлении, переход со слоя на слой н некоторые другие. Реализация «штрафов», как правило, осуществляется путем включения задержек при дальнейшем распространении волны в указанных участках волнового фронта. Варьирование величин задержек н удачный выбор нх значений позволяют повлиять (хотя н несущественно) на конечный результат трассировки. Интересная модификация волнового алгоритма предложена [52]. Суть модификаций сводится к следующему. Процесс трассировки реа­лизуется, например, в пять нтерацнй. На первой из них выполняется обработка всего списка трассируемых цепей средствами волнового алгоритма. Особенностью итерации является то, что на модели поля остается только 20% общей длины соединений каждой цепи («хвосты»). На второй итерации выполняется повторная обработка списка трассируемых цепей. При трассировке очередной цепн ее «хвосты» удаляются с модели поля, выполняется повторная трассировка контактов. На модели поля остаются «хвосты» с суммарной длиной 40% от общей длины соединений в цепн. В результате выполнения последующих итераций обработки списка трассируемых цепей «хвосты» цепей будут растн следующим образом: 60, 80 и на последней 100%. Такой подход позволяет уменьшить число блокируемых контактов н тем самым повысить процент разводимых цепей в ДПП.