2.1.2 Паралельне трасування та евристичні методи

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

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

Рисунок 2.2 Фрагмент двухслойного монтажного простору

Монтажне пространство розділяється на канали лініями, що проходять між горизонтальними рядами контактів. Кожен канал Ki містить один горизонтальний ряд контактів і деяке число контактів роз'єму. Ряд контактів розділяє канал Кi на дві частини: верхню Кi( і нижню _Кi( .

Кожній частині каналу відповідають певні контакти роз'єму. Кожен канал Ki характеризується пропускною спроможністю ₍i, — числом горизонтальних магістралей для проведення трас, (i( і (i(пропускні здібності відповідних підканалів Ki( і Кi(. У міру проведення трас зменшуються пропускні здібності деяких ділянок каналів. Тому необхідно знати пропускні здібності кожного вертикального перерізу каналу, проведеного через контакті горизонтального ряду. Позначимо _через гi(х) січення, проведене через контакт з координатою х канала Ki.

Усі з'єднання залежно від того, які контакти вони сполучають, розділяються на наступні групи (на малюнку 2.2 приведені з'єднання кожної групи).

• Сполучаючі контакти одного горизонтального ряду (s1).

• Сполучаючі контакти горизонтального ряду і контакт роз'єму (s2).

• Сполучаючі контакти різних горизонтальних рядів (s3).

Окремо виділяються наступні групи:

• Сполучаючі суміжні контакти одного горизонтального ряду (s4).

• Сполучаючі контакти різних горизонтальних рядів, які знаходяться на одній вертикалі (т. е. з однаковими значеннями x координат) або для яких різниця їх x координат дорівнює відстані між двома сусідніми контактами ряду (s5 і s6).

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

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

Спочатку ГС усіх з'єднань розподіляються по каналам, потім уточнюється локалізація кожної ГС в каналі і проводиться їх трасування з урахуванням локализації. Розподіл з'єднань по каналах. Будемо щитать, що з'єднання призначене каналу Кr, якщо ГС цього з'єднання проводитиметься в досліджуваному каналі.

З'єднання перших двох груп (s1 і s2, на малюнок 2.2) призначаються каналу, в якому знаходяться контакти, що сполучаються ними. З'єднання третьої групи, які з’єднують контакти каналів Кi і kj, можуть бути назначені будь якому з цих каналів. Розподіл зв’язків проводиться для рівномірного заповнення горизонтальних каналів.

Вважатимемо, що з'єднання si першої або .другої групи, що сполучає контакти з х координатами x1 і x2 (x1<x2), проходить через переріз ri(х) каналу Кi, якщо ці контакти знаходяться в цьому каналі і Х1<х<Х2. Після розподілу з'єднань першої і другої груп по каналах відомі усі t'i(x) числа з'єднань, проходячих через усі перерізи _ri(х). Тоді відносні пропускні здібності кожного перерізу рівні

2.5

Нехай з'єднання третьої групи si сполучає контакти каналів

К_i и К_j, с xкоординатами X₁ и X₂, (x₁<х₂). Обозначим через R¹ (рисунок 2.4) безліч перерізів

r_i (х), где x₁<x<x₂ Залежно від каналу, в котрий буде призначено з'єднання si_, воно проходитиме через перерізи безлічі R'i, або R'j.

Нехай tзi(x) число з'єднань si третьої групи, які підключені до контакту каналу Кi, і ri(x)(^Rli. Якщо прийняти, що вірогідність призначення такого з'єднання _si каналу _Кi дорівнює 0,5, можна підрохувати імовірнісні пропускні здібності усіх січений

2.6

Розподіл з'єднань третьої групи є послідовним, т. е. вони розглядаються по одному. Нехай розглядається з'єднання si, що сполучає контакти каналів Ki і Кj

