Область наук:
  • Математика
  • Рік видавництва: 1998
    Журнал: Известия Південного федерального університету. Технічні науки
    Наукова стаття на тему 'Алгоритм видалення циклів у графі вертикальних обмежень завдання трасування багатошарового каналу'

    Текст наукової роботи на тему «Алгоритм видалення циклів у графі вертикальних обмежень завдання трасування багатошарового каналу»

    ?УДК 621.3.049.777.14.001.63: 681.3

    Марченко А.М., Плис А.П.

    Алгоритм видалення циклів у графі вертикальних обмежень завдання трасування багатошарового каналу

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

    Одним з важливих етапів автоматизованого проектування топології НВІС є трасування каналів. Каналом називається однозв'язна прямокутна область на поверхні кристала, призначена для з'єднання контактів, що належать одній і тій же ланцюга. У першій постановці завдання контакти розташовувалися на двох протилежних сторонах каналу, а трасування була дозволена в двох комутаційних шарах. При цьому в одному шарі розміщувалися горизонтальні сегменти з'єднань, а в іншому - вертикальні. Такий канал називається HV - каналом [1].

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

    1 .Построеніе графа вертикальних обмежень.

    2. Видалення циклів з графа вертикальних обмежень.

    3. Укладання горизонтальних сегментів в канапе.

    Відомо багато евристичних алгоритмів канальної трасування, які ефективно вирішують задачу укладання горизонтальних сегментів за умови, що граф вертикальних обмежень не містить циклів [2-4]. У той же час проблема побудови графа вертикальних обмежень і видалення з нього циклів вивчена недостатньо повно. У міру вдосконалення технології виготовлення НВІС проблема канальної трасування постійно ускладнюється. Наприклад, збільшується число комутаційних шарів, дозволяється порушувати прийняту модель розшарування з'єднань, контакти можуть перебувати на будь-якій стороні каналу і в будь-якому шарі. Перераховані нові технологічні вимоги призводять до ускладнення графа вертикальних обмежень і перетворюють проблему його перетворення до ациклічні увазі у вкрай актуальну.

    Граф вертикальних обмежень (Vertical Constraints Graph) це граф такого вигляду: VCG = (X, U), де X - безліч вершин, відповідних горизонтальним сегментам ланцюгів, U безліч орієнтованих ребер. У разі двуслойного каналу з прийнятим розшаруванням HV ребро UjDU з'єднує вершини xm, xnD X, якщо існує пара

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

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

    Рис.1. Вертикальний розріз УУН каналу і його УСС.

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

    Завдання приведення до ациклічні увазі (задача 2) може бути сформульована таким чином: використовуючи інформацію про ланцюгах в каналі і про графа вертикальних обмежень, так змінити конфігурацію ланцюгів, щоб відповідний УСй не мав Циклов.

    Основна ідея, покладена в основу алгоритмів вирішення цього завдання, полягає в розщепленні вершини графа, яка бере участь у створенні циклу, на дві або більше частини. Це відповідає поділу горизонтального сегмента на два або більше нових сегмента. Такі механізми були запропоновані Дойчем [2] (термінальний доглег) і пресом [5] (нетермінальний доглег).

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

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

    а2 Ь2

    Ь2

    с11

    с! 3

    аЗ

    Рис.2. Приклад каналу з контактами на бічних сторонах і його УСС.

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

    1. Якщо в VCG немає циклів або вже розглянуті всі його вершини, ЩЦ завершити роботу алгоритму.

    2. Знайти критичну вершину в VCG, вибираючи серед ще не розглянутих вершин.

    3. Побудувати розширений граф вертикальних обмежень.

    4. Побудувати локальний граф контактів.

    5. Якщо в локальному графі контактів немає петель, mg розфарбувати його в мінімальне число кольорів, інакше повернутися на крок I.

    6. Розщепити вершину відповідно до кольорів контактів.

    7. Створити вертикальне з'єднання для доглега, якщо це можливо, і повернутися на крок 1.

    Розглянемо окремі кроки алгоритму більш детально. На кроці 2 для кожної ітерації вибирається критична вершина в VCG. Критерієм вибору є значення наступної функції:

    f = cycles01 * width'P * priority * ^, де

    cycles - кількість циклів, що проходять через дану вершину, width - ширина, priority - пріоритет відповідного кола,

    а > О, у? 0 - коефіцієнти важливості перерахованих параметрів, які

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

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

    На кроці 3 для знайденої критичної вершини а будується розширений граф вертикальних обмежень (Expanded Vertical Constraints Graph) наступного вигляду: EVCGa =

    ((X \ a) JKa, Ua), де X - безліч вершин вихідного VCG, а - критична вершина VCG, Ка

    - безліч нових вершин, утворених контактами сегмента, відповідного вершині а, Ua - безліч орієнтованих ребер, що з'єднують нові вершини з іншими вершинами

    VCG. Такий граф містить більш детальну інформації про циклах, що проходять через критичну вершину. На малюнку 3 наведено приклад EVCGa для каналу, показаного на

    малюнку 2.

    На кроці 4 будується локальний граф контактів для критичної вершини a (Local Pin Graph): LPGa = (Ka, Va), де Va безліч неорієнтованих ребер. ребро VjDVa

    з'єднує вершини kjj ,, kn G Ка, якщо в графі EVCGa існує шлях між вершинами 1 ^ і

    kn. Локальний граф для вершини а зображений на малюнку 3.

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

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

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

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

    Якщо локальний граф контактів не містить непарних циклів, то, по теоремі Кеніга [6], він може бути розфарбований в два кольори. У цьому випадку досить бінарного доглега. В інших випадках потрібно мульти-доглег. Приклад розмальовки локального графа контактів для вершини а показаний на малюнку 3.

    Граф вертикальних обмежень після однієї процедури мульти-доглега зображений на малюнку 3. Критична вершина а розщеплена на три нові вершини (а ', а ", а'") відповідно до розфарбуванням графа ЬРй », а ребра, що відносяться до а, побудовані заново для трьох нових вершин.

    В

    Ріс.З. Основні етапи алгоритму: а - розширений граф ЕУССа, б - локальний граф контактів ЬРСа, в - отриманий ациклічний УСС.

    Щоб завершити процедуру мульти-доглега, необхідно знайти місце для вертикального з'єднання між новими сегментами. Це завдання вирішується на етапі 7 відповідно до [5].

    У загальному випадку ітерації повторюються до тих пір, поки не будуть видалені всі цикли. Граф, розглянутий в нашому прикладі, був приведений до ациклічні увазі за один крок. Після цього було вирішено завдання укладання горизонтальних сегментів в каналі. Результат канальної трасування показаний на малюнку 4. Необхідно відзначити, що це рішення не вдається отримати раніше відомими методами.

    А2 Ь2 аЗ

    сіЗ АЕ

    Ріс.4.Трассіровка прикладу

    Алгоритм мульти-доглега був реалізований на мові С ++. На рис. 5 представлений приклад каналу, який є складним для завдання видалення циклів. Контакти фіксовані на верхній і нижній і впорядковані на лівій і правій сторонах, УСС містить 33 циклу. Алгоритм мульти-доглега видаляє цикли в цьому прикладі за 9 ітерацій.

    1 2345 6789 10

    10 9876 54321

    Ріс.5.Трассіровка складного прикладу

    Розроблений алгоритм приведення VCG до ациклічні увазі забезпечує, на відміну від відомих алгоритмів, трасування багатошарових каналів з контактами, розташованими на будь-якій стороні і в будь-якому комутаційному шарі, що є в даний час необхідним технологічним умовою застосування САПР НВІС.

    література

    1. 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.

    2. Deutsch D.N. "A Dogleg Channel Router" in Proc. 13th Design Automat. Conf. June 1976, pp. 425-433.

    3. T.Yoshimura, E. S. Kuh "Efficient algorithm for channel routing", IEEE Transactions on Computer-Aided Design, CAD-1 (l): 25-30, January 1982.

    4. H.H.Chen, E. Kuh "Glitter: A gridless variable-width channel routing", IEEE Transactions on Computer-Aided Design, CAD-5 (4): 459-465, 1986.

    5. Bryan Preas "Channel Routing With Non-Terminal Doglegs", Proc. European Design Automation Conference (EDAC), March 1990, pp. 451-458.

    6. Берж К. "Теорія графів і її застосування", Іноземна Література, Москва, 1962.


    Завантажити оригінал статті:

    Завантажити