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

РГБ ОД

НАЦИОНАЛЬНА АКАДЕМ 1Я НАУК УКРА1НИ

1НСТИТУТ 1МЕН1 Г. В. КАРПЕНКА

На правах рукопису

КОЖАН Володимир Петрович

МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА СИНТЕЗ СПЕЦ1АЛ130ВАНИХ СИСТЕМ ОБРОБКИ 1НФОРМАЦН

Специальности 05.13.16 — застосування обчислювальноТ технши, математичного моделювання ] математичних метод!з

в наукових досл1дженнях, 05.13.14 — системи обробки шформацп та управлшня

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

/V п/^я

ЛЬВ1В — 1994

ДисертаиДев е рукошс.

Ройота виконака в ф1зико-ыехан1чному 1нститут1 Г. В.Карпенка Нац1онально1 акадеып наук Украхни

1ыен1

Науков1 кер!вники:

Член-кореспондент АН Украхни, докт.техн.наук, професор Грицик Володимир Володимирович,

канд.техн.наук, ст.наук.сп. Деркач Богдан Теодорович.

0$1ц1йн1 опонёнти:

докт. $1з. -мат. наук

Вальковський Володимир Олександрович.

канд.техн.наук, доцент Р1эник Володимир Васильович.

Пров1дна установа: 1нститут Кибернетики 1ы. В. М. Глушкова

НАН Укра1ни, м.Ки!в к

Захнст в1дйудеться

и 3 и

Ш

1994 р. о ' ' год. н«*

зас1данн1 спец1ал1зовано! ради К 04.01.01 при Ф1зико-механ1Чном; 1нститут1 НАН Укра1ни (290601,:Львхв, вул. Наукова, 5).

3 днсертац1сю иожна ознайомнтись в Й1(Зл1отец1 институту.

Автореферат роэ!сланий " ^ " ^1994 р.

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

Р.А.Бунь

Загальна характеристика роботи

Актуальность роботи. Стр1мкий pier ^велико! к1лькост! проект!в i розробок спецхалхэованих обчислювальних структур обумовлено рядом причин. По-перше, значно шдвищились вимоги до швидкостх обробки 1нформаци - в б4львост! випадков вона повинна оброблятись в режим! реального часу.. По-друге, технология HBIC Снадвеликих 1нтегральних схем) доэволяе виготовляти недорог! i компактах опец!ал1зован1 процесори або збирати хх э 1снуючих 1С. По-трете, через те, «о вартХсть ун1версальних високопродуктивних ЕОМ все не залишаеться високою, необходно звхльнити ix В1Д розв'язку задач, що часто зустр1чапться i як! достушп для. спец1ал1зованих обчислювач1в.

Використання високопродуктивних обчисловальних aacodiB для обробки онформацП визначило розпаралелювання алгоритм!в як один i3 основних напрямк1в.на сучасному етап! роэвитку науки i техники, особливо при автоматизаци складни* систем реального часу. Значний вклад у розв'язок них -задач внесли украхнськ1 вченх, Глушков В. М., Малиновський Б. Н., Самофалов К. Г., Капитонова D. В., Летичевський А. А., Боен В. П. , Луцький Г. М., Каневський D.C. та irani.

Побудова i використання спец1ал!зованих обчисливальних систем розглядаеться в нерозривному зв'яэку з задачею побудови паралельних алгоритмов. 3 одного боку, ватливо» задачею е автоматичне розпаралелювання алгоритм!в обробки хкформацП, В1Д якого залехить, в основному, yenix впровадхення багатопроцесорних систем в практику паралельних обчислень. 3 другого йоку,- при розробцх високопродуктивних обчислювальних эасойхв паралельно! дх! вимагаеться anpiopi визначятн Ti ochobhi властявост! внутрХшнього паралелхзму алгоритму i закономерности, яки« пхдкоряеться структура паралельних процесхв обробки iH$opMauii. Це дозволить максимально наблиэити структуру задач! до структур» обчислювально! системи,. во розробляеться. Така в!дпов*дн1сть шве. бути повнхетю досягнута лише тод!, койв Biioni основах принцшти побудови KnaciB алгоритм!в, но допускавть" розпаралелпваншг, тобто эакояи, якх виэначають внутршно структуру паралельних алгоритмов. В зв'яэку з цим, вакливос с задача розробка моделей паралельних сх}числень, ефективни? методов, паралельних алгоритмов i спец1а.-Хзоваких пристро!в реалхзац!! задач обробки 1н$ормац11 J реальному часх.

Виникае необХ1ДН!СТЬ в розробц! певного математичного апарату, який би.дозволив вивчати проблему синтезу паралельних алгоритмхв, ор1ентованих на обробку велико! кхлькост! швидкопоступаючо! 1нформац11 в системах реального часу,, а такок структур пристро!в ix реал!заци.

0дн1ею э головних тенденций роэвитку сучасно! обчислювально! техники в беэперервне удосконалення метод!в i засобхв паралельних обчислень i створення нових арх!тектур паралельних обчислювальних систем. Досягнення обчислювально! супертехнолог!i стимулювть розробки нових.проекпв арххтектур ыатричних процесор!в.

