Р П Базилевич, А Р Ждан - Аналіз вхідних даних та оцінка якості кластеризації для алгоритму оптимального згортання схем - страница 1

Страницы:
1  2  3 

ІНСТРУМЕНТАЛЬНІ ЗАСОБИ АВТОМАТИЗОВАНОГО

ПРОЕКТУВАННЯ

УДК 621.382

Р.П. Базилевич, А.Р. Ждан

Національний університет "Львівська політехніка", кафедра програмного забезпечення автоматизованих систем

АНАЛІЗ ВХІДНИХ ДАНИХ ТА ОЦІНКА ЯКОСТІ КЛАСТЕРИЗАЦІЇ ДЛЯ АЛГОРИТМУ ОПТИМАЛЬНОГО ЗГОРТАННЯ СХЕМ

© Базилевич Р., Ждан А., 2008

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

The main features of algorithm of construction of tree of the optimum rolling up of chart are considered at different criteria and parameters of work. The analysis of entrance data and estimation of quality of clusterization.

Вступ

Розділення складних схем на частини є однією з важливих часткових задач у проектуванні сучасних мікропроцесорів, складних електронних схем, НВІС, багатопроцесорних систем. Важкість розв'язування задачі зумовлена неполіноміальною обчислювальною складністю та великою розмірністю схем (сотні тисяч базових елементів).

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

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

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

2.   Аналіз вхідних даних

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

Табл. 1 ілюструє відношення кількості елементів до кількості зв'язків схеми. Від цих співвідношень залежить кількість пар зв'язаних елементів, які необхідно утворити для швидкої побудови дерева згортання. Під парою зв'язаних елементів <p; _ pj> розуміємо такі два елементи схеми S=(P, E); P=(p1, .... , pn }; E=(eb...., e2}; що мають хоча б один інцидентний для обох них зв'язок.

Формування списку впорядкованих пар як вхідних даних для побудови дерева згортання дає змогу визначити один раз суміжні елементи і не повторяти цю процедуру на кожному кроці згортання схеми, що істотно збільшує швидкодію роботи алгоритму. Від кількості утворених пар зв'язаних елементів також залежить швидкодія і тому доцільно мінімізувати це число. Якщо зв'язок є бінарним, то він утворює одну пару. Кожен n-арний зв'язок утворює V% n(n-1) пар. Тобто довгі зв' язки можуть утворювати значну кількість додаткових пар. Тому доцільно вивчити можливість їхньої фільтрації при побудові пар зв'язаних елементів з оцінкою змін кластеризації та швидкодії алгоритму. Табл. 3 ілюструє зменшення кількості утворених пар при фільтрації зв'язків певної довжини. Так, неурахування зв'язків з довжиною, більшою за 10, зменшує кількість утворених пар на 24 %.

Таблиця 1

Відношення кількості елементів до кількості зв'язків

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

IS

0,88

1,01

0,84

0,85

1,03

0,92

0,95

1,02

0,87

0,92

0,86

0,92

0,84

0,96

0,86

0,96

0,97

1,04

Таблиця 2

Характеристика тестів щодо кількості зв'язків різних довжин

 

 

 

 

 

Довжина зе

'язкіб

 

 

 

 

кількість

 

 

 

2

3

3-5

5-10

10-15

15-20

20-30

30-40

40-50

>50

зе язкіб

IbmOl

 

12752

8341

2082

3863

1953

653

169

93

26

1

0

14411

Ibm02

 

19601

10692

1934

5831

3765

1164

481

45

36

1

51

19584

ІЬтОЗ

 

23136

17619

3084

6289

3354

981

444

84

16

1

0

27401

Ibm04

 

27219

19246

5160

8826

5120

385

124

159

57

15

0

31970

Ibm05

 

29347

18013

1073

4174

5335

2223

1879

0

0

0

0

28446

ІЬтОб

m

32331

20555

4194

9397

4351

2192

473

291

2

0

0

34826

ІЬт07

 

45926

34500

10161

17135

9242

2895

1146

91

15

0

0

48117

IbmOS

■d

51309

26669

8221

14158

6758

2873

802

52

0

0

0

50513

Ibm09

s

53395

286S7

6911

15019

6698

1381

1712

545

312

74

0

60902

IbmlO

 

69429

42 9 45

7742

18194

13844

45 6 3

1435

653

21

1

0

75196

Ibmll

 

70558

44436

14843

26622

14257

3107

760

21

0

0

0

81454

Ibml2

Я

71076

44312

8064

15741

13406

6617

1080

877

0

0

0

77240

ІЬтІЗ

 

84199

55301

17679

30699

12716

5100

1778

144

0

0

0

99666

Ibml4

 

147605

85328

23041

46 2 29

23661

6675

2199

310

7

0

0

152772

Ibml5

 

161570

101899

28516

55307

28123

8605

