Променевий алгоритм трасування - Лекція основні поняття та визначення

Променевий алгоритм трасування

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

Побудова шляху починають від осередкуСдо точокАіВ. Виберемо для точокАіВпо два промені з протилежними напрямками:А(1) ,А(2) ,В(1),В(2) (рис. 47).

ПроменіА(1) іВ(2) зустрічаються в осередкуС(рис.47). Зазвичай променевий алгоритм дозволяє побудувати до 80% трас.

^Евристичні алгоритми трасування

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

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

На кожному кроці з-поміж вільних осередків вибирають ту, в якій відстань до осередку-мети зменшується на максимально можливу величину. Якщо на шляху зустрічається перешкода, то його обходять за першим вільним напрямком, визначаючи стан сусідніх осередків у порядку обраного пріоритету (рис.48, шляхи І, ІІ шлях III – отриманий за хвильовим алгоритмом з урахуванням мінімуму вигинів).

^ При побудові траси можуть бути використані додаткові критерії.

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

2. Побудова колії з мінімальною кількістю згинів. У цьому випадку вага незайнятого осередкуk-го фронту дорівнює вазі сусіднього осередку (k–1)-го фронту, якщо колійна координата не змінюється, і (k+1)-го - інакше.

ЛЕКЦІЯ 23. Канальне трасування

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

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

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

^ Канальне трасування зазвичай складається з двох основних етапів:

1) попереднього трасування;

2) трасування всередині каналів.

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

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

^ Трасуваннявсередині каналу, або остаточне трасування, розподіляє всі відрізки з'єднань магістралями деякого каналу.

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

^ Оптимальне рішення найпростіше дає наступна модифікаціяметоду інтервалів.

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

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

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

В даний час канальне трасування знайшло широке застосування при проектуванні ВІС. Часто елементи БІС компонуються та розміщуються в лінійках. Між лінійками виділяються вільні області, які повинні забезпечити 100% розведення сполук. Такі області утворюють канали, на межі яких розташовані висновки, що вимагають з'єднання трасами всередині каналу. Тому недостатньо розмістити всі з'єднання на горизонтальних магістралях, необхідно також в іншому шарі сформувати вертикалі для приєднання до висновків і переходу в сусідні канали. При цьому неприпустимо накладання двох вертикалей різних з'єднань одна над одною. Це створює суттєві труднощі для вибору магістралей.

Головним критерієм проектування конструкцій БІС є мінімізація загальної площі кристала. У цій площі потрібно помістити всі елементи схеми та розвести всі необхідні з'єднання між висновками цих елементів. Щодо трасування, то його головне завдання – розвести всі з'єднання з використанням мінімального числа магістралей. Метод інтервалів тут не дає оптимальних результатів.

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

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

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