автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Математические и программные способы для размещения элементов методом скановальной области

'о ^

<0 л ^

о 4 <даржавний университет "Льо1вська пол1техм'|ха"

На правах рукопису УДК. 658.512-52

Телюк Тарас Михайлович

Математичн! та программ! засоби длп розшщеннч елемент!в методом сканувальноТ облает!

Спец|'альн!сть 05.13.^^- матемагччне та программе эабезгичення обчислювальних машин / систем

Автореферат дисертаци на здобуття паукового ступеия кандидата техжчних наук

Льв1ц-1997

Дисертац^ею е рукопис

Робота виксжана на кафедр1 програмного забезпечення 'Державного уншерситету "ЛьЕНВська полггехчи а" Науковий кертник - доктор техн(чних наук,

професор Бааипсггм P.P..

Оф'щжж опаиенти:

1. Доктор техжчних наук, доцент ГЧзник В.В.

2. Кандидат техн1чних наук, с.н.с. Буш, P.A. Провщна орган!зац1я - (нститут проблем м о ш и но буду в г и н я HAU

Укради, вщдт математичного мидежсзання (м.Харкш)

/У л<у

Захист вдбудеться 1 г/ и • 1997 р. о 14®3 годин!" на зэгчдаш-и cneuia/iiaoeaHoi вченоГ ради Д 04.06.21, у Державному уишерситет! "Льв1'вська noniTexHiKa" {290646, Льз1в-13, вул.С.Бандерч, 12, ауд. 225 головного корпусу).

Вщгуки на автореферат у двох прим1рниках, aaeipeni печаткою, просимо надсилати на адресу:

290646, Льв1в-13, вул. С. Бандери, 12 -

Державний ун!версигет "Львиська полнехжка"

вчено^у секретарю ради. Д 04.06.21 доценту Мельнику P.A.

3 дисертацйю можиа ознайомитися у б!блготезц| Державного yni-верситету "Ль!шська полаехнжа" (м.льв1в, вул.Професорська, 1) ■

Автореферат роз1'сланий ^ ^ 1997 р.

Вчений секретар спец(ал1зованоТ. -

вчеио? ради, к.т.н., доц. ____ Мельник P.A.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Одними ¡э найбтьш складних сучас-них прикладник задач е зздач1 дискретно! (комбшаторно!) oiithmí-заци, яю мають неколжомьгпьну складнють (NP-CK/iafliii задачу. Теоретичш i прикладш аспекти u¡e! проблематики почали форму-ватисл в 60-70-х роках i тривають до сьогодн1'шнього дня. Особливо гостро потреба íx дальшого розвитку виникае у тих випад ках, коли posMÍpuicrb задач е великою i надвеликою (десятки ¡ со-th¡ тисяч параметр1в). Це мае mícub, зокрема при проектуианш великих i надвеликих ¡нтоГральних схем та ¡нших 3acoóia сучасно! комп'ютерно! та радюелёктронно! техжки. Задача розм1щення елеменг'ю, яка с одним' з eianio такого проектування, вщповщае матвматичиш задач: квадратичного призначвння i мае фактор'1аль-ну складнють. Пошуку.ефективних шляхт.Я розв'язуаання приевя-чено багаго наукових po6¡T, для и реагизацн розроблено ряд програмних засоб!в. Проте неперероне стр1мке зростання ¡нтег-раци схем ставить hobí вимоги, яю не. мржуть бути забе.лючеш ic-нуючими математичними i програмними засобами.

Базопими в дисертацм'використаш запропонован1 Р.П.Бази-левичом методи сканувально! об/iactí та ¡ерарчнио! декомпозицй, як! гвдтвердили свою ефективк1с.гь дня задач поршняно ¡невелико! po3MipHocT¡. Прото методи ni залишалися ще недостатньо обгрун-тованими, недостатньо досл'щжен) особлиаост! íx peaniaaují для задач велико! та надвелико! розм1рност1, що обумовлюе актуаль-HÍCTb дисертацп.

Mera ra задач! маслшження. Мета роботи - розвиток i доспи дження методу сканувально! обласп як ефективного шдходу до розв'язуоания задач квадратичного» призначення, розроблеиня нових ефективних алгоритмов та програмних засоб'ш для викорис-гання методу у випадку задач велико! poawipiiocTi.

Робота спрямована на створення ефективних математичних та програмних засоб|'В розв'язування зада1« розмкцення елемен-пв, необх1дних для проектування конструкщй сучасноТ високсин-тегроьано! комп'ютерно! та радюелектронно! техики, а також ¡' дли задач в ¡нших областях, де е потреба оптимального розм1-щення взаемозв'яэаних об'ект.

Метохм лос/и'лже. ;ь. В дисертащйий робоп використовуаа-дися методи дискретно/ олтимшацн, зокрцма еврюглчн! та градЬ-ентж методи розв'язування камб1нагорних задач, прякч й рекур-сивн'| методи побудови комбшаторних кокг^'гурацт, ¡терашйн! та конструктив^ методи розбипя 1 розмпцення, статистичш методи оцжки якосп результат та надмносп алгоритмш, методи побудоаи складних програмних систем.

■ Шукошлюжшша

» Роэроблено I обгрунтовано нов1 стратег¡1 ефективного засгосу-вання методу сканувально? облает!; а також досшджено валив розм1р1в та конф1гурац(й ■ сканувадьних областей, опособ1в проходжемня облает! по конструктиву, . методов знаходження розв'язку для елементарних областей на як1сть результата.

• Для моделюваннй скануаальних областей великих розмюиостей вперше запропонована 'I досл!джена 6агатор1внева 1ерарх»чна стратега •• "сканувальна область в сканувальн>й областГ.

• Запропоновано способи виведйння ¡терацшнот методу з локального оптимуму, зокрема розроблено ждкоди до використання випадкового та спрямованого мутнт'ш як елемеит1в апарагу генетичних алгоритмш, що дае можлив'ють продовжйти ¡терац]йний npou.ee I досятути кращого варианта розмщення.

• Запропоноватто новупосш'дошнсть використання макромодеяю-аання э модифкоааним пщходом до пщрахунку критерию якосп,

що дозволяв сформувати краще початкове розмпденнч - переду-моау ефектипного застосувзння методу скэнувалвно! облает!.

• Роэроблоно нооий алгоритм компактного групового початкового розмщення рЬмогабаритних елеметчв на основ! ix конструктивных параметра.

Прз* ипна uimiicth роботи обусловлена потребами проектмих орган1зац!й в розроблент сучасних засоб!в комп'киерноТ i радюелектронноТ технки, зокрема в проектуванш великих та надвеликих штегральних схем, мжрозборок, друкованйх плат. Отимальне розмТщеннп елемент!в конструкщй MiniMi3ye загальну довжину з'еднань та число мжшароёйх переходш i, як наел ¡док, створюе xpaiui умови для трасування, п1двищуе шиидкодго, зменшуе паразитн! ефокти, спрощуе апаратуру, пщвищуе ii над1йнють та здешевлюе П виготовлення.

Дисертацмна робота еиконана у pyc/ii наукових дослщжень кафедри програмяого забвзпечёиня Держужверситету 'Льв1вська пол1техжка", як! проводилися дисёртантом за перюд 1992-1Э9брр. в ход! наступних держбюджетиих та госпдогов1рних науково-досл!Дних poG'it:

» "Математичко та программе забезпечення ¡нтблектуальних систем автоматизовзного проектування топологи великих ¡нтеграль-них схем" (ДБ.84.ПЗ, замовник: Мжгстерст-'о Ocb'itm УкраТни, 1991-1993 p.p.); -

• "Мате^атичне та программе забезпечення ¡нтелектуальних систем синтезу топологп великих ¡нтегральних схем" (ДВ.84.ПЗ'94, замовник: М|нютерство OcaiTH УкраТни, 1994-1995 p.p.);

• "Методй та алгоритми розв'язування оптимЬацмних комбЫа-торних задач велико? po3MipHOCTi (на приклад1 задач електрон'1ки)" (ДБ.84.Б, замовник: Мжютерство осв!ти УкраТни,1991-19Э5 p.p.);

"Розроблення та досл!дження математичних метод1в та алгорит-MiB для авюматизованог о проектування тополоп! великих ¡нтег-ральних схем i конструкцм радюелектронно! апаратури" (ДО.34.1, замовник: Мжютерство Оборони Укра'ши, 1991-1996 p.p.).

Результати роботи впрозаджен1 в навчальний процсс при п'щготовц1 ¡нженер!в cneuianbHocTi "Програмне забезпечення обчислювальноТ техн!ки i автоматизованих систем", можуть бути рекомендован! для специальностей "КомгГютерн! системи про-ектування", "Спец1ал1эован1 комп'ютерн! системи", та спеЦ!аль-ностей рад!Отехн)чних напрямш; а гакож реко.мендуються для впровадження в ripoeKTHi органЬацм, йк< розробляють ¡нтегральж схеми (6 тому чис-л! надвелик!), мжрозборки, друкоааы плати.

Розроблено пакет прикладних програм "Сканувальна область" для теоретичних та екперйментальних досл1джень опти-мальних параметрш методу сканувально! облает!. ППП "Сканувальна область" використовуеться студентами, що вивчають ме-тоди дискретно! оптимтци в .курсах "Обчислювальн! аспекти проектування HBIC", "Матёматичне та програмне забезпечення САПР", "Опрацюаання експериме. дальних даних на комп'ютерi". Розроблено цикл лаборатории* роб!т i опублюовано методичж вказтки.

Р використанням ППП "Сканувальна область" розроблено пакет прикладних програм "Розмщення" для реального проектування конструкц1й комл'ютерноТ та радюелектронно! технки, який сп!впрацюе з циирокорозповсюдженою системою проектування PCAD.

АпробаШя. OcHOBMi результати дисертацшно! роботи були подан! на':

- 4-у Мжнародну науково-практичну конференцпо "Укрсофт-94", м.Львш, жовтень 1994;

- М1жнародну наукову конференцло з генетичних алгоритмш в м.Одес1, кв!тень 1995р.;

- КЦжнародну наукову конференц'1Ю з генетичних алгоритм|'в "МЕШЕЬ95" в м. Брно, Чех1я, вересень 1995р.;

-5-у М1жнародну науково-практичну конференцйо "Укрсофт-95", м.Льв1в, жовтень 1995р.

Публ/каиН. Ос.новж матер1али дисертац!йноТ роботи воображено в 7-ми опубгпкованих • роботах (б-ти статтях, тезах . та мотодичних вказшках).

Структура та обсж роботи

Дидертац1я мютить ' вступ, чотири роздши, висновки, оикладеж на 130 сторЫках друкованого тексту, '50 малюнюв, 7 таблмць, 61блюграф1ю з 102 наймонувань 1 додатки.

ЭМ1СТ РОВОТМ

У всгуп/ обгрунтовано актуальнють тематики дисертаицйних дослЦркень, коротко описано структуру 1 змют роботи, гшсвплено зм!ст положень, яю складають наукову новизну та П практичну цЫн'ють.

В першощ' роэд/л/ проведено критичиий огляд в!домих гид-ходв та методов до розв'язуаання задач! оптимального розмкцен-ня елемв1П1в (вектора сладу, послщовно! статистичноТ оптим!-заци, парних перестановок, силових функций, посящовного зсуву елемент та ¡нших), дана 5х по^лзняльна характеристика, приведена оцидка переваг та недолМв. Вйгомим недолшом бшьшост') метод1о е нодостатни точнють та швидкодт, сулева залежн'ють часу роботи вщ розм'фносл задач!, яка.. часто еблизькою до фактор1ально1. Тому вони не зааждц е достатньо'ефектинними до задач велико! I тим б)льшз надоеликоТ розм1рност1.

Описано та обгрунтовано.критерг? оптимшцн, сформульова-на постановка основно! опт'имзацтноТ задач!, На основ! критич-

ного огляду метода зроблено висновок про. доцтьнють досли дження методу сканувально! облает!, який п!дтвердив свою ефек-тивнють на задачах невелико! розмрност!, про потребу йога роз-витку, розроблення на йоге основ1 нових алгоритма та програм-них засоб!в для задач велико! та надвелико! розм^рносл.

Метою другого роэпту е всесторонне дослщження аласти-востей методу сканувально! облает, його вдосконалення, розви-ток та розроблення нових ефективних алгоритма для викорис-тання при велик1й розм1'рност1 задач.

Суть методу сканувально! облает полягае в тому, що поверхня в кснструктиву, який мютить певну множину мюць для розм1'ш,ення елеменл'в: /= 1, 2,..., ц, де цгп (л - потухнуть

множини Р елеменлв для . розм1ш,ення), розбиваеться на деяку множину елементарних областей, що перекриваються; й/, 2..... Н, ТаКИМ ЧИНОМ, ЩОб б/П-<3;' *■ 0, ЯКЩО й; ] в] - сум1жн'| I

к

[)Сй1 = в. Кожна елемантарна область мютить по до позиций ы

множини Z. Це число вибираеться таким чином, щоб при роза1-язуванш окремих часткових задач базовою оптям1зац!йною процедурою розм1щення реальиим було безастосування метрд!в, яю забезпечують необхщну гочн!сть. Поту к розз'язку виконуеться посл1Довним багатократним "скануванням" и,!ею процедурою всю! поверхж конструктиву за обраною стратеп'ею. У бтьшост! випад-юв отримон1 результати е локально оптимальними - для кожно! окремо! елемеитарно! облает! С/, одержуеться оптимальний результат.

Основними параметрами методу е: розм1ри 1 конф'1гурацп елементарних областей в/, стратеги сканування, методи знахо-дження розв'язку для елементарних областей в/, критери оптим!-заци та застосован'1 метрики. В'дисертаци досл!джено вплив цих

гшраметр1в на роботу мотоду, обгрунтовано оптимальний Тх виб1р та на ц!й основ! запропонозано нош ефектйвм! алгоритми реа-/мзацИ мотоду.

Ррзупрнют1.. .олементарн! облает!. Для досягнення високо! якоСт! розм'ндення бажано розм!р елнментарно! облает! С/ виби-рати якнайбтьшим. Проте фамтральна складн!сть перебору вар!ант|'в резмццення елементт всередин! елементарноГ обласл призводить до сутгезого збмьшення обчйслюв'альних затрат. Тому в рол! елементарних областей скамузання обгрунтовано та за-пропоновано використовув&ти облает! наступних розм!риостей: з двох елемент!в -."2-ка" (вертикальна, горизонтальна, права ! л!ва похил1); з чотирьох елеменпв (квадрат) - "4-ка"; з п'яти елементт - "5-ка" (хрестиком. 1 з!ркою); з шести елемент!в - "6-ка" (вертикальна ! горизонтальна); з б!льшого числа елементт -9, 12, 15, 16-ти . елемент!в, як! реал!зуюгься послщовнютю елс-ментарних областей, менших розм1рностей - сканувальна область в сканувальЫй облает! (див. приклад на мал.1).

^г2 ш ЦУ: - » i • —*> I::.:

-*—1 *

Мал.1. Приклад послщовносш' меделювзнвя "дяв'ятки",'в1дпое! "-,о: "п'ят!рка" хрестиком, "п'ят!рка" зфкою, 4 "чегв1рки" та 4 "ш1ст'ки".

Часов! характеристики oflHi'ei ¡TepauiT методу еканувально! облает! для задач! Штейнберга ■ (теетувзння проводилося на комп'ютер! IBM 'PC 486DX4-120 PCI) таю: у випадку повного перебору "двшкою" час виконання одн!с'| ¡тераци 0.09с., "четверкою" - 0.44с., "шюткою" - 11.43с., а "дев'яткою" - вже 1 год. 4хв. 34.61с. Виходячи з цього використовувати повний переб!р для областей великих розм|'рност.ей рекомендуеться лише в окремих випадках на швИдкод!ючих комп'ютерах.

Щодо послщовносл застосування сканувальних областей рекомендуетьсп послщовне за ¡тера^ями укрупнения 1х розмрв. Якщо, наприюкэд, сканування будь-якими "двмками" не призао-дить до покращення критер!ю якост!, То здмснгаеться перехщ до "четв1ркн" I т.д. Такий шдхщ дозволяе уникнути утворення згусткш елеменлв, як1 Сякими зм1нами розм!ру сканувальноТ облаем на можна розбити, значно зменшитм час роботи методу.

Конф1гураи'1я рбласт1 б/ може бути довщьною. Але найдоцтьышою слщ вибирати п форму у вигляд! кола або набли-жену до нього, наприклад, квадрата. Така форма створюе умови для найрацюнальн!шого взаемного розташуваннп групп сум1жних елемемтт. На лочаткових ¡терацшх рекомендуеться вико-ристовувати "роЗ|'рвану" сканувальну область, тобто розглядати не сусЩн!, а в!ддален1 елементи, осктьки це скорочуе загальне число 1теращй знаходження розв'язку.

Стратепя сканування визначае напрямок обходу елемен-тарною областю поверхж конструктиву, а значить \ послщовн1сть груп елеменлв, як! будуть брати участь у оптим!зац1йному процесс Можлив1 р1эноман)Тн! стратег!? сканування: горизонтальна або вертикальна стр1чков1, спиралевидна, зм1евидна, гвинтова I т.д. Кожна цих стратеНй мае один I той ж недолж; неравноправие (щодо можливост1 перем!щення по конструктиву у проЦес! сканування) становище елеиентщ. Подолати цей недолк можна, наприклад, чергуванням р1зних стратепй сканування. Дослщження показали, що таке чергування слабо вплинае на покращення критерио якосл. Застосування посл'довно р^номажтних стратепй сканування у пор^вйянж до використання ппьки одн1еТ горизонтально? стрнково! стратеги лише для 11-ти -{2%) э п'птисог тестових приклад'т дало покращення критерю якосл в середньо-,му на 0.8%.

Запропоновано I доедщжено "розр|джену" стратепю. 1герацш сканування проходить в дектька етапш: до одного етапу з1 вас! множини елемеитарних сканувальних областей, якими буде проскановано конструктив, входить лише т1,. як! не перетинаються (не мають сп'тьних гюзицм). Така стратега ставить ус1 елеменги в р'тноправне положения,

Розр1джена стратепя сканування у поршнянж до звичайно! при тестуваннГ виявилася дещо пош'льшшою, - л сам1 початкош вар!анти розмкцепня при. однакових ¡нщих параметрах роботи алгоритму I використашн розрмркено! стратеги сканування зб1галися до локального оптимуму ка 2-3 ¡терацп повтьнше, н!ж при використант щтьноТ стратеги', зате, э другого боку, отримаж реэультати були на 14% ближч1 до найкращого розв'язку задачи

Знаходження розв'язку всеродин) елементарпих областей. Використаннп точних методов вимагае на кожному кроц1 сканування ровного перебору елемени'в ¡, як наслщок, - великих часових затрат. Складнють одте! пгераци 0(т*п!), дв т - к1лькють областей сканування в конструктив! на прогяз! одже! лерацп, п -юлькють елементт елементарноТ обдяся сканування.

Для областей з 4-х, 5-ти, В-ти та 9-ти елементт дослЦркено шляхи оптим!зацн базових процедур, то б то метода розмицення елементт всередиж елементарно! област'1 сканування. У випадку обпаст з чотирьох елемейт1о при повному.перебор! необхщно розглянути 41-24 вар!айти розм!щенняг 1 виконати 6*4!=144 опе-раци знаходження довжини зв'язш м!ж елементами. При застосу-31

а3

а2 а4

. а2 аз

54 ал

(а,,а2), (а,,аз), (а1,а4), (аг,а3), (а2,а4), (а3,а4);

(а|,а}), (а,,а;,), (а2,а4), (аг,а3);

Мал. 2.

{аиа2), (а3|а4);

uaimi оптим'13овано1 базовоТ процедури достатньо розглянути лише три вар!анти розм1щення i виконати 12 таких операцы (мал.2).

Bei ¡Hkui випадки розмщення зводятьсп до тих самих трьох роэм!щень, як випадок дзеркального вщображення елеменив, що лежать один навлроти другого по /уагонал! або випадок переходу елеменив по колу без змжи конф!гурацм розмМення (мал.З). При таких вар!антах розм1щення не буде спостер!гатися зм!ни значения критерию «KOCTi всередин! облает!.

¡а, a2j ¡а, а4[.

а^ | а2 а4!

U

аз а4| |j2_a4j !_а_»_ _ а_э;

елемэмти а2 I а3 перехгд вей влементш по колу

Мал.З.

Аналопчний виграш досягаеться \ для ¡нших елементарних областей, причому чим бтьша область, тим бтьше вар1анг!в з однаковим значениям критерю можна вщкинутм, тим бтьше об-числень можна "зекономиш". Так, для элементарно! скайувально! облает! з шести елементш при повному перебор! необх1дно пере-глянути 6!=720 вар!анга розм'ицення ¡-викоиыги 15(6!)—10800 операц!й, а при эастосу'ванн! оптим!зоаано! базовоУ процедури достатньо розглянути 60 вар!ант!в ! викинати 60 операц!й знахо-дження довжини зв'яэюв. ГМдраховамо, то такий лЦуод энижуе обчислюаапьну складн!сть задач! з 0(п!) приблизно до

Критери рптимтзацп. Для оцЫювання якоелм розм1щення використовуютьея р^зномаштн! критери оптим1зац!Т »а метрики Р(р): м!шмуми.сумарно! довжини з'еднань, максимально! довжини окремих пров|дник1в, с'умарного числа ^ перетинш з'еднань, сумарного числа м!жшарових переходов, сумарно! площ) прямокутник!в, що охоплюють з'едмаиня, I т.д. Найпроетшим, уншерсальним 1 найч.аслше вживаним критерюм оптимальноет! е

м'!жмуад сумарно! допхини проэдникт - -з'еднань м!ж елементами схеми: К , - ттУ де Гр ■ коефадент эа'язност! м:'ж

I

елементами. е,- I Оу, а - довжина з'еднаннн" (ощетань М1ж елементами а I е,-). Метод обчислекия ц!еГ в/дстанг визначае метрику. Е* залежносп вщ вимог згдоч! • рекомендуетьсн використовуваш вщпошдш метрики: при необлдностт прокласти найкоротший. шлях М1ж з'бднаними точками - вибнрати есзклщову, а для проведения, напрйклад, пров1'дникооих або друкованих з'еднань по каналах I мапслралях, ш,о е паралрльними до координатних осей, доцтьжше йикормотЬоувати оптогоьальну метрику.

Введения. _з__локального_мУмум& Одним з найбшыи

суттевих недолив методу ска'нувальчоТ облает!, як 1 ¡нших 1т'ерац1Йних методкз, с отримакня локального оптимуму, тобто попадания рочн'яэку й локальну "яму". У багатьох випадкач ¡терац!йний процес можна продовжити, якщо застооувати ефективы методи аиходу з локального оптимуму. 3 ьуею метою досл/джено дек'.пька таких шляхт, зокрема, пврехщ до ¡пшо! сканувально? облзен; використання апарату генетичних алго-ритмш - дн двох генних мутантш: випадкового (збурення в екол1 елемента) 1 спрямованого або з елементами селекци (перехщ на ¡ншу метрику). Переход (хоча би на одну ¡терацто) до сканувально! облаем бтьшого розм!ру також часто .стнорюё умови для продовження оптим1зац1йного процосу.

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

и

нозищ'ями з будь-яким з елеменпв окопу (мал.4). Пгсля проведения такого "збурення" опгим1зац'1йний процес

продовжуегься. /т\

. /

/'• '

ta у КГ/-' ?

\>' у

а) -^б)

Мал.4. Збурення елемонта в окол1 раадусом: а) г<1. б) г<2.