Серед усіх перерізів Rli і Rlj визначаються перерізи ri(x')(^Rli і _rj(x'')⁽_Rlj з мінімальними значеннями імовірнісних пропускних здібностей, т. е. "найвужчі" перерізи для з'єднання si в каналах Кi і Кj Для цієї мети обчислюються мінімальні значення імовірнісних пропускних здібностей

З'єднання Si призначається каналу Кi або Kj, для якого «найвужчий» переріз має велику ймовірну пропускну спроможність Після призначення з'єднання s; одному з каналів слід змінити імовірнісні пропускні спосібності перерізів безлічі Rli і R1j,.. Нехай з'єднання назначено каналу А,. Тоді значення імовірнісних пропускних здібностей tPi(x) усіх перерізів tPj(x)(Rli зменшуються, ^a tpi(x) усіх перерізів ri(х)( Rlj збільшуються на 0,5.

Після розподілу усіх з'єднань третьої групи по каналах відомі відносні пропускні можливості ti(x) усіх перерізів горизонтальних каналів, Якщо деякий переріз ri(x) переповнений, т. е. ti(x)<0, розглядається можливість перенесення в другий канал одного із з'єднань, що проходять через цей переріз. Для отримання більше рівномірного заповнення каналів можна застосовувати ітераційне перерозподіл з'єднань по каналах.

Надалі з'єднання одного каналу розглядаються окремо.

Розподіл з'єднань по підканалах. Зв'язок каналу А, призначаються верхньому і нижньому підканалам K₍i і _До(i. При цьому з'єднання в одному підканалі не повинні перетинатися і мають бути враховані пропускні здібності кожного підканалу. Оскільки розглядається тільки один канал, не будемо використовувати індекс каналу у вживаних позначеннях.

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

Рисунок 2.3 Рисунок 2.4

На рисунку 2.3 зображені варіанти взаємних розташуванні горизонтальних складових трас з'єднань першої (s₁), другої (s₂) і третьої (s₃, s₄, s₅, s₆) групи. З'єднання S₁ и з'єднання S₂, S₃, S₅ противоположні противоположні також S₄ і S₅. З'єднання S₃ покриває S₂, S₁ покриває S₄, S₆ покриває з'єднання S₁, S₄, S₅.

Кожному з'єднанню s, досліджуваного каналу поставим у відповідність вершину графа G(A, U  V)a_iA. Тут A— безліч вершин; U— безліч ребер, а V— безліч дуг графа G. Вершини а_i і аj графа сполучені ребром u(U, якщо з'єднання s, і Sj протилежні. Вершини _аi і _аj сполучені дугою v(V, що виходить з вершини аi і входить у вершину аj якщо з'єднання si покриває sj. На малюнку 2.4 приведений граф, відповідний з'єднанню, показаним на малюнку 2.3.

З'єднання каналу розподіляються між підканалами так, щоб з'єднання, призначені в один підканал, не були протилежні і виконувались обмеження на пропускну спроможність підканалів.

Початковими даними для розподілу з'єднань по підканалах служать матриці инциденцій вершин суграфов Gu(A, U) і Gv(Л, V).

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

Позначимо через t((х) і t((x) відносні пропускні здібності верхнього і нижнього підканалів в січенії r(х). Вершина ai(Gu, що відповідає зв’язку si, може бути забарвлена фарбою g({(, (} (в смисле не перевищення пропускної спроможності), якщо в усіх перерізах ^r(x)(R1, через які проходить з'єднання si, пропускні здібності tg(x) більше нуля.

Проведення трас з'єднань. Спочатку проводяться горизонтальні складові усіх з'єднань. Для одного підканалу, наприклад верхнього, чергового каналу Кi формується орієнтований граф G^_i(A^_i, V^_i), вершини якого відповідають з'єднанням цього підканалу, а дуга, що йде від вершини aiA^_i к вершини a_kA^_i означає, що з'єднання s. покриває зв'язок S_k. . Встановлюється порядок трасування з'єднання. Першим проводитиметься з'єднання, для котрого з відповідної вершини графа G^_i не виходить жодна дуга. Наступне з'єднання визначається після виключення з графа цієї вершини і инцидентних їй дуг. Для прикладу, показаного на малюнок 2.5, порядок трасування з'єднань наступний: s₁, s₂, s₃, s₄.

Для проведення трас з'єднань застосовується модифікація променевого алгоритму [1]. Використовується дискретне робоче поле (ДРП), для одного элементарної осередку якого потрібно всього 3 біта оперативної пам'яті ЕОМ. Горизонтальна складова траси проводиться з притиском до вже прокладених трас. Це досягається завданням відповідного пріоритету напрямів. Конфігурації трас при виході з контактів можуть бути задані залежно від вживаної конструкції і технології. Горизонтальні составляющие траси проводяться від контакту до контакту або від контакту до міжшарового переходу в одному підканалі.

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

Якщо трасу провести не вдається, ознаки занятості прокладеної частини траси оставляются в ДРП і

Рисунок 2.5

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

Цим алгоритмом вдається здійснити трасування 7090% усіх з'єднань. Використання цього алгоритму спільне з модифікованим хвилевим алгоритмом дозволяє отримати менше число не побудованих з'єднань.

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

Розглянемо з'єднання двох осередків А і В ДРП усередині мінімального прямокутника, що покриває ці осередки. З кожного осередку поширюватимемо по два світивши, які позначимо A1, A2, В1, B2. Одночасно поширюватимемо усе чотири світивши до зустрічі будь яких двох різнойменних променів A і В, в ячейке Р або до блокування усіх променів (неможливості подальшого їх поширення).

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

Допустимо, що для цього променя маємо наступний заданий порядок ППК : вниз, управо, вгору і вліво. Тоді промінь матиме тенденцію поширення вгору, оскільки путня координата «вниз», задана в ППК першою, може бути присвоєна тільки осередку, розташованому над досліджуваною. При зустрічі з перешкодою і неможливості поширення вгору промінь поверне вліво, оскільки на другому місці в порядку ППК вказана путня координата «управо»: Якщо осередки згори і зліва від досліджуваної виявляться зайнятими, будет проведена спроба повернути промінь вниз, а якщо такий поворот неможливий, — остання спроба повернути промінь управо. При цьому необхідно врахувати, що при расповсюдженні світивши зайнятими вважаються також осередки із вже присвоєними путніми координатами одно іменних променів. Неважко переконатися, що в описаному процесі поширення променя може виникнути ситуація, коли на певному кроці усі сусідні осередки, котрим можуть бути присвоєні путні координати, окажуться зайнятими. У такому разі промінь вважається заблокованим в безвиході.

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

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

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

Після зустрічі двох різнойменних променів в осередку Р траса визначається по напряму путніх координат.

Розглянемо приклад (рисунок 2.6) з'єднання двох осередків А і B за допомогою двопроменевого алгоритму. Використовуватимемо промені із наступними порядками ППК : A1 _вниз, управо; А2_— управо, вниз;

В1 — вгору, вліво; В2 — вліво, вгору.

Рисунок 2.6

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

Після сьомого кроку поширення промінь В2 виявився заблокованим в осередку (6,3), а після одинадцятого кроку промінь B1 достиг осередку Р (5,8), через який раніше пройшов промінь A2. Визначена траса показана суцільною лінією.

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

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

Для чергового з'єднання визначається шлях в моделі монтажного простору між двома підмножиствами електрично сполучених осередків З* і З**, що включающими контактів з'єднання. Отже, трасування з'єднання проводиться таким чином:

а) визначається безліч осередків З*;

б) визначається безліч осередків З**;

в) визначається шлях між будь ким двома осередками великих кількостей З* і З**.

 простір реалізується в пам'яті ЕОМ за допомогою дискретного робочого поля (ДРП). Для кожного осередку великої кількості З відведена необхідна кількість бітів пам'яті. Алфавіт S состоит з набору значень відповідних бітів пам'яти. Відображення Г і М реалізуються програмним шляхом, т. е. правила цих відображень включені в програми поширення хвилі і проведення шляху, а також підготовки ДРП по конструктивних вказівках. При застосуванні моделі N2 і ортогональних і діагональних напрямів сусідні осередки для з'(функція сусідство N), т. е. n=8.

Якщо в одному шарі використовується усі напрями, необхідно, щоб будь які дві пересічні траси перетиналися в осередку ДРП. При використанні діагональних напрямів без обмежень і ортогонального ДРП це умова не виконується, оскільки можливий перетин двох діагональних трас в загальній точці чотирьох осередків ДРП. В цьому випадку потрібно використовувати трансформоване ДРП [2], у якому кожній такій точці ставиться у відповідність один додатковий осередок. У цих осередках записується інформація тільки про проведення по них трас діагонального напряму. Відображенням такого осередку в пам'яті ЕОМ може служити один додатковий біт для кожній осередку основного ДРП.

Якщо не дозволяється проведення траси між висновками елементів і МП (тим самим і поряд з ними) під кутом 45°, то можна заборонити використання діагональних напрямів в осередках безлічі Cs (у осередках, що мають загальні ребра з осередками Сp можливих МП).

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

У числі вхідних параметрів такої програми повинен бути масив технологічних обмежень (ТЕ). На відміну від інших гнучка програма трасування включає блок налаштування на фіксовану технологію і ряд паралельних гілок на кроках розповсюдження хвилі і на етапі проведення шляху. Блок настройки на технологію застосовується при початковій генерації програми або при зміні масиву технологічних обмежень. Функції, що виконуються таким блоком, можна умовно розділити на три групи.

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

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

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

Принцип побудови подібної програми не лімітірує можливі технологічні обмеження. У ефективній програмі подібного роду їх кількість може досягати декількох десятків. Для побудови ефективних програм трасування в них має бути передбачена можливість перетасування і автоматичного коригування непроведенних з'єднань. Для цього необхідно стирати з ДРП деякі траси, а також пов'язані з ними ознаки ТЕ. Останнє обумовлене необхідністю мати інформацію не лише про вид заборони, але і про те, яка сусідня траса його викликала. Безпосереднє занесення даних про таку трасу в осередок зв’язано X. з великим об'ємом пам'яті, а робота із спеціальними масивами різко збільшує час трасування. По цьому використовується спеціальна структура для відображення ДРП. Кожен осередок займає одне машинне слово (4 байти) пам'яті ЕОМ. Причому перший і третій байти в цілях економії пам'яті мають потрійне значення залежно від спеціальних ознак, які указаны, відповідно, в нульовому і другому байтах.

Потрійне використання одних і тих же бітів пам'яті можливе тому, що на окремих етапах трасування в одному осередку ДРП повинна зберігатися різна інформація.

Заборона для проведення траси через осередок може бути викликана двома причинами. По перше, проводити трасу не дозволяє конструкція монтажного простору; подруге, заборона викликана ТЕ і створений трасами, проведеними в сусідніх осередках. У другому випадку в нижньому ряду ознак першого (чи третього) байта записана одиниця в біті, відповідному напряму до осередку, траса в якій визвала заборона в досліджуваному осередку. При знятті траси, що викликала заборону, одиниця стирається. У осередок можуть бути занесені заборони від декількох трас.

Якщо через осередок проведена траса тоді ознака в середньому ряду ознак першого (чи третього) байта означає, що раніше проведена траса з осередку виходить по напряму, що відповідає напряму ПК.

Блок 1. Вхідним параметром програми трасування служить масив ТЕ. Він складається зі значень альтернатив, що вказують на введення різних ТЕ для конкретного випадку. Наприклад, одиниця в деякому розряді масиву ТЕ означає, що прохід траси поряд з МП по вертикальному напряму не дозволяється; якщо в цьому розряді стоїть нуль, такого обмеження немає.

Для деяких таких альтернатив окремі частини початкової програми можуть виконуватися по різному.

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

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

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

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

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

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

— осередок з* належить С. р, якщо координати х* і у* парні;

— осередок з* належить С. i, якщо х1 і у' непарні;

— у інших випадках Ci(Cs.

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

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

Блок 2. Для чергового з'єднання відомі координати з’єднаних контактів х', у' і х", у". Якщо через осередок з' ¹ з координатами х', у' проведена траса, то за ознаками d',, До. і R визначається безліч пов'язаних осередків З'. У окремому випадку, якщо Г1=Г2=:0, ця множина містить тільки осередки c'Tl і з* (2).

Так само визначаться C для іншого контакту з координатами х", у". Нехай множина C' має меншу потужність, чим C". Якщо це не так, вони міняються місцями. Якщо вимагається підвести з'єднання до будьякої ламелі роз'єму, в множину C' включаються усі вільні осередки, в яких знаходяться ознаки ламелей роз’єму. Для осередків великої кількості C' в ДРП заноситься код ПК .

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

Нехай розглядається черговий осередок C' множини C' для осередку c*. При дослідженні чергового осередку з впорядкованої безлічі сусідніх осередків можливі наступні випадки:

1. Осередок с1 вільна і не має заборон. Тоді осередок c' включається в список C* з тією, що відповідає ПК.

2. У осередку d(u) ознака траси Т або ознака контакту До=1, т. е. осередок належить множині C". Тоді осередку c' привласнюється та, що відповідає ПК, і переходять до процедури проведення шляху.

3. У осередку d(u} ознака заборони C, т. е. занесені заборони для проведення траси. Осередок має бути включений в C*, якщо усі заборони викликані трасами, проведеними в осередках множин C' і C". Для цього по нижньому ряду ознак осередку c' перевіряється, чи є у відповідних сусідніх нею осередках код хвилі A або В. Осередок c' c ПК включається в З*, якщо код хвилі рівний А або У в усіх осередках, від яких викликані заборони в осередку с5.. Для випадку uv, т. е. коли досліджується сусідній осередок іншого шару, додатково слід перевірити, чи можна ставити МП.

4. У інших випадках осередок з' не може бути включена в список С*. Таким чином, є видимими усі осередки, сусідні осередкам великої кількості З'. Проте залишається неперевіреним, чи можна ставити МП в цих сусідніх осередках. Для цього досліджуються осередки с'е еС* і перевіряється, чи можна ставити в них МП, т. е. включати осередок ' в множину З* з відповідною вагою затримки.

Так само складається список C**, і для осередків цього списку в ДРП заноситься ПК F. Тут теж можливі випадки переходу до процедури проведення шляху без поширення хвилі.

Блок 3. Осередки великої кількості C* складають список початкового фронту L. У списку для кожного осередку вказані адреса і вага задержки. Поширення хвилі від осередку починається тільки у тому випадку, якщо вага затримки дорівнює нулю. Інакше осередки переписуються в список наступного фронту, а вага затримки зменшується на одиницю.

Якщо від осередку c'eL можливе поширення хвилі, то залишається список констант переадресації, по яких встановлюються адреси сусідніх осередків с'еД (D), і ПК осередку c* (у) переписується в ДРП. Після цього розглядаються усі ці сусідні осередки.

Осередок с'е A* (D) включається в список Zi, якщо в ній дозволяється досліджуваний напрям (це перевіряється за допомогою маски за ознаками першого або третього байта залежно від шару и) і в нульовому або другому байті (залежно від шару и) стоять нулі. Тоді осередку з привласнюється та, що відповідає ПК і обчислюється вага затримки; ПК і вага записуються в список L. Якщо B'u=F, осередку з' теж привласнюється та, що відповідає ПК, і переходять до процедури проведення шляху. Таким чином перевіряються усі осередки, сусідні осередкам списку L.

Блок 4. Процедура проведення шляху виконується у тому випадку, якщо досягнутий осередок с'С**. Спочатку серед сусідніх осередків відшукується осередок з множини З". Координати осередку множини З" є координатами МП або кінцевої точки відрізку траси. Від цього осередку рухаємося у напрямку до осередку з' і т. д. по ПК, записаним в ДРП, до тих пір, поки ПК не змінюється. Так формується відрізок траси. У осередку, ПК якої відрізняється від попередньої, ставиться МП або починається формування нового відрізку, залежно від значення ПК. У відповідні осередки заносяться ознаки трас і МП, а в сусідніх осередках формуються заборони, викликані цією ознакою.

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

Порядок привласнення путніх координат (порядок ППК). Для ортогонального способу трасування використовується чотири путні координати: вниз, вгору, вліво і управо, і усього існує 4!=24 раз особисті порядки ППК. Мінімальне число кутів в трасі виходить у тому випадку, коли осередки записуються в список фронту L, а потім досліджуються в порядку привласнення ним путніх координат. Тому надалі для усіх порядків ППК приймемо, що фронти хвилі формуються і досліджуються в порядку привласнення ним ПК.

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

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

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

Лінії збору однорідних порядків ППК використовуються при виконанні з'єднань з осередком, розміщеної в будь якому квадраті. Тому саме лінії збору найчастіше викликатимуть блокування контактів.

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

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

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

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

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

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

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

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

Резюмуючи сказане, для практичного застосування можна рекомендувати будь який порядок ППК, де чотири ортогональні ПК мають пріоритет над чотирма діагональними. Пріоритет різних ортогональних ПК Друг на другом і різних діагональних ПК Один над одним може бути будь яким.

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

Зменшити число необґрунтовано застосованих діагональних трас можна, зменшивши до мінімуму число привласнюваних ПК діагонального напряму. Для цього процес формування фронту ділиться на два етапи: а) привласнення всіляких ортогональних путевих координат усім осередкам формованого фронту;

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

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

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

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

Реалізація додаткових обмежень. Додаткові обмеження (обмеження Z) вводяться для підвищення відсотка проведених з'єднань і зменшення часу поширення хвилі. Вони діють тільки на певних етапах трасування, а потім знімаються.

Якщо G=1, то розглядається тільки частина осередків монтажного простору. Задаються контури, що обмежують цю частину осередків, за які хвиля не повинна поширюватися. Тому, щоб створити перешкоду для поширення хвилі, в осередки ДРП, які входять в задані контури, записується будьякий код хвилі від 1 до 9 в обох шарах.

Якщо Я=1, то конструктор повинен задати або повинні бути встановлені програмним шляхом списки осередків, в яких тимчасово заборонене горизонтальне або вертикально напрям траси. Ці списки зазвичай задаються відрізками прямих, що проходять по осередках, що складає списки. Для осередків цих списків в ДРП записуються ознаки ЗГ, і ЗВг.

Якщо iA=lи, то зменшується число досліджуваних сусідніх осередків. Обмеження реалізується зміною под. програми складання впорядкованого списку досліджених сусідніх осередків.