Алгоритми та методи компонування й розміщення. Графові моделі схем обчислювальних пристроїв та їхнього перетворення

1. Алгоритми компонування (оглядовий матеріал)

Для побудови формальної математичної моделі завдань компонування зручно використовувати теорію графів. При цьому електричну схему інтерпретують ненаправленим мультографом, у якому кожному конструктивному елементу (модулю) ставлять у відповідність вершину мультографа, а електричним зв'язкам схеми - його ребра. Тоді завдання компонування формулюється в такий спосіб:

Заданий мультограф G(X,U). Потрібно “розрізати” його на окремі шматки G₁(X₁,U₁), G₂(X₂,U₂), G_k(X_k,U_k) так, щоб число ребер, що з'єднують ці шматки, було мінімальним:

мінімізувати

i?j

при ]

i,j = 1,2,…,k,

де U_ij - множина ребер, що з'єднують шматки G_i(X_i,U_i) і G_j(X_j,U_j).

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

Відомі алгоритми компонування можна умовно розбити на п'ять груп:

1.алгоритми, що використають методи цілочисельного програмування.

2.послідовні алгоритми

3.ітераційні алгоритми

4.змішані алгоритми

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

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

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

У змішаних алгоритмах компонування для одержання початкового варіанта “розрізування” використовується алгоритм послідовного формування шматків; подальша оптимізація рішення здійснюється перерозподілом вершин між окремими шматками графа.

2. Послідовні алгоритми компонування

У послідовних алгоритмах компонування «розрізування» вихідного графа G(X,U) на шматки G₁(X₁,U₁), G₂(X₂,U₂), G_k(X_k,U_k) зводиться до наступного:

У графі G(X,U) знаходять вершину x_i X з мінімальним локальним ступенем .

Якщо таких вершинне багато, то перевагу віддають вершині з максимальним числом кратних ребер. З множини вершин, суміжних з вершинами формованого шматка графа G₁(X₁,U₁), вибирають ту, котра забезпечує мінімальне збільшення зв'язків шматка із ще нерозподіленими вершинами.

Дану вершину x_i X \ X₁ включають в G₁(X₁,U₁), якщо не відбувається порушення обмеження по числу зовнішніх зв'язків шматка, тобто

де б_jе - елемент матриці суміжності вихідного графа G(X,U);

д(x_g) - відносна вага вершини x_g, , дорівнює збільшенню числа зовнішніх ребер шматка G₁(X₁,U₁) при включенні вершини x_g у множину X₁;

E - множина індексів вершин, включених у формований шматок графа на попередніх кроках алгоритму;

m - максимально припустиме число зовнішніх зв'язків окремо взятого шматка з усіма що залишилися.

Зазначений процес триває доти, поки множина X₁ не буде містити n елементів або приєднання чергової нерозподіленої вершини x_j до шматка G₁(X₁,U₁) не приведе до порушення обмеження по числу зовнішніх з'єднань шматка, рівному

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

Як остаточний варіант вибирають шматок G₁⁰(X₁⁰,U₁⁰), що містить максимально можливе число вершин графа G(X,U), для якого виконуються обмеження на число зовнішніх зв'язків і вхідних у нього вершин (n_min-n_max).

Після перетворення шматка G₁⁰(X₁⁰,U₁⁰) процес повторюють

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

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

1) t:=0

2) X_f = X_t = Ш; t=t+1; И=1; б=n_max,

де t, И - порядкові номери формованого шматка й вершини, що

приєднується

б - обмеження на число вершин у шматку.

3) По матриці суміжності вихідного графа | б_hp|Nx, де N - число вершин вихідного графа (при великому значенні N для скорочення обсягу оперативної пам'яті ЕОМ використаємо не саму матрицю суміжності, а її кодову реалізацію), визначаємо локальні ступені вершин

4) З множини нерозподілених вершин X вибираємо вершину x_j з с(x_j) = . Переходимо до п.6. Якщо таких вершин декілька, то переходимо до п.5

5) З підмножини вершин X_l з однаковим локальним ступенем вибирають вершину x_j з максимальним числом кратних ребер (мінімальним числом суміжних вершин), тобто

Гx_j| = .

6) Запам'ятовуємо вихідну вершину формованого шматка графа . Переходимо до п.10

