Белой О.И., Струнилин В.Н. - РОЗРОБКА АЛГОРИТМУ МІНІМІЗАЦІЇ ВНУТРИШНЬОСХЕМНИЙ ПЕРЕСІКАНЬ ПЕЧАТНОГО МОНТАЖУ

УДК 681.32

О.І. Білой, В.М. Струнілін

Донецький національний технічний університет

кафедра комп’ютерних наук і технологій

РОЗРОБОТКА АЛГОРИТМУ МІНІМІЗАЦІЇ ВНУТРИШНЬОСХЕМНИЙ ПЕРЕСІКАНЬ ПЕЧАТНОГО МОНТАЖУ

Анотація

Білой О.І., Струнілін В.М. Розробка алгоритму мінімізації внутришньосхемних пересікань печатного монтажу. Виконано аналіз алгоритмів мінімізації внутришньосхемних пересікань печатних з’єднань. Пропонується метод розбиття графа пересікань схеми на яруси, що дозволяє виконати оптимальне розшарування печатних плат.

Ключеві слова: розшарування, печатна плата, внутришньосхемні пересікання.

Постановка проблеми.

Сучасні САПР конструкторського проектування радіоелектроніки виконують компоновку і розташування елементів монтажних схем, трасування і розшарування електричних з’єднань по шарах. Задача розшарування печатних з’єднань є однієї з найбільш трудомістких, що має місце при реалізації з'єднань у монтажному просторі. Метою цього етапу є розміщення провідників по шарам без пересічень. Критерієм якості розшарування є мінімум кількості шарів, рівномірність розподілу провідників по шарам. При цьому від того, наскільки вдало вирішена ця задача, залежать такі характеристики спроектованого пристрою як надійність і вартість.

Аналіз літератури. При вирішенні задачі конструкторського проектування комутаційну електричну схему можна представити з використанням теорії графів у вигляді математичних моделей: графу комутаційної схеми (ГКС), мультиграфу комутаційної схеми (МКС), гіперграфу комутаційної схеми (ГКС) [1, 3].

В літературі [1, 2] описано наступні методи розшарування печатних з’єднань.

Послідовний метод виділення плоских суграфів.

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

По матриці Q необхідно створити вектор-стовпець Вi = ||bi||, елементи якого вiдповiдають числу пересікань ребра Ui з іншими ребрами. Метою є знайти ребро, яке необхідно перемістити на інший шар: bk = max (bi).

Усі ненульові елементи b1, b2..., що вiдповiдають ребрам k1, k2..., i що пересікаються з ребром k, зменшуються на одиницю. Внаслідок цього одержимо вектор-стовпець B1. З вектором B1 поступаємо аналогічним чином до тих пір, поки він не стане нульовим.

Через U1 позначимо множину ребер, що ми усунули на другий шар, на першому шарі залишаться U\U1. Перший плоский суграф буде містити U\U1 ребер. Аналогічним чином виділяємо другий плоский суграф, що буде містити U1\U2, де U2 - множина ребер, які усунуті на третій шар i т. д. Слід мати на увазі, що кожний елемент вектору В2, В3, …, Вk вiдповiдає кількості пересікань ребра, видаленого на 2, 3, …, k шар з ребрами 2, 3, …, k шару.

Метод мiнiмiзації внутришньосхемних пересікань на основі розфарбування графа пересікань.

Початковими даними є: G = (E, U), G' = (E', U'): E' ↔ U'.

Подальше завдання укладається у розфарбуванні графа з найменшою кількістю кольорів, що вiдповiдає розбивці початкового графа G на найменше число суграфів.

При розфарбуванні графа G' k−хроматичному числу надаються значення k=1, 2, 3,..., n. Крім того, треба обрати таке розфарбування, при якому число вершин кожного iз цих підмножин було приблизно однаковим.