Тестування 500 розм!щень показали , що найбтьш ефектив-ним е збурення елеменл'о в окол1 г<2: в 359-ти випадках (72%) критерий якосл покращизся в середньому на 24 одинищ для тесту Штейнберга (результат на 9% ближчий до оптимального), в 102-х випадках (20%) не в/дбулося покращення критерий я»'ост i (тобто подальша оптим1зац!я привела до того ж самого локального розв'язку), i-лише в 39-ти. випадках (8%) оптим!зац1я гнсля збурення привела до "локально! ями" э пршим критерием «kqctí.

Дослщжено та рекомендовано тзкож можливосл застосування нел^ж'йних метрик (напри/слад, евклщовоТ в квадрат!" або в Ky6¡) як генного мутанта, що мае еламенти спрямовано! се-лекцм. Це пщвиЩуе вагу поодино: их вуэдалених зв'язкт míx еле-ментами, оскшьш можливою е ситуация, коли в!дцален1 один вщ одного сильнозв'язан! елементи не можуть наблизитися один до однЪга через те, що Тх угримуе велика юлькють др1бних локальних зв'язюв з ¡ншими елементами. Тестування показали, що в 331-му з 500 випадюв (66%) застосування евшдово)" в квадрал метрики дало покращення критерию якосл а середньому на 22-i одинищ (на 8% результат ближчий до оптимального), лише в 20-ти випадках (4%) спостер1галося попршення критерто якосл, а в peurri ви-падюв - 149-ти (30%) подальша оптим1защя привела до того <ж локального оптимуму. Використання куб1чно! метрики вимагае застосування для шдрахунку критерию hkoctí компьютером чисел по-

