АЛГОРИТМ МИНИМИЗАЦИИ КОЛИЧЕСТВА ПЕРЕХОДНЫХ ОТВЕРСТИЙ В ПЕЧАТНЫХ ПЛАТАХ
Изложен подход к минимизации числа переходных отверстий в печатных платах, основанный на теории максимальных паросочетаний в графах. Приводятся сведения о практической реализации подхода. Рис. 3, Ист. 5.
В настоящее время математические методы оптимизации широко применяются для решения задач автоматизации конструкторского проектирования. Многие проблемы автоматизации конструкторского проектирования можно решить путём сведения к задачам линейного целочисленного программирования, и в частности к сетевым задачам, которые имеют степенную оценку трудоёмкости решения. Известны эвристические решения задачи размещения межслойных переходов [1, 2]. В отличие от них в данной работе исследуются точные методы, позволяющие получить минимум числа переходных отверстий при заданном эскизе совмещённой трассировки.
Содержательно задача ставится следующим образом. Пусть имеется эскиз трассировки, выполненный условно в одном слое и содержащий пересечения цепей. Необходимо разместить межслойные переходы на цепях без изменения конфигурации цепей, которые должны располагаться в двух слоях без пересечений, а число межслойных переходов должно быть минимальным. Обычно при трассировке эти требования дополняются ещё условиями, ограничивающими места расположения межслойных переходов.
Рассмотрим формальную постановку задачи. Пусть задан плоский неориентированный мультиграф. На его рёбрах определим разбиение на два класса: рёбра, разрешенные для межслойных переходов, и рёбра, запрещённые для межслойных переходов. Определим на рёбрах разбиение на рёбра одной цепи, которое должно быть таким, чтобы рёбра каждого подмножества являлись связными. Каждое из этих подмножеств назовём цепью. Это понятие эквивалентно понятию «цепь» в эскизе трассировки.
Указанный мультиграф (вместе с определёнными рёберными разбиениями) будем называть графом двухслойной трассировки, если все кратные рёбра запрещены для межслойных переходов и каждой вершине инцидентны рёбра, принадлежащие не более чем двум цепям. На графе трассировки, следуя [3], определим понятие границы грани, т.е. связного множества рёбер, ограничивающих грань.
Для рассматриваемого метода размещения межслойных переходов важным понятием является чётность числа переходов с цепи на цепь на границе. Будем говорить, что в границе произошел переход с цепи на цепь, если два смежных ребра границы принадлежат разным цепям графа, и что граница грани чётна, если она имеет чётное число переходов с цепи на цепь, и нечётна в противном случае.
Сформулируем следующую теорему. Цепи графа трассировки размещаются в двух слоях без пересечений тогда и только тогда, когда все границы граней в графе чётны. Доказательство следует из анализа чётных и нечётных границ графа трассировки.
Рассмотрим трассировку в двух слоях с межслойными переходами вне узловых точек цепей. К межслойному переходу цепь может подходить в одном слое или в разных слоях. Иначе говоря, каждый такой межслойный переход разрезает цепь на две части. На графе трассировки такие межслойные переходы эквивалентны разрезу ребра и слиянию двух прилежащих к нему границ. При слиянии двух границ суммарное число их переходов с цепи на цепи равно числу переходов в результирующей границе. Таким образом, для размещения цепей в двух слоях без пересечений необходимо ввести такие разрезы рёбер графа, чтобы все полученные границы стали чётными. Разрежем рёбра графа трассировки так, чтобы получить одну границу; согласно теореме эта граница чётна. Следовательно, в любом графе будет чётное число нечётных границ.
Разобьем вершины графа трассировки на два подмножества: узлы и пересечения. Вершину графа назовём узлом, если ей инцидентны рёбра одной цепи; в противном случае она называется пересечением. Эти понятия эквивалентны понятиям «узел» и «пересечение» в эскизе трассировки. Для графа трассировки построим двойственный граф, для чего сопоставим каждой границе грани вершину двойственного графа. Для каждого ребра графа трассировки определим пару границ, в которых оно содержится, и соединим ребром соответствующую пару вершин двойственного графа. Вершины этого графа будем называть чётными или нечётными в зависимости от чётности соответствующей границы грани в графе трассировки.
Общая задача минимизации числа межслойных переходов рассмотрена в [4]. Там же показано, что в общем случае она приводится к задаче линейного целочисленного программирования, которая весьма трудоёмка.
Оригинальность подхода, предлагаемого в [4] состоит в том, что вначале определяется набор разрезов цепей на графе трассировки, то есть набор межслойных переходов, а только потом устанавливается, какой фрагмент цепи окажется в первом, а какой во втором слое.
Там же в [4] приводится частный случай задачи минимизации, когда минимизируется число разрезов в цепи. Этот частный случай соответствует ортогональной трассировке, когда число разветвлений цепи на 4 направления невелико.
Тогда, как показано в [4], задача минимизации числа межслойных переходов может быть решена путём построения минимального взвешенного паросочетания.
Формально, эта задача формулируется следующим образом. Пусть не допускается проведение отрезков цепи в двух слоях друг под другом, все узлы принадлежат произвольному слою, и пусть локальная степень узлов не выше трёх. Тогда задача минимизации числа межслойных переходов эквивалентна задаче минимизации числа разрезов. В свою очередь, эта задача эквивалентна построению минимального дополнения графа до эйлерова и сводится к построению минимального взвешенного паросочетания на матрице кратчайших расстояний исходного графа [3, 5].Полученная система кратчайших расстояний определяет совокупность рёбер, которые реализуют эти расстояния в двойственном графе. Эта совокупность рёбер однозначно соответствует системе разрезов на графе трассировки.
Фактически, в данном случае речь идёт о построении рёберного покрытия двойственного графа, в котором число рёбер покрытия, инцидентных вершине отнесённой к чётным – чётно, а к нечётным – нечётно. При этом суммарный вес рёбер покрытия должен быть минимальным.
Кроме подхода, предложенного в [4], для решения данной задачи можно предложить прямое сведение данной задачи к задаче о минимальном взвешенном паросочетании.
Для этого, предлагается построить модельный граф. В нём нужно каждую вершину исходного двойственного графа, заменить полным подграфом, число вершин которого равно числу рёбер, инцидентных этой вершине в двойственном графе, если чётность числа таких рёбер совпадает с группой чётности вершины двойственного графа, иначе оно больше этого числа на единицу. Таким образом, чётность числа вершин каждого подграфа, будет совпадать с чётностью вершины исходного графа.
Каждое ребро двойственного графа соответствует ребру модельного графа, которое соединяется ровно с одной вершиной каждого из двух подграфов. Рёбра внутри подграфа соединяют каждую вершину подграфа с каждой другой в подграфе. Внутренние рёбра получают вес равный нулю, а остальные рёбра – сохраняют прежний вес (как правило, равный 1). Так как в максимальном паросочетании минимального веса для такого графа, суммарный вес рёбер с ненулевым весом будет таким же, как в задачи о покрытии, то задача о покрытии – эквивалентна задаче о парасочетании на модельном графе.
Очевидно, что каждому подграфу будет инцидентно чётное или нечётное число рёбер с ненулевым весом, в зависимости от того, к какому классу, чётных или нечётных была отнесена вершина двойственного графа. Все остальные вершины каждого подграфа можно будет покрыть рёбрами с нулевым весом.
Итак, рёбра с ненулевым весом в модельном графе можно интерпретировать как рёбра искомого покрытия.
Естественно, польза от такого сведения будет только в том случае, если встроить работу с подграфами прямо в алгоритм построения паросочетания, что и предлагается автором.
Задача построения соответствующего паросочетания является достаточно трудоёмкой, несмотря на то, что рёбра, как правило, имеют всего 2 варианта веса, 0 или 1. Эта задача может быть реально решена только для сравнительно небольшого числа вершин (несколько тысяч).
Поэтому в качестве альтернативы предлагается приближенный алгоритм, основанный на идеях алгоритма Форда для ориентированных графов, который работает непосредственно с двойственным графом.
Рассмотрим двойственный граф с весами на рёбрах. Вначале все рёбра графа вне покрытия. Рёбра, которые отнесены к покрытию, будем учитывать, изменяя знак их веса. Построим для нечётной вершины дерево кратчайших путей в соответствии с алгоритмом Форда, запрещая переходы по дереву непосредственно в ту вершину, откуда осуществлён переход. Если в процессе построения дерева будут возникать циклы с отрицательным весом, то в этом цикле поменяем все рёбра покрытия на рёбра вне покрытия и наоборот, естественно, изменяя знак у веса рёбер цикла. После чего старое дерево разрушаем и переходим к построению нового дерева с корнем в прежней вершине.
Когда дерево построено, то выбираем вершину с минимальным весом в выбранном пути, причём для вершин чётных знак у веса должен быть отрицательным, а для нечётных – любой. В этом пути также поменяем все рёбра покрытия на рёбра вне покрытия и наоборот, также меняя знак у весов рёбер. После этого меняем чётность у крайних вершин пути. Если использовался путь в чётную вершину, то она должна быть выбрана как очередная нечётная вершина для построения следующего дерева.
Когда все вершины дерева станут чётными, то, аналогично строим деревья из каждой вершины, однако для улучшения покрытия используются только циклы с отрицательной длиной пути. Если после построения деревьев для всех вершин окажется, что не было циклов с отрицательным суммарным весом, то алгоритм завершается.
Апробация функционирования предложенного алгоритма произведена с помощью среды визуального программирования Delphi на языке Pascal.
Рис. 1. Совмещённая трассировка
Покажем применение метода на примере. На рис. 1 изображён граф, отображающий совмещённый эскиз трассировки. Для построения паросочетания формируется следующий двойственный граф, представленный в списочной форме, где первый элемент – это граница грани, а в списке указаны номера смежных границ. Вес любого разреза считается равным 1. Тип вершины указывается в скобках 0 – чётная, 1 – нечётная.
(1) 1 -> 21
(0) 2 -> 3,21
(0) 3 -> 2,4,7,21
(0) 4 -> 3,5,8,21
(0) 5 -> 4,7,9
(1) 6 -> 8,10,21
(0) 7 -> 3,5,9,11,21
(1) 8 -> 4,6,9,12
(1) 9 -> 5,7,8,13
(0) 10 -> 6,12,15,21
(1) 11 -> 7,13,21
(0) 12 -> 8,10,13,15,19
(0) 13 -> 9,11,12,14,16,21
(1) 14 -> 13,17,21
(0) 15 -> 10,12,18,19,21
(1) 16 -> 13,17,19
(0) 17 -> 14,16,20,21
(1) 18 -> 15,21
(1) 19 -> 12,15,16,20,21
(1) 20 -> 17,19,21
(1) 21 -> 1,2,3,4,6,7,10,11,13,14,15,17,18,19,21
После решения задачи о покрытии, оказалось, что в покрытие входят рёбра (1,21), (2,21), (21,6), (9,13), (13,11), (12,19), (19,16), (14,21), (21,18), (19,20). Эти рёбра на рис. 2 интерпретируются как межслойные переходы между соответствующими границами граней. В итоге получено минимальное число межслойных переходов для данного графа трассировки, которое равно количеству рёбер покрытия, т.е. 10.
Рис. 2. Трассировка первого слоя
Рис. 3. Трассировка второго слоя
В заключение отметим, что предлагаемые подходы позволяют эффективно решать задачу о минимизации числа межслойных переходов для очень больших печатных плат практически без потери точности. А при небольших размерах печатных плат, - задача может быть решена точным образом. Предлагаемые подходы можно практически использовать в существующих системах автоматизации проектирования печатного монтажа.
Список литературы:
1. Каплан А. В. Алгоритм уменьшения числа межслойных переходов в печатных платах. – «Вычислительная техника», т. IV (материалы конференции «Автоматизация технического проектирования», - Каунас, 1973), – с. 126-131.
2. Абрайтис Л. В., Каплан А. В., Ришкус А. В. Исследование алгоритма минимизации числа межслойных переходов печатных плат. – «Вычислительная техника», т. VIII (материалы конференции «Автоматизация технического проектирования», - Каунас, 1976). – с. 143-146.
3. Зыков А. А. Теория конечных графов. Новосибирск, - Наука, 1969. - 544 с.
4. Курейчик В. М., Королёв А. Г. О минимизации переходных отверстий при двухслойном монтаже. «Управляющие системы и машины» № 4, 1978, Наукова думка, Киев. – с. 108-111.
5. Edmonds J. Maximum matching and polyhedron with 0, 1 vertices, - “Mathematics and Mathematical Physics”, 1965, v. 69B, № 1, 2, – p. 125-130.
УДК 681.325.65
Герасименко Е.П.
ПАКЕТ ПРОГРАММ РАЗРАБОТКИ ПРИНЦИПИАЛЬНЫХ ЭЛЕКТРИЧЕСКИХ СХЕМ GeeTeeSoft (Русский Стандарт)
Исследованы возможности пакета программ разработки электрических схем GeeTeeSotf на предмет обеспечения проектирования РЭА и выпуска конструкторской документации в строгом соответствии с требованиями отечественных стандартов без дополнительной ее корректировки. Обеспечено совместное использование исследуемого пакета программ с популярными САПР РЭА на уровне импорта библиотечных электронных компонентов и схем. Рис.7, ист.5.
Постановка задачи.Подавляющее большинство используемых в настоящее время систем автоматизированного проектирования многослойных печатных плат (МПП) представляют собой разработки ведущих западных производителей [1,2]. Безусловным лидером в этой области является фирма Altium, которая предлагает пользователям САПР радиоэлектронной аппаратуры системы Р-САDиAltium Designer (Protel).
Достоинством названных САПР является возможность сквозного бездефектного проектирования радиоэлектронной аппаратуры (РЭА) с использованием МПП, а недостатком – разработка и выпуск документации согласно стандартам IEEE и ISO, которые существенно отличаются от принятых отечественных стандартов.