Область наук:
  • Комп'ютер та інформатика
  • Рік видавництва: 2007
    Журнал: Известия Південного федерального університету. Технічні науки

    Наукова стаття на тему 'Адаптивна процедура вибору орієнтації елементів в задачі розміщення'

    Текст наукової роботи на тему «Адаптивна процедура вибору орієнтації елементів в задачі розміщення»

    ?4. Курейчик В.М. Математичне забезпечення конструкторського і технологічного проектування із застосуванням САПР. - М .: Радио и связь, 1990..

    5. Січі н ників В А. Алгоритмізація комбинаторно-оптимізаційних задач при проектуванні ЕОМ і систем. - М .: Изд-во МГТУ ім. Баумана, 2001..

    6. Бар інше С.В., Курейчик В.М., Гладков .ЛАКомпоновка МЕМ на основі ітераційної кластеризації з урахуванням тимчасових затримок. Известия ТТІ ПФУ, 2006.

    С.А. Степаненко, В.Б. Лебедєв

    АДАПТИВНА ПРОЦЕДУРА ВІДБОРУ ОРІЄНТАЦІЇ ЕЛЕМЕНТІВ В

    ЗАДАЧІ РОЗМІЩЕННЯ *

    .

    процесі проектування НВІС, оскільки вона визначає межсоединения, які до теперішнього часу стали <зкім місцем », що визначає продуктивність схем в субмікронних технологіях [1-2]. Проблема розміщення інтенсивно вивчається протягом останніх 30 років. Проте, останні дослідження по,,-ня, дають результати, які далекі від оптимальних [1,3,4]. Тому завдання розміщення залишається як і раніше актуальною.

    . -зом: є безліч елементів M = | i = 1, ... N} з фіксованими раз-

    заходами і безліч ланцюгів C = {ci | i = 1,2, ..., K}, що зв'язують елементи мно-

    M . -

    , , цільова функція: F (х) ^ min. В якості критеріїв оптимізації використовуються загальна площа схеми, сумарна довжина провідників, тимчасові затримки.

    Для уявлення відносного розташування елементів на площині використовується пара послідовностей (Sequence-Pair), цей метод вперше був запропонований Murata і ін. В 1996 році [5]. Подання плану топології за допомогою пари послідовностей складається з двох перестановок цілих чисел < 1,2, ..., N >,< 1,2, ..., N > . Кожен елемент послідовності відповідає номеру прямокутного елемента, розташованого на площині без перекриттів з іншими елементами, де загальна кількість елементів одно N.

    Ця пара послідовностей визначає відносне розташування елементів в просторі, але для упаковки елементів необхідно також знати їх просторову орієнтацію. Просторова орієнтація елементів задається вектором O = {oi | i = 1,2, ..., N}, oi е {1,2,3,4}, 1 < i < N. Таким чином,

    для кожного елемента існує чотири можливих орієнтації (North = 1, East =

    2, South = 3, West = 4).

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

    * Робота виконана за підтримки РФФД (гранти № 05-08-18115, № 07-01-00511) та програм розвитку наукового потенціалу вищої школи 2006-2008 рр. (РНП.2.1.2.3193, РНП 2.1.2.2238).

    Сформулюємо задачу в такий спосіб: для наявної пари послідовностей < 51,52 >, визначальною відносне розташування елементів на площині, потрібно підібрати орієнтації елементів в просторі, тобто значення елементів вектора О, що забезпечують мінімізацію цільової функції Р (X) ^ шт (загальна площа кристала, сумарна довжина провідників, тимчасові затримки).

    Для вирішення поставленого завдання використовується підхід, заснований на моделюванні колективної поведінки автоматів адаптації. Цей підхід був запропонований МЛ. Цетлін [6], який запропонував використовувати імовірнісний (). : -Ренія при удачі (+) і покарання при невдачі (-). Під дією цих сигналів здійснюється перехід АА в нові стани. Стан АА є певною альтернативу вирішення завдання. В процесі адаптації на основі відгуків зовнішнього середовища автомат переходить в стан, відповідне кращої альтер-.

    пошукових алгоритмів [6,7].

    Уявімо формулювання завдання у вигляді адаптивної системи, що працює на основі моделювання колективної поведінки автоматів адаптації.

    Безліч елементів М з фіксуванням ими розмірами, пара послідовностей < 51,52 > і орієнтації модулів Про однозначно визначають розміщення елементів на площині.

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

    Як об'єкти адаптації будемо розглядати модулі mi. Кожен об'єкт може бути в одному з чотирьох альтернативних станів (Д, А2, А3, А4). Стан об'єкта адаптації відповідає обраній альтернативі (орієнтації).

    Глобальна мета колективу автоматів адаптації визначається цільовою функцією задачі розміщення. В якості цільової функції будемо розглядати: 1) загальна площа кристала; 2) сумарна довжина провідників.

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

    Для кожного об'єкта адаптації mi середовищем буде безліч взаємодіючих один з одним і з ним самими модулів Mi = М \ mi. стан середовища

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

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

    Адаптивний алгоритм настройки орієнтації елементів з метою мінімізації розмірів схеми. Оче видно, при мінімізації загальної площі мікросхеми нас будуть цікавити тільки дві можливі орієнтації модулів: 1) North = South; 2) East = West, таким чином, наступні стану автоматів

    адаптації мають однакове перевагу: A1 = A3 і A2 = A4 .

    Оцінка станів об'єктів адаптації проводиться таким чином. У наявних графах горизонтальних H (X, EH) і вертикальних V (X, EV) обмежень необхідно знайти безліч критичних шляхів. Критичним шляхом будемо називати такий шлях в графі обмежень, який починається в вершині, яка не має вхідних ребер, і закінчується в вершині, яка не має вихідних ребер. Ширина схеми визначається шляхом максимальної довжини (при визначенні довжини шляху підсумовується ширина елементів) в графі горизонтальних обмежень. Висота схеми визначається шляхом максимальної довжини (при визначенні довжини шляху підсумовується висота елементів) в графі вертикальних обмежень.

    Визначимо безліч критичних шляхів у графі горизонтальних ограни, m - WHm ,

    графі вертикальних обмежень, які містять елемент m - WVm. Для мно-Wm

    - JJ / m W V

    WH V, m -

    на орієнтація o е {1,3}, також зробимо перерахунок їх довжин, коли для елемента m задана орієнтація o е {2,4}. Нехай ширина і висота схеми, коли для елемента m задана орієнтація o е {1,3} позначається Widthl3 і Heightl3 відповідно, тоді як ширина і висота схеми, коли для елемента m задана орієнтація o е {2,4}, позначається Width24 і Height24 (як зазначалося раніше, при визначенні площі схеми орієнтації 1, 3 і 2, 4 рівнозначні). тоді віддай перевагу-

    m,

    S = Width X Height має найменше значення. Якщо ж розміри схеми заду-

    (), Кращою буде та орієнтація елемента, при якій ці обмеження не порушуються. Якщо обмеження на розміри схеми порушуються при будь-ориен-m, ,

    величина перевищення розмірів по горизонталі і вертикалі має найменше .

    Далі докладно опишемо, як реалізується механізм адаптації. Для його реалізації кожного модуля mt ставиться у відповідність автомат адаптації AAt з

    двома групами станів {Sj, S2}, що відповідають двом альтернативам A1 і A2. Альтернатива A1 відповідає орієнтації o е {1,3}, а альтернатива A2

    o е {2,4} . -

    Qi,. AAi

    сигнал заохочення (+) або покарання (-) в залежності від стану об'єкта адаптації в середовищі. На рис.1 показана граф схема переходів автомата адаптації. Знаком (+) позначені переходи під дією сигналу заохочення, знаком (-) позначені переходи під дією сигналу покарання.

    (+) (+) ( ') (+) (+)

    А А

    "1 2

    Рис.1. Граф схема переходів автомата адаптації в разі двох альтернатив:

    А1 і А2

    Якщо краща альтернатива збігається з реалізованої в даний , ,

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

    ).

    Локальна мета кожного об'єкта адаптації (модуля mi) - досягти такого зі,. Адаптивний алгоритм настройки орієнтації елементів з метою мінімізації сумарної довжини провідників. Оцінку стану об'єкта адаптації

    mi в середовищі будемо робити в такий спосіб. Для кожного елемента mi визначаємо безліч ланцюгів Zi (Zi З C, С - все безліч ланцюгів) пов'язаних з ним. Вважаючи позиції інших елементів і їх орієнтації фіксованими, міняємо орієнтацію елемента mi і для кожної орієнтації з безлічі

    О = {1,2,3,4} визначаємо сумарну довжину провідників кіл безлічі Zi: HPWL (Zi). Бажана орієнтація елемента mi - орієнтація, для якої величина HPWL (Zi) має мінімальне значення.

    Для реалізації механізму адаптації кожного модуля mi ставиться у відповідність автомат адаптації А1 з чотирма групами станів 51, 52, 53, 54,

    які відповідають чотирьом альтернативам. Число станів в групі задається параметром до, званим глибиною пам'яті. На вхід автомата адаптації подається (+) (-) -таціі (модуля mi) в середовищі. На рис.2 показана граф схема переходів автомата адаптації.

    Методика вироблення керуючих сигналів полягає в наступному. Якщо краща альтернатива (у відповідності зі значеннями HPWL (Zi)) збігається з реалізованої в даний момент альтернативою, то виробляється сигнал заохочення, в іншому випадку - покарання.

    Локальна мета кожного об'єкта адаптації (модуля mi) - досягти такого зі, .

    А1 А2 А3 А

    Рис.2. Граф схема переходів автомата адаптації (для чотирьох можливих

    альтернатив)

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

    1. Для кожного автомата адаптації визначаються кращі ориен-

    .

    2. Проводиться вироблення керуючих сигналів заохочення або наказу-

    .

    3. Під дією керуючого сигналу здійснюються переходи в авто-

    .

    4. Відповідно до станами автоматів адаптації реалізуються альтер-

    mi . . .

    Потім проводиться розміщення елементів.

    , -, , на малюнку (див. рис.2), а визначення переважної орієнтації проводиться на основі врахування як розмірів схеми, так і довжини провідників.

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

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Jason Cong, Joseph R., Shinnerl і Min Xie (UCLA Computer Science), Tim Kong (Magma Design Automation) і Xin Yuan (IBM Corporation, Microelectronics Division). Large-Scale Circuit Placement. ACM Transactions on Design Automation of Electronic Systems, Vol. 10, No. 2, April 2005.

    2. Adya S. N., Yildiz M., Markov I. L., Villarrubia P. G., Parakh P. N., Madden P. H. Benchmarking for large-scale placement and beyond. In Proceedings of the International Symposium on Physical Design. ACM, Monterey, 95-103., 2003.

    3. J. Cong, T. Kong, J. R. Shinnerl, M. Xie, and X. Yuan. Large-scale circuit placement: Gap and promise. in Proc. of the International Conference on Computer-Aided Design, November 2003.

    4. Chang C. C., Cong J. і Xie M. 2003. Optimality and scalability study of existing placement algorithms. In Proceedings of the Asia South Pacific Design Automation Conference. 621-627.

    5. Hiroshi Murata, Kunihiro Fujiyoshi, Shigetoshi Nakatake, Yoji Kajitani. VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair. IEEE "Transactions on computer-aided design of integrated circuits and systems", vol. 15, no. 12, december тисяча дев'ятсот дев'яносто шість.

    6. Цетлін МЛ. Дослідження з теорії автоматів і моделювання біологічних систем. - М .: Наука, 1969. - 316 с.

    7. Лебедєв Б.К. Адаптація в САПР. Монографія. - Таганрог: Изд-во ТРТУ, 1999. - 160 с.

    Е.А. Зубков, О.Б. Лебедєв

    Імовірнісний СТАТИСТИЧЕСКИЙ ПІДХІД ДО часу

    АНАЛІЗУ КІЛ '

    . -

    ня розміру активних елементів і підвищення ступеня інтеграції привносить нові проблеми в процес проектування і розробки. Деяких проблем не було раніше, деякі придбали велику значимість. Ефект ємнісних перехресних перешкод не перестає бути домінуючою проблемою при проектуванні як на рівні блоків, так і на рівні інтеграції кристалів в «системах на чіпі» (SoC). Незважаючи на те, що довжина з'єднань зменшується, вимога до низького шумового порогу в пристроях з низьковольтних харчуванням, збільшилася ставлення паразитної ємності до ємності щодо «землі» з огляду на тонких і вузьких металевих доріжок і жорсткі вимоги до функціонування специфічних схем і сигналів роблять перехресні перешкоди одним з найважливіших параметрів проектування.

    Часовий аналіз поведінки схем ускладнений так само тим, що при наближенні до нано-метровим масштабами, розкид параметрів кристалів збільшується (з огляду на технологічні особливості виготовлення НВІС, наприклад, нерівномірності розподілу присадок в напівпровіднику, неоднорідності товщини,), -чітельному відхилення реальних і розрахованих інструментальними засобами затримок сигналу. Як показує практика промислового виготовлення, таке відхилення може досягати 30%, що є недопустимим збільшує вартість готових кристалів, внаслідок меншого числа виходу «придатних» кристалів 1.

    ,

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

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

    * Робота виконана за підтримки РФФД (гранти № 05-08-18115, № 06-01-00272) та програм розвитку наукового потенціалу вищої школи 2006-2008 рр. (РНП.2.1.2.3193, РНП 2.1.2.2238).


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

    Завантажити