Огляд алгоритмів кластеризації схем на основі дерева оптимального згортання

Рис. 5. Представлення структури даних дерева згортання

 

 

3. Осбливості програмної реалізації

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

Для побудови пари елементів визначається значення її критерію згортання, і пара додається  до списку пар. Для ефективнішого  опрацювання списку пар посилання  на ці пари групуються за значенням  критерію (рис. 5). Формуються блоки посилання (K) на пари (D) з однаковим значенням  критерію.

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

Рис. 6. Групування списку пар за значенням критерію

Для підвищення ефективності визначення пар для  модифікації застосовуємо підхід, при  якому посилання на пари групуються за значенням назв елементів. Доступ до пар здійснюється за допомогою  масиву, аналогічного до масиву блоків значень критеріїв. У цьому випадку  блоки об'єднують у пари, в яких присутні одинакові елементи чи кластери. Схема групування списку пар відносно елементів, які утворюють пару, аналогічна до схеми на рис. 6.

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

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

 

4. Експериментальні дослідження процесу згортання схеми

Дослідження проводились на основі реальних схем фірми ibm на пакеті з 18 тестів ibm01- ibm18. Розмірність  тестів знаходиться в діапазоні  від 12752 до 210613 логічних елементів. У  таблиці наведено характеристики тестів, затрати часу на побудову дерева згортання, загальний час (побудова списку елементів, зв’язків, пар елементів, дерева згортання). За критерій згортання вибрано різницю  внутрішніх і зовнішніх зв’язків.

η1 = E^Ext(P_T) – E^Int(P_T).

 

Таблиця 10

Згортання найкращих  пар елементів згідно з критерієм

 

Рисунки 6–8 ілюструють графіки залежності часу побудови дерева згортання від  кількості елементів, зв’язків та утворених  пар схеми. Як бачимо, залежність хоча і є показниковою, маємо невеликий степінь (1,55) , що робить алгоритм придатним для розв’язування задач великої розмірності.

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

 

 

 

 

 

Рис. 7. Залежність часу побудови дерева згортання від кількості зв’язків схеми

Рис. 8. Залежність часу побудови дерева згортання від кількості пар зв’язаних елементів схеми

 

5. Алгоритми послідовного пакування схем в процесі побудови дерева

оптимального  згортання схем

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

 

 

Основні кроки алгоритму є такими:

6. Алгоритми послідовного пакування схем на основі побудованого

дерева  оптимального згортання

Ідея запропонованого  методу полягає у послідовному виділенні  підсхем, що задовольняють потрібний розв’язок або є близькими до нього. Для цього будують дерево оптимального згортання схем. На основі інформації, що дає дерево оптимального згортання, шукають підсхему, що задовольняє або є близькою до заданих обмежень. Цей пошук полягає в спуску із верхнього рівня дерева на нижчі рівні дерева оптимального згортання схем. Знайдена підсхема (кластер) відділяється від решти елементів дерева; для елементів, що не увійшли до знайденої підсхеми, будуємо дерево оптимального згортання схем. Цей процес триває циклічно доки не буде знайдено всіх підсхе. Для підсхем, кількість елементів в яких є меншою або більшою за потрібну, добираємо або вилучаємо елементи.

Основні кроки алгоритму є такими:

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

Рис. 9. Дерево оптимального згортання із виділеною першою підсхемою

Рис. 9а. Дерево оптимального згортання із елементів між двома знайденими підсхемами

 

 

 

Рис. 9б. Розподіл залишку

 

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

 

 

 

 

 

 

 

 

 

 

 

 

Висновок

При виконанні  курсової роботи було розглянуто алгоритми кластеризаціїї схем на основі дерева оптимального згортання та особливості алгоритмічної та програмної реалізації побудови дерева оптимального згортання схеми. Експериментальні дослідження і тести алгоритму дають добрі результати. Також було розглянуто декілька підходів програмної реалізації алгоритму згортання схем. Проведено експериментальні дослідження з різними значеннями параметрів.

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

 

 

 

 

 

 

 

 

 

 

 

 

Література

1. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. – Львов: Вища школа. Изд-во при Львов. гос. ун-те, Львів. 1981. – 168 с.
2. Базилевич Р.П., Подольський І.В., Ієрархічна кластеризація – ефективний засіб розв’язування неполіноміальних комбінаторних задач схемного типу високої розмірності // Штучний інтелект, НАН України, № 3, 2002. – С. 474–483.
3. Базилевич Р.П., Подольський І.В. Особливості організації пакету программ для ієрархічної кластеризації схем // Вісник НУЛП “Радіоелектроніка та телекомунікації”, №440, 2002. – Львів. – С. 139–144.
4. Charles J. Alpert,The ISPD98 Circuit Benchmark Suite. ISPD98 Monterey CA USA, 1998.
5. R.. P. Bazylevych, R . A . Melnyk and O. G. Rybak. “Circuit Partitioning for FPGAs by the Optimal Circuit Reduction Method”, VLSID DESIGN 2000, Vol. 11, No. 3, pp. 237–248.