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

ХАРК1ВСЫШИ ШШТЕХН1ЧНШ УН1ВЕРСИТЕТ

. 11а правах рукопису

Ша >вський Юр1й СерМйовнч

АЛГОРИГМИ 0ПТИМ13АЦП ГОРЮОНТШНИХ ШКРОПРОГРАИ

05.13.11 - натеыатичне х программе'задеэпечекня ."";.■ ойчислсваянх машня га систвы

Автореферат дисертацП на адойуттл эченого ступеня • ' кандидата техШч/ган наук

Харк1в - 1094

Праця виконана у Харк1вськоыу пол1теян1чкому уч!верситет1

Пауков! кср1вники:

- доктор тек[Цчнмх наук,, професор Костенко Ю. Т.

- кандидат техн1чиик наук, доцент Мали* О.М;

ОфШЯн! опоненти:

- доктор ф1з.-мат. наук, професор Яковлев C.B.

- кандидат техшчиих наук, доцент Miлов О. В.

Ведуче п1дприенство:

- 1нститут к1бернетикн , iu. В. M. Глушкова АН Укра1нн

Захист в1дбудеться "/? 1994 р. о "_" годин!

на зас!датп спец1ал1зованоГ ради К 068.37.03 у Харк1вському техничному ун!верситет1 рад1оелектрон1кн С3100£Э, и. Харък1в, пр. Лен1на, ,14).

3 дисертац1еп можна ознайомитися у б!сШотец1 Харк1вського техн!чного университету рад16електрон!ки.

Автореферат роз!слано

Вчений секретар спец1ал1зовано! ради канд. техн. Наук, доцент

г?»

a±kâL

Ljx.

1994 p.

Сукесов Е. А.

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

Актуалыпсть просЗлеми. Шкропрограмне управгиння иамъ центра лыи процесори класу 808G, епхвпроцесори арифметики вводу-виводу типу 8087/8089 та трансп' стерн. KpiM того ткропро- • граине управления це . основний cnocid peàniaaiuï обчиопень в . опец1ал1эованих йагатопрсцесорних ойчислсвачах, Такий BapiaHT. управления спрощус схемотехн!чну peajiisauic .- MÎKponpouecopiB та обчислввач1в, тому щокожна команда реал1зуеться не апаратно, а .иляхом виконання днтерпретурчо! ы1кропрограмн С МП), котра розм1щу-етьея в управлягшй пам'яп.

НашЛлыи складну opranioauic мае горизонтальна ы1кропрограмне управл1ккя, при як1й в ' горизонтальних; макрокомандах (МЮ, складасчих МТС мо»утъ одночасово роамщуватнсл i, як наслхдок, виконуватися декшька onepauifl.

Складность пронесу заповкення, тобто-упаковки, МК операщяш1 з врахуванням усього спектру ¿нформатйних та ресурсннх ойыежень обуиовила роэробку . систем автоматиэаци ы1кро.програмування, елеиентом яких являеться подсистема упаковки М1Крок£>ду.

В1др1энясть локальну та глойальну упаковку. При локалыий упакоьц-i операци одного лШйного участку.. микропрограмм' С ЛУШ розм1щуються в МК без врахування операций 1нших ЛУН. .ГНд час глобально: упаковки одночасно роэмццувтъея oriepaaiï рхзних ЛУМ.

Вийiр .задач1 локально! упаковки як основного об'екту дослхджень эумовлений ткм," що локальна упаковка являеться основой глобально! i для задач! локально! упаковки . В1дсутн1 ефективн! . методи рпиень. Останне пояснсеться тим, то дана задача взноситься до разряду комсЯнаторних багатоекстремалъних задач з важко находяуваним допустимим ршенням. Щльова функция задач1 визначена на мнояин1 перестановок операций, складаючих ЛУМ.

Традид1йной-ыоделло задач1 локально! упаковки являеться граф aaneïHocTi з.'данних СГЗД), ь1дбиваючий умови . зв'эку операций з , даних. IU умови встановкввть порядок використання сп1льних для onepauifl pecypciB з пам'яттп (типу per1стр) обчислевача. Порядок використання таких pecypciB визначаеться початковиы представлениям ЛУМ. .Джералом BapiaHTHOcTi розв'зання при фхксованому ГЭД' являеться форматно та функциональна оймежання, по визначавть правила запбвнення горизонтальных МК та порядок завантахення функц1-

3 ■

ональних ресурсАв (ком<51нац1нних схем та сп!льних лШй зв'зку). Серед умов взаемодН' операц1й э даних осойливу роль в!д1грають т! з них, котрх характеризуем ос5м!н даними мхж операциями, тобто визначають потоки даних в початковому ЛУМ. Остамих умови взаемодП оперший 'на статичних ресурсах, встановлвють порядок 1х виксристання р!зноман1тними потоками даних ЛУМ.

Суть нового гидходу до виршення задачГ локальной упаковки полягас в тому, цо як початков! 'розглядавться т!льки т! умови зв'язку М1* операциями, як! визначаоть обм!н даними, а оотанн! умови передуиалня на статичних ресурсах фориуються в процес1 резв'язування задач!. 1накше какучи, ГЗД скорочусться до графу .обмпив, створеного заданими потоками даних.

При такому . пхдход! предметом пошуку являеться не • т1льки порядок внкористання функц:!ональних ресурс!в, але 1 посл1довн1сть загрузки ресурс!в з пам'ятти р!зноман1тними потоками даних, складавчмми ЛУМ. Це засЗезпечуе вихГд- на як1сно новий прост1р р1шень, котр! ран1ш не враховувались при реал1эац11 дано! задач1. Метро роботи являються: . ' • . ' .

розройа методов та алгоритм!в одержання допустимих р1шень задач! локально! упаковки з ново! облает! пошуку;

розробка алгоритмов, ор^етованих на крату як!сть р!шень, як1 формувться;

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

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

Наукова новизна работи: 1) дроблена постановка задач! локально! упаковки, яка дозволила установити новий прост1р рхшень; 2) доведен! умови 1снування допустимого ршення в задач! локально! упаковки; 3) раэробяенх два методи та !х алгоритм!чна реал1зац!я "пя одержання допустимого ршення локально! упаковки; 4) розроблен! 8'алгоритм!в для покращення якост! допустимого ; ршення локально! •. упаковки; 5) розроблено алгоритм, дозволясчий використовувати ' пр!оритети теорх! розпису- в задач! локально! упаковки; 6) доведен! .корект^сть та к!нцев!сть, '■ дослужена складн!сть роэроблених алгоритм!в; 7) розроблен! 3 алгоритми глобально! упаковки, основанг на запропонованих методах локально!

