А.М. Марченко, А.П. Пліс
Розглянуто проблему усунення циклічних конфліктів при трасуванні багатошарового каналу з будь-яким розшаруванням при розміщенні контактів на будь-якій стороні. Запропоновано алгоритм перетворення графа вертикальних обмежень до ациклического увазі шляхом розщеплення його вершини на мінімальне число нових вершин, який, на відміну від відомих, використовує інформацію про контакти ланцюга, відповідної вибраної вершині.
Одним з важливих етапів автоматизованого проектування топології НВІС є трасування каналів. Каналом називається однозв'язна прямокутна область на поверхні кристала, призначена для з'єднання контактів, що належать одній і тій ж ланцюга. У першій постановці завдання контакти розташовувалися на двох протилежних сторонах каналу, а трасування була дозволена в двох комутаційних шарах. При цьому в одному шарі розміщувалися горизонтальні сегменти сполук, а в іншому - вертикальні. Такий канал називається HV - каналом [1].
Якість виконання завдання трасування багато в чому визначає остаточний результат проектування таких широко поширених типів кристалів, як тракти передачі даних, в яких канали займають близько 20% загальної площі. У канальної трасуванні можна виділити три основні завдання:
1. Побудова графа вертикальних обмежень.
2. Видалення циклів з графа вертикальних обмежень.
3. Укладання горизонтальних сегментів в каналі.
Відомо багато евристичних алгоритмів канального трасування, які ефективно вирішують завдання укладання горизонтальних сегментів за умови, що граф вертикальних обмежень не містить циклів [2-4]. У той же час проблема побудови графа вертикальних обмежень і видалення з нього циклів вивчена недостатньо повно. У міру вдосконалення технології виготовлення НВІС проблема канальної трасування постійно ускладнюється. Наприклад, збільшується кількість комутаційних шарів, дозволяється порушувати прийняту модель розшарування сполук, контакти можуть знаходитися на будь-якій стороні каналу і в будь-якому шарі. Перераховані нові технологічні вимоги призводять до ускладнення графа вертикальних обмежень і перетворюють проблему його перетворення до ациклического увазі у вкрай актуальну.
Граф вертикальних обмежень (Vertical Constraints Graph) - це граф наступного виду: VCG = (X, U), де X - множина вершин, відповідних горизонтальним сегментами ланцюгів, U - множина орієнтованих ребер. У разі двуслойного каналу з прийнятим розшаруванням HV ребро ui? U з'єднує вершини xm, xn? X, якщо існує пара протилежних контактів, що належать відповідно горизонтальним сегментами m, n, перший з яких розташований на верхній, а другий - на нижній сторонах каналу.
У багатошаровому каналі можливі більш складні вертикальні обмеження. Якщо контакти розташовані один над іншим у сусідніх вертикальних шарах, що може мати місце в VVH каналі, то порядок відповідних їм горизонтальних сегментів представляється у графі додатковими ребрами так, як це показано на малюнку 1.
Рис.1.
Якщо в каналі існують контакти, розташовані на бічних сторонах, то порядок їх розташування також відображається в графі додатковими ребрами. На малюнку 2 наведено приклад каналу, що містить чотири ланцюги a, b, c, d з контактами на бічних сторонах, і відповідний граф вертикальних обмежень.
Рис. 2.
Завдання приведення VCG до ациклического увазі (завдання 2) може бути сформульована таким чином: використовуючи інформацію про ланцюгах в каналі і про графа вертикальних обмежень, так змінити конфігурацію ланцюгів, щоб відповідний VCG не мав циклів.
Основна ідея, покладена в основу алгоритмів вирішення цього завдання, полягає в розщепленні вершини графа, яка бере участь у створенні циклу, на дві або більше частини. Це відповідає поділу горизонтального сегмента на два або більше нових сегмента. Такі механізми були запропоновані Дойчем [2] (термінальний доглег) і пресом [5] (нетермінальний доглег).
Ці варіанти доглега відрізняються один від одного способами перерозподілу контактів горизонтального сегмента між новими сегментами. Розташування контактів визначає існування і орієнтацію ребер між відповідними вершинами VCG, тому метод поділу контактів на групи в найбільшою мірою впливає на успіх процедури видалення циклів. При термінальному доглеге контакти діляться за ознакою лівий - правий щодо контакту, по якому відбувається розбиття. При цьому в ланцюзі може з'явитися кілька горизонтальних сегментів, але немає гарантії видалення циклів.
При нетермінальним доглеге, у свою чергу, контакти сегмента поділяються на дві групи за ознакою верхній - нижній. Цей метод гарантує видалення всіх циклів, що проходять через розщеплюваних вершину, за умови, що верхні контакти породжують тільки виходять ребра, а нижні - лише вхідні.
Наявність в каналі більше двох комутаційних шарів і контактів на бічних сторонах призводить до того, що контакт може породжувати в VCG вхідні та вихідні ребра одночасно. У цьому разі поділу контактів на верхні і нижні недостатньо і для успішного розбиття вершини потрібен додатковий аналіз графа і, можливо, багаторазовий (мульти-) доглег. У даній статті пропонується алгоритм мульти-доглега, яка здатна ефективно розщеплювати вершини в такій ситуації. Він складається з наступних кроків:
1. Якщо в VCG немає циклів або вже розглянуті всі його вершини, то завершити роботу алгоритму.
2. Знайти критичну вершину в VCG, вибираючи серед ще не розглянутих вершин.
3. Побудувати розширений граф вертикальних обмежень.
4. Побудувати локальний граф контактів. Якщо в локальному графі контактів немає петель, то розфарбувати його в мінімальна кількість кольорів, інакше повернутися на крок 1.
5. Розщепити вершину відповідно до квітами контактів.
6. Створити вертикальне з'єднання для доглега, якщо це можливо, і повернутися на крок 1.
Розглянемо окремі кроки алгоритму більш детально. На кроці 2 для кожної ітерації вибирається критична вершина в VCG. Критерієм вибору є значення наступної функції:
f = cyclesa * width-b * priority-g, де
cycles - кількість циклів, що проходять через дану вершину,
width - ширина, priority - пріоритет відповідного кола,
a> 0, b ³ 0, g ³ 0 - коефіцієнти важливості перерахованих параметрів, які вибираються користувачем в залежності від конкретного завдання.
Визначена таким чином функція вибору дозволяє розщеплювати більшу кількість циклів за одну ітерацію, вибирати для доглега ланцюга меншою ширини, а також не ускладнювати конфігурацію пріоритетних ланцюгів, наприклад ланцюгів землі / харчування.
На кроці 3 для знайденої критичної вершини a будується розширений граф вертикальних обмежень (Expanded Vertical Constraints Graph) наступного вигляду: EVCGa = ((X a)? Ka, Ua), де X - множина вершин вихідного VCG, a - критична вершина VCG, Ka - безліч нових вершин, утворених контактами сегмента, відповідного вершині a, Ua - безліч орієнтованих ребер, що з'єднують нові вершини з іншими вершинами VCG. Такий граф містить більш детальну інформації про цикли, що проходять через критичну вершину. На малюнку 3 наведено приклад EVCGa для каналу, показаного на малюнку 2.
На кроці 4 будується локальний граф контактів для критичної вершини a (Local Pin Graph): LPGa = (Ka, Va), де Va - безліч неорієнтованих ребер. Ребро vi? Va з'єднує вершини km, kn? Ka, якщо в графі EVCGa існує шлях між вершинами km і kn. Локальний граф для вершини a зображений на малюнку 3.
Кожне ребро локального графа контактів відповідає як мінімум одному циклу, що проходить через критичну вершину VCG, і вказує на контакти, що утворюють цей цикл. Таким чином, якщо ребро існує між парою вершин локального графа, то відповідні їм контакти повинні бути призначені в різні групи при розщепленні вершини VCG. У цьому випадку відповідні ребру цикли будуть видалені.
Можливий випадок, коли в локальному графі з'явиться кільце. Петля не може бути вилучена шляхом розбиття контактів на групи, так як контакт не може бути розщеплений на частини. У цьому випадку проходить через вершину цикл не може бути видалений шляхом розщеплення тільки даної вершини.
Використання локального графа контактів дозволяє звести задачу розбиття контактів на групи до задачі розмальовки неорієнтованого графа. Необхідно розфарбувати локальний граф контактів в мінімальне число кольорів так, щоб вершини, з'єднані ребром, виявилися розфарбовані в різні кольори. Розмальовка графа в мінімальна кількість кольорів буде відповідати розподіленню сегмента на мінімальне число частин, достатню для видалення циклів у VCG. Необхідно відзначити, що, незважаючи на складність завдання розмальовки довільного графа в мінімальна кількість кольорів, для даного випадку завдання завжди може бути вирішена методом повного перебору, так як розмірність локального графа контактів визначається числом контактів у ланцюги і для сигнальних ланцюгів зазвичай не перевищує 5.
Якщо локальний граф контактів не містить непарних циклів, то, по теоремі Кеніга [6], він може бути розфарбований у два кольори. У цьому випадку досить бінарного доглега. В інших випадках потрібна мульти-доглег. Приклад розмальовки локального графа контактів для вершини а показаний на малюнку 3.
Граф вертикальних обмежень після однієї процедури мульти-доглега зображений на малюнку 3. Критична вершина a розщеплена на три нові вершини (a ', a'', a''') відповідно до розфарбуванням графа LPGa, а ребра, пов'язані з a, побудовані заново для трьох нових вершин.
Рис.3.
Щоб завершити процедуру мульти-доглега, необхідно знайти місце для вертикального з'єднання між новими сегментами. Це завдання вирішується на кроці 7 згідно з [5].
У загальному випадку ітерації повторюються до тих пір, поки не буде видалено всі цикли. Граф, розглянутий у нашому прикладі, був приведений до ациклического увазі за один крок. Після цього було вирішено завдання укладання горизонтальних сегментів в каналі. Результат канальної трасування зображений на малюнку 4. Необхідно відзначити, що це рішення не вдається отримати раніше відомими методами.
Рис.4.
Алгоритм мульти-доглега був реалізований на мові С + +. На рис. 5 представлений приклад каналу, який є складним для завдання видалення циклів. Контакти фіксовані на верхній і нижній і впорядковані на лівій і правій сторонах, VCG містить 33 циклу. Алгоритм мульти-доглега видаляє цикли в цьому прикладі за 9 ітерацій.
Ріс.5.Трассіровка складного прикладу
Розроблений алгоритм приведення VCG до ациклического увазі забезпечує, на відміну від відомих алгоритмів, трасування багатошарових каналів з контактами, розташованими на будь-якій стороні і в будь-якому комутаційному шарі, що є в даний час необхідним технологічним умовою застосування САПР НВІС.
Список літератури
A. Hashimoto and J. Stivens. "Wire routing by optimization channel assignment within large apertures." Proc. Of the 8th Design automation workshop, pp. 155-163, 1971.
Deutsch DN "A Dogleg Channel Router" in Proc. 13th Design Automat. Conf. June 1976, pp. 425-433.
T. Yoshimura, ES Kuh "Efficient algorithm for channel routing", IEEE Transactions on Computer-Aided Design, CAD-1 (1) :25-30, January 1982.
HHChen, E. Kuh "Glitter: A gridless variable-width channel routing", IEEE Transactions on Computer-Aided Design, CAD-5 (4) :459-465, 1986.
Bryan Preas "Channel Routing With Non-Terminal Doglegs", Proc. European Design Automation Conference (EDAC), March 1990, pp. 451-458.
Берж К. "Теорія графів та її застосування", Іноземна Література, Москва, 1962.