Алгоритми трасування друкованих плат РЕМ
Завдання трасування полягає в побудові з'єднань між висновками елементів, розміщених в заданому монтажному просторі, відповідно до електричної принципової схеми пристрою при обліку конструктивних обмежень. Зазвичай траса формується у вигляді безлічі пов'язаних відрізків, що з'єднують точки електричного кола. При вирішенні задачі трасування враховуються такі критерії:
1) мінімальна сумарна довжина з'єднань;
2) мінімальне число з'єднань, довжина яких перевищує задане значення;
3) мінімальне число переходів між шарами;
4) мінімальне число шарів;
5) мінімальні паразитні перешкоди;
6) максимальна віддаленість трас з'єднань;
7) число шарів не повинне перевищувати заданого значення;
8) довжина з'єднання не повинна перевищувати заданого значення;
9) рівень перешкод, що наводяться в кожній трасі, не повинен перевищувати допустимого значення;
10) число з'єднань (пайок) до одного висновку не повинно перевищувати заданого значення.
При проектуванні багатошарових структур, як правило, окремо вирішується задача оптимального розшарування, в якій мінімізується показник
де г - номер шару; z - число шарів; М - число ланцюгів в схемі; - характери-стика ступеня перетину k-й і s-й трас;
якщо траси до і s не належать шару r;
якщо траси до і s належать шару r.
Характеристика задається різними величинами, наприклад: пло-щадью перекриття зон реалізації ланцюгів аr і as; числом перетинів повних подграфов ланцюгів аr і as; числом перетинів мінімальних зв'язують мереж аr і as; числом висновків ланцюгів аr і as, що належать перетинанню зон реалізації цих ланцюгів.
У загальній проблемі автоматизації конструкторського проектування трасування з'єднань - це найбільш важке завдання, в якій простежується особливо тісний зв'язок з конструктивно-технологічної реалізацією. Вихідною інформацією завдання трасування в загальному випадку є:
1) список ланцюгів проектованої схеми;
2) параметри конструкцій елементів (форма і геометричні розміри);
3) параметри монтажного простору (допустимі відстані, форма сполук, кількість перетинів і т.п.);
4) дані по розміщенню елементів, (трасування здійснюється між точками, координати яких задані в абсолютних або відносних одиницях).
Завдання трасування має метричний і топологічний аспекти. Метричний аспект пов'язаний з урахуванням конструктивних розмірів елементів, з'єднань і монтажного простору (розміщення). Топологічний аспект пов'язаний з урахуванням обмежень на число допустимих перетинів, число шарів схеми і т.д. тобто пов'язаний з просторовим розташуванням окремих частин і з'єднань схеми. Алгоритмічні методи трасування, незважаючи на їх різноманіття, не гарантують проведення 100% з'єднань. За способом побудови трас методи трасування поділяють на конструктивні та ітераційні.
У послідовних конструктивних алгоритмах траси ланцюгів проводять в певному порядку, одну за одною. Зазвичай прокладку трас починають або з найдовших з'єднань, так як в сильно заповненому монтажному просторі їх важче формувати, або з найкоротших з'єднань, які щільніше заповнюють монтажне простір. Прокладені траси фіксують і при подальшій трассировке розглядають як перешкоди, тобто як зайняті осередки монтажного простору. Таким чином, в послідовних алгоритмах здійснюється локальна оптимізація при прокладанні кожної траси, але в результаті після проведення ряду трас деякі ділянки монтажного простору можуть блокуватися, що не дозволяє виконати трасування автоматично.
В ітераційних алгоритмах після прокладки всіх трас, яка здійсню-ється без урахування взаємного впливу трас, визначається функція якості трасування як зважена сума параметрів траси (довжина, число пе-ресеченій, число перегинів). Після оцінки варіанта трасування найгірші траси видаляються, і процес трасування повторюється з урахуванням безлічі кращих з'єднань як перешкод.
Для вирішення завдань трасування розроблені також алгоритми, в яких об'єднані послідовні та ітераційні процедури - "заважають" траси деформуються або видаляються, тобто змінюється конфігурація вже прокладених з'єднань або черговість прокладки трас.
На рис.1 приведена послідовність застосування методів трасування до різних типів схем і використовуються алгоритми.
Приклади алгоритмів трасування
Більшість відомих універсальних алгоритмів трасування осно-ють на хвильовому алгоритмі визначення шляху (траси з'єднань еле-ментів), що мінімізує деяку багатовимірну функцію якості цього шляху. Ідея хвильового алгоритму ілюструється на рис. 2, де поєднуються елементи А і В, розташовані в точках (1, 4) і (4, 7) регулярного монтажного простору.
Мал. 2. Трасування з'єднань хвильового алгоритму при наявності перешкод
Цифрами 0, 1, 2. 14 показані "фронти" поширення хвилі від точки (1,4) - стан 0, до тих пір поки вона не досягається точки (4, 7) - стан 14. Оптимальна траса виходить з'єднанням точок в зворотній послідовності 14-13-. -1-0, як траса, що має мінімальну довжину, мінімальне число вигинів і забезпечує максимальну щільність монтажу. Штрихами показані траси, мають ту ж довжину, але гірші за іншими критеріями. Модифікації хвильового алгоритму спрямовані на підвищення швидкодії і зменшення необхідного обсягу пам'яті.
Трасування з використанням іншого евристичного алгоритму - променевого - показана на рис. 3. Між сполучаються точками А (6, 3) і В (5, 8) проводиться промінь. При переході до наступної точки монтажного простору визначається напрямок траси, мінімально відрізняється від напрямку променя з урахуванням зазначеного на діаграмі пріоритету (нумерація напрямків) і необхідності обходу перешкод, утворених зайнятими позиціями.
Мал. 3. Трасування з'єднань променевим алгоритмом при наявності перешкод
Штриховий лінією відзначений оптимальний шлях (його довжина в два рази менше першого), прокладений під час проведення променя від В до А, тобто у зворотньому напрямку.
Слід зазначити, що наведені при розгляді постановки задачі трасування критерії оптимальності вводяться не для управління процесом трасування, а лише для оцінки якості отриманого рішення.
У ряді випадків робиться спроба врахувати наступні кроки трасування і організувати паралельну трасування всіх з'єднань. Прикладом є алгоритми, що використовують канальне уявлення магістралей межсоединений.
На рис. 4. показана мережа вертикальних В1, В2, В3 і горизонтальних Г1, Г2, Г3 каналів, на яких наведено з'єднання двох елементів. Монтажне простір з двома шарами горизонтальної та вертикальної комутації і можливістю введення контактних переходів в точках сполучення горизонтальних і вертикальних шарів типова для пристроїв, що реалізуються на двосторонніх друкованих платах, а також для великих гібридних та інтегральних та монолітних інтегральних схем. В алгоритмах, що використовують уявлення про каналах, трасування здійснюється в два етапи: попередня, з метою розподілу трас по каналах при рівномірній їх розвантаженню, і остаточна, в процесі якої уточнюється розташування з'єднань на магістралях каналів.
Мал. 4. Трасування з'єднань з використанням каналів
Особливий тип алгоритмів призначений для трасування з'єднань на площині без перетинань. Вони використовуються при проектуванні однослойного монтажу при наявності в пристрої різнотипних за формою і розмірами елементів.
У зв'язку з тим, що жоден з відомих алгоритмів не гарантує повної трасування при автоматизованому проектуванні, вважається за доцільне, щоб в розвинених системах автоматизованого конструкторського проектування було кілька різних програм трасування і була можливість їх спільного використання при вирішенні однієї задачі. Решта невбитій після трасування з'єднання допрацьовуються конструкторами вручну або в діалоговому режимі взаємодії з ЕОМ.
Слід зазначити, що при використанні САПР час проектування топології пристроїв, що містять 20. 30 ІС, скорочується приблизно на порядок, а для БІС практично немає іншого способу досягнення високої якості проекту і його документації. Однак великим недоліком сучасних систем автоматизованого конструкторського проектування є необхідність величезного обсягу вихідної інформації, яка може готуватися порядку декількох тижнів для БІС з уже розробленої логічної схемою. Для подолання цього недоліку необхідні створення САПР, що з'єднують всі етапи проектування РЕА і мають інтегровану базу даних, що містить інваріантну інформацію, пополняемую в процесі розробки, а також стандартизація найбільш раціональних схемотехнических і конструктивних рішень.