При роз^'язуваннх складних задач, коли процес пошуку оптимально! структури духе складниД, ..виникае необххдн!сть в декомпозши! великоI задач! на декхлька «агате тдзадач, розв'язок яких Б1домий або dinbiu простий j проектування обчислввачхв для яких простое. Для забезпечення вааемодп mix процесорами С як правило з рхзною геометрхею зв'язк!в ) при розв'язуваннХ складних задач в реальному масштаб! часу вицикае ;необх1дн!сть в розробц1 ■ ефективних методов просторово-часового узгодхення в макроконвей-epi систолхчних масивхв (СМ), пов'язаних умовою розв'язку задачу в результат! яких форми 1нформащйних поток ¡в даних на виходах одних СМ пристосовустьЬя для подач! ,на входи 1нших. Один з П1дход1в для розв'язку uiei проблеми - проектування вузлхв узгодхення Сконвертор!в), як1 б включалися Mix кристалами СМ, що узгодхуються.

Мета робота та задач! досл!дження. Метою роботи е роз робка i дослХдження структури алгоритмов, принципхв моделювання i синтезу ефективних паралельних алгоритм!в, як! ор1ентован1 на реалхзац1г> в спец!ал!зованих засовах обробки Хнформацд! в реальному 4aci.

Для досягнення мети були сформульованх наступи! завдання:

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

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

- досл1д»ення та ■ розробка методХв i алгоритм!в просторово-

часового узгодження в ыакроконвейерних системах для розв'яэку складних задач обробки ¡нформацП;

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

- дослгдження 1 роэв'язок задач! множення розргджених полхномхв I пол!номхв над полями Гаяуа, а також синтез спецгал1зоваиих структур для хх реал1зацП;

- доол1дження I перев1рка основных реэультат!в шляхом математич-ного 1 комп'ютерного моделювання.

Наукова новизна. Запропоно'ваний п!дххд доэволяе в рамках одн1ех модели описувати як алгоритми, так I 1х реал1зац1п, 1 е зручним 1нструментом в задачах автоматизацН дослхджень 1 розробки спецхалхзованих обчислювальних систем для робота в реальному час:. Виходячи з анализу структури алгоритму, отримано розв'язки задач оптимхзаци спец1ал1зовано! систем-!. Роз роб лен! методи' I алгоритми просторово-часового "згодження 1 моделювання систолхчних процесор1В, пов'язсиих умовоо задачх, що розв'язуеться. Синтезовано спецхалхзован! I ун1версальн1 узгоджувач1 для реалхзацН взаемних ' перетворень рхзнах класхв форм 1нформахийних потоков даних. Запропоновано ряд арххтектурних ршень. задач! множення розр1джених пол1ном1в I множення пол1ном1в над полями Гьлуа для реалхзацН спецхал13ованих систем обробки 1нформацх1.

На захист виносяться'наступи 1 основнх положения:

- схемно-функцхональна модель обчислень, ' яка орхентована на ефективний опис к л ас I в паралельних алгоритмов, обробки хнформацы;

- розв'язок оптимхэац1йних задач спецхалхзованих систем Сзнаход-ження мхнхмального часу обробки 1 мШыальнд! к1лькостх процесор1в) на основ1 аналхзу структури алгоритмов;

- методи х алгоритми просторово-часового узгодження СМ, як! об'еднан1 в макроконвейер для розв'яэку складних задач обробки 1нформацП; • '

- моделювання спецхалхзованих систем ойробки ]нформацх! для класу . прим1тивно-рекурсивних'функц1й;

- синтез структурних схем узгодження в макроконвейер1 СМ;

- методи розв'яэку задач1 множення. розрХдкеиих пол1.гомхв 1 полхном1в над полями Галуа, а також структури ойчисдювачхв для IX

реалхзацм,

Практична uiHHicTb. Отриманх результата дають моклив1сть реал1зувати концепцию глибокого розпаралелввання процесу обробки на •pi3HHx р1внях iepapxi4Hoi структура алгоритм!в, синтезуватй новх виоокоефе.ктивн! паралельнх алгоритма i засоби ix реал!зац1! в реальному. 4aci. На основГ теоретичних дослхдхень розроблено структурнх схеми узгодхення систолхчних обчислсвачхв для синтезу макроконвейеру при роэв'яэуванн! складних задач обробки 1нформац1!. Синтезовано спец1ал1зован! помножувач! розр1джених полхноыхв i пол1ном1В; над полями Галуа . Розроблено программе забезпечення як Инструмент в задачах автоматизацд! дсслхдхень i синтезу спецха-лхзбваних обчислввальних пристрохв для роботи в реальному 4aci.

Реал1зац1я "результатхв робота. Дослхдження, як! виконувались в дисертац1йн1й робот!, проводились у вхдпов1дностх з планово» тематикой ФМ1 НАНУ - згхдно Державно! науково-теххичнох програми 6.2.2. "Перспективы! хнформадхйнх технолог!! i високопродуктивн! системи", затвердженох ДКНТ Укра!ни. Теоретичн1 i практичнх. результати роботи використовувались в науково-дослхдн1й роботi "Розробка експертних систем для синтезу високопродуктивних паралельних обчислввальних систем на базi систол!чних структур i системних середовищ Г' !х застосування до розв'язку задач комп'ютерного матерхалознавства".

• Апробацхя роботи. Основнх результати були викладенх i обговоренi;

