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

Міністерство  освіти та науки України

Національний  університет “Львівська політехніка”

Інститут  комп’ютерних наук та інформаційних  технологій

 

 

                                                                                                                 Кафедра: ПЗ

                                                                    

 

Курсова робота

 

з дисципліни: “ Комбінаторні моделі в автоматизованих системах ”

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

 

 

 

 

  Виконав:

ст. гр.

                                                                                                                        

                         

    Перевірив:

                                                                                                                           

 

 

 

 

 

 

 

«Львів – 2010»

Зміст

Вступ………………………………………………………………………………..3

1.Ієрархічна кластерізація…………………………………………………………4

   1.1.Постановка задачі……………………………………………………………4

   1.2. Формулювання задачі……………………………………………………….5

   1.3. Алгоритмізація задачі формування кластерів……………………………..5

   1.4. Формування списку пар елементів/кластерів, зв’язаних між собою ……5

   1.5. Визначення критерію об’єднання для виділених пар…………...........…...6

   1.6. Упорядкування пар за значенням критерію…………………….................6

   1.7. Вибір пар елементів/кластерів для об’єднання……………………………6

   1.8. Вилучення пар елементів із списку впорядкованих пар………………….7

   1.9. Модифікація впорядкованого списку пар…………………………………7

2. Опис структур даних……………………………………………………….....8

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

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

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

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

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

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

Висновок…………………………………………………………………………..17

Література…………………………………………………………………………18 

Вступ

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

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

Для розв’язання  задач можна застосовувати метод  оптимального згортання схеми, який полягає в паралельно-послідовному формуванні підсхем, що мають однакові або близькі за взаємною зв’язністю елементів характеристики. Метод  оптимального згортання схеми виявляє  ієрархічну кластерну структуру  схеми на основі багатокрокового  процесу ідентифікації та об’єднання підсхем, які є щільнішими за інші. Бажано виявити реальні згустки  схеми, їхнє взаємне входження –  менших у більші – та зв’язки між ними. Це сприяє виділенню окремих сильно зв’язних груп, а також вказуватиме на їхнє взаємне входження. Одержання якісних кластерів є не менш важливим за швидкодію роботи алгоритму. Хороші результати кластеризації дають змогу спростити багато інших задач, таких, як декомпозиція, оптимізаційні задачі.

Якість  кластеризації можна оцінювати залежно від якості множини окремих кластерів верхніх рівнів, близьких за розмірами, які не мають входжень один в одного.

 

 

 

 

 

 

 

1.Ієрархічна кластерізація

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

Рис. 1. Приклад представлення кластеризації

Мета кластеризації - побудувати оптимальне розбиття об'єктів на групи.

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

 

1.1. Постановка задачі

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

 

1.2. Формулювання задачі

Більшість реальних складних схем можна представити  як пару: S=(P, E); (1), де P={_p1,…,p_n} –множина елементів, E={e₁,…,e_m} – множина зв’язків між елементами.

Необхідно виявити сильно зв’язні згустки системи та побудувати дерево оптимального згортання T^R, яке відображає ієрархічне входження малих згустків (кластерів) у більші та корінь якого відповідає всій схемі. У випадках, коли система містить кілька незв’язаних підсистем, будується ліс дерев F^R={T^R₁,…,T^R_n}.

 

1.3. Алгоритмізація задачі формування кластерів

Метод оптимального згортання схеми ґрунтується  на виявленні сильно зв’язних згустків схеми – кластерів. На кожному кроці два елементи (кластери) об’єднуються в один, кластери формують дерево оптимального згортання T^R, яке відображає ієрархічне входження малих згустків у більші та корінь якого відповідає всій схемі. Базові кроки алгоритму побудови дерева оптимального згортання схеми T^R є такі:

 

1.4. Формування списку пар елементів/кластерів, зв’язаних між собою

Для побудови пар елементів P_T використовується інформація зі списків NetList i ElementList. Для кожного зв'язка із множини зв'язків існує множина елементів, для яких цей зв'язок є спільним.Net₁={p₁,p₂,p₄,p₈} зв’язок Net₁ формує пари з елементів P_T1=p₁p₂; P_T2=p₁p₄; P_T3=p₁p₈; P_T4=p₂p₄ ;P_T5=p₂p₈; P_T6=p₄p₈.