Завдання вирішується наступним чином. Із графа G' послідовно виймаємо вершини разом з iнцидентними їм ребрами, локальна міра ρ кожного з яких менш k. Причому, починаємо з вершини з найменшим значенням ρ. Якщо на деякому кроці при видалені буде декілька вершин з найменшим i однаковим значенням ρ, отже вибираємо меншу по номеру. Процес повторюємо до тих пір, поки вершини, що залишились, не будуть мати локальну міру ρ, яка більш або дорівнює k, або вершин взагалі не залишиться.

Множину вершин, що ми видалили, позначимо через S.

Далі виділяємо множину S1 наступним чином.

Позначимо через G1' граф, що ми одержуємо в наслідок видалення з G' вершин та iнцидентних їм ребер множини S. В графi G1' послідовно видаляються вершини i iнцидентні їм ребра з максимальною локальною мірою ρ. Видаляємо до тих пір, поки не одержимо не суміжні між собою вершини. Ця множина вершин S1' є частиною S1. Вершини, котрі ми видалили з iнцидентними їм ребрам з G1', утворять новий граф пересікань G1''. Якщо в G1'' є вершини, у яких ρ<k-1, то ми їх також видаляємо та заносимо в список S, а в графі пересікань, що залишився, аналогічно визначається підмножина не суміжних між собою вершин: S1'' ⊂ S1', S2'' ⊂ S2'..., причому в множину S додаються вершини, у яких ρ < k-1, ρ < k-2, i т. д.

Після визначення останньої множини Sk'' в графі може опинитися не пуста множина вершин. Позначимо її через S'. Далі, вершини iз кортежу S в порядку, зворотному включенню їх в кортеж, розподіляємо по підмножинам S1', S2'..., Sk' так, щоб не порушити розфарбування, тобто, щоб в кожній підмножині не з'явилося жодного ребра i щоб кiлькiсть вершин була приблизно однаковою.

Аналогічно поступаємо з множиною S'. Якщо це зробити з множиною S' не вдається, не порушивши розфарбування, то розфарбувати граф G в k кольорів неможливо. Треба збільшувати значення k.

Мета статті – розробка оптимального алгоритму мінімізаціїї внутрішньосхемних пересікань печатного монтажу багатошарових печатних плат на основі розбиття графу пересічень на яруси.

Рішення задачі і результати досліджень.

Хай маємо початкове розміщення графа схеми в позиціях комутаційного поля (КП). Будемо вважати, що ребра графа жорстко розташовані в вузлах КП. Необхідно вирішити завдання мiнiмiзацiї внутришньосхемних пересікань, яке пов’язане з пересіканням ребер графа, відображених на КП.

Граф схеми необхідно розтрощити на m плоских суграфів, так, щоб m прагнуло до найменшого. Початкову iнформацiю про пересічення задаємо у вигляді:

а) матриці пересікань Q=Q ‖ Qij ‖ _{|u| x |u|}; Q_ji= { 1 0 ,

де Q_ji=1, якщо ребро Ui та ребро Uj пересікаються між собою;

Q_ji=0, якщо ребро Ui та ребро Uj не пересікаються між собою;

Ui, Uj − ребра графа.

б) списку пересікань: для будь-якого Ui записуємо список ребер (Ui1, Ui2,..., Uik), що пересікаються з Ui.

Кожний плоский суграф взаємно вiдповiдає шару друкованої плати. Таким чином, мiнiмальне число плоских суграфів дає мiнiмальне число шарів.

Розглянемо приклади мінімізації кількості внутришньосхемних пересікань трьома методами. Метою є виявлення умов та обмежень, при дотриманні котрих той чи інший метод стає доцільним.

Хай граф пересікань буде завданий у вигляді матриці пересікань (табл.1).

Таблиця 1 – Матриця пересікань

	U₀	U₁	U₂	U₃	U₄	U₅	U₆	U₇	U₈	U₉	U₁₀	U₁₁	U₁₂
