МЕТОД РАССЛОЕНИЯ ПЕЧАТНЫХ ПЛАТ

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

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

Но в большинстве случаев расслоение выполняется после размещения элементов и более простой путь состоит в учете "взаимодействия" отдельных соединений или связывающих деревьев при условии их одновременного рас­положения на одной плоскости. При этом учитываются метрические параметры соединений, так как положение КП на коммутационном поле уже известно. Наиболее распространенным приемом является выделение некоторых приоритетных направлений, группирование соединений в соответствии с выбранными направлениями и разнесение этих групп на отдельные слои. Различные способы оценки "взаимодействия" соединений приводятся в работах [6, 7, 12].

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

Фундаментальные теоретические основы указанного подхода заложены работами Кодреса [13] и Вайссмана [14, 15].

Задача Кодреса заключается в ликвидации минимального числа пересечений таким образом, чтобы было возможно реализовать соединение без пересечений в двух слоях. Для каждой цепи предварительно строится минимальное дерево и связь между слоями возможна только в точках, соответствующих выводам элементов. А неизбежные пересечения устраняются с учетом дополнительных конструктивных возможностей (проход между выводами элементов ...). Системе проводников на плоскости ставится в соответствие граф пересечений Z=(X,U), вершины которого соответствуют отдельным проводникам, а ребра  - их пересечениям. Ищется такая двухцветная раскраска графа Z, при которой суммарное количество ребер, соединяющих одноцветные вершины будет минимально (количество не устраненных пересечений). При этом вершины одного цвета соответствуют проводникам, расположенным в одном слое. Такая задача выделения в графе Z максимального по числу ребер бихроматического подграфа решается методами линейного программирования.

Аналогичная задача состоит в ликвидации минимального числа проводников для получения двухслойного разложения [2, 8].

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

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

Расслоение проводников сводится к получению раскраски вершин графа пересечений Z=(X,U) в минимальное число цветов. Особенностью задачи является то обстоятельство, что для каждой пары выводов требуется выбрать по одному пути таким образом, чтобы обеспечить разложение всей системы соединений в минимальное число слоев.

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

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

В ряде работ при ортогональной трассировке соединений предлагается тривиальное распределение проводников на два слоя, когда все горизонтальные отрезки помещаются в одном слое, а вертикальные - в другом. В точках изгибов соединений размещаются контактные переходы. Однако в этом случае возникает избыточное число переходов. Приближенный способ их минимизации приводится в работе [3]. Алгоритм дает сокращение числа переходов до 60% по сравнению с чисто ортогональным расслоением.

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

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

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

1. Абрайтис Л.Б. Определение конфигураций соединительных деревьев ком­плексов с распределением коммутаций по слоям // Вычислительная техника.- Каунас: Каунас, политехи, ин-т, 1971,- Т.П.- С. 162 - 169.
2. Беляков А.Н., Бугаев Е.К., Розанов В.А. Метод распределения проводников в многослойных печатных платах // Труды МИЭМ,- 1971,- Вып. 16, Ч.1.-С. 148 - 165.
3. Гуревич Д.З., Селютин В.А. Алгоритмические методы проектирования то­пологии БИС ячеечного типа // Методы расчета и автоматизации проекти­рования устройств микроэлектронных ЦВМ,- Киев: ИК АН УССР, 1973,- С. 83 - 92.
4. Каплан A.B. Алгоритм уменьшения числа межслойных переходов в печат­ных платах // Вычислительная техника,- Каунас: Каунас, политехн, ин-т, 1973,-T.IV.-  С. 126-131.
5. Каплан A.B. К вопросу уменьшения числа межслойных точек перехода в пе­чатных платах // Вычислительная техника.- Каунас: Каунас, политехн, ин-т, 1973,-T.IV. С. 122 - 125.
6. Помазанов В.Н., Крыжановский Ю.М., Клименкова Т.И. Алгоритм и про­граммы комплекса трассировки // Обмен опытом в радиопромышленности.- 1971,- Вып.7,- С. 29-31.
7. Селютин В.А., Гуревич Д.З. Реализация на ЦВМ системы алгоритмов топологического проектирования // Электронная техника. Сер. VI,- Микроэлектроника." 1971,- Вып.6.- С. 145 - 152.
8. Шеуйкис В.А. Исследование алгоритмов для распределения связей по двум слоям платы // Вычислительная техника.- Каунас: Каунас, политехн, ин-т, 1971,-Т.Н.-С.170 - 174.
9. Chein M. Decomposition d'un schema en un nombre minimal de schémas pla­naires // L'onde electrique.- 1970,- V.50, £11.- P. 934 - 939.
10. Chung S.H., Roe R.H. Algoritms for testing the planarity of a graph // Proc. of the 13th Medwest symposium on Circuit Theory.- New York, 1970, P. 321 - 332.
11. Geyer J. M. Connection routing algorithm for printed circuit boards // IEEE Trans.- 1971,- V.CT-18.-P. 95 - 100.
12. Hightower D. W. The interconnection problem: a tutorial // Computer.-1974.- V.7, № 4,- P. 18-32.
13. Kodres U. R. Formulation and solution of circuit card design problems through use of a graph methods // Advances in Electronic Circuit Packaging.- 1962,- V.2, №7,- P. 121 - 142.
14. Weissman J. Boolen algebra, map coloring, and interconnections // The Mathe­matical Monthly.- 1962,- V.69, № 7,- P. 608 - 613.
15. Weissman J. The mathematical basis of the Automatics Etched Interconnection Design Program // IRE International Convention Record.- Rome, 1962,- Part 6,- P. 26-133.