Зв’язок, який об'єднує n елементів, формує число M = (n-1)*n/2 пар. Для кожної пари елементів визначаються множини зовнішніх, внутрішніх та довгих зв’язків і критеріїв згортання. Множина внутрішніх зв’язків пари є результатом перетину множин зв'язків елементів, які утворюють пару.

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

 

1.5. Визначення критерію об’єднання для виділених пар

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

Досліджуються три критерії згортання:

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

2) η2 = E^Ext(P_T) – E^Int(P_T) – E^com(P_T);

3) η3 = Et^Ext(P_T)

де:

E^Ext(P_T) – кількість зовнішніх зв’язків пари елементів;

E^Int(P_T) – кількість внутрішніх зв’язків пари елементів;

E^com(P_T) – кількіцсть довгих зв’язків пари елементів.

 

1.6. Упорядкування пар за значенням критерію

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

 

1.7. Вибір пар елементів/кластерів для об’єднання

Розглядаються два підходи до вибору пар елементів/кластерів  для об’єднання:

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

Відібрані пари формують множину пар елементів  кандидатів для об’єднання. З цієї множини для об’єднання (утворення  нових кластерів) відбираються пари, які не конфліктують між собою. Конфліктуючі пари – це пари, в яких є спільний один з елементів: P_T1 = p₁p₂ , P_T2 = p₁p₃ , p₁ –спільний елемент.

 

1.8. Вилучення пар елементів із списку впорядкованих пар

Всі відібрані  пари, які згорнулись у кластери, усуваються із списку впорядкованих  пар. Пари, які конфліктували, заносяться на початок списку. У результаті згортання список пар постійно скорочується.

 

1.9. Модифікація впорядкованого списку пар

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

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

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

 

2. Опис структур даних

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

затрати пам’яті  і повторні обчислення.

Пари  елементів будуються зі списків ElementList і NetList. ElementList – це спискова структура, кожен зв’язок якої підпорядкований одному елементу схеми та містить список зв’язків, інцидентних до цього елемента (рис. 2), NetList – спискова структура, кожен елемент якої відповідає одному зв’язку схеми та містить список елементів, інцидентних до цього (рис. 3). Пара елементів – це структура, яка містить: назву першого елемента; назву другого зв’язку; посилання на список зовнішніх зв’язків; посилання на список внутрішніх зв’язків, посилання на список довгих зв’язків, інформацію про кількість внутрішніх і зовнішніх зв’язків; значення критерію згортання; два прапорці, які вказують, з чого утворена пара (елементів, кластерів, елемента і кластера); посилання на список зв’язків для першого елемента (кластера); посилання на список зв’язків для другого елемента (кластера).

Рис. 2. Представлення структури NetList

Рис. 3. Представлення структури ElementLis

Рис. 4. Представлення структури даних для пари елементів/кластерів

 

На рис. 4 подано інформацію, що зберігається в пам’яті про пару зв’язаних елементів. Введено такі позначення: P_α іP_b– елементи, або кластери, які утворюють пару; e^ext, e^int, e^com – список внутрішніх, зовнішніх довгих зв’язків між P_α і P_b; η– значення критерію згортання; N^ext, N^int, N^long – кількість внутрішніх, зовнішніх і довгих зв’язків пари P_α і P_b; f1, f2 – прапорці, які вказують, чи P_α і P_b є елементами, чи кластерами; e_a , e_b – посилання на списки всіх зв’язків для елементів (кластерів). Пари, які згорнулись, записуються в масив. Елементи цього масиву є структурами і містять таку інформацію: P_α і P_b – назва елементів чи кластерів, які утворили цей кластер; С – назва утвореного кластера; N_c – кількість елементів, які об’єднує кластер С; Itr – кількість ітерацій, потрібних для згортання кластера С. На рис. 4. представлена інформація про модель дерева згортання.

Рис. 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.