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

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - лежень Андрій Анатолійович, Дуккардт Олександр Миколайович


PROBLEMS KEEPING TIME DELAYS IN CONSTRUCTION DESIGN TASKS

The work deals with the problem of constructing models for assessment and management of time delays in solving the problems of the design phase of the design. The authors offer new models for assessing the time delays that occur on interconnects, for the initial stages of the design problems of design: layout and placement. Using the proposed models for calculating the time delay estimate takes into account the temporal characteristics of the early stages, thus reducing time spent on design, which can improve the results of design engineering.


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

  • Комп'ютер та інформатика

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


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


    Наукова стаття на тему 'Проблеми обліку тимчасових затримок в задачах конструкторського проектування '

    Текст наукової роботи на тему «Проблеми обліку тимчасових затримок в задачах конструкторського проектування»

    ?Shcheglov Sergej Nikolatvich

    Taganrog Institute of Technology - Federal State-Owned Educational Establishment of Higher Vocational Education "Southern Federal University".

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    44, Nekrasovskiy, Taganrog, 347928, Russia.

    Phone: +7863371625.

    The Department of Computer Aided Design; Cand. of Eng. Sc .; Associate Professor.

    681.3.06

    A.A. Лежень, A.H. Дуккардт ПРОБЛЕМИ ОБЛІКУ часових ЗАТРИМОК В ЗАДАЧАХ КОНСТРУКТОРСЬКОГО ПРОЕКТУВАННЯ *

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

    Конструкторське проектування; тимчасові затримки; розбиття; компоновка; розміщення; інтегральні схеми; моделювання.

    A.A. Lezhebokov, A.N. Duckardt PROBLEMS KEEPING TIME DELAYS IN CONSTRUCTION DESIGN TASKS

    The work deals with the problem of constructing models for assessment and management of time delays in solving the problems of the design phase of the design. The authors offer new models for assessing the time delays that occur on interconnects, for the initial stages of the design problems of design: layout and placement. Using the proposed models for calculating the time delay estimate takes into account the temporal characteristics of the early stages, thus reducing time spent on design, which can improve the results of design engineering.

    Design engineering; time delays; partitioning; layout; placement; integrated circuits; simulation.

    .

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

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

    0.09 мікрон! В даний час промисловістю випускається широка але,, -сталле 25x25 мм. Неухильне підвищення ступеня інтеграції НВІС призвело до того, що в них більше 60% загальної тривалості затримки сигналу доводиться на за-

    * Робота виконана за часткової підтримки РФФД (проекти: № 09-01-00509, № 11-01-00122). 108

    тримки в межсоединения. Зростання розміру області, що відводиться для межсоединений, випереджає зростання розміру області, призначеної для активних елементів. У чіпі, що містить 10 мільйонів транзисторів і використовує 4 шари металізації, близько 40% площі відводиться під межсоединения [2].

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

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

    1. Модель оцінки тимчасової затримки для завдання розбиття. В по след-неї час з'явилося багато робіт за рішенням завдання розбиття з урахуванням тимчасових затримок [3,4]. В результаті проведеного аналізу існуючих методів вирішення задачі розбиття, були виявлені наступні проблеми.

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

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

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

    С = | (Уу) [е п Ху Ф еш. (1)

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

    N до

    D = + Y DJkJ, (2)

    i j

    де yi - вага ребра; ei коефіцієнт, який приймає значення 1 або 0, в залежності від того розрізається ребро чи ні; | EK | - кількість ребер в критичних шляхах K; Dj - поточна затримка j-ro критичного шляху; kj - скільки разів відбувалося розрізання критичного шляху j.

    Dj -

    нента. Перший - це затримка вентилів. Затримка вентилів вважається постійного-

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

    яке потрапило в розріз, (ребро відповідає провіднику) у відповідності з наступною формулою:

    D (e) = Re (C- + C), (3)

    де Re - загальний опір провідника e; Ce - загальна ємність провідника е; Ci-загальна ємність витоків кожної ланцюга. Re і Ce обчислюються за формулою:

    Re = r • Le, Ce = c • Le. (4)

    Re Ce . -

    на ланцюзі [14], що з'єднує m елементів визначається за формулою:

    Le = (a * my - р) --- + (a + b), (5)

    a + b

    де a і b - сторони описує елементи прямокутника; a, Р, у -настроечние параметри, обчислені в [15] як a = 1,1, Р = 2,0, у = 0,5. Питомий опір на одиницю довжини провідника вважаємо г = 0,115, питома ємність на одиницю довжини провідника з = 0,00015.

    Для прикладу розрахунків, розглянемо модель, представлену на рис. 1. Для зазначеної схеми і зазначеного варіанту вирішення завдання компонування сумарна оцінка затримки буде дорівнює D = 2 * t12 + 1 * t23 + 1 * t13. Г де оцінка затримки між кожною парою блоків розрахована відповідно до моделі Ельмора, представленої вище. Як координат описує ребро прямокутника використовуються координати центрів блоків, які вводяться оператором при вирішенні задачі.

    1. Модель оцінки тимчасової затримки для задачі розміщення. За д оптимизационной завданням розміщення компонентів НВІС розуміється завдання, в якій необхідно знайти такий розподіл елементів на площині або в лінійці, яке, в заданому сенсі, є найкращим або оптимальним. Відзначимо, що найкращого рішення у всіх сенсах бути не може. Воно може бути прийнято оптимальним на основі заданого критерію розміщення або ЦФ. Для,, -вать модель ланцюга на основі Дерева Штейнера для оцінки тимчасової затримки межсоединений [5,6]. Розглянемо запропоновану модель більш детально.

    Розміщення елементів на дискретній робочому полі (ДРП) здійснюється в стандартні осередки (standard cells), для визначення відстаней між елементами пропонується використовувати Манхеттенську метрику (метрика, яка використовується для «решіток»).

    11G

    Мал. 1. Модель розрахунку тимчасової затримки схеми для задачі розбиття

    Розглянемо приклад роботи алгоритму побудови моделі:

    1. Припустимо, на деякому етапі рішення задачі отримали деякий розміщення 4-х елементів, з'єднаних ланцюгом, в вузли сітки дискретного робочого поля (рис. 2).

    2. Будується модель ланцюга на основі зоряного графа, координати центру обчислюються як середнє арифметичне координат всіх елементів ланцюга.

    3. Так як координати точки центру можуть не збігатися з координатами яче, .

    4. Через цю точку проводиться «стовп», для побудови дерева Штейнера.

    5. Кожен елемент ланцюга зв'язується зі «стовпом Штейнера».

    6. Маємо модель ланцюга на основі дерева Штейнера в Манхеттенський метриці (рис. 3).

    7. Далі обчислюється оцінка тимчасової затримки на контактах Б1 і на межсоединения ланцюга Б2.

    8. Підсумкова затримка обчислюється як сума Б1 і Б2.

    9. Робота алгоритму завершена.

    Мал. 2. Модель ланцюга у вигляді зоряного графа

    .

    Ud (

    Xd.yd)

    6

    UitXi.i

    Про

    /-

    про..

    Uq (x

    Цр (Хр.Ур)

    Про

    ,yq)

    Мал. 3. Модель ланцюга в Манхеттенський метриці для оцінки тимчасової затримки

    між контактами ланцюга

    На рис. 2 і 3 показаний приклад як обчислити затримку між контактами ui і ud в мережі з кількістю контактів k. Ми практично не трассіруем схему, а отримуємо значення оцінки затримки, наближене до значення оцінки для ланцюга, по.

    Покладемо, що: Rd - провідне опір ( «driver resistance»); Cg - ємність навантаження, що складається з ємностей затворів транзисторів на кінцях ланцюга; r -; c - -

    , - ui ud.

    Тимчасова затримка обчислюється в два етапи:

    D (n) = Rd (c * L (Nj) + (k -1) * Cg), (6)

    | Затримка початкового опору заряду ланцюга навантаження і всіх контактів цього ланцюга:

    D2 (Ui, ni) = rC * ld, i + r * ldiCg

    (7)

    | Внутрішня затримка шляху від ш до М за рахунок внутрішньої ємності і внутрішнього опору. Обчислюється для кожної пари елементів ланцюга;

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

    б = ад + X А). (8)

    до

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

    Використання запропонованих моделей дозволяє враховувати тимчасові характеристики на ранніх етапах конструкторського проектування. Що в сукупності з новими методами пошуку [7] дозволить скоротити часові витрати на проектування і підвищити ефективність результатів конструкторського проек-.

    2.

    СПИСОК Норенков ІЛ. Основи автоматизованого проектування. - М .: Изд-во МГТУ ім. Н.е. Баумана, 2006. - 360 с.

    Donath W.E. et al. Timing Driven Placement Using Complete Path Delays Proc. ACM / IEEE DAC, 2008.

    3. Лебедєв Б.К., Дуккардт AM. Розбиття на основі комбінованих генетичних процедур // Известия ТРТУ. - 2006. - № 8 (63). - С. 46-51.

    4. Дуккардт AM. Рішення завдання розбиття на основі процедури «Вибивання» // відом-

    ку ТРТУ. - 2006. - № 6 (61). - C. 63-66.

    5. . .

    // -

    практичної конференції «Інтегровані моделі і м'які обчислення в штучному інтелекті». T. 1. - М .: Физматлит, 2007. - C. 429-436.

    6. . ., . . -

    // III

    науково-технічна конференція «Проблеми розробки перспективних мікро-і на-ноелектронних систем- 2008" (МЕС-2008), 2008 / Збірник наукових праць під заг. ред. АЛ. Стемпковського. - М .: ІППМ РАН, 2008. - C. 130-136.

    7. Курейчик В.М., Біоінспірованний пошук з використанням сценарного підходу. // Известия ПФУ. Технічні науки. - 2010. - № 7 (108) .- С. 7-12.

    Статтю рекомендував до опублікування д.т.н., професор ЮЛ. Чернишов.

    Лежень Андрій Анатолійович

    Технологічний інститут федерального державного автономного освітнього закладу вищої професійної освіти «Південний федеральний університет» в м Таганрозі.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    347928, м Таганрог, Некрасовський, 44.

    .: 88634371651.

    Кафедра систем автоматизованого проектування, к.т.н., асистент.

    Дуккардт Олександр Миколайович E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    Кафедра систем автоматизованого проектування, к.т.н., асистент.

    Lezhebokov Andrey Anatolyevich

    Taganrog Institute of Technology - Federal State-Owned Autonomy Educational Establishment of Higher Vocational Education "Southern Federal University".

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    44, Nekrasovskiy, Taganrog, 347928, Russia.

    Phone: +78634371651.

    The Department of Computer Aided Design; Cand. of Eng. Sc .; Assistant.

    Duckardt Alexander Nikolaevich

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    The Department of Computer Aided Design; Cand. of Eng. Sc .; Assistant.

    УДК 681.3.016: 658.512.2.011.5: 519.711.3

    ..

    ФОРМАЛІЗАЦІЯ ПРОБЛЕМИ ОПТИМІЗАЦІЇ РОЗМІЩЕННЯ ДАНИХ САПР в «хмарі» *

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

    *

    Робота виконана за часткової підтримки РФФД (проект № 11-01-00122).


    Ключові слова: КОНСТРУКТОРСЬКЕ ПРОЕКТУВАННЯ /Тимчасові ЗАТРИМКИ /розбиття /КОМПОНОВКА /РОЗМІЩЕННЯ /ІНТЕГРАЛЬНІ СХЕМИ /МОДЕЛЮВАННЯ /DESIGN ENGINEERING /TIME DELAYS /PARTITIONING /LAYOUT /PLACEMENT /INTEGRATED CIRCUITS /SIMULATION

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

    Завантажити