- на Всесосэнхй нарадх "Конвейерн1 обчислввальн1 системи", Кихв, 1985 р.; "

- на V,VI,VII Всесовзних школах-семхнарах "Розпаралелввання обробки ¿нформаШ", Льв1в, 1985р., 1987р., 1989 р.;

- на III Всесоюзн1й конференцп "Математичнх ■ методи розпхэнавання образхв", Льв1в, 1987 р.;

- на BcecoB3Hifl Hapaki "Високопродуктивн! обчислювэлыи системи", Талл1н, 1988 р.;

- на Мхжнароднхй конференци и1нформац1ййх технологii для аналхэу зображенъ i розпхэнавання образ!в", ЛьЫв, 1990 р.;

- на MlxHapoflHiS конференци з хнформацхйних технологий i систем, Льв1в, 1993 р.

Публ1кац11. По темх дисертад1йно! роботи опублХковано 16 робхт, в тому числ1 6 винаход1в.

Структура 1 об'ем роботи. Дисертац!я складаеться а вступу, чотирьох роздШв та висновкхв 1 викладена на 142 сторЛнках включно з 25 стор. графХчного матерхалу 1 перелхком 122 иайменувань л1тератури.

Эм1ст роботи

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

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

Запропойована модель, яка визначаеться трхйко»: <Т,1,М>, де Т - хндуктивний клас об'ектхв - функц1ональних схем ТС V,ГЗ, причому V 1 Р - вхдповхдно мнохина елементарних функц1й 1 хх операторов композицП; КV) - хнтерпретацхя; М - модель. ХнтррпретацХя К\0 для кохнох (Ч е V -*адае функгЦю IС Г1 >. Модель обчислень М описуе процес визначення значения функцП, яка вхдповхдае деяк1й 1 функцхональнхй схем! мнокини Т х 1нтерпретац1х I. Функциональна ; схема вхдобрахае структуру консгруспчох функцхх, тобто е'| структурованим описом вкбраного методу . роэв'язку задач1 в ; функциональна формх. Бона »нрахав суть эадачХ, яка розв'язуетьс,., I сукупнхсть функцхй Сабо Шдзадач) 1 хнформацхйн! эв'язки мхх ними.-Мнохина ТСУ.Р) ( як э&микання мкохизи Г правил композиций над ! ннохиною V виххдаого базису) використовуеться в якост1 функц1ональноХ мое* задания фуюсихй, де V «= < б , I ™,'о >, ! Р = < Р.в ), 5, I о - в1дпов!дно функцх! сл!дування, вибор'у, 1 функц1я-константа, а - в1дповхдно оператора примхтивно! ,

рекурсП 1 суперпозицН.

Досл1дхено мохливХсть опису структур орган1эац11 обчислень термальними представлейняки деяких обчислювальних функдхй, 1 навпаки мохливхсть а деякями термальними представлениями обчислсвальних функцхй асоцхввати певн! структури обчислень, як1 спряыован1 на паралельну обробку.

Визначимо функцхр 1 •,композиц1йнох" складностх у I € Т(У,П рекурс!ео:

якщо t i С. l(t) =0; • „

якцо t t Ct ,t......t ), то Ht) « I iCt, ) + 1, де

1 * " 1 si

C= < t'e T(V,F) I topCt') e (R.S) >, top(t3 - "вершина" терму t.

На останню р1вн1сть сл1д дивитись як на правило, в силу якого можна обчислити КО, якцо bIaomî значения l(ti). Функц1я ■l(t) визначае к1льк!сть правил коыпозицП, якх беруть участь в noàyaosi терму t.

На uhoxhhî п1дтерм!в sbtCt) виэвачимо функцию sbtCi) <0,1> таку, що.Су i) (у t'= a(Li.... ,UD) € sbt'Ct), i=l,dCt):

■ift.î = •/ 0, t'É С •

\ 1, в iMiioMy випадку,

d(tb глибина терму t.

Сформулюемо достатн! уыови розпаралелюваяня процесу

отчисления функц!i, яка представлена термом t e TCV.F) в

формал!зацП прим1тивно-рекурсивних функций.

Теорема 1.1. Якщо для t e TCV.F) виконуеться умова dit)

I E t Mt ) > 1CU. (1)

i si t^e «ы'а> * VA

то процес обчислення функц1х, представленоï термом • t, допускав паралельну орган1зац1в одчислень,

В podoTi приводиться алгоритм, який дозволяв реал!зувати концепцхю розпаралелювання фуншцй на заданому ptBHi ( представления в ярусно-паралельнхй $opMi - ЯПФЗ шляхом структурного аналХзу терму t e TCV.F), за допомогов якого вони представляоться. Реалхзацхя алгоритму проводиться шляхом комп'ютерно! обройки.

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

Оптимальний метод розпаралелювання Mo визначимо через Сто,То). Такий эапис означае, цо можна розв'яэувати задачу за допомогою то процесорхв за То ярусХв, де шо = i|n п, То .= ш^а Т» ,1=ГГр ,де р визначае к!льк1сть всеможливих И». Задача забезпечення мШмаль-

ного часу роэв'яэку формулюеться наступним чином: ш - задано, а Т ® То • т^п Т1, Друга в&жлива задача мохе бути представлена так: Т » Тх, га ■ Ио » т|п пи, де Т« е наперед заданий час роэв'яэку задач!.