AQiiíiioí доожиии, а це ч викликае значки зб!лыиення необхщного posMipy оперативно! пам'ят1 комп'ютера то збтьшення часових затрат, що не в!дпошдае оимагам швидкого i ефективного si/дшу-кания розп'язку; але може бути рекомендованим для заотосуван-ия в окремих випадках на вмсокоефективних комп'ютерах.

Р[зно1'абаритн1____едемещи, В основ! базово! процедури

методу сканувально? обласн лежить принцип певного перебору BapiatfTin ро?м!щемнл елемент!в, Якщо елементи значно вщр!зняються розм1рами, то може вин и кнут и сигуацш, коли таю елементи неможливо помшяти мюцямн через те, що б!льший елемент лерекрие своими • межами íhluí елементи, Для застосування методу сканузально! облает! у випадку p¡3H0i абгфитних елемент1'а рекомендуеться:

* використовунати cneiijanÍ30caHÍ методи початкового розмацен-

ня, яю энбезпечать добрий "стартосий" варюнт розммцення; « визначати групи елеменпв, víkí незначно вц1р!зняються розм!рами та сканувакня здойемюаати всередиж таких труп (sapianT роз!рвэно! обласн).

Таким чином, для ефективно! роботи методу сканувально! облает! рекомендуеться послщовно збтьшувати за ггерацтми po3Mipn сканувалыю! облает! вщ найменших (з деох елемент!в) до бтьших (в залежност! вщ вимог точност1 I часу ra продуктивное^ комп'ютера}. Для великих областей з 9-1G елемент!в рекомендуеться здшеиювати íx моделювання областями менших роз-мгоностей; для елементарних областей доцкльно застосивувати оптим!зовану процедуру пщрахунку кри"тер!ю якост!; для виводу з локального оптимуму - застосовувати почергово "збурення в околГ' та перехщ на метрику вищого степеня з 1иаступним ловерне'нням на початкову метрику.

Метою тоетього роздщу е роЗробленнн алгоритмов для вибо-ру' початкоаих умов, як! забезпечують ефёктивний х(д оптим!за-цмного процесу в метод! еканувально! облает!, та !х до'ся!дження.

Початкове розм!щення елеменпв може вибиратися випадково або формуоатися безпоеередньо на основ! жформаци про схему, про эе'язки мЬк елементами, або на основ! додатково? ¡нформац!!, зокрема дерева розбиття схеми. Запропоновано де-кшька алгоритм!в для побудовй дереза розбигтя схсгли. До них вщноептьея послщовний метод розбитти зс. зв'яэн!с1Ю, пара-лельний та ггеращйний мегоди покращення розбиття. Досл!джено дек!лька алгоритм1в без посереди ього огримання печаткового роэ-м!щення, зокреМа ¡ерархнног багатор!внево! декомпр?ицп"та посл!довного розм!щення за за'язн!стю. Як результат дослщжень рекомендуеться застосовувати ¡ерарх!чну багатор!вневу деком-позицго в пар1 з методом еканувальноТ облает!, оск!льки вони використовують однакову базову процедуру.

Для (зипадку складно? реально! задач! з р1зиогзбаритними елементами розррблено новий метод - роэм1щення трупами, що дозволяе отримати компактне розм1ш,ення елемент!в, як! е погру-пованими на основ! 1х конструктйаних особливостей (геометрич-них розм!р!в).

Розвинуто можлйвост! поёднання методу макромо-делюиання з методом еканувально! облает! з метою пщвищення точност! та швидкоди, досл!Джено стратег!! ефективного викорис-тання макромоделей. Конструктив розбиваеться на таке максимально аелике число (4-16) макромоделей, для яких ще.можна отримати точний результат, виконуеться алтим!зац!я методом еканувально! облает!, дал! кожна макромодель розбиваеться на др!бн!ш!, знову проводиться оптим!зац!я, знову розбиття ! т.д. В

результат! отримуемо поелементне розм1щення, яке опгимкзуеться методом сканувально! области

Дослщжено можливють використання ршних шдход1в до тд-рахунку критер1ю якост! при застосуванн! макроскануваьня. Зок-рема, оптимальним виявився пщхщ, при якому скануванни конструктиву в'щбуваеться макромоделями, але значения критерю лкост! гпдраховуетьсп поелементно з врахуванням мюцеположен-нп кожного елемента всередин! макромодел!. При цьому шдстань м!ж будь-якими двома елементами, навпъ якщо вони належатимуть до р1зних макромоделей, залишиться така ж як I при -поелементному розгляд! конструктиву, Такий пщхщ не спотворюе критерш якосп. Гестування 500 иипадкових початкових розмицень гпдтвердили доцшьжоть йога використання до шдрахунку рлдстаней м!ж елементами у макромоделях. Иокращення критерию якост1 вщбулося . в ус!х без аинятку випадках, тод1 як при .частосуванж вщомого гндх1.ду, коли макромодель розглядасться як матерюльна точка; покращення вщбулося лише в 339-ти (68%) випадках. 'Тестування показали, що використання макромоделювання о метод| оканувально! облает! дозволяе отриматй результати ближч'Г в середньому на 19% до оптимальною роэв'язку задач!.

Таким чином, для створе) 1ня передумов ефективного застосувпннп методу сканувально? облает! особливо для задач велико! розм1рност| рекомендуеться; формула ги початкове розмщення методом ¡ерарх1ЧноТ багатор1внецоТ декомпозицИ, вибираючи максимально можлииий коеф!ц!еит дтення для аапоб!гпння а трат точнооп; зд'1Йснювати попередию оптимшщю розмкцення, застосовуючи макромоделювання э поепементним плодом до гндрахунку критерию оптимальност!. Для окремого класу задач з р!зногабаритнимн елементами рекомендуеться метод розмидення трупами.

моез упраатння заеданиями

--1 Головна прогрзма |

;МОН!ТОр ВЗЭСМОДЦ 3

| користуеачем

опрацювання вхщних даних

I режим роботй_____| [ макромодслюеания

Модуль аиконання |

опоацювання еих'(дних даних .

евклщоеа в квадрат)

ортогональна а квадрат*

| горизонтальна [_ вертикальна сл!рагювиднэ

евклщова в куб!

к

эмювидна гвинтова

_Г

Ш1ЛЬН5

I ортогональна ! в куб!

>

розрщженз

-=г I - Г——-1-, { 1 1 !

| замЫа ь2"-ми ' -(горизонтальна! Ц нертикэльна "]

-¡горизонтальна [ -( вертикальна"]

-[ л¡ва похила ) -) хресгиком | "Г 31рКОЮ |

-{ поава похила! { Л1аа 1 права 1 -1 ПОХИЛ! 1 | почергово

тип сканувально! ооласгп •6" || "9" I!"12"

| замша "5"-ми {-Гза"м1на "б"-ми~Т

|. комбжована |побний пере

Мал.5. Структурна схема ППП "Сканувапьна область"

Четвертый розш'л грисвячений практичнм реал!зацн ¡нстру-ментальних систем з зикористаннпм рОзроблених алгоритма. Розроблено два лакоти прикладних програм: "Сканувальна область" i "Розм|'щення" yyin раал!зацм на персональному комл'-ютер! IBM PC. Розглянуто деяю можливост! розпаралелювання обчислювальною лроцесу для його рочлюяцп на багатопроце-сорних машинах.

У склад математичного i програмного забезпечення ППП "Сканувальна область" (мал.5) включено розроблеш' та дасл!джеи| в дисертац1йн!й робот! методи 1 алгоритми.

Мал. б. Структурна схема ППП "Розм1щення".

На баз! ППП "Сканувальна область" розроблэно ППП "Розм!щення" (мал.6), призначейий для використання методу ска-нуйальноТ облает! до реальних задач проектування конструкц!й комп'ютерно? та рад'оелектрокноТ техн!ки. В пакет вмидено комплекс алгоритма, що зд!йсйюють лочаткове розм1щення елсментш з подальшою його оптиМ1'зац1ею методом сканувальноТ облает!. Пакет реал!зовано як додатковий модуль розм!щбння до в!домо! системи проектування РСАЬ.

Описано результат експериментальних дослщжень розроб-ль-пих алгоритма при розв'язувант тестових ! прикладних задам. Експериментально дослщжено точн!сть та шэидкодто метод ¡в. Приведено найкращ! результату а тако>г представлено результата розв'яэку реальних тесгоаих задач.

ППП "Розм!1Цйння" написаний на мов( програмування С1++ I розрахований на розм!щення до 250 еламантш (так! обмеження системи РСАО) I вимагае 483 Кбайт« оперативно? пам'ят! (ОП), збтьшення розм!рност1 задач! на кожен наступний (п+1)-й елемент вимагатиме збтьшення ОП на (4п-2) байти (для 251 еле-мента, наприклад, об'ем ОП зб!льшиться лриблизно на 1 Кбайт). У випадку задач велико? та надвелико! р'озЫрност! необх^дио використовувати принципово гюгужжш! комп'ютери, а також робоч! отанцГ?, осшьки вже для задач! розмщення 10000 еле-мент!в необхЩно б!ля 96 Мбайт оперативно? пам'ят!.

В основ! методу сканувально? облает! лежить багаторазове розв'язування однотипних задач, що створюе широю можливост! для розпаралелювання обчислень. Окрем! з таких можливостей розглянуто в дисертац!?. У випадку л-процесорно? системи конструктив розбиваеться на л-сум!жних областей, - кожен окремий процесор зд!йснюе сканування в окремм облает). При застосуваин!' розр|джено? облает) сканування кожен етап сканування рекомендуеться- до виконання окремим з паралельних лроцесорт, причому необхщно вщелщковувати, щоб одн! ! т! сам! елементи не попадали одночасно в р!зн1 облает!. Також рекомендуеться розпаралелити обчислення критер!ю якост1, наприклад, роздтити обчислення сумарно? довжини зв'язйа на три групи: зв'язки м1ж елеМендами всередйн! сканувально? области зв'язки елеметтв всередин! облает! з елемёнтами поза облас-тю I зв'язки М1'ж елементами за межами сканувально? облает!.

В залежност! зщ наяаних техн!чних i часових pecypcie рекомендуються ряномажгж стратеги peani3au,iT методу, а саме:

« для комп'ютер1в типу Pentium поошдовно за ¡тераиуями збшьшу-вати розм!ри сканувально? обласн в!д найменших (з двох елемен-т!в) до максимально можливих (6-9 елемент1в);

• для робочих станц!й послщовно зб!льшувати розм!ри сканувально! облает! шд найменших до областей з 9-12 елеменпв, для областей з 15-16 елементю здшснювати моделювання областями мен'ших розм^рностей;

• для багатопроцесорних комп'ютер1в здмснювати розпаралелю-вання при скануванш та гидрахунку критерию якост1,;

• при формуванн! початкового розм!щення методом iepapxi4iioi декомпозици вибирати на кожному Kpoui розбитгя розбитгя максимально великий (в залежност! вщ обчислювальних pecypcie та заданих потреб точност!) коефндент дшення (4-16).

OCHOBHI РЕЗУЛЬТАТУ! РОБОТИ.

Розроблено нов! математичн! та программ! засоби для розв'язування задач! квадратичного призначення - розмидення елеметтв. Досл'щжено та розвииуто метод сканувально'! облает! з точки зору його ефективного зйстосування для задач высоких розм!рностей. Отримано наступи'! ochobh'i результат

1. Розвинуто для методу сканувальноТ облает! ¡ерархнний пщхщ до процесу onTHMiaauii розм1щення елеметтв, при якому пр'оцес зна-ходження розв'язку задач'1 велико? розм!рност! зводиться до пбвним чином оргажзоеано! множини задач мало! poaiviipiiocTi, як! роза'язуються !терац!йно.

2. Розроблено i об грунтовано нов! Стратеги (схеми) эастосуванея методу сканувально! облает». Для' зябезпечення бажаних харак-. теристик методу (точност! i часу виконання) рекомендовано ркзн!

послщовносп проходжання сканувальною областю конструктиву, дослщжено вплив П розм.рв I конф1гурац!й.

3. Роэроблено нош алгаритми та засоби для виведення оптим1за-ц!йного процесу з локальних мЫ1мум!в, в тому числ! застосовано

. елементи апарату генетичн.их алгоритма - випадков1 та спрямо-ваш мутанти.

4. Роэроблено новий апгоритм розмщення трупами для форму-вання початкового розв'язку задач1 з р1зногабаритними еле-ментами, який дае змогу отримати компактно розм!щення елеменш, що е погруроиаж на основ1 ¡х конструктианих особливостей.

5. Розвинуто I досл1джено триетапну схему пошуку розв'язку задач1 роэм1щення: на першому - здмснюеться початкове розмицення елемент!а; на другому - виконует^ся "груба" оптим!зац!я розмЬ щення засобами макромодипювання; 1 на гретьому етап! проводиться оптим1зац!я засобами . методу сканувально! облает!, Досл!дження Ыдтвердиди доц1льнють використання тэко! схеми.

6. Роэроблено ППП "Сканувальна область" для теоретичних та екс-периментальних дос/иджень методу СкануаальноУ облаоп. На його баз1 роэроблено ППП "РозмщенНй" для розв'язуванни задач проактуаання конструкций комп'ютерно! та рад!оелектронно! тохнки, який епшпрацюе з системою РСАО. ППГ) "Сканувальна область" впроваджено в навчальний процес для виачення методов дискретно! оптим1зац'п. ПГШ "Розмицення" рекомендуеться проектно-конструкторським орган!заи,1ям, ям проектують засоби ново! комл'ютерноТ та рад1оелоетро^ноТ технки.

(ЗСНОВН! ПУБЛ1КАШ1

I. Башпввяч Р.П., Телюк Т.М. ДеякГ можливост! застосування генетичних алгоритм!в а САПР конструкц1й електронно? технки.. -

36. доп. Mi*nap. конф. з генетичних алгоритм!в а м.Одес) (1995): Вид-во ОДУ, 1995, с. 217-218.

2. Базилевич Р.П., Тслюк Т.М.. Застоеування генетичних алго-ритм1в для розмицення олемемяи BIG та ДП на основ) методов iepapxi4Hoi декомпозици та сканувальноТ облает!. - 36. доп.: 5-та MiJKnap. науково'-практична конф. "УкрСофт-95" (м.Льв'щ, 1995): Вид-во ДУ"Льв!аська пол'|Технжа", 1995, с. 114-117.

3. Базилевич Р.П., Телюк Т.М. Застосугзання "мутац|й" як складово! частини апарату генетичних алгоритма для розмедення еле. меняв BIC та ДП на ocuoai Методу сканувальноТ облает). - Льв!в:

Вид-во ДУ "ЛьЕшеька полггехнка", Комп. в!смик-95, 1995, с. 6-11.

4. Базилевич Р.П., Телюк Т.М. Оптим!зац1я арифмётичних процедур в метод! сканувальноТ облает!. * Льеш: Вид-во ДУ "Льв!вська пол!техн!ка", Комп'ютерний вюнйк - 94, 1994, с. 5-10.

5. И.P. Bazylevych, Т.М. Telyuk. Application of mutants as operators of genetic algorithms for optimising VLSI and PCB elements placement at the basis of scanning area method. - Proe. Internet. Conf. on Genetic Algorithms .ancJ their Applications "MENDEL-95", Brno, Czech Republic, 1995, p. 25-28.

6. Телюк T.M., Базилевич P.П. Программе забезпечення методу сканувальноТ облаетт для ортиьпзацШ розм!щення елемвняв. -Зб. тез: МЬкнар. конф. "УкрСофт-94" (м.ЛьЫв, 1994): Вид-Bo ДУ "Львтеька пол!гехн!ка", 1994, с. 117-119.

7. Базилевич Р.П., Телюк Т.М. .'Матодичн! вказ!вки до циклу лаборатории* po6iT "Дослщження Методу сканувальноТ облает! для розм!щення елемент конструктивних вузл!в комп'ютерноТ технжи" з курсу "Математичне ! прогр&мне забезгтечення систем автйматизованого проеггування конструкздй комп'ютерноТ технки" - Льв!в: ДУ"Льв1йська пол!технка", 1995( - 12 с.

Особиетий внесок автора у розроблёння наукових результат^, <цо виносйться на эахист е вирпшльним.

Telyuk T.M. Mathematical, and programming means for eleinents placement using scanning area method.. Dissertation for candidate degree in technical sciences in speciality 05.13.09 -Mathematical and programme software for computer systems, - Lviv Polytechnic State University, Lviv, 1996. 7 scientific papers are defended, which include theoretical arid experimental researches för placement optimising by scanning area method. The new approaches and strategies for effectivis for the largë dimension problems method using in common with hierarchical decomposition method are elaborated. The new method for compact group initial placement is suggested. The new special CAD software is elaborated.

Телюк T.M.. Математические и программные средства для размещения элементов методом сканирующей .области. Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.09 - математическое и программное обеспечение вычислительных машин и систем, Государственный университет "Львовская политехника", Львов, 1996г. Защищается 7 научных работ, которые содержат теоретические и экспериментальные исследования метода сканирующей области, предназначенного для оптимизации размещения элементов. Разработаны новые подходы и стратегии эффективного его использования для задач большой размерности совместно с методом иерархической декомпозиции. Предложен новый алгоритм компактного, группового начального размещения разногабаритных элементов. Разработаны программные средства для использования в САПР.

Кпючов/ слова: дискретна оптим!зацш, задача квадратичного призначення, розм!щення еламентт, сканувальна область, гемегичн1 алгоритму прс"------1 —