Область наук:

  • Математика

  • Рік видавництва: +1997


    Журнал: Известия Південного федерального університету. Технічні науки


    Наукова стаття на тему 'Алгоритм розміщення елементів НВІС'

    Текст наукової роботи на тему «Алгоритм розміщення елементів НВІС»

    ?На підставі вищеописаного алгоритму була розроблена програма на мові C ++ для IBM PC. Експериментальні дослідження показали можливість застосування даного методу для трасування ланцюгів довільної ширини за допомогою хвильових алгоритмів.

    УДК 658.512

    М.М. Рябець Алгоритм розміщення елементів НВІС

    Існуючий підхід до використання матричних БІС, особливо високої інтеграції, призводить до значної втрати площі кристала Як правило, використовується жорстка конструкція БМК з фіксованим розташуванням осередків. Основною причиною низької ефективності такого підходу є складність у перерозподілі розмірів кристала при проектуванні конкретної НВІС {1,2}. Зазвичай застосовуються розподілені площі кристала між каналами в залежності від їх завантаженості між функціональними осередками і каналами Для трасування. Ідея проста, однак при проектуванні універсального КМОП БМК вона досить ефективна за рахунок розподілу функціонального призначення осередків НВІС При використанні бібліотек моделей робочого поля БМК процес проектування істотно наближається до технології повністю замовних БІС і НВІС.

    Однак зменшення вартості .Тимчасовий проектування і досягнення Бажаних електричних параметрів мікросхеми вважається важкою проблемою.

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

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

    До геометричним обмеженням слід віднести розміщення кожної Функціональної осередки всередині кристалу; осередки не повинні перетинатися між собою. Це призводить до вирішення звичайної завдання двовимірної упаковки. Пропоновану завдання розміщення можна представити в наступному вигляді: знайти Мінімум розміщення, такий, що Р задовольняє геометричним обмеженням, ^ = f (Р), 0? R? З, де Р - вектор позиції функціональних осередків, R - оцінка кассіруемое ™.

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

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

    Розглянемо простий алгоритм, який використовує ефективний спосіб розрахунку електричних ланцюгів. Якщо ми використовуємо цільову функцію як квадратичну, тобто можливість представити функцію мети в лаконічному варіанті Ь (х, у) = х1 В «+ у * Ву, де х, у - є п • мірні вектори, х1, у * - транспонований вектори ; В = О - С, причому Б діагональна матриця з'єднань; З матриця зв'язності. Очевидно, що запропонована функція мети можна вирішити. Часто використовують співвідношення, що х1 Вх - це функція мети, а х 'х = 1. Це призводить до формули Лагранжа Ь * = х' В * + А. хт х, яка може бути використана лише для початкового розміщення (до- вектор множників Лагранжа).

    Більш ефективний спосіб вирішення даного завдання полягає в знаходженні оптимуму функції мети шляхом подання її у вигляді схематичного аспекти:

    Ах | = Ь, де А = Ві; Ь = - В12Х2, за умови, що Вп, Віт = В21- подматріци проводимостей пасивної електричного кола, де вектор Х | визначає т модулів для розміщення,

    ХГ • положення фіксованих модулів. Завдання легко вирішується за допомогою використання релаксационного методу, заснованого Гауссом-Зейделя:

    А = А (Ь + I + Ц), де Л - діагональна, позитивно певна матриця, Ь, і відповідно нижня і верхня трикутні матриці. Вектор Х | обчислюється итеративно Х | (К + 1) = МХ | (К) + а,

    де М = \ у) 1 - \ уі), а = Л'Ь;

    У разі ш = 1 рішення зводиться до простого методу Гаусса. Для зменшення числа ітерацій зручно застосувати блоковий метод вирішення вихідного алгебраїчного рівняння. Уявімо вектор Х | як Х | '= (Х | а, Х | Р), тоді аих | а + А | ГХ | р = Ь |,

    А21 Х1а + А22Х1Р = Ьг,

    де Ь (= (Ь |, Ьг) - визначає координати фіксованих модулів на кристалі (або контактні площадки введення - виведення).

    Тут Х | а, Х | р - блоки розбиття і результату рішення можна досягти за одну ітерацію:

    Х |<ж = А | г | (Ь | -А | 2Х | р),

    Х | р = А22'1 (Ьг - А21 Х | ").

    У цій статті пропонується наступний алгоритм розміщення .

    0 °. Вхідні дані: список ланцюгів, бібліотека елементів, ваги ланцюгів, число ітерацій, число рівнів розбиття.

    Вихідні дані: результати розміщення.

    1. Ввести вихідні дані.

    2. Призначити всі модулі у внутрішній блок (всі зовнішні висновки утворюють один зовнішній блок).

    3. Сформувати модифіковану матрицю з'єднань в розрядженому вигляді.

    4. Для кожного рівня розбиття виконати необхідну кількість блокових ітерацій (для першого розбиття виконати один раз).

    4.1. Для кожного внутрішнього блоку перетворити модифіковану матрицю з'єднань.

    4.2. Обчислити праві частини лінійних рівнянь на основі методу Гаусса -Зейделя, враховуючи граничні умови і відображення зовнішніх модулів.

    4.3. Виконати глобальне розміщення.

    4.4. Тимчасово розділити блок на дві частини для подальшого сортування позицій.

    5. Зафіксувати модулі в кожній частині для подальшого розбиття.

    Експериментальні дослідження показали ефективність даного підходу, до

    Наприклад, розміщення 100 елементів НВІС зменшило сумарну довжину

    Известия ТРТУ

    Тематичний випуск

    з'єднань на 10% при скороченні часу рішення на 18% в порівнянні зі звичайними методами дихотомічного поділу і релаксації.

    література

    1. Карамзінський А.Н., Аношин В.М. Універсальний КМОП - базовий матричний кристал для високопродуктивних ЕОМ. // ЕОТ. 1988. Вип.2.

    2. Швидкодіючі матричні БІС і НВІС. Теорія і проектування / Б.М. Файзулаев і ін .; Під загальною редакцією Б.М. Файзулаева і І.П. Шагуріна. М .: Радио и связь, 1989.

    УДК 681.323

    Ю. М. Почтман, А. А. Босов, В. В. Скалозуб, В. В. Холоша Структурний математичне моделювання на основі суперпозиції неперервних функцій однієї змінної

    Стаття містить теоретичні, обчислювальні та прикладні аспекти проблеми математичного структурного моделювання (ЧСЧ) в умовах невизначеності (в областях прогнозування, відновлення залежностей, розпізнавання). У ній запропоновано підхід до вирішення детермінованих завдань МСМ на основі результату роботи А. Н. Колмогорова [1], в якій отримана структура представлення безперервної функції N змінних (N>1) за допомогою Двох операторів: суперпозиції і підсумовування (2№1) безперервних функцій однієї змінної. У цій статті ця структура використана для отримання рішень МСМ-проблеми (алгоритм базової структури БС). Як додаток вирішується завдання МСМ для будівельних конструкцій і прогнозування динамічних параметрів залізничних екіпажів.

    Як відомо, МСМ-проблеми можуть бути вирішені методами еволюційного програмування (ЕП), самоорганізації (метод групового обліку аргументів (МГУА)) та іншими [2]. Ці концепції використовують дві наступні основні ідеї: 1) існування декількох структур рішення; 2) хоча загальна структура моделі невідома, вона може бути отримана на основі заданих елементарних форм і алгоритмів відбору. Ми представляємо підхід до вирішення детермінованих проблем ЧСЧ, заснований на результатах роботи [1]. Далі рішення МСМ проблем проводиться на основі відомої загальної структури виду

    2п + 1 (л >

    Р (Х1, Х2 ........ ХП) = а =? ш] (х]) | (1)

    (-1 V} ш \ /

    Тут функції Р (Х1, Х2, ..., хп), фК ^), ау (х, 0) - безперервні; причому вид всіх аУ0ц) не залежить від виду Р (Х1, Х2, ... ХП): він може бути обраний однаковим для будь-яких Р (Х1, Х2, ... ХП) (наприклад, квадратичні поліноми) Форми функцій ф {2 ) також можуть бути фіксованими (у цій статті також квадратичні поліноми) Коефіцієнти в <р? (20, ац ^)) можуть бути визначені

    або методом найменших квадратів, або за методом мінімуму суми абсолютних значень відхилень, обчислених на послідовностях експериментальних точок Еп = {Рг *, {ХД} п, г = 1..п}

    Основними етапами (і властивостями) БС - алгоритму є наступні:

    1) Параметри об'єкта дослідження поділяються на незалежні групи, Що представляють альтернативні моделі (АМ) .І тому може бути використано відношення толерантності г: 1) Х,) ГХ, |; 2) XkгXj => X] ДХК. В


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

    Завантажити