48 7 7

1571

23

0

0

186608

ІЬтІб

 

183484

103586

22996

47 5 22

38010

12569

40 2 2

1553

19

2

0

190048

Ibml7

 

185495

102749

18273

36154

39524

19044

5039

2070

16

0

0

189581

IbmlS

 

210613

97538

42159

73802

26343

11772

7156

739

470

73

24

201920

Таблиця 3

Застосування фільтрації зв'язків певної довжини

Тест

Фільтрація зе 'язкіе певної довжини

Кількість с формованих: пар

IbmOl

< 10

82807

 

< 20

99207

 

< ЗО

102944

 

< 40

108253

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

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

1) *і= mcExt;

2) K2 = m(d)Ext + m(c2)Ext ;

3) Кз= m(ci) Ext + m(c2)tExt - mExtC1C2 ;

л\ ту _ Ext / _ Int

ExtC1C2

6) K6=

nelem

/ (11(d) +n(c2) );

де mcExt - середня кількість зовнішніх зв'язків на всіх рівнях згортання; mcInt - середня кількість внутрішніх зв'язків на всіх рівнях згортання; m(ci) Ext і m(c2)Ext - кількість зовнішніх зв'язків двох найбільших кластерів дерева TR, що не мають входження один в одного; mExtC1C2 - кількість зовнішніх зв'язків між двома найбільшими кластерами дерева TR, що не мають входження один в одного; nelem - загальна кількість елементів у схемі; n(ci) і n(c2) - кількість елементів у першому і другому найбільшому кластері, що не мають входження один в одного.

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

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

У табл. 4-9 відображено такі характеристики дерева оптимального згортання схем:

- кількість ітерацій у кластеризації схеми;

- максимальна кількість зовнішніх зв'язків дерева згортання;

- максимальна кількість внутрішніх зв'язків дерева згортання;

- середня кількість зовнішніх зв'язків на всіх ітераціях згортання;

- середня кількість внутрішніх зв'язків на всіх ітераціях згортання;

- ідентифікація двох найбільших кластерів, які не входять один в одного;

- розмірність двох найбільших кластерів (кількість об'єднаних елементів);

- кількість зовнішніх зв'язків двох найбільших кластерів;

- кількість внутрішніх зв'язків двох найбільших кластерів;

- кількість зв'язків між двома найбільшими кластер.

Також у табл. 7- 9  відображена інформація про середню кількість зовнішніх, внутрішніх зв'язків, про кількість згорнутих пар на цьому рівні. Аналіз виконано для 10 %, 20 %, 30 %, 100 % ітерацій від всієї їхньої кількості, а також для (10-20) %, (20-30) %, ... , (90-100) %.

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

Табл. 4 відображає характеристики кластеризації при різних критеріях згортання:

1) hi = EExt(Pr) - EInt(Pr);

2) h2 = EExt(Pj) - EInt(Pj) - Ecom(Pr);

3) h3 = EtExt(Pr);

4) комбінований критерій з r\1 і г|2.

Таблиця 4

Характеристики кластеризації для тесту IbmOl за різних критеріїв згортання

IbmOl

1

2

3

4

Кількість ітерацій

329

308

254

337

Мах. зовн. зв.

603

573

702

475

Мак. Енутр .зе.

263

358

229

309

Середня кількість зоен.зе.

12,3

12

12,6

12,2

Середня кількість внутр. Зе .

2,36

2,86

2,86

2,86

Кластер

Назва

12745

12743

12746

12745

 

Кіп. елем

5990

5929

6059

6078

 

КіП. зобн. зе.

452

390

551

415

 

Кіп. Енутр

SO

90

178

112

Кластер 2

Назва

12748

1274S

12750

12746

 

Кіп. елем

4022

5667

3666

43 5 6

 

КІП. зоен. зе.

603

573

702

416

 

Кіл. внутр. зв.

239

167

229

92

кількість зе, між Кластері іКластер2

263

240

246

152

Кількість пар

109183

Кількість елементів

12752

Кількість зв'язків

14411

Таблиця 5

Характеристики кластеризації для тесту IbmOl при фільтрації довгих зв'язків і плаваючих елементів

IbmOl

бф

5

7

10

15

20

фе

Кількість відфільтрованих елементів

0

1924

718

237

113

60

781

Кількість ітерацій

329

351

350

351

345

348

319

Мах. зобн. зе.

603

2662

1102

617

652

612

725

Мах. внутр. зв.

263

317

296

334

315

339

224

Середня кількість зовн. зв.

12,3

15,0

13,3

12,6

12,5

12,4

13,4

Середня кількість

ЗНуТр. ЗЕ.

2,86

2,9

Страницы:
1  2  3 


Похожие статьи

Р П Базилевич, А Р Ждан - Аналіз вхідних даних та оцінка якості кластеризації для алгоритму оптимального згортання схем