U₀	0	0	1	1	1	1	0	0	0	0	0	0	0
U₁	0	0	0	0	1	0	0	0	0	0	0	0	0
U₂	1	0	0	0	0	0	0	0	1	1	0	0	0
U₃	1	0	0	0	1	1	0	0	0	0	0	0	0
U₄	1	1	0	1	0	0	0	0	1	0	0	0	0
U₅	1	0	0	1	0	0	0	0	0	0	0	0	0
U₆	0	0	0	0	0	0	0	0	0	0	1	0	1
U₇	0	0	0	0	0	0	0	0	0	0	1	1	1
U₈	0	0	1	0	1	0	0	0	0	1	1	0	1
U₉	0	0	1	0	0	0	0	0	1	0	1	1	0
U₁₀	0	0	0	0	0	0	1	1	1	1	0	1	1
U₁₁	0	0	0	0	0	0	0	1	0	1	1	0	0
U₁₂	0	0	0	0	0	0	1	1	1	0	1	0	0

Розглянемо послідовний метод виділення плоских суграфів.

Завдамося кількістю шарів К=2, тобто граф треба розбити по можливості на два плоских суграфи.

Відповідно до алгоритму сформуємо вектори-стовпці B:

* відмічені елементи з максимальною кількістю зв’язків на кожному кроці. Вони заносяться до списку U₁.

До другого шару надійдуть U₁ = {8,10,0,3,7,9,1,6}.

До першого шару надійдуть U\U₁ = {2,4,5,11,12}.

При використанні метода мiнiмiзації пересікань на основi розфарбування графа пересікань граф пересікань, який, завданий у вигляді матриці пересікань (табл.1 ), розіб’ємо на К плоских суграфи. К=4.

Згідно алгоритму сформуємо список-кортеж S:

S = (1, 5, 3, 0, 4, 2, 6, 7, 12, 8, 9, 10, 11).

У порядку, зворотному включенню елементів до списку, розподіляємо їх по К підмножин, так щоб у довільному підмножині не з’явилось жодного ребра:

S₁ = (11,12,4) – перший шар;

S₂ = (10,2,1,3) – другий шар;

S₃ = (9,7,0) – третій шар;

S₄ = (8,6,5) – четвертий шар.

Пропонується алгоритм зменшення внутрішньосхемних пересікань на основі розбиття графа пересічень на яруси.

Суть алгоритму, що пропонується, укладається у наступному.

В графі пересікань шукається вершина E₀ з максимальною локальною мірою ρ. Якщо опиниться декілька вершин з максимальним і однаковим значенням ρ, то вибираємо меншу по номеру. Вершині E₀ надаємо вагу, яка дорівнює 0. Далі розповсюджується числова хвиля, поки її фронт не досягне всіх вершин, суміжних із E₀.

Формування чергового фронту числової хвилі F_k починається із надання всім суміжним з вершинами фронту F_k-1 ваги Pk=P_k-1+1. Процес триває до тих пір, поки всім вершинам не буде надана вага. Далі множину вершин з парною вагою вносимо в список L₀, множину вершин з непарною вагою вносимо в список L₁. Очевидно, що множина вершин списку L₀або L₁ не будуть мати між собою ребер. Це справедливо лише в разі бiхроматичностi графа пересічень, тобто в ньому не повинно бути циклів непарної довжини. В цьому випадку одержуємо розбиття вихідного графа пересічень на два плоских суграфа.

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

Граф пересікань, який задається у вигляді матриці пересікань (табл.1) треба розбити на К плоских суграфи. К=4.

Згідно алгоритму надамо кожному ребру графа вагу (табл.2).

Таблиця 2 – Вага ребер графа

Ребро U_i	U₀	U₁	U₂	U₃	U₄	U₅	U₆	U₇	U₈	U₉	U₁₀	U₁₁	U₁₂
Вага	3	3	2	3	2	4	1	1	1	1	0	1	1

Згідно алгоритму розподіляємо ребра по спискам

L₀ =(U₂, U₄, U₅, U₁₀);

L₁=(U₀, U₁, U₃, U₆, U₇, U₈, U₉, U₁₁, U₁₂).

