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

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

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

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