Білой Олег Ігорович

Факультет комп'ютерних наук і технологій

Кафедра комп'ютерної інженерії

Спеціальність «Системне програмування»

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

Науковий керівник: Ковальов С. А., доц. каф. КІ.

Консультант: Струнілін В. Н., ст. викл. каф. КІ.

Реферат за темою магістерської роботи

Зміст

Вступ
1. Актуальність теми
2. Мета і завдання дослідження, плановані результати
3. Огляд тематичних джерел.
3.1 Огляд міжнародних джерел
3.2 Огляд російськомовних джерел.
4. Розробка і дослідження ітераційних алгоритмів компонування
4.1. Постановка проблеми
4.2. Дослідження достоїнств та недоліків ітераційних алгоритмів на прикладі двох: ітераційного алгоритму 4х правил та модифікованого алгоритму.
Висновки

Список джерел

Вступ

Компонування — одна з обов'язкових процедур, які виконуються при конструкторському проектуванні. В процесі компонування електрична схема розбивається на модулі, модулі на осередки, і так далі. Що в результаті призводить до отримання представлення електричної схеми таким чином, який придатний до безпосередньої реалізації на реальних компонентах [20].

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

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

Алгоритми першої групи хоча і дозволяють отримати точне рішення задачі, проте для облаштування реальної складності фактично не реалізовуються на ЕОМ.

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

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

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

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

1. Актуальність теми.

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

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

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

2. Мета та завдання дослідження, плановані результати

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

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

Під час розробки планується:

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

Створити призначений для користувача інтерфейс для роботи з програмою

3. Огляд тематичних джерел.

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

3.1. Огляд міжнародних джерел

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

Від проблеми побудови гіперграфа загалом до проблеми його оптимізації для комп'ютерної обробки, його представлення тао відрисовки, дозволяють перейти наукова публікації Хенриксона і Кольда, Catalyurek'a і Aykanat'a [2,3], книга Хендриксона [4].

Безпосередньо питання ітераційної моделі проведення компонування, дослідження різних алгоритмів компонування торкаються в книгах Eduardo R Miranda, Sen Su, Bregman, G.Karypis [5-8], публікаціях K.Mohan, A.Feldstein, E.Carrillo, Bergmann, Alex Townsend і Lloyd N. Trefethen [9-12]

Також однією з перспективних сучасних гілок дослідження алгоритмів компонування є так звані генетичні алгоритми. Ці алгоритми використовують механізм випадкового підбору, комбінування початкових параметрів (у випадках з компонуванням провідників на мікросхемі — перестановки провідників) і відсіювання непридатних за допомогою способів, що нагадують біологічну еволюцію. З цією галуззю знань можливо ознайомитися в роботах Goldberg'a, Muehlenbein H., Schwarz, Rodriguez, Byung Ro Moon, Croix V, S.Raman [13-19].

3.2. Огляд російськомовних джерел.

Аналогічну інформацію також можна знайти в російськомовних джерелах, з якими легше працювати, оскільки вони створені на рідній мені мові. Опис математичної моделі побудови графів, розбиття на підграфи і побудови матриць суміжності і інцидентності можна знайти в книзі Курейчика [20]. У своїй монографії [21] Лебедєв описує можливості оптимізації початкового графа, для відображення його у виді, найбільш придатному для подальших автоматизованих обчислень і проектування, представлених в навчальних посібниках Алексєєва [22] і Мироненко [23] для ВНЗ.

Безпосередньо прямий перетин з темою моєї магістерської роботи має наукова працю мого керівника Струнілина В. Н. в співавторстві з Саломатіним В. А. [24], де розглядається алгоритм ітераційного розподілу елементів електричної схеми.

4. Розробка і дослідження ітераційних алгоритмів компонування.

4.1. Постановка проблеми

Компонування — одна з основних процедур, які виконуються при конструкторському проектуванні РЕА [20]. Це процес переходу від електричної схеми до конструктивному розподілу(розбиттю) усіх елементів на групи, в відповідності з конструкцією різних рівнів, тобто процес перетворення функціонального опису апаратури в конструктивний.

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