7) По матриці суміжності будуємо множину

X_s =

і визначаємо відносні ваги вершин

: .

8) З множини X_S вибираємо вершину

.

Переходимо до п.10. Якщо таких вершин декілька, то переходимо до п.9.

9) З підмножини вершин X_v з однаковою відносною вагою вибираємо вершину x_j з максимальним локальним ступенем, тобто

.

.

10) Якщо >m , то переходимо до п.13.

11) Розглянуті вершини включаємо у формований шматок

X_f = X_t .

12) И = И + 1.

13) Якщо И> б, то переходимо до п.15, в протилежному випадку - до п.7.

14) Якщо |X_f|<n_min, де n_min - мінімально припустиме число вершин у шматку, то переходимо до п. 21.

15) Вибираємо остаточний варіант сформованого шматка графа:

X_t = X_f ; X = X \ X_t ; б = n_max .

16) Якщо |X|> n_max , то переходимо до п. 20.

17) Якщо |X|< n_min , то переходимо до п. 21.

18) Визначаємо число зовнішніх зв'язків останнього шматка графа:

,

де F - множина індексів вершин, що входять в X.

Якщо , то переходимо до п. 21, у противному випадку - до п. 24.

19) Якщо t<k - 1 , де k - число шматків розрізування графа, то переходимо до п.2, у противному випадку - до п.23.

20) Попередній цикл «розрізування» вважаємо недійсним. Якщо t>1, тобто є як мінімум один раніше сформований шматок, то переходимо до п.22. у протилежному випадку - до п.23.

21) Шукаємо інший припустимий варіант формування попереднього шматка з меншим числом вершин:

t = t - 1; .

Переходимо до п.7.

22) Завдання при заданих обмеженнях не має рішення.

23) Кінець роботи алгоритму.

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

Основним недоліком послідовного алгоритму є нездатність знаходити глобальний мінімум кількості зовнішніх зв'язків (не аналізуються можливі ситуації). Найбільша ефективність методу послідовної розбивки графа має місце, коли число вершин графа G значно більше вершин у будь-якій частині розбивки.

3. Ітераційні алгоритми компонування

Сутність даної групи алгоритмів полягає у виборі деякого початкового «розрізування» вихідного графа на шматки (вручну або за допомогою послідовного методу компонування) і наступного його поліпшення за допомогою ітераційного парного або групового обміну вершин з різних шматків. При цьому для кожної ітерації здійснюється перестановка тих вершин, що забезпечує максимальне зменшення числа зв'язків між шматками графа або максимальне поліпшення іншого обраного показника якості з урахуванням використовуваних обмежень (наприклад, на максимальне число зовнішніх ребер будь-якого окремо взятого шматка).

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

Розбивку графа G = (X,U) на l підграфів G₁ = (X₁,U₁), G₂ = (X₂,U₂),G_l= (X_l,U_l) зведемо до розбивки на два підграфа. З цією метою в матриці суміжності R виділимо по головній діагоналі дві підматриці R₁ й R₂. При цьому порядок підматриці R₁ дорівнює числу вершин, які повинні перебуває в G₁, а порядок підматриці R₂ - числу всіх вершин, що залишилися, графа.

Необхідно так переставити рядки й стовпці матриці R, щоб число ребер між G₁ і частиною, що залишилася, графа G було мінімальним. Після цього підматрицю R₁ з матриці R виключаємо, викресливши з R рядки й стовпці, що відповідають елементам R₁. Далі підматрицю R₁' розбиваємо знову на дві підматриці R₂ й R₂', причому порядок R₂ відповідає числу вершин другого підграфа який виділяється, а порядок R₂ - числу вершин графа які залишилися. Переставляємо рядки й стовпці R₁' з метою мінімізації числа сполучних ребер. Після цього підматриця R₂' виключається й процес повторюється доти, поки не буде виконана розбивка графа G на l підграфів.

Основна ідея алгоритму полягає у виборі таких рядків і стовпців, перестановка яких приводить до зосередження в діагональних клітках матриці R максимального числа елементів.

Побудуємо прямокутну матрицю

W = ||w_i,j||n_ix(n-n_i),

у якій рядки визначаються вершинами з множини I, а стовпці - з множини

V, .