'4.

Упаковки; 8) проведено ' числений експеримент, який дозволив встановити обчислввану ефективн1сть роэроблених алгоритмов.

Практична цхнихсть роботи.' Розроблений комплекс алгоритц!в .та . програм - внкористовувався при створеннх систем . автоматизаци ы1кропрограмування, як1 були випробуванх та •■ впровадженх у ПВО точних приладхв См. Москва) та у НД1 приладобудування Си.Москва).. ЗагаяышЯ еконснокпчний. ефект в!д впровадження розробок склали 60 тисяч карбованц!в С1900 р.).

Апробац1я результат^ працх Результатц роботи доповхдалиеь на сеи1нар1 "Теория автоматов и ее применение" в хнститут! к1бернетики ака[деыЦ наук Украхни (Кихв, 1990). та на I Всесовзнхй науково-технхчнхй конференцП "Координирусщэв управление, в технических и'природных системах" СКрим, 1991);

Публхкацп'. 'Результата ро<5оти в1дбит! , в дев'яти друкованих роботах..

• Обсяг х структура.роботи. Дисертац1я складаеться з. введения, п'яти роздхлхв, заклвчення, викладених на 130 стор1нках," списку використанох л1тератури. а 30 назв .та трьох ' додаткх.в; м!стить 19 ыалвн!ив.

Перший роздхл дприсвячено , зм1стовн1й постановах .задачх локально! и глобально! упаковки м!крокоду та аналхэу вхдсыих методов IX роэв'язку,.на баз! яКого сформульовано перел1к задач дослхджень та розробок; другий роздхл -.. формуванню та аналхзу иатематично! ыодел1 задач! локально! упаковки макрокоду, методам будування допустимих рхшень та-способам покращення хх > якостх при врахуваннх обыежень на ресурсах з паи'ятто; третхй • роэд1л -способам покрацення якост1 мхкропрограьш при врахуванн1 форматних та функцхональних обмежень.; четвертой роздал и иётодаы глобально! упаковки; п'ятий роэд1л' - оцхти обчислсвано1 ефективност1 розробленйх.алгоритмхв.:

Перший додаток мостить приклади, аллсструхш роботу системи м!кропрограмування та.: розроблених алгоритмов упаковки; другий додаток - результата експериментального досхцдження алгоритм!в; трет1й додаток - 1н$ормац1с про вправад*ення.результатроботы.

■'-.""• ■'.•:' ■ ЗМ1СТ Р0Р0ТИ.

Задача локально? упаковки горизонтального м!крокоду-вважаеть-

ся заданою, якао виэначен!:

1. Початкова посл1довн!сть э п операд1Я 0=СО^|1=ГГп),. складасчих Л1н1йний участок вертикально! МП.

2. Для кожно! onepauiï Oj nepepeniK викристовуваних pecypciB, во складае шюхмну pecypciB э пам'яттс Pj (тобто статичних pecypciB) та множину фуншионалышх pecypciB Стобто des пам'ятЬ ♦j. Множина Р^ складаеться э двох.гидкноюш та 4j, ресурси яких використовусться в!дпов1дно в режимах эалису та читання.

3. Моменти початку TBir i завершения TEjr а1тервалу внкористаня кожного ресурсу г ç Р^ и Ф^ в^носно початку,, в загальнону випадку, многофазно!" Oj.

4. Формати ьпкрокоманд обчисловача як множина складасчих ïjt noniB Fj=( fîj ^ПТр, 1=Г7Г.

5. Множина noniB < формат!в »пкрококанд для розм1«екйя кожно! Oj. . . -

Нехай <0j позначае умову передування onepauifl в початков1й посл1довност1.

Оператя . взаемод!е э 0j, якщо icnye такйй ресурс э пам'яттю г, до . • • • •

Г г € п Р j.

. L г 6 Pj n 3j. '

Взаемод1вч1 onepauiï 0^, Oj обм1нг«)ться 1нформац1сг> по ресурсу э пам'яттс г та являеться джерелом, a Oj - приймачеи, якщо: .

г б 3f n 4j,

°i<0r Г 0k<0if

. V к такого, що г е 3j,, виконуеться ^ о <0^

Налекн^сть будь-яко! onepauiï до МК горизонтально! МГГ визначаеться моментом початку П виконання Tj. Якао интервал виборки МК, тобто машинний цикл обчислсвача, являеться однофазним, одну МК складасть onepauiï з однаковим моментом початку. У випадку багатофазного машинного циклу одну МК складасть yci onepauiï, моменти початку яких належать до одного циклу.