У послідовних алгоритмах спочатку обирається перша вершина графа і послідовним приєднанням до неї інших вершин з числа нерозподілених (за умови задоволення заданим критеріям) формується перший шматок графа. Потім набирається другий шматок графа і так далі до повного розрізання.

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

У даному алгоритмі необхідно знайти пару вершин x і ∈ X 1 , x j ∈E\ X 1 , для яких приріст числа зовнішніх зв'язків (ланцюжків) буде більше чим 0 і максимальний.

maxΔ S ij = S ij − S ji >0 ;

S ij =|Γ X 1 ∩ΓE\ X 1 | , S ji =|Γ X 1 \ X i ∪ X j ∩ΓE\ X 1 \ X j ∪ X i | , де:

X 1 — шматок матриці Q,
E\ X 1 — матриця Q без шматка X 1 ,
S ij – число зовнішніх зв'язків між двома шматками після перестановки вершин i і j
S ji – число зовнішніх зв'язків між шматками після перестановки вершин i та j.

Δ S ij =|Г X 1 ∩ГE\ X 1 |−|Γ X 1 \ X i ∪ X j ∩ΓE\ X 1 \ X j ∪ X i | . [25]

Таким чином, матриця Q розбивається на 2 підматриці X 1 и E\ X 1 , для кожної пари вершин X ij розраховується Δ S ij . Потім серед усіх Δ S ij шукаємо найбільше додаткове число і міняємо місцями i- тую і j- тую рядка матриці. Потім знову розраховуємо Δ S ij для усіх можливих пар вершин підматриць. Якщо найбільше Δ S ij дорівнює 0, або негативне — тоді закінчуємо компоновку.

Цей алгоритм досить легко запрограмувати, але він має істотний недолік — в кожному циклі необхідно наново розраховувати Δ S ij для усіх пар вершин підматриць, тому що після того, як ми міняємо місцями строки матриці, змінюється число зовнішніх і внутрішніх зв'язків кожного вузла схеми.

4.2. Дослідження достоїнств і недоліків ітераційних алгоритмів на прикладі двох: ітераційного алгоритму 4х правив і модифікованого алгоритму.

Ітераційний алгоритм 4х правил набагато складніше запрограмувати, чим попередній, він вимагає велику пам'ять в процесі роботи, але має істотний плюс — в кожному циклі необхідно розраховувати Δ S ij тільки для тих пар вершин які пов'язані ребрами з переставленими на попередньому кроці.

У випадку модифікованого алгоритму матриця Q спочатку розбивається на підматриці Q 0 , Q 1 ,⋯, Q k , що відповідає розбиттю гіперграфа на частини G 0 , G 1 ,⋯, G k . У підматрицю Q 0 включаємо елемент e 0 , який відповідає роз'єму.

Відмітимо, що при перестановці вершин e i , e j приріст Δ S ij знаходиться тільки для частин G n та G m , та відповідно, для підматриці Q n та Q m .[25]

З детальнішою інформацією про приведені алгоритми, з математичними викладеннями, ви можете ознайомитися в моїй статті на конференцію [25].

Тестування алгоритмів проводилося випадково згенерованим гіперграфом з кількістю ребер і вершин від 10 до 100. При цьому гіперграфи «розбивалися» на 2 - 10, 15, 20, 30, 40 і 50 частин з рівною кількістю вершин в кожній. Результати досліджень залежності часу обчислення декількох з алгоритмів від розміру матриці приведені в таблиці 1.

Таблиця 1 — Залежність часу обчислення алгоритмів від розміру матриці Q

№	Міцність вершин X	Міцність ребер Е	Кількість вузлів	Час обчислення, сек.
№	Міцність вершин X	Міцність ребер Е	Кількість вузлів	Алгоритм 1	Алгоритм 2
1	20	20	2	0,165	0,055
2	40	40	2	0,934	0,22
3	80	80	2	4,286	0,495
4	100	100	2	10,165	0,989
5	100	100	3	48,297	5,275
6	100	100	4	51,978	5,934
7	100	100	5	91,319	12,365
8	100	100	10	110,275	20,275
9	100	100	20	39,725	8,846
10	100	100	50	16,648	4,066

