Розділ 2
Алгоритми початкового розміщення
2.1. Алгоритми групування елементів
2.1.1. Групування елементів як ефективний засіб формування початкового
розміщення
Як було відмічено вище, основною задачею розміщення є пошук таких позицій для
елементів, щоб в найкращій мірі забезпечити спрощене наступне трасування
зв’язків [66]. Для цього необхідно мінімізувати довжину зв’язків – розміщувати
елементи, що мають спільні зв’язки, як можна ближче один до одного. Для
вирішення цієї задачі в задачах автоматизованого проектування пропонувались
різні критерії розміщення: мінімізація довжини найдовшого зв’язку, мінімізація
середньої довжини зв’язків, мінімізація сумарної довжини зв’язків та ін.
Одним з найкращих вважається критерій мінімізації сумарної довжини з’єднань між
елементами. Кожне з’єднання між двома елементами є частиною зв’язка, який
задається множиною елементів, що входять в нього і множиною виводів в кожному з
цих елементів, через які повинен проходити зв’язок. Наявність великої кількості
елементів і зв’язків (тисячі), що їх з’єднують в реальних схемах, суттєво
ускладнює задачу пошуку оптимального рішення.
Для підвищення ефективності пошуку найкращого рішення доцільно здійснювати
попереднє групування елементів на основі показників зв’язності між ними.
Групування елементів дозволяє виділити групи сильнозв’язаних елементів –
кластери, які доцільно розміщувати компактно. Утворені групи елементів можуть
об’єднуватись в інші групи утворюючи ієрархічну структуру. Ієрархічна
декомпозиція дозволяє знизити обчислювальну складність задачі до
лінійно-логарифмічної замість початкової факторіальної.
2.1.2. Багаторівневе групування елементів на основі методу оптимального
згортання схеми
Для побудови ієрархічної структури схеми з врахуванням зв’язності між
елементами ефективним є застосування методу оптимального згортання схеми
запропонованого Р.П. Базилевичем [5, 10, 11, 13]. Даний метод лежить в основі
паралельно-послідовних алгоритмів розбиття, пакування та розміщення. Моделлю
згортання схеми є дерево оптимального згортання TR, яке дає певну інформацію
проектанту про зв’язність окремих елементів, виділяє кластери схеми та їх
взаємне ієрархічне входження.
Вхідна інформація для побудови дерева оптимального згортання задається:
– множиною з n елементів P = {p1, ..., pn};
– множиною зв’язків між елементами .
Процес формування дерева згортання є багаторівневим ієрархічним. До першого
рівня дерева згортання відносяться всі елементи множини Р: Р1 є Р. На першому
кроці з множини Р1 виділяються рівноцінні групи, що містять по два або більше
число елементів, які утворюють множину вершин Р2 другого рівня дерева
згортання. Незгорнуті вершини першого рівня переносяться до другого рівня. На
наступному кроці з множини вершин другого рівня Р2 формується множина Р3
третього рівня і так до тих пір, поки всі вершини не будуть об’єднані в
одноелементній множині Рt, яка відповідає кореню дерева згортання, тобто всій
схемі.
При побудові дерева згортання для визначення зв’язності пар елементів рi та рj
вхідною інформацією служать множини з їх зв’язків E(pi) та E(pj). Перетин цих
множин утворює множину спільних для обох елементів зв’язків:
На основі критеріїв зв’язності між елементами множини Р формуємо впорядкований
за вибраним критерієм список зв’язаних пар.
Всі зв’язки, які з’єднують елементи pi та pj з іншими елементами, називаються
зовнішніми. Для зовнішніх зв’язків можна записати наступне визначення:
Eзв(pi, pj) = { (eОE) | ((e a pi) Ъ (e a pj) & (e a px), px № pi, pj) }.
На рис. 2.1 наведено приклад внутрішніх та зовнішніх зв’язків для елементів pi
та pj.
Рис. 2.1. Типи зв’язків для двох елементів
2.1.3. Критерії побудови дерева згортання
Спосіб вибору сильнозв’язаних елементів та їх груп залежить від вибраного
критерію. Вибір критерію впливає на структуру дерева згортання. В розробленій
комп’ютерній системі реалізовано наступні критерії:
1. Максимізація кількості внутрішніх зв’язків між елементами:
2. Мінімізація кількості зовнішніх зв’язків:
3. Максимізація кількості різниці внутрішніх та зовнішніх зв’язків
На рис. 2.2 (а-в) показано вигляди дерев згортання, сформованого розробленою
комп’ютерною системою "Розмел" для реального конструктиву, з використанням
різних критеріїв об’єднання елементів між собою.
2.1.4. Алгоритм побудови дерева згортання
Процесу формування дерева оптимального згортання передує ряд підготовчих
етапів:
– формування початкової множини елементів P1;
– визначення критерію зв’язності між елементами.
З врахуванням сказаного вище, алгоритм формування дерева складається з 3-х
етапів:
1. Формування множини з n елементів, на основі яких формується дерево згортання
P={p1, ..., pn}. В реальних конструктивах це, як правило, нефіксовані елементи,
що підлягають розміщенню.
2. Побудова списку зв’язаних пар, впорядкованих за спаданням значення критерію.
3. Виділення пар елементів з найкращим значенням критерію (процедура
ФОРМ_ДЕРЕВО). На основі заданого критерію серед всіх можливих пар вибирається
множина з найкращим значенням критерію. Розглядаються тільки пари елементів, що
мають зв’язки між собою, а не всі можливі пари, кількість яких є великою:
Оскільки кожен елемент має невелику обмежену кількість зв’язків з іншими
елементами, то число пар, для яких необхідно визначити значення критерію, є
суттєво меншим від k та звичайно зв’язано з кількістю початкових елементів
лінійною залежністю.
а)
б)
в)
Рис. 2.2. Вплив вибраного критерію на вигляд дерева згортання
Етап 3 програмно реалізований процедурою ФОРМ_ДЕРЕВО, яка отримує на вході таку
інформацію:
– множину елементів