На перетинанні k рядку ( і q стовпця перебуває елемент

,

де r_k,q - елемент матриці суміжності R.

Елемент w_k,q матриці W характеризує зміну числа сполучних ребер між G_i й G_j при перестановці вершин

й .

Використовуючи матрицю W , можна знайти підстановку, що збільшить число елементів у підматрицях R₁ й R₁' . Такий процес повторюється доти, поки в підматриці R₁ не зосередиться максимальне число одиниць.

В ітераційних алгоритмах передбачена можливість пошуку оптимального варіанту для різних початкових розбивок. Це пов'язане з тим, що при використанні ітераційних алгоритмів оптимальність рішення значною мірою залежить від того, наскільки вдало була зроблено початкова розбивка графу G(X,U).

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

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

4. Алгоритми розміщення

5. Силові алгоритми розміщення

В основу цієї групи алгоритмів покладений динамічний метод В. С. Линського. Процес розміщення елементів на платі представляється як рух до стану рівноваги системи матеріальних точок (елементів), на кожну з яких діють сили притягання й відштовхування, що інтерпретують зв'язки між розташовуваними елементами. Якщо сили притягання, що діють між будь-якими двома матеріальними точками r_i й r_j пропорційні числу електричних зв'язків між даними конструктивними елементами, то стан рівноваги такої системи відповідає мінімуму сумарної довжини всіх з'єднань.

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

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

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

Недоліками є трудомісткість методу й складність його реалізації (підбора коефіцієнтів для силових зв'язків); необхідність фіксування місця розташування деякого числа конструктивних елементів на платі для запобігання великої нерівномірності їхнього розміщення на окремих ділянках плати.

6. Ітераційні алгоритми розміщення. Алгоритм Штейнберга

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

У випадку мінімізації сумарної зваженої довжини з'єднань формула для розрахунку зміни значення цільової функції при перестановці місцями елементів r_i й r_j , закріплених у позиціях t_f й t_g, має вигляд:

,

де p й h(p) - порядковий номер і позиція закріплення нерухомого елемента r_p.

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

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

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

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

Частковим випадком ітераційного алгоритму є алгоритм Штейнберга або так званий алгоритм парних перестановок.

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

7. Послідовні алгоритми розміщення. Послідовно-груповий метод

Для вирішення завдання розміщення елементів на платі по існуючому файлі зв'язків складається матриця інциденцій, що описує число електричних з'єднань між всіма елементами схеми й будується граф всіх зв'язків. Далі визначається мінімальна розмірність матриці посадкових місць m x n, де m - число місць по горизонталі n - число місць по вертикалі. Ця модель розширюється до розмірів (2m-1) x (2n-1).

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

Fi = Уk Уj (ЬjДxijk +вjДyijk) + Si,

де: Si - невикористовувана площа плати, пов'язана з різногабаритносттю елементів; алгоритм компонування розміщення клас

Ьj, вj =0, якщо і-й елемент не пов'язаний з j-тим;

Ьj=0, вj=4, якщо елемент пов'язаний з корпусом;

вj=0, якщо елемент зв'язаний з вільним виводом з'єднувача.

У всіх інших випадках Ьj=1 вj=2, якщо і-тий елемент пов'язаний з j-тим дxijkдyijk - різниця відповідно між абсцисами й ординатами виводів установлюваного елемента із установленими.

підсумовування по k означає перебір по всіх виводах установлюваного елемента, а підсумовування по j - перебір по всіх установлених елементах.

Література

1. Автоматизация схемотехнического проектирования на мини-эвм: Учебное пособие/ Под ред. Проф. Анисимова. Л. Изд-во ЛГУ, 1983. - 200 с.

2. Чуа Л.О., Пен-Мин Линь. Машинный анализ электронных схем: Алгоритмы и вычислительные методы. Пер с англ. Г.: Энергия, 1980. - 640 с.

3. Математическое и программное обеспечение САПР радиоэлектронной аппаратуры: Учебное пособие/ Огороднейчук И.Ф., Семенец В.В., Куник Э.Г. и др. К.: УМК ВО, 1988. - 104 с.

4. Копченова Н.В., Марон И.А. Вычислительная математика в примерах и задачах. Г.: Изд-во «Наука», 1972. - 365 с.

Размещено на Allbest.ru