За результатами досліджень, приведених в таблиці. 1, можна зробити висновок, що швидкодія алгоритму 1 відносно алгоритму 2 не лінійнА і залежить від багатьох чинників. Гістограма швидкості обчислення приведена на рис.1.

Рисунок 1 — Гістограма швидкості обчислень алгоритмів, які досліджуються.

Графік залежності часу обчислення графу від кількості вузлів в схемі при розбитті на 7 підсхем приведений на рис.2.

Рисунок 2 — Графік залежності часу розрахунку від кількості вузлів вхідного графа для двох даних алгоритмів.

Кількість кадрів анімації : 7

Час затримки:2сек на кожен кадр, останній, — 4 сек. За 2 сек. можливо оцінити шкалу графіку і її зміну. Останній кадр з текстом, тому затримка вища

Висновки

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

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

Список источников

Dauber E., in Graph theory, ed. Harary ,Wesley A., 1969. — 172 p.
Hendrickson B., Kolda T.G., "Graph partitioning models for parallel computing", Parallel Computing, 2000. — 16 p.
Catalyurek, U.V.; Aykanat C., "Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication", 1999. — 673 p.
Hendrickson. "A multilevel algorithm for partitioning graphs", 1995. — 14 p.
Miranda E.,"Composing with Computers,Algorithmic composition, Iterative systems", — 34 p.
Sen Su, "Iterative selection algorithm for service composition in distributed environments", 2008. — 1841 p.
Yin E., Osher S., "Iterative algorithms for minimization with applications to compressed sensing", — 26 p.
Karypis G., "Multilevel hypergraph partitioning: applications in VLSI domain", 1999. — 69 p.
Mohan K., "Iterative Reweighted Algorithms for Matrix Rank Minimization", — 34 p.
Feldstein A., "A study of Ostrowski efficiency for composite iteration algorithms", 1969. — 147 p.
Carrillo E., "Iterative algorithms for compressed sensing with partially known support", 2010. — 4 p.
Bergmann S., "Iterative signature algorithm for the analysis of large-scale gene expression data", 2003. — 18 p.
Goldberg, "Genetic Algorithms", 1989. — 412 p.
Muehlenbein H., "Marginal Distributions in Evolutionary Algorithms", 1999. — 6 p.
Rodriguez, "Schemata, Distributions and Graphical Models in Evolutionary Optimization, submitted for publication", 1999. — 34 p.
Schwarz, "Genetic algorithm for partitioning circuits", 1998. — 126 p.
Moon B.B., "Genetic Algorithm and Graph Partitioning", 1996. — 841 p.
Croix V, "Graph partitioning using learning automata", 1996 — 195 p.
Schwarz, "Hypergraph Partitioning Based on the Simple and Advanced Genetic Algorithm BMDA", 1999. — 130 p.
Курейчик В.М., Математическое обеспечение конструкторского и технологического проектирования с применением САПР [Текст] / В. М. Курейчик. – М.: Радио и связь, 1990. – 352 c.
Лебедев Б.К., Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография / Б. К. Лебедев. – Таганрог: изд-во ТРТУ, 2000. – 192 с.
Алексеев О.В., Автоматизация проектирования радиоэлектронных средств: Учеб. пособие для радиотехн. спец. вузов [Текст] / Под ред. О.В. Алексеева. — М., 2000. — 479 с.
Мироненко И.Г., Автоматизированное проектирование узлов и блоков РЭС средствами современных САПР: Учеб. пособие вузов / Под ред. И.Г. Мироненко. — М., 2002. — 391 с.
Саломатин В.А., Итерационный алгоритм распределения конструктивных элементов при задании электрической схемы в виде гиперграфа [Текст] / В.А.Саломатин, В.Н.Струнилин // Наукові праці Донецького національного технічного університету. Серія «Інформатика, кібернетика і обчислювальна техніка» (ІКОТ-2008). Випуск 9 (132). — Донецьк: ДоНТУ. — 2008. — 316 с.
Белой О.И., Струнилин В.Н. Модифікація ітераційного алгоритму компонування на базі гіперграфової моделі електричної схеми. Матерiали мiжнародної науково-технiчної конференцiї студентiв, аспiрантiв та молодих вчених. — Донецьк, ДонНТУ — 2012