Трасування
Вихідним для цього завдання є результати розміщення (всі вершини розташовані на фіксованих позиціях).
ОБМЕЖЕННЯ: тут пов'язані з можливістю та неможливістю проведення трас (провідників), наявністю на поверхні друкованих плат (комутаційних полів) заборонених для прокладання провідників ділянок поля, можливістю або неможливістю виготовлення двосторонніх та багатошарових друкованих плат.
Найбільш поширені критерії якості трасування такі.
КРИТЕРІЙ №1: мінімальна сумарна довжина всіх провідників.
КРИТЕРІЙ № 2: довжина максимального провідника має бути мінімальною.
В результаті виконання етапу трасування отримують вихідні дані з топології розташування провідників, які далі використовуються на етапі параметричної верифікації, вирішення питань внутрішньоапаратурної електромагнітної сумісності при випуску конструкторської документації.
Лекція 5. Алгоритми розв'язання топологічних завдань
Вирішення топологічних завдань починається з етапу графо-теоретичного опису принципової схеми. Один із прийомів полягає в тому, що радіоелемент представляється у вигляді вершини графа. Все начебто просто, але тут є підводні камені, які пов'язані з представленням багатовивідних елементів. Двовивідні елементи можуть бути представлені вершиною, якою інцидентні два ребра. При наступних ізоморфних перетвореннях вершина другого ступеня може бути видалена з графа, що не вплине на розв'язання топологічних завдань, а спростить граф.
Складніша справа з трививідними елементами. За спрощення графа ми можемо змінювати положення ребер так, як нам зручно з метою мінімізації перетинів або для вирішення інших завдань. Якщо ж ми, наприклад, у процесі перетворень змінимо наНа малюнку графа послідовність висновків транзистора, то при реалізації схеми, транзистор доведеться встановити в перевернутому стані.
З багатовиводними ситуація складніша. Після перетворень графа можливе повне порушення послідовності висновків. Звичайно, ми не маємо можливості міняти місцями висновки елемента. Тому для багатовивідних елементів доводиться "зв'язувати" ребра графа, фіксуючи їх певну послідовність, як показано на рис. 5.1.
Мал. 5.1. Приклади представлення радіоелементів малюнку графа
Існує велика кількість алгоритмів розв'язання топологічних завдань. Переважна більшість із них оперують матрицями, і вони поділяються на два великі класи: паралельні алгоритми (у яких перетворення ведуться над графом загалом), та ітераційні (ведуться покрокові зміни графа). Ці зміни можуть бути цілеспрямованими та випадковими з наступними оцінками результатів.
Алгоритм послідовного розбиття
Алгоритм послідовного розбиття передбачає розбиття графа на шматки із заданою кількістю вершин у кожному шматку. Алгоритм спрямований на реалізацію критерію розбиття - мінімум числа сполучних ребер. Отже, число ребер усередині шматків графа має бути максимальним. Тому в основі алгоритму лежить послідовне формування шматків графа шляхом нарощування шматків за принципом зв'язності вершин.
Початок алгоритму (перша ітерація) – виділення вершини з максимальним ступенем. На наступних кроках до цієї вершини приєднуються вершини максимально пов'язані з нею. Розглянемо алгоритм детальніше (рис. 5.2).
Мал. 5.2. Розбиття графа - виділяємо вершину з максимальним ступенем (наприклад, X3).
Вибираємо вершини, максимально пов'язані з вже включенимиу шматок графаG1(1) після першої ітерації. Видно, що третя вершина має зв'язок з вершиноюX1двома ребрами, з вершиноюX2 одним ребром. Отже, на другій ітерації включаємо в подграфG1 вершинуX1. Включені в шматокG1(2) вершиниX3,X1 умовно стягуються в однуX3,1. Таким чином, утворюється шматок графаG1(2) другої ітерації. При цьому ступінь отриманої вершиниr(X3,1) дорівнює сумі ступенів вихідних вершинX3,X1без урахування числа>u12 сполучних ребер між ними:
Знаходимо вершинуX2, максимально пов'язану з отриманою на попередньому етапі об'єднаною вершиноюX1,3, включаємо її в подграфG1(3) на третій ітерації, і визначаємо ступінь об'єднаної вершини:
Процедура включення нових вершин у шматокG1 ведеться до того часу, поки у ньому буде отримано заданого числа вершин. Якщо зв'язність шматка з кількома вершинами однакова, доведеться подумати, яким шляхом піти, бо залежно від цього будуть отримані різні результати розрахунку. В ідеальному випадку треба прорахувати всі варіанти. Тут питання впирається у витрати машинного часу та машинних ресурсів.