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

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

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

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

    , -

    ,

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

    ,

    оцінки затримки сигналу в ланцюзі, що піддається впливу шуму за час в 23 рази менше, ніж при використанні статичного часового аналізу [1].

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

    1. M. Ringe, T. Lindenkreuz, E. Barke "Static Timing Analysis Taking Crosstalk into Account", DATE 2000, p. 451, 2000..

    2. Sachin S. Sapatnekar, "Capturing the Effect of Crosstalk on Delay", Proc. of the 13th Int. Conference on VLSI Design, p.364, 2000..

    3. L. H. Chen and M. Marek-Sadowska. "Aggressor Alignment for Worst-Case Crosstalk Noise". newblock IEEE Trans. on Computer-Aided Design, Vol.20: pp.612-621, May 2001.

    4.. .,. . "",

    доповідей міжнародної конференції "Інтелектуальні САПР", AIS'05 / CAD, 2005.

    5. Janet Meiling Wang, Omar Hafiz, Pinhong Chen, "A Non-iterative Model for Switching Window Computation with Crosstalk Noise", ASPDAC'04 pp. 844-849, 2004.

    M.B. Рибальченко

    АЛГОРИТМ КОМПОНУВАННЯ, враховувати тимчасові ПАРАМЕТРИ НА ОСНОВІ розбиття "Конус" СХЕМИ *

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

    [1].

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

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

    * Робота виконана за підтримки програми розвитку наукового потенціалу вищої школи РНП.2.1.2.3193

    Известия ТРТУ _____________________________________________ Тематичний випуск

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

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

    t max ____ t ^

    critical critical (i)

    Size

    Costp = ---------- _ max, (2)

    p IOp

    SizeP < MaxSize, (3)

    IOP < MaxIO, (4)

    де

    tcriticai - затримка критичного шляху в вихідної комутаційної схемою;

    max

    tcriticai - затримка цього шляху після розбиття схеми;

    Costp - конструктивний критерій розбиття, відповідний питомій числу зовнішніх зв'язків компоненти;

    Sizep - розмір (число елементів) компоненти розбиття;

    MaxSize - максимально допустимий розмір компоненти розбиття;

    IOP -;

    Max IO - максимально допустиму кількість зовнішніх зв'язків компоненти раз.

    Безпосередній облік критичних за часом затримки шляхів може бути виконаний при використанні орієнтованого графа в якості моделі комму. -ня конусних структур розглянута в [3].

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

    i. . список CRoot всіх первинних виходів, причому розмір цього списку відповідає числу конусів в схемі.

    2.:, -рекривающіхся між собою, а також з областей, отриманих шляхом вирізання цих областей з конусів:

    | Проглядаються всі вузли схеми з кожного вузла в списку CRoot до пров, ,

    CRoot.

    має список міток LL:

    #P (Nd)

    LL (Nd) = U LL (P (Nd)), (5)

    i = i

    де #P (Nd) - число батьків P (Nd) вершини Р з вузла Nd. Якщо в ньому не існує батько з таким списком міток, то вузол Nd додається до списку CRoot, так як це - корінь кластера.

    Ці нові CRoot входи мають розміри списків міток більше, ніж 1. Новий розмір списку CRoot відповідає числу кластерів в схемі;

    | З'єднання в кластери перекриваються конусів відбувається групуванням вузлів з однаковими списками міток. Кожен кластер містить унікальні вузли, які визначаються як:

    jNd | (((Nd), [LL (Nd) = LL (p (Nd),)]) 1

    Cluster. = CRoot, u i,, s, s, u ^, (6)

    ґ [a (LL (Nd) = LL (CRooti) = LL (CRooti))

    де CRoot - об'єднаний корінь кластера Clusteri і P (Nd) i = CRoot, за умови Vi ij (LL (CRoot) nLL (CRoot) = 0)

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

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

    4. ,

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

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

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

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

    1. G. Saucier, D. Brasen, J.P. Hiol. Partitioning with cone structures / Proc. design automation conf., 1993.

    2. K.J. Singh, Sangiovanni-Vincentelli. A heuristic algorithm for the fanout problem / Proc. design automation conf., 1990..

    3. . ., . . , -

    параметром на основі збереження кращих конусів схеми. Известия ТРТУ. - Таганрог: Изд-во ТРТУ, 2002 № 3.

    В.А. Литвиненко, О.В. Рябов

    НАВЧАЛЬНО-ДОСЛІДНИЦЬКА САПР НА ОСНОВІ САПР KICAD *

    У відомих промислових САПР друкованих плат ЕВА і РЕА використовується обмежений набір алгоритмів і методів вирішення завдань конструкторського проектування. Розробка нової системи - це тривалий і трудомісткий процес.

    * Робота виконана за підтримки РФФД (грант №06-01-00272)


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

    Завантажити