В допустима горизонтально МП моменти початку onepauifl noBHHHi в!дпоь1дати сл1дусчим обмеженням:

1. Якщо Oj обм1нс>еться з 0, m г, то

6

[Т <Т -ТР

1г кг'

тк!Ь+т^г"твкг-

Якщо операнд взасмод1с з 0: на ресурс! г.

то

&

.V то

.ХТ^ТВ^-ТЕГ г, 3. Якщо операция С^ иае сшлышй $унвд1окалышЙ ресурс г о

.♦та^-лу

[трт^т

4. Якщо Тр Т^ належить одному машинному циклу, то хснуе фориат ^ такнй, що

Пц.Пи«^.

Неойхшш сфориувати' горноонтальиу МП, тобто упакувати складаюч! п НК операциями так, ш,о<$ ыШьизувати заданий критер!й дкост1 прх Т^.

Натеыатична цо'дочь локально! упаковки Нехай ПВ - ыноиша пар, вэаемод1ючих олерэц1й, а ПО - множила, пар, взаеиод^вч! операид! яких о<Ынмпъся данями.

Графовое ыоделло о<Лин1В початковок'' посл!довноат1 операций О являеться (Зезконтурний орграф ойипив Г0=(0,ДО), де ыножина дуг о(3м1нов Д0=«л>чр ^.О^.'е ПО и 0Х<0^>. '

Будемо ввахати, що в кножш:! пар ПВ\ГО порядок використання операц1ями стильних статичних ресурс1в не визначаеться почачковоо посл1дов1ист!) 0.' Гнакше кажучи, ш* операциям! кожно! пари з ПВМТО в1дсутня уыова передування, не дивлячись на и !снувания в 0. ' Але поскхлькн для, кожно! пари операций повинен <5ути роэв'язаний конфл1кт на сшльному ресурс!, тобто встановлений порядок його ьикорйстаинл, ыохлив! вар!анти розв'язання кон$Л1кт1в зображуються шляхом доповнекня ГО шюжиною диз'внктнвних дуг взаемодН ДДВ^Ш.рД.М)!«)^} е ПВ\П0>. У результат! отримуемо диз'лнктивний граф взаеыоди' ДГВ=С0,Д0 и ДДВ).

Поскхльки множина ДДВ эображае сукупн1сть потенц1йних умов передування операц1Й, конкретизац!я осташих ад1йсноеться вис5орок одного з двох ыожливих напряшав для кожно! диэ'юнктивнох дуги. У

7

результат! множила ДДВ перетворюеться в мноюшу дуг вэаемод11 ДВ=<С а е ПВЧ10), як! визначають орграф взасмодП

1В=С0,Д0 и ДВ).

Проте не у всякому довольно знайденому ГВ ■ в1дпов!дае виконувана, КП. Од!иею з умов недопустимой формуваного ГВ являеться наявн!сть у ньому заборонених п!дграф1в, появления яких у процес! орхентац!! диз'юнктивних дуг приводить до порушення умов обихну. НехаЯ С* - деякий подграф графу. НТВ, в яхоиу ресурси читання Ч^ кохно! операци' . О! . зображуються над д1аметром,. а ресурси запису - п1д дгаметром у в1дпов!дн!Я вершин!. У цьому подграф! (1,2) являеться дугою обм!ну, а вершини пар {О^.Од) 1 (С^.Од) з'еднан! диз'юнктивними дугами. У результат! розв'язання конфликтов на диз'юнктивних дугах одержимо заперечний п1дграф (3, умови зв'язку в якому порушують наданий'обМ1н м!ж и 0.

р.1>ч V РХ /

б

Твердження. ГВ являеться допустимим тод1 1 т1льки тод:, коли у ньому не !снус заперечних шдграфов та' контур!в.

При наявност: в початков1й посл1довност! 0 ыножинн пар" операций ПФ з сшльними фушодональними ресурсами вар!антн!сть порядкгв IX використання зображуеться множиноо диз'юнктивних дуг ДО={и,-.}},(.),1)1(0^,€ ПФ). - При допо'вненн! ДДФ до ГВ одержуемо диэ'юнктивний граф ДГФ=(0,Д0 и ДВ и ДДФ), в!дбиваючий вар!антн!сть використання функцоональних ресурс1ь. Виб1р одного з двох можливих напряшив для кожно! диз'юнктивноо дуги, в ДГФ приведе до орграфу порядку використання сп!льних ресурс1ь м!кропрограми ГМП=СО,ДО и ДВ и ДФ), де ДФ=Ш,.р| (04,0.> е ПФ). -

■ ГМП являеться допустимим,тобто • з нього можливо .отримати ьиконувану.МП, якдо в!н побудований на основ! допустимого ГВ та не иае контур!в. ■ - /

Форматно. обмеження (обмеження 4 в постанови! задач!) не мають графово? 1нтерпретаи,11. 1х врахування зд1йснюеться одним з двох способов. Зг1дно до першого з них будуеться перестановка операцой,

8

Jr як i й дотримуеться. упорядкування, эадане ГМП. Вона можв не

' «мпвпадати з початковою посладовшств. Ha ochcbí uiei перестановки

' зд1йсноеться будування горизонтально!' МП шляхом посл!доьного

вклвчення операций в МК. • Другий споскЗ передбачае- псбудову'

сполучень з мнохин onepauift, предки яких в ГМП вхе вклсчен! в •

складе^ МК. Пот^м з . сполучень вибирастъся те, яке, як •

передбачаеться, приведе до м1й1ыально! по подовхеннс МП. ОперацП

цього сполучення-вклвчаються в МК одночасово.

. .•• Якщо вадсутн! формата! ■ обмехення, побудова виконувано! МП

вводиться до. отчисления cítkh, сформовано*. з ГМП. Довхина' дуги

(i,j) uiei cítkh визначаеться як max (ТЕ;-ТВЛ, де Е(-тыно*ина^

•• . . . г € Rj ¡ 1Г Jr 1J

» JJ ...

яка /складаеться э стльних статичних pecypciB взаемоди та •

функциональных pecypciB onepauift O^Oj.'

При" фopмyвáннi МП зменшення значения max Т^ досягаеться ■ вибором opieHTaa.il диз'снктивних дуг при побудов! ГВ, _ вибором орГентацИ .диз'снктивних- дуг при побудов! ГМП та вибором перестановки чи сполучень при' ypaxyBanni форыатних обмежень. Поск1льки процес onTiiMisauii складаеться з трьох eTaniB, мохливе допущения , iao зменшення -max , роэрахованого на наступному ■ eTani; приведе. до зменшення max Т^ для слгдусчого етапу.

Алгоритм п'обудови допустимого ТВ. 'Побудова ГВ починаеться э ГО. noTiM в-ГО по одн1Й добавляються дуги Mix , парами операций,.' мавчими сп!льну диз'внктивну дугу в ДГВ. Побудова' ГВ зак^чуеться • при BH3Ha4eHHi напрямку, дуг дяя 'усах таких пар. Орграфи, виникавч! . при переход! вдд ГО до' ГВ, о'удемо називати графами стримуючих дуг (ГСД). Якщо.при побудов1 ГВ'в ГСД створився контур чи' эаперечниЯ пиграф, то bíh залишиться- у результувчому ГВ. Тому необидно .' запосйгти .створення KOHTypiB чн залеречних . п1дграф!в це в ГСД. -Анал!з.структури"заперечного. тдграфу показуе, nip Bin складаеться э трьох вершин, як! эв'.язан1 одндев дугою oóuiny та двома дугами . взаемодй', введеними при визначешп напрямку диз'снктивних дуг.-; Так як ui дуги взаеыоди вводиться посл!довно,' то. в процес! роэв'яэання дснуе ГСД, Ъ якому одна а них вхе введена, а друга цэ Hi. Шдграф такого ГСД, створений з вершин, .приймавчих участь в эаперечному пiдгpaфi, називаеться небезпечним. НебезпечниЙ подграф необх!дно знайти при його виникненнг та ввести в нього дугу,' протилехну tíй, яка приведе дб: заперечного падграфу. Така дуга

•' -а ■....■'■ - '

вазиваеться блокувчов. Аналогхчний прийом використовусться для запосЯгання контуров. У KOHrypi м1стяться три дуги взаемодП. Якао знаходити п!дграфи, в яких е двх з цих дуг, то введения дуги протилежно! до то!, яка приводить до контуру, 3anodirae його створенн». '

Будемо називати безальтернативное дугу (Oj.Oj), якто введения в ГСД протилежно направлено! дуги (Oj.Oj) приводить до створення ГСД, о якого не може бути одержано допустимий ГВ. Доведено, цо дуги, блок^гт небезпечнГ шдграфи, та дуги, 3ano6iraD4i створеннс контуру, яелйоться безальтернативними.

Наотупний алгоритм будус з ГО допустимий ГВ.

Bxifl: ГО, список pecypciB з пам'яттв та тип !х використання для кожно! onepauii.

ВихЦ: допустимий ГВ.

1. Перетворити ГО в початковий ГСД. " .

2. Знайти в ГСД yci безальтернативна дуги i ввести !х до графу.

3. Яквд в ГСД ус! пари вэаемодхочих onepauifl эв'язаи! дугами, то зупинитися.

4. Вкбрати у 'ДГВ пару операций, ' з'еднаних диз'внктивнос дугою; до ГСД ввести мхж цими операц1ями дугу в одному з. двох напрямкль; з ДГВ ьиклвчити вид!лену диз'внктивну дугу.

5. Перейти до п.2.

У цьому алгоритм! п1сля введения дуги на кроц! 4, може сл!дувати введения значно! к!лькост! беэальтернативних дуг на Kpoui 2. Можливо вважати, що введения цих беэальтернатиышх дуг зумовлено введениям дуги на Kpoui 4. У протилежшеть дугам, ао рводяться на Kpoui 2, дуги, як! вводяться на крои! 4, будемо називати альтернативними. ;

Для рхзноманхтних вар 1 антiв вибору пари операций та напрякку дуги Mi* ними на Kpoui 4 приведенный алгоритм може будувати будь-якпй допустимий ГВ.

У-приведенному алгоритм! суворо не визначеш TaKi дi i:. '

1. На Kpoui'1 алгоритм побудови початкового ГСД з ГО.

2. На Kpoui 2 правила пошуку беэальтернативних дуг,

3. На Kpoui 4 правила вибору пари onepauift та напрямку дуги «¡ж ними. ■ • - '

10

Пошук безальтернативних дуг.. Одним 1з тип!» безальтернативных дуг являсться дуги, попрреджуюч1 контур. Дуга, поперджуоча контур, може бути знайдена, як дуга транзитивного эамикання двох 1нших дуг п1дграфу, но приводиить до контуру, Транзитивне эамикання • графу можно побудувати за допомогою алгоритма ЮшЦ який будуе транзитивне замикання будь-якого графу за час 0(п"Ь. При побудов! ГВ треба багатократно будувати транзитивне замикання ГВ. Тому для зб!льшення швидкост1 розроблено алгоритм, ■ будусчий. транзитивне замикання графу, який був трэнзитивно замкнений, ало втратив цв як!сть у результат! введения до нього ново! дуги.

Алгоритм вшювления транзитивного замикання графу.

Вх!д-. транзитивно замкнений граф;' С1,р- дуга, що вводиться До нього.

Вих1д: транзитивне эамикання нового орграфу.

1. НемаЯ к1=1. 2. Якцо'у граф! немае дуги Ск1,1) та при цьому 1*к1 чи у граф1 е дуга (к1,.р, тр перейти до. п. 7. 3. Ввести- до графу дугу Ш,.р.' 4. Покласти к2=1. 5. Янщо с дуга С],к2) та иемас дуги Ск1.к2), то ввестн'до графу дугу Ск1,к2), 6. . Покласти К2=к2-»1; якщо к2<п, то перейти до п.5. 7. Покласти к1=к1+1; якщо к1<п, то перейти до п.2. 8. Зупинитися.

Приведений алгоритм вводить до графу такок дугу, яка викликала його запуск. Иого часова складность 0(п*1), де 1 -к1льк!сть-дуг, введших алгоритмом до графу. Поск1льки до орграфу, я якого дуги не виклпчались, не може бути введено б1льш н1* 0(п ) дуг, то сумарна складность використання цього алгоритму до одного графу не цс>реб1льшув 0(гА.

Ьгший приклад безальтернативних дуг - дуги, . блокурч1 небезпечн1 п!дграф;1. Небсзпечний п1дграф мгетить одну дугу э ГО та одну дугу взаемпди. Побудова цьго графу зв'язана з введениям дуги взасмод11. Тому небеэпочш тдграфч мохливо -знайте, переворяпчи для ложно! дуги, ¡'до вводиться до ГВ , чн не створве вона лебезпечного подграфу. Переварку появи небетпечного тидграфу необхздно гиконулати такок для дуг, ш.о вводяться алгоритмом транзитивного замикання: Шсля введения блокувчо!" дуги необхШю вшгопити трэнзитирну замкнен1сть орграфу.

1) Лхо А., ГшЩгафт Дк., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М: Кир, 1979, 536с. '

11

Алгоритм введения до графу дуг, ' блокувчих небезпечн! П1дграфи, та дуг транзитивного замикання.

Вход: ГО, транзитивно замкнений ТСД без небезпечних п!дграф1в, - альтернативна дуга, цо вводиться до графу.

. Вих1д: транзитивно замкнений ГСД без небезпечних п1дграф1в. • 1. Вм1стити до стеку дугу (!,,}). 2. Вибратн а вершин« стеку дугу. Нехай ця дуга 3. Для усхх операц1й 0^, нащадк1в 0^

у ГО, виконувати п.4. 4. Нехай г - ресурс обм1ну'и1ж И и 1с. Якщо г е 3^ та (к^1) " <( ГСД, то виконати алгоритм ь1дновлення транзитивного замикання для дуги (к,,эробивши занесения даних про кожну дугу, введену ним алгоритмом до стеку. 3. Для вс!х' 0^, предков 0ц у ГО, виконувати п. 6. 6. Нехай г - ресурс обм1ну и1* к н ,¡1. Якщо г е 3^ та дуга (11, к) <{. ГСД, то виконати алгоритм в!дновлення транзитивного эаыиканйя для . дуги (11,к), аробивши. занесения даних про кожну дугу, введену.цим алгоритмом до стеку.

* Приведений алгоритм мае часову складн1сть 0(п*1), де • 1 .-. ' к1лы»сть дуг, введених'до ГСД цим алгоритмом. Сумарна складность його використання до графу, э'якого не виклвчалися дуги.ОСп^).

В1дсут1исть заперечних ¡и дграф!в та контур1в достатня для .допустимой ГВ. Для ГСД ця умова необх1дна, але недостатня. Тому :' безальтернативн! дуги не вичерпуються дугами, , транзитивного замикання'та дугами, блокусчими небезпечн1 п1дграфи. ■ Аягоритми пошуку хнших безальтернативних . дуг' називаються ' алгоритмами •провокацШ та визначаетъся . рекурсивно.•. Як алгоритм провокаций нульового порядку .використовуеться алгоритм, якйй знаходить . блокуючГ дуги та дуги, транзитивного'замикання. Алгоритм провокаций порядку к вчзначаеться через алгоритм провокаций порядку (к-1) такое процедурою. . ' ■' •

'■ Вх1Д: ГО, ГСД. . . ■ '• . .' . . • '

Вихдд; ГСД, цо можливо щотить , додадков1 безальтернативн1 ' ЛУГИ. ■.. .'. , .. :''

.1. Нехай 1=1.' 2.' Покласти ^ =1, 3. Якщо чи в ГСД е дуга (1,.,Р чи (j, 1), то перейти до п. 7. 4. Ввести до ГСД дугу а ¡'в ,) за допомогою алгоритму пошуку безальтернативних дуг порядку (к-1). 5. Якщо.у ГСД створився цикл, .то виключити э нього дуги, введен! при останньому виконанн1 кроку 4, ввести за допомогою алгоритма порядку Ск-1) дугу(,},П и перейти до п.1. 6, Виклсчити з ГСД

' ■ : ■ ... 12"■•■•• •

дуги, введен! в нього при останньому виконаши кроку 4. 7. Покласти ^+1; якщо ,|<п, то перейти до и.З. Й. Покласти 1=1+1; якщо !<п, то перейти до п.2. 9. Зупинитися. '

В .практичних ц!лях рекомепдусться використовувати таку 'каскадну схему вибору порядку викорисговуваних провокаций.

1. Нехай к=0. 2. Зробити спробу побудови ГВ за- допомогоп алгоритма порядку- к. Якцо в процес! побудови ГВ не створено циклу, то вважати одержаний ГВ - шуканим. та зупинитися. 3,- Покласти к=к+1; якщо к<к|пах, то перейти до п.2. 1на«'ше як шуканий узяти ГВ

ПОЧаТКОВО! посл1довност1.

Наведен! аргументи на користь ИР повноти. эадач1 пошуку ус!х безальтернатиышх дуг. •

Побудова початкового ГСД э ГО. • Граф обмШв. у загальному випадку являетьед мультиграфом, поск!льки э одно! його вершини до !ишо1 мохе 1ти дек!лька дуг, по характеризувться р1зними ресурсами обмШв. Початковий ГСД з ГО можно побудуоати зам!ноо усах дуг зв'язувчнх пару вершин одрисв дугос. Проте такий граф буде ы1стити не введен! безальтернативн! дуги. Тому найб!льш ефективним ■е наступний алгоритм побудови початкового ГСД.

Вх1д: ГО.

Вих1д: початковий ГСД, що не. м!стить безальтернативних дуг виявляемих алгоритмом порядка к.'

1. Для вс1х дуг, иалежачих до ГО, виконувати алгоритм провокац!й порядку к. 2. Зупинитися.

Пошук кращого ГВ. Як!сть ГВ виэначаеться вибором ' пари : операцдй та напрямку дуги м!ж, ними на кроц1 4 алгоритму побудови ГВ. ГВ з найкращим значениям шр Т^ можна одержати за допомогоп описаного в робот! алгоритму, що використовус метод в1твей ' та границь, Але поск^льки це потребус великих ьитрат обчислсваного •часу то окр!м нього запропоновано 8 евристичних правил, як1 вибирають пару операнд та напрямок дуги киж ними,, виходячи з с!ткових характеристик поточного. ГСД. Якщо для ус1х операцШ поточного ГСД розрахувати ранн1 строки початку операц1й Тр^ та П1зн! строки Тп•, то можливо побудувати так! 4 характеристики для коию!" упорядковано! пари операцХй П,,]):

ПР2=Тр ПРЗ=ТпГТ^; ПГ4=Тп: -Т^. •

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

13

найсИлыие значения вибраного критер!я. Якщс> для кожно* з можливйх альтернативних дуг побудувати Ly - множину, яка складаеться з дуги (i,j) та безальтернативних дуг, що викликан1 вводом uiex дуги, то можливо одержати так1 4 пр!орйтети:

ПР5= niax Т -Tnh; ПРй= пах Т. -Т,. ; (a,b)eLj ¡Р- Pb . Ca,b)eLuPa пЬ

ПР7= max Т -Тг,; ПР8= max Тп,-ТпЬ; (a.WeLy"3 рЬ Са,Ь)еЦ j nb

Розроблено алгоритм, дозволявчий вшсориотовувати для .побудови

ГВ з кращою якаете приоритет!! теорп розпису;

Вх1д: ГО, список pecypciB з пам'яттв'та тип ix використання

для КОК1Ю1 onepauii. .'.•''

Вих1д: перестановка gnepauift, В1дм1нна в1д початково!

nocnifloBHOOTi, ГВ яко'г мож& бути використано для побудови.

горизонтально! МП. ' ■

1. Побудувати початкбвий ГСД з ГО. 2. Вьажати yci onepäui'i

нев1дм1чон1. 3. Серед нев1дм!чених onepauifi вид1дити л1дмножину в

яку не. заходить дуги з iHuiHx невшичених оиераидй. Ця п^дыножина

називаеться множинос onepauift доступних з даних. 4...- Ко'ристувчись

приоритетами загально! задач1 Teopiii розпису вибрати з множини

операшй доступних з даних одну. Пехай це буде 0^. '5. Покласти

. J=l. 6. Якщо 0j вне, В1дм1чена, то перейти до п. 9, 7. Якщо . 0^ та

0j не ьзасмодиоть чи вже з'еднан! * дугов., то перейти до п. 9.

8. Ввестив ГСД дугу Ci,j) за допомогос одного з алгоритм1в пошуку безальтернативних дуг. • Якщо в ГСД э'явилася дуга, яка виходнть • "з нев1дм1чено1 onepauii в onepauio i чи контур, то перейти до" п.12.

9. Покласти j=j+l; якщо j<n, то перейти до п. 6. 10. В1дм1тити ■ 0^ та додати Vi ь К1нець формуичо! посл)доьносх1. Якщо не Bei

■ onepauii BiflMi4eHi, то перейти до п.З. 11. Эупинитися.. 12. Виклйчити 0^ э множили доступних з даних; з ГСД. ьиклвчити. дуги, як1 введен! ь нього \ид час остачнього ьикоиання никну, ь im . 5-9; перейти до п. 4.

Врахування фунтцоналышх pecypciB та .форма'гних обмекань зручно виконувати одночасово. Це досягаеться шляхом побудови перестановки операцдй, яка вклвчае в codi упорядкування, задане ГВ. Для визначення порядку використання сгилышх функц!ональних pecypciB використовуеться порядок onepauift в перестаноыи. Побудова перестановки визначае також порядок включения onepauifl до

14

м1крокоыанди з врахуванням форматних обмежень.

Побудова перестановки по ГВ зд!йсниеться шляхом присвоения операц!ям пр1оритетхв. 0перац1я э б1льшим пр!оритетом 'дуде мати менший, номер. ТрадшЦ/lHi эасоби визначення пр!оритет!в роэрахован! на одноциюкш onepaii.ii. У uift podoTi пропонусться використовуватя як прюритети onepau,ii п1зн1 строки podiT с1тки, розраховано! по ГВ, що доэволяе розрахувати приоритета також для багатоциклових операцЦ.

Як то BiflcyTHi функц1ональн1 обмеження. Mix операц1ями р1зних МК можна використовувати алгоритми, як! будусть горизонтальну МП без побудови перестановки, шляхом вибору сполучень 'onepauifl з • -«ножини, предки яких у ГВ вже вклсченх до Ж. Для багатоциклових onepauifl крацу як!сть розв'язку з uiei групи дае алгоритм описанний в Иого недол1к у тому, що в визначених умовах в1н коректуе вже виконану частину розв'язки на иевизначену глибину. Така кореюия може потребувати dinbumx витрат обчислсваного часу.. У дисертацШий po6oTi запропонована коди$1кац1я цього алгоритму, яка позбавлена такого недол"1ку.

При BiflcyTHocTi форматних обмежень ■ врахування порядку використання ресурсов з пам'яттс та фушшонаяьних можна виконувати в сдший Texniui, шляхом одержання: э ГО безпосередньо ГМП. Для цього необх1дно зам1нити yci функц1ональн! ресурси, як! використовупться операц1ями на ресурси з пам'яттс, i вважати, що вони використовупться в режим! запису. Тепер застосуваняя : алгоритму побудови ГВ надает в!дразу порядок використання ресурсis з пам'яттс та фунмЦональних pecypciB.

Глобальна упаковка. Эапропоновано метод, збер1гавчий обм!ни Mi* oпepauiями pimmx ДУМ при змхн! порядку використання pecypciB з пам'яттю всередин! ДУМ. Це. дбсягасться введениям до початкового ГСД додаткових дуг.

Кожний метод глобально! упаковки складаеться з двох структурних частин. Це метод локально! упаковки i принцип видхлення сум!жних ЛУМ, як1 будуть разом упаковиватися. Зпдно з '¿У Тосого м., • iamura Е. et al. An Aproach to microprogram ' optimization considering resourse occupency and instruction formats. //Proceedings of 10lh Annual "Workshop, on Microprogramming. - 1977. - pp. 92-1Q8;

15-

правилами вщцлення таких труп ЛУМ метрди локально! упаковки под1лявться на шляха-ор1ентован1, в якиХ для кожного застосування алгоритму локально! упаковки вшцлявться ЛУМ, як! лежать на одному шляху, тобто Т1, Ы1ж якиш можлива безпосередня передача управления, та блок-ор1снтовань в яких операц!! можуть пересуватися т1льки М1* двома суы!хними ЛУМ. Для ус1х знайд^них в' лхтературх шляхо-ор1йнтованих метод1в ыожливо викориотання алгоритм1в, змишвчих порядок застосування сп1льних ресурсов з : паы'яттв, шляхом просто! замени ними традшЦйних алгоритм!в локально! упаковки.

Ус! блок-орхснтован! методи збер1гавть ыдображення ' одн1е! . операц!! вертикально! Ы1кропрограми в одну'операц!ю горизонтально! н!кропрограми. У робот! знайдена максимальна область,' в якШ виконуеться ця вОдповгдиисть - нижне дерево. Розроблено алгоритм, викормстовувчий ом!ну порядку застосування ■ сгильних ресурсов з ,-пам'яттю, та працювчий на нижньому дерев!. ■

Запропонована новаоцшка якост! горизонтальних мокропрограм, не потребуюча апр!орно! !нформаци про ймов!рност! виконання ЛУН, до базуеться -на припущен!, що ус! нащадки конкретного ЛУМ .. одержувть в!д нього упраыпння р!вно1мов!рно. Ця оиднка якост! ' К1кропрограми названа !нтегральнов.

Експерименталне дослЦження алгоритм!в. ' Перша група ' м!кропрограм генерувалась з- застосуванням датчика випадкових -чисел. Эксперимента дозволили ьщЦлити краще а пр!оритеФних правил, використовувться лри виборх альтернативно! дуги. Цим . правило^ стало правило. ПР2. Було Шдтверджено речения, ; жо. аыеншення тр Т}, розрахованого по ГБ, приводить до аыеншення •.'.. довжини одержувано! з нього МП. При робот! алгоритма з 400 • эгенерованих МП,', талька в одн!й з них необххдно було .застосування провокаций'першого . порядку. У вс!х пших . виявилось' достаткам . -алгоритма- нупьового. порядку.': Це • (идтверджуе обчисярвану ' ■ ■'. ефективнхсть Каскадно! схеми при побудовь ГВ.

' У друг!й'.частин; експерименту дослхджувались 23 МП з патетичного аабезпёчення реального обчислввача. Досл!дувалась. як!сть МП в'эалежност1 в!д застосування глобально! упаковки та зм!Ни" порядку викориотання ресурс!в з пам'ятто. Неэалежне застосування глобально! упаковки та способу зм1ни порядку ' ' ■ 16 / ''■'.'."

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

■ ВИСНОВКИ .

1. Сформована та досл!джена математична модель задач1 локально! упаковки макрокоду.

2. Використовувана модель дозволила знайти новий клас р!шень; як! не використовувались традицхйними методами упаковки.

. ,3. Досл!джен! умови допустимост! ■ графу взаемодИЕ, застосовуваного' при формуванн!. допустимого р!шет'я задач! локально!' упаковки.

4. Розроблено, метод одержання допустимого графу взаемодИ" по графу обм!н!в.

5. У рамках методу одержання графу взаемод!! розроблен! алгоритми пошуку. безальтернативних дуг, як дуг транзитивного замикання та дуг, блокуочих. сТворення заперечних п!дграф!в з

'пебезпеччих.

6. Розроблено алгоритм .в!дновлення транзитивного замикання графу, який був тр'анзитивно замкнений, але втратив цс властив1сть внаслиок вводу до нього ново!' дуги. • Це дозволило шдвищити швидк!сть роботи алгоритмов у раз!в, де N - число операц1й м!кропрограми.

7. Одержана група алгоритм!в, яка дозволяв знаходити безальтернативн! дуги, що не знаходяться як при транзитивному замиканн!, так I при пошуку небезпечних п1дграф!в.

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

9. Запропоновано 8 нових пр!оритетних правил та метод, дозволясчий застосовувати пр!оритети теорП розпису . для побудови графу взаемодП, що гарантуе м1кропрограми кращо! якост1.

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

11. Усунена необх!дн!сть повернень. при. використашп алгоритму, будуючого . горизонтальну м!кропрограму • вибором сполучень.

12. Эапропоновано метод, враховуючий обмеження ¡¡а функцхоналышх ресурсах та ресурсах з пам'яттв в един!й техн1ц1.

■ 13. Для ycix розроблених алгоритмов проведен! дослхдження ix часовох складностх.

14. Одержан! методи локально! упаковки м!крокоду поширен! на глобальну упаковку.

15. Проведен! .обчислвванх експерименти, но доводить ефективнхсть розроблених схем рхшень та раалхзуочих ix алгоритм1в.

' ПУБЛ1КАЦИ ПО TEMI ДИСЕРТАЦП

1. Мал-jx D. Н., Ардельян А. В., Боблак М. D., Наумов Л. Н., Шахновский Ю.С. . Алгоритм упаковки многоцикловых 'микроопераций. //Вестн. Харьк. политехи, ин-та. 1987; - N240: Техническая кибернентика и ее прил. - Вып. 7. г С. 59-62.

2. Малых О. Н., . Ардельян А. В. , Кожин' D.H., Шахновский Ю. С.' Моделирование микропрограмм сетями /Петри. //Вестн. Харьк. политехи, ин-та. - 1988. - N252: Техническая кибернентика • и ее прил! - выпуск 8. - С. 41-45.,

3. Малых Ö.H. i Ардельян A.B., Кожин D.H., Шахновский Ю. С. Этапы анализа структуры' микропрограммируеыого SIMD-вычислителя. .//Вестн. Харьк. политехи." ин-та. - 1989. . - N263; Техническая кибернентика и ее прил. - выпуск 9. - C¡. 59 -61. . '

. • 4. Шахновский Ю. С., Малых 0. Н., Ардельян A.B., Кожин D.H. Об ' ■ одном подходе к решению задачи расписания о динамическими ограничениями. //Вестн. Харьк. политехи.- ин-та. - .1990,— N277: Техническая кибернентика и ее прил. - выпуск 10. - С. 71-75.

5. Шахновский J0.С. Формирование микрокода о помощь» правила, определявшего порядок вклечения операций. //Вестн; Харьк. '

. политехи, ин-та..- 19Ö2. - N2: Техническая кибернетика и ее прил. - выпуск II. - С. .36-38. . •

6. Кожин D.H. , Малых 0.Н.; Прокопенков В.Ф., Шахновский О.С. ' Настраиваемая система ' автоматизации микропрограммирования матричного вычислителя. //Вестн. Харьк. политехи, ин-та. - 1992. -N2: Техническая кибернентика и ¡ее прил. - выпуск II. - С. 87-91.

7. Акопов В. И., Губарев Н. В. ; Евдокимов А. В., Малых 0. Н., Кожин D. H., Прокопенко» В.Ф., Шахновский Ю.С. Мультипроцессорный вычислитель для параллельных вычислений: структура и система

• ' - ■ 18

автоматизации микропрограммирования. - Научно-технический сборник "Вопросы авиационной науки и техники", серия. "Бортовые приборы навигации, контроля и управления", выпуск 7, 1992, •Московский институт электромеханики и автоматики. С. 23-31.

8. Малых О.Н., Иахновский С. С. Новый подход к локальной упаковке микрокода. //Вестн. Харьк. политехи, ин-та. - 1993. -Резание и инструмент. - выпуск 47. - С. 161.

9. Кожин Ю. Н., Малых 0. Н., Прокопенков В. Ф., Шахновский Ю. С. Описание перенастраиваемой системы генерации микропрограмм. //Вестн. Харьк. политехи, ин-та. - 1993. - Резание и инструмент, выпуск 47. - С. 162.

■ • пил. до друку7е'' С 9¥ . Форма! 60 X 847«- ПаЫр . '

Друк офсетчнй. Умпвн.-друк. арк. /,С ОЛ.т^-ьил. ът>«../,£ - Тир.

, - Зам. . .

.Хлрк1эське орсндне по.'игряф^щс Ыдпрпемство. 31№!>3 Хврхт, вул Свердлова, 115.