Аналізуємо список L₀. Множина елементів цього списку – не суміжні між собою вершини, тому це є перший плоский суграф.

Аналізуємо список L₁. Ребро U₈ має пересічення з ребром U₉, тому відносимо його до списку L₂. L₂=(U₈).

Список L₁ прийме вигляд L₁=(U₀,U₁,U₃,U₆,U₇,U₉,U₁₁,U₁₂). Ребро U₀ має пересічення з ребром U₃, тому відносимо його до списку L₂. L₂=(U₈, U₀).

Список L₁ прийме вигляд L₁=(U₁,U₃,U₆,U₇,U₉,U₁₁,U₁₂). Ребро U₉ має пересічення з ребром U₁₁. Це ребро не можливо розподілити до існуючих списків, тому відносимо його до списку L₃. L₃=(U₉).

Список L₁ прийме вигляд L₁=(U₁,U₃,U₆,U₇,U₁₁,U₁₂). Отже, у кожному списку L₀- L₃ знаходиться множина не суміжних між собою ребер, що відповідає поставленій задачі.

L₀= (U₂, U₄, U₅, U₁₀) - перший плоский суграф;

L₁= (U₁, U₃, U₆, U₇, U₁₁, U₁₂) - другий плоский суграф;

L₂= (U₈, U₀) - третій плоский суграф;

L₃= (U₉) - четвертий плоский суграф.

Треба відзначити, що алгоритм розбиття графа пересікань на яруси працює тільки зі зв’язними графами, тому при реалізації його на ЕОМ його треба модифікувати.

Для дослідження методів розшарування була розроблена програма, інтерфейс якої наведено на рис. 1.

Рисунок 1 – Інтерфейс програми розшарування

Дати порівняльну характеристику методів розшарування дуже важко, тому що всі розглянуті методи є евристичними алгоритмами. Як звісно, евристичні алгоритми не піддаються аналітичній оцінці, тому було прийнято рішення провести порівняльну характеристику методів шляхом аналізу результатів роботи кожного алгоритму з графами пересікань різної складності.

У таблиці 3 наведено порівняльну характеристику методів розшарування.

Таблиця 3 – Порівняльна характеристика методів розшарування

Параметр	Метод розшарування
Параметр	Послідовний	Розфарбування	Ярусний
Тип графу	Зв’язний, незв’язний	Зв’язний, незв’язний	Зв’язний, незв’язний (з доробкою алгоритму)
Швидкість	Велика	Низька	Велика
Виділення плоских суграфів	Не гарантується	Гарантується	Гарантується
Якість розшарування (рівномірність розподілу)	Низька	Висока	Висока
Реалізація на ПЕОМ	Проста	Складна	Проста

Висновки. Аналіз результатів роботи алгоритмів розшарування печатних з’єднань з майже 50 графами пересікань дозволяє зробити висновок, що запропонований метод розбиття графа пересікань на яруси найбільш ефективний з точки зору швидкості реалізації, якості розшарування і простоти реалізації серед представлених методів.

Перелік літератури

1. Автоматизированное проектирование узлов и блоков РЭС средствами современных САПР: Учеб. пособие вузов / Под ред. И.Г. Мироненко. – М., 2002. – 391 с.

2. Селютин В. А. Автоматизированное проектирование топологии БИС / В.А. Селютин. – М.; Радио и связь, 1983. – 112с.

3. Модифікація ітераційного алгоритму компоновки на базі гіперграфової моделі електричної схеми/ Білой О.І., Струнілін В.М. Інформаційні управляючі системи та комп'ютерний моніторинг (ІУСКМ – 2012): III Всеукраїнська науково-технічна конференція студентів, аспірантів та молодих вчених, 16-18 квітня 2012 р., м. Донецьк / Донец. націонал. техн. ун-т; редкол.: Є.О. Башков (голова) та ін. – Донецьк: ДонНТУ, 2012. – С. 567 – 571

Параметр

Метод розшарування

Послідовний

Розфарбування

Ярусний