Нехай для I « аСЦ ., Дга) € Т(У,Ю заданий час Т* » А ♦ с, А « (КО + 1, 1 нехай го - задов!льняе умову

-» I

я - 1 < С4%с) I £ ХАЭ й и. (2)

1^6 «ь1л '""а) *■

X«

I Е ^ хв,-э-¿мсо«5 2 Е

«ы,А ' "и> * ¡а гке »ы ,А 1 *

е 2 , > 0, с > 0.

Теорема 1.3. Якщо виконуеться умова С 2 ), то мШмальне число необххдних обчисловачхв для реалхзацН функцН, яка представлена термом I е ТСУ.РЗ нор1внче га.

Отже, роэв'ячок задачх визначення мхнхыального числа обчислсвачхв, як1 эдатнх реалхзувати обчислювальний процес за 1 заданий час Т», дорхвнпе то=Г У "), де

-1 з

Т - пах + сЭ I £ ..ХЯ.»,

1 1=1 1.6 «ьг 1 а»

к

1 величина Г х 1 означав найменше ц1ле, яке бхльше або р1вне х.

Роз^'язок задачх знаходження мхшыального часу обчислень функцП , яка представлена термом I е Г(У,Ю, дас наступна

Теорема 1.4. Якщо число обчисловачхв ш задов1лыше умовг С2), то об'ем обчисйень, Який заданий термалышм представлениям I е Т(У,ГЗ, шгна виконати за То = сКО+с+1 одишць часу.

Створено систему комп'ш-ерного анал1зу термальних представ-лень обчислсвзльних функцЦ з метос рсзиаралелпва"ня функцхй на заданому р1внх, роэв'яэку задач знаходження мШиального часу • скЗробки 1 мШмально! к1лькост1 процесор1в.

У другому ЪоздШ . проводиться досл1дження метод!в просторово-часового узгодження в макроконвейер1 СМ. При проекту-

iO

ванн1 систол 1Чних о<5числввач!в для роэв'язку складно! задач1 природньо розбити задачу на гпдзадач: так, щоб для кожко! з цих задач проектування систол1чних обчислювачхв було простхше .С або структура яких вже ведома). KpiM того, обмежрчня на к1льк1сть ВВ0Д1В/ВИВ0Д1В i площу кристалу не дозволяв реалхзувати на одн!й HBIC матричн1 операц!! довхльно! розмхрностх. Розыхри матриць HBIC обмежуються технолог:чними факторами. Вони також ыають i фхзичн! обмеження, о<5уыовлен1 к1льк1стю виводхв (вход1в/виход1в). Не дивлячись на передбачуване зб^льшення рхвня 1нтеграцН число виводхв буде обмехуватись кхлькома сотнями. Це обмежуе пристро! на НВ1С з точки рору входхв/виход1в. Природнхм розв'язком проблеми вход1в/виход1в, так як i подолання обмежень на розм1ри матриць, е розбиття обчислювавлыю! задачх на бхлыи др!бнх. Таким чином, кожна ыатрична операцхя з набору у ыоже бути виконана з •використанням не одного, а декхлькох СП, як: утворюоть Ha6ip <р. Для забезпечення взасмодхх мхх матричними процесорами з рханос reoueTpiec зв'язк1в СniHiflHi, квадратах, гексагональн!,' трьохмхрнх i хн.) виникае необх1дн1сть в розробц1 ефективних методхв просторово-часового узгодження СП при розв'язуваннх складних задач в реальному масштаб! часу.

Форми розпод1лу д^них або форми !нфорыацхйних поток!в (Ф1П), що проходять через систолi4Hi процесори з р1зною конф1гурацхею тя час ix робота можуть бути р!зними, а це ускладнюе з'еднання СМ для розв'язку о дню! задач!. Для усунення цих перешкод необх!д::, узгодження систол1Чних npouecopiB, в результат! якого форми !нформашйних потокiв на виходах одних систол!чних npouecopiB пристосовусться для подачх на входи !нших npouecopiB. Для розв'язку uiei проблеми icHyDTb наступи! п!дходи:

- використанйя загально! пам'ят! для обм!ну даними;

- проектування СМ таким чином, щоб вйх!дний формат даних одного масиву був таким як вх1дний формат наступного масиву в систол1чноыу какроконвейср1;

- використання рхзних тип1в схток обм1ну;

- проектування вузл1в узгодження, як! включалися б uix кристалами систсшчних npouecopiB, до узгоджусться. > :

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

fi

останньс 1 п1дходу.

Ф1П Дании будемо представляюти за допомогов вектор1в, як! характеризурть, змщеиня один в1дносно одного рядкхв ado стовпцхв матриц!. Напрямок роэпод!лу даних аада§т^ся зростанням хндексхв. В робот! досл!д«усться клас <ИП даних DC I, JJ :

К g < DCI.J) I I,J e 2 \ I*,Iy,Jx,Jy e <-1,0,1», де Ix,Iy,J*,Jy проекцИ векторхв на Bicb X i Y.

Вимачимо властивост! Ф1П даних, як! необх!дно враховувати при проектуваннI конвер£ор|. ч

Дв1 Ф1П даних D (I' ,J' ), D CIa,Ja) е К назвемо екв1валент-

I я

ними, якщо Ii = IiS , Л. ~ Jft , СЗ)

де 1х , IS Счр1дпдв!дна Jit , J| Проекц^! ректор!в I1, I1 С в1Дпов!дно J* . J* Ф1П DC I1, J* ) i DCIa,Ja) на Bicb X .

Без втрати эагальностх, вважаемо, що елемент хп,, для обох форм, як вххднох так i виххдно!, розмщений на початку система координат ! дан1 рухасться в додатньому напрямку oci X. Отже, "порядок", в якому з' являються на входх СМ Сабо виходх) двх Ф1П !дентичний. Пров!вши розбиття мнояини К на систему п!дмножин, зг!дно умови СЗ), що е, очевидно, в!дношенням екв1валентност1 на множин! К, отримуемо:

Теорема 2.1. Якцо р е в!дношення екв1валентност! на множин! К, то сукупн!сть BiciM р - клас1в екв!валентност! становить розбиття множини К.

С у i) К».«0,. К= р К|,. Kfx* 0, i*j, де

Ku = <D(Î, J) e К I Ix=l, J*=s, l,s e {-1,0,1)) .

V D e К визначимо onepauic !нвертування R:

R: DCI,J) -► D'C I*J*3 I I*=b, Iy=-Iy, J*=Jx, Jy=-Jy,

onepauic мультиплексування M:

V D e Ksi с К , s,1*0

M: DCI,Ъ -> D'C Î.'j'd j I*=b, Jx= Jx, JyJy, ïyly e < 0,1 ),

V D e Koi с К , 1*0

M: DCI.J) -► D'C Î'J') I Ix=li, Jx'Jx, JyJy 6 { 0,-l>, tyly-i,

Y D € Kso с К , s*0

M: DCI.J) -► D С I.J ) I I«*!,, Jk«Jx, JyJy«Í, lyly e < 0,-» .

Класи Ktl замкнут! в1дносно вееданих ontpaiU«. Для »заемного

перетворення доэ!льних ФШ дани* DtI,J), D(I!j5 «

достатньо скориетатись операцию мультапюкоуминя i (або) опсра-

ц!ес !нвертування.

Теорема 2.2. Взаемн! перетворення Ф1П даних D^CI,J) s Kt,cK . j =ТТБ зд!йскюються за допомогою операций днвертування i • мультиплексування.

Для кожного класу К^виберемо дов1льну Ф1П даних, яку наэвемо стандартною для даного класу. Однак, з метою м!н1зац!! KinbKOCTt зв'язк1в вибирати необх!дно Ф1П даних з мШмальною KinbKicTD ПОТОК1В, тобто для яких виконуеться умова IyJy=0. Отже, для реалхзац!i взаемних перетворень Ф1П даних кяасу К , беруться до уваги 8 вх!дних ( i в1дпов1дно вих!дних ) стандартних Ф1П даних. Якщо ж в poní bxííhoí С або вих1дно! ) трапляеться Ф1П в!дм1нна в:д стандартно!, то зПдно теореми 2.2. вона зводиться до стандартно! i дал1 до розгляду вже беруться перетворення стандартних Ф1П даних. Взаемн! перетворення стандартних Ф1П даних назвемо базовими.

Теорема 2.3. Для ^р|ал1эацИ взаемних перетворень стандартних Ф1П даних DjCI,J) е К, 1=1,0 достатньо 14 базових перетворень:

Отже, всi взаемн! перетворення стандартних Ф1П зводяться до 14 базових перетворень з двома вх1дними Ф1П А С -f-*) í Е С ^ ' ).

Таким чином, будь-яке взаемне перетворення Ф1П даних класу К можна представити наступним ланцюжком перетворень:

Dtj-► DInr—» D0ut—♦ Dkl,

де Di j СDici) - вх1дна Свих!дна ) Ф1П даних, i,k=T73, j, 1 =ГГШ ; pin cpOvitj _ ВХ|ДНа ( вих1дна ) форма !нформац!йних поток1в базового перетворення.

В poöoTi запропоновано алгоритм взаемних перетворень Ф1П даних, що належать класу К.

ВаХливою задачею при проектуванн! вузл1в узгодження с

роэв'яэок задач! энаходхення мШмуму залам'ятовуючих ком1рок ' пам'яТ1 Вш1п, нео<5х1дних для перетворення даних з одного формату в 1нший. Позначимо через Сх(1,1 СуО.р - координата елем§нтачх1); I* 1 3» С1у х Лу) - проекцП вектор1в I 1 .1 на в1сь X Сна в1сь У). Тод1, С*(х,Л = (1-1)1* + д-Шх ;

Су(1,р = Сх-1)1у + д-Шу . В координатн1й 1нтерпретацН х - координата представляв хронометраж,- то<3то елементи э однаковою х координатою з'являються на вход1 (виходо) в один 1 той самий час.

Проведемо розбиття ынояини даних X = < х) ^ : п >

1 визначимо частковий порядок на них. Вххдне розбиття д!лить вххдний масив X на N1 пЦынохин 1р. Ш ,11 п ^ = 0, де

1р=<хи1СхС1,р - <1-»1][ ♦ д-Ш? . ар> , ,

■—7 7

причому Iх I Зк проекцП на в1сь х векторов I, входноо Ф1П даних., Вих1дне розбиття долить вих1дний масив X на N0 мнохин Ок, 1 < к < N0, 01 л С^ = 0, де -

О^х^С.Сх.р - (1-131®. = а,) ,

причому 13 х 33 -проехцН векторов виххдно! форми 1° 1 Л°на аось х.

Позначимо через 3 10 в1дпов1дно множину вх1дних 1 виххдних роз<5итт1в:

в = < 1р I 1<р<Ы1 > , 0 = { Ок| 1<к<И0 >, П = 8 и о .

Визначимо частковий порядок "—на множин1 П наступним чином. Якщо 1к —► 1р, тодГдан1 1р з'являються на входх ран1ше, н1* 1к. Якщо 0* —» 0р, тодх дан1 в 0р з'являються на виход1 ран1ше, н!ж в Ок . Далх, якщо Ок —► 1р тод1 дан1 в 1р повишп з'явитися на входх ран1ше, нож дан1 в Ок на виход1. Для появи елемент!в многани 0р на виход1 елементи множини 1р так!, що Ок п 1р * 0 повинн1 бути на вход!. Таким чином,

1) 1к—» 1р , якщо Юр ;

2) Ок—► 0р , якщо к>р ;

3) Ок—► 1р , якщо Ок п_ 1р * О а<5о 3 е 2 таке, *о ; 1Ч п Ок »«0 1 1ч—► 1Р.

1э означенна вкшшм. то якцо О* —> 1Р, тод!

Ок—► 1р-1—► 1р-'» !»■ Число чк таке, до Ок —► 1р 1

О* -!<-» 1Ри назввМО клвч*м для Ок , так як вс1 сп!вв1дношення м!ж 1р 1 Ок будуть Ё1ДОМ1, яктхльки чк буде знайдене.

ПМ викориат»?и метод динамичного програмування для знаходження Втщ, мнэкини 01,0»,,..,0к анал1зуються посл!довно.

Теорема 2,4. Кхлыисть буферних ком1рок пам'ятх Ьк , як1 неабххднх для ыножини виххдних елементхв Ок визначаеться сп1вв!днощенням: ч

Ьк = 1к|1М-кГ|01| •

1 =« X ¿1 • .

Задача знаходження мШмального числа буферная КОМ! рок, пам'ятх Втт, якх необххднх для" перетворення даних одного формату в ¿нший визначаються алгоритмом динам1чного програмування наступним чином: "

, V 0;

В = шах { В , В - \ 0 | * ? | IЛ ) ,

Роз'язок задач! проводиться за допомогою комп'стера.

В третьому роздхл! на 'основI розроблених алгоритм!в запропоновано розробки спеиДалхзованих 1 унхверсальних узгоджувач1в СМ, якх призначен1 для реалхзацН взаемних перетворень даних э одного формату в хнший 1 включаоться в тракте передач! даних мхх парами систол1чних масивхв. Проектущю* конвертора залежить вхд типу макроконвейеру СМ. Якщо статйЧйа реконфхгуратя реал!зуеться до початку виконання задач, <$а перетворення хнформадхйних поток!в даних мхж сумхжними стадхяиа макроконвейеру фхксоване х в ' цьому . випадку . використовувть спец1ал1зован! конвертори, то в динамичному макроконвейерх використовусться множина СМ, якх при необххдностх Хв. залежностх вхд поставлено! задач!) можуть змхнвватися. В цьому випадку виникае необхгднхеть у використанн1 ушверсального конвертора. Остання стратепя використовусться в таких техн1чних системах, в яких схема зв'язк!в не е детерм1нованоп. Виб1р характеру

реконф1гут>ацИ визначаеться вимогаыи облает! застосувань.

Для опису роботи запропонованих узгоджувачхв визначимо формальну модель, яка баэуеться на cniвставлвнн1 кожшй дуз! графу обчислювача неск!нчено! поел!довност!, елементи лко! належать до множини 1R(j= IR U Ш , де символ б означав "не мае значения". Посл!-довн!сть даних тц ,яка пов'язана з ребром Су,13, де у - задае тип дуги, a i - е м1ткою вершин, на якхй дуга зах!нчуеться, представляв собою воображения щ: H ч ^ таке, що rçiCU е И?^. Множину таких посл1довностеЯ позначимо через 0^= { т?| rj: Ш —» }. Виз-начивши функцхо ТСт)3 « ti| 7jCi3 * â л С y j>i ) rçCj) = б 1, позначимо множину ск!нчених послхдовностей <т) е Rj f ТСт)Хоо ), на якхй введемо наступи! оператора: Г^, який виконуе вставку к 6-елемент1в спочатку послхдовност! 9г, який nouinae г б-елемен-tîb Mi» yciMa сус!дн!ми елементами i

О*

?

е^ = ç

ДО ,W2,

= V

7) en

• {

6 i i fi-k)

i < k i > V

Де

ç _ ^ £IC i+r)/(r+l)], i*Cn-i)r+n yn e N

в !ншому випадку

'""С^!,...¿¡я) 1 ? - оператор мультиплексор визначае модель мультиплексора, який мхетить т вход!в . В!н

починае свос роботу в момент I = г ! пер1одично мультиплексуе сво! входи через хнтервали часу ул ...

Використовуючи формальне операторне представления с!тки процесорного масиву, розглянемо клас перетворень Ф1П даних АС в В С $). На Мал. 1. аображено направлений граф, який складаеться з вершин двох типхв: вершин вбоду/виводу 1ГП. внутр!шн!х вершин Л, !^=ГГп, п - розм!рн!сть оброблюваного масиву даних.

- i t -H •»А t 2

20 ..P~i.lt 7)2 о 21 Jhz fiai 22

-и

iS-

Мд

П8П-«

Мал.1.Граф узгоджувача для перетворення Ф1П даних А в р.

Кожний вузол Ci,j) репреэентуе залам'ятовуючу комхрку пам'ят!, яка описуетъся за доломого» сп!ьв1дношень

■ í.j e ITñ ;

7)i j-i = fl cüj ;

cuj = 0 1 T)ÍJ Cl-p(/3ij)) + ftfrp ¡ftj ] # де

лГП _ f i, L > O ;

~ i 0. t < O ;

<3ijm s fl ( /íij-1) .

Оператор Л моделое роботу буферно! ком1рки пам'ят!. Вххдн! посл!довнаст!

?ii = Ai , i,t = ITñ ;

At(l) « ait = íau ,aja,,. .ain)

представляють Ф1П даних ACf~*>. Посл1довност1 /3ii використовують-ся в skootí 'управляемых посл!довностей:

/Э»|= { п.п-1.....1,0.....0 >, i = ГГп .

Як результат «а виход! отркмаемо пося1довност! i)it>;

1)19 = Yl- i.t = ПК ;

Yi (t) = ai iv-t+» ,

якi представляють Ф1П даних ВС

Ця операторна модель систол!чноi структури дозволяе проводити 11 моделсвання 1 аналхтичну верифхкадхв, тобто знайти явний вигляд результуючих посл1довностей i переконатися, що вони Д1йсно е розв'язками вих1дного алгоритму,

Дослхджуеться клас л1н1йних Ф1П даних С тобто вектори за допомогою яких вони представляються е кол!неарними ) з точки зору 1х взаемних перетворень та перетворень в планарн! Ф1П даних.

Эапропонованх розробки призначаються для використаняя у великих ойчислювальних системах, якх ой'еднують систолiчн! масиви р1зних типхв i де е можливхсть реконфхгурацхх макроконвейеру СМ. Апаратурно- часов! затрата . оц1нювться к1льк1стю синхротакт!в затримки Сх, як! вносяться в офобку: О <С* < 2n-l . i кхлькхстю залам'ятовувчих komípok'N, на основ! яких базуеться пристр1й: N=na, де п - розм!рн1сть оброблюваного масиву даних; к1лькхсть виконува-них перетворень - 2256 (без врахування класу л1нхйних Ф1П даних)

В чг-вертому роад1л! досл!д»уеться задача множекня розр!дкених

пол1ном!в, 1 пол!ном1в над полями Галуа СГ(2Ш) з точки зору

ефективно! реалхзацп на системах паралельно! д 11.

п 1 '

Розр1д«ений полIном Р<Х)=1?1 а4 х эадаеться списком пар, як1 складаються з ненульового коеф!ц1ента 1 показника степен1 зм1нно! х: (а .....^„^п1,

де ^ эадов1льняють умовам: у 6 Н ^ jl, - '

При множенн1 пол1номхв, представлених таким чином, знаходимО добутки пар (а^,^* кг3, г=Г7т, де Ьг1 кг~ вхдпов1дно, коефШент 1 показник степени пол1нома мнсжника, 1 розм1щаемо 1х по величин! показншав С тобто по другим компонентам пар ), об'еднюючи вс1 члени з одинаковыми показниками. По сут! виххдна задача вводиться до двох: мнохення пар коеф1ц1ент1в 1 сортування послхдовност1 пар коеф1ц1снт1в з приведениям подхбних членхв. В робот! запропоновано методи розв'яэку задач1, рхэнх кон$1гурац11 обчислсвач1в для 1х реал1зацП ( лпийн!, деревопод1бн1, матричн1 структури

обчислювальних ком1рок для хх реал1зацИ, приведен! оц1нки необх1дного числа операций при хх реал1зацИ.

Мнокення в ск!нчених полях бРСг") е б1льш складною задачею 1 проводиться по модулю незваного многочлена Г(х) степен1 ш, який е породжуючим поля . На основх розглядуваного п1дходу,

розроблено помножувач пол1ном!в в ск1нчених полях 1 описана робота на приклад! обчислення елемента поля йРС24), приведен! апаратурно-часов! характеристики, якх дають можливхсть ефективно використовувати НВ1С технолог!ю при його виготовленн!.

Основн! результати робсяи

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

2. В межах запропоновано! модел1 розв'язано задач1 оптимхзацН спе-ц1ал1зованих систем Сзнаходження мШмального часу йбробки 1 ыпи-мал ьно! кхлькост! процесор!в) на основх аналхзу структури алгоритм!в.

3. Створено систему комп'ютерного анал!зу термалвних представлень обчислювальних функцхй э метою розпаралелювання функтй на ааданому р1вн1 та розв'язку задач знаходження мШмального часу обробки I

мШмально! KínbKocTi процесор!в.

4. Дослужено основ»! властивост! Ф1П даних ! на !х основ! розроблено 1 проведено комп'ютерне та аналхтичне моделювання алгс-ритм!в просторово-часового узгодження в макроконвейер! СМ.

5. Роэв'яэана задача знаходження мхнхмуму запам'ятовувчих комхрок пам'ят! при перетвареннх Ф1П даних 1 £1 комп'втерна реал1зац!я.

6. Розроблен! структуры: схеми узгоджувачхв для вирхшення проблема просторово-часового узгодження в макроконвейер! СМ при розв'язуванн1 складно! задач!.

7. Розроблено методи розв'язку задач! множення розрхджених • полхном!в i множення над полями Галуа GFC2"), а також синтезовано

обчислюаальн! структуры для ix реалхзацН.

Основи! результат* дксертддШо! роботи викладен! в наступних публ!кац!ях:

1. Кожан В. П. Алгоритм распараллеливания рекурсивных функций / Автоматизация научных исследований и параллельная организация вычислений. - Львов: <Ш АН УССР, 1985.- С. 39-48.

8. Грицык В.В., Кожан В.П. Об одной вычислительной модели / Конвейерные вычислительные системы. - Киев: КПИ, 1985. - С.36-37.

3. Грицык В. В., Кожан В.П. Структурно-функциональный подход к. описатто задач f Общая математическая теория систем. - Львов:

АН УССР. 1986.- С. 14-15.

4. Кожан В. П. Od умножении разреженных полиномов. / Матем. методы распознавания образов,- Львов; Ш АН УССР, 1987, ч.Ш,- С.62-63.

5. Коха» В. П. Организация вычислительного процесса на многопроцессорных вычислительных системах / Распараллеливание обработки информации. - Львов: ФМИ АН УССР, 1987, 4.J. - С. 38-39.

Ь. Грицык В. В., Паленичка Р. И., Кожан В. П. Устройство для умножения полиномов. // A.c. 1432554. Опубл. 23.10.88, Бсл.К 39,

7. Грицык В. В,, Кожан В. П. Структурный анализ алгоритмов для их реализации на системах параллельного действия ,/ Высокопроизводительные вычислительные системы. - Москва: ИЛУ, 1988.- С. 50-51.

р. Кохан В.П., Страмец С.П. Устройство для умножения полиномов /✓ A.c. 1488829 Опубл.23.06,89. Бюл.Н 23.

9. Кожан Р.П. Анализ алгоритмов в целях распараллеливания вычислений // Отбор и обработка информации. 1989,- Вып.З.- С.86-91.

10. Грицьпс В.В., Кожан В.П. Устройство для умножения полиномов' //

A. с. 1568053 Опубл. 30.05.90, Бвл.Н 20.

И. ICozshan V. Р., Stryaraets S. P. Space-time coordination of systolic arrays / Proc.Conf.on Inform. Technol. for Image Anal, and Pattern Recogn CITIAPR'90) - Lviv: IPM, 1990, 2.- P.183-187.

12. Kozshan V. P., Stryamets S. P. Matrix multiplier of sparse polinomials /Ibid. - P. 179-182.

13. Батик A.E., Грицык В.В., Кожан В.П. Устройство для умножения полиномов х/ А. с. 1583939 Опубл. 07.08.90, Бол. N 29.

14. Батвк А. Е., Грицык В. В., Кожан Э. П. , Стряиец С. П. Умножитель разреженных полиномов // А. с. 1649564 Опубл.. 15.05.91, Ecn.N 18.

15- Грицык В. В., Кожан В. П., Стрямец С. П. Устройство для умножения полиномов у/А. с. 1677707 Опубл. 15.09.91, Бвл. N 34.

16. Кожан В. П. Синтез макроконвейеру високопродуктивних обчислв-вач!в для розв'язку складних задач обробки сигнал1в / 1нформа-ц1йн! технологи та розШзнавання обраэ!в / П1д ред. Я.Драгана,

B. Омельченка. - Тернопхль, 1993, 3. HI. - С. 69-72.

Особистий вклад. Bci результата, що складають основний эмхст дисертацхйно! роботи, отриман! автором самост1йно. В публ!кац!ях, як: написан! в спiвавторствi, дисертантов! належать: в робот1 t21 - схеино-функц!ональна модель паралельних обчислень; в [31 -алгоритм розпаралелввання обчислень, ml представлен! термом в формал1зацП примгтивно-рекурсивних функц1й; в (71 - розв'язок задач! оптим!зацх! багатопроцесорних систем; в 16,8,10,12-15) -розробка алгоритм!в пол1ном!ального множеяня i структурних схем пристро1в !х peaniaauii; в (11) - методи уэгодження обчислввач!в э р1знов геометр1ею зв'язк!в.

Щдписано до друку 24.05.94р. Формат 60x64/16 Друк офсет. Пяп1р д/ыас.вид. Умов друк. арк. 0,93 Умов фарбо-в}дб, 1,16 Обд.-вид, •рх. 0,8 Тираж 100 прим. Зам. 2547

Льв}вська обласна кнмжкова друкарня,290000,иЛьв!в,вул.Стефан1скв,II