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

КШВСЬКИЙ П0Л1ТЕХН1ЧНИЙ 1НСТИТУТ

РГО од

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

МАСЛЕНН1КОВ Олег Володимирович

УДК 681.322

МЕТОД ПРОЕКТУВАННЯ ТА СТРУКТУР И СИСТОЛ 14НИХ ПРОЦЕСОР1В ДЛЯ ВИР1ШЕННЯ ЗАДАЧ Л1Н1ЙН01 АЛГЕБРИ

Спещальшсть 05.13.13 — обчислювальш машини, комплекси, систем» та мерели

АВТОРЕФЕРАТ днссргац!! на здобуття вченого сгупеня кандидата гехШчинх наук

кит Б 1993

ШВСЬКИЙ П0Л1ТЕХН1ЧНИЙ 1НСТИТУТ

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

МАСЛЕНИКОВ ОЛЕГ ВОЛОДИМИРОВИЧ

УДК 681.322

МЕТОЛ ПРОЕКТУВАННЯ ТА СТРУКТУРИ СИСТОЛ1ЧНИХ ПРОЦЕСОР1В ДЛЯ ВИР1ШЕННЯ ЗАДАЧ Л1Н1ЙН01 АЛГЕБРИ

Спещальнють 05.13.13 - обчислювальн1 машини, комплекси,

системи та мерех!

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

КИ1В - 1993

Робота виконана у Ки1вському по л! техничному Хнстатуп.

Науковий кер1вник: доктор техтчних наук, професор

КАневськии ю.с.

ОФ1Ц1ЙН1 опоненти: доктор техтчних наук, професор

ПОЛОНОВ О/Г., кандидат техтчних наук НЕКРАСОВ Б.А.

Проыдна установа: 1нститут проблем моделювання в енергетиш

АН Укра1ни

Захист в!дбудеться " 4{Г" Х/(_1993 р. о 14.30 на

зааданн! спец1ал1зовано1 Ради Д 06B.I4.09 в Ки1вському пол1тех-тчному 1нститут1 (м.КиХВ, пр. Перемоги, 37, корпус 18, ауд.ЗОб).

В1дгуки на автореферат у двох приихрниках, засв1дчен1 печаткою установи, просимо надсилати за адресов: 252056, м.КиХв, проспект Перемоги, 37, КП1, Ученому секретарев! КПГ.

3 дисерташепо мохна ознайомитись в б1блютещ Кихвського пол1-техтчного 1нституту.

Автореферат роз1сланий " У Ч" У_1993 р.

Учений секретар спетал1зовано1

Рада Д 068.14.09 д.т.н.. професор

Бузовський О. В.

АНОТАШЯ

'/хэтоа роботи являеться Шдвищення ефектизносп мэтолш проекту-вання та синтез з 1:с допомогою структурних схем сг.етал1заваних паралельних обчислюэальних пристро1з (СПОП), орьзнтованих на рэал1зац1ю методами НВ1С-технологи (СПОП на НВГС), а також розроака паралельних обчислювальких схем алгоритме (ОСА) виршення задач Л1Н1ЙН01 алгебри (ЛА).

В В1ДПОВ1ДНОСТ1 з поставленою кетою вир1шуються наступи! задач1:

1. анал1з основних задач ЛА та метод!в !х виртення з мотом ви-значення ступени IX придатност! для паралельно! реалхзацп на СБ1С;

2. анал1з вгдомих метод1В структурного проектування СПОП на НВ1С та дзяк1 направления хх розвитку з точки зору.практично! реалгзаци синтезованих структур:

3. розробка метода синтезу синронгзуючо! функцн, описувчо! роботу структуры СПОП в ЧЭС1;

4. розробка п1дход1в до синтезу структур СПОП ф!ксованого розм1ру для виршення задач ЛА;

5. розробка сПособ!в перетворення реинтчатих Функшоналыш граф1в (РФГ) алгоритма ЛА для оптчм1заци апаратно-часових витрлт при 1х реалпацп на паралельних обчислювальних системах (ОС);

. 6. розробка та досл1дження паралельних ОСА та структурних схем СПОП на НВ1С для вир1шэння деяких задач ЛА. Автор захиаае так! основн! положения га результата:

1) метод синтезу часово! компонента в!дображення РФГ алгоритму в структура схеми СПОП на НВ1С; '

2) способи 1зоморфних та гомоморфних перетворень Р5Г ряду алго-ритм1в ЛА для 1х ефективно! паралельно! рсал1зацп;

3) спос1б проектування структурних схем СПОП на НВ1С, незалежних В1Д розм!р1в вирШуемих задач;

4) паралельн! ОСА та структурн1 схеми СПОП на НВ1С для виршення р!зних задач ЛА.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ Актуальн1сть досл!джень. Ло задач ЛА зводаться' щлий ряд проблем з са!^х р!зних областей науки 1 техн1ки. Однак виршення б!льшост! задач ЛА потребуе виконання 0(м3) (де м - порядок оброблюваних мат-риць) операцШ типу множення з додаванням. Тому в ряд1 зипадкхэ 1чльки СПОП, орхентован1 на виршення визначеного класу задач 1 максимально зраховупч! 1х специф!ку. придатн! для виконання останн!Х в

а

реальному масштаб! часу. Пояза високошзидк!сних НВ1С, як! мають на одному кристал1 дек!лька процесорних елеменИв (ПЕ) середньоХ склад-ност1, пр/скорило досл!дження в структурному проектуван! СПОП на Н31С, оснозними представниками яких являються систол!чш процесори (СП) та процесорн! матрищ (ПМ). При цому постШне тдвицення складаосп вирхшуваних задач та скорочення с?рок!в на розробку таких СПОП, а такох постхйний р!ст вартост! помилок евристичного проектування привели до появи ряду формал!зованих та частково автоматизованих метод!в структурного проектування СПОП на Н31С.

Значними недол1ками в1домих метод1в проектування СПОП на НВ1С е беспосередня залежнхсть одержаних архитектур X в!д розм1р1в структур початкових даних вир1шувано! задачи а такох складн!сть одержан-не синхрон!зуючо! функцл, описуючо! роботу СПОП в час!, в випадках зниження розм1рност! графа структури СПОП в1дносно розм!рност1 РФГ початкового алгоритму (ПА) б!льше, н!х на одиницю. Тому актуальною язл-чзться задача 5.x удосконалення шляхом усунення названих недол!к1в. Кр!м того, множина одержаних з допомогою указаних методов структурних ршень однозначно визначагться базисним РФГ ПА. Разом з тим, 1з-за в1дносно високоI вартост! реалхзацп з'еднань в НВ1С, рк?т ефективнзстХ застосування СПОП на НВ1С можна чекати т!льки тодГ, коли ПА тдготовлениЯ (модиф1 кований) з урахуванням не пльки збалансованого розподхлу роб1т, але 1 з - дотриманням вимог локальност! (тобто коротких л!н!й зв'язку). Отже, актуальною також е розробка ОСА вир1шення задач ЛА (НВ1С-алгоритм!3), дозволя^чих оптимхзувати апаратт витрати на. побудову СПОП на НВ1С та м!н!м1зувати час виршення вказаних задач на паралельних ОС. Методи досл!дження. В робот! використанн! метода ЛА, теорП гра<±>1в, теори лШйних оператор!в, теорп ыножин, тeopiI проектування ЕОМ та систем. ■.

Наукова нов!тн1сть роботи полягаг в сллдуючому:

I. розроблено-' метод синтезу часоврХ компонента воображения графу алгоритму розмхрноста п в структурн1 схеш СПОП розм!рност1 а = п-2, який на в1 дайну в1д . в!домих дозволяв зменшти трудом1стк1сть цього процесу та повыстю формалХзувата йога;

2. запропонован! способи !зоморфних та гомоморфних перетворень РФГ ряду алгориткиз ЛА, як! дозволяють' оптимхзувати паракетри в!япов1Дних структур СПОП на.НВ1С.чи реал!зашю вказаних задач на пасслельиих

3. розроблено спосДб-прсжгуваня? структурних схсм СПОП на Н31С, розм1ри 'яких не залежать ви розм1р1в реал!зуемих 1га задач. Практична ШнШсть робота. Запропснован! в робот! метод та способи дозволяють спростити, систематизувати, а "також в деякхй Шр: азтоматизувати розробку' структурних схем СПОП на НВ1С. При 1>: Д0П0М031-. автором розроблено ряд структур СПОП на НВ1С та Н31С-алгоритм1в для виринення основних задач ЛА, практична користь та нов!тн!сть яких' п!дтвержуються авторськими св!доцтвами СРСР . Реал1зац1я результат!в роботи. Теоретичн1 та прикладн1 результата дисертащйно! роботи покладен1 в основу лабораторних роб1Т з курсу "СпеШал1зован1 ЕОМ" для студенпв КП1 спеШальност! 2201 -обчислювальш машини, комплекси, "системи та м<эреж1. Апробатя работа. . ОсновШ положения . дисертащйно! роботи обговорювались на:

- 2-й Всесоюзна нарад! "Конвейерн! ■обчислю'вальн1 систеш", Ки1з, 1988 р.; ■ .

- Всесоюзна конференцп "Метода та м1кроелектронн! засоби цифрового перетворення та обробки сигналов", Рига, 1989 р.;

- 1-й Всесоюзна конференцп "Одаор:дн1 обчислюзальн! середовища та систол1чн1 структури", ЛьвГв, 1990р.;

- Всесоюзному сем1нар! "Геор!я та практика створення систем техн!чного зору" Москва, 1990 р. •

- Всесоюзних семинарах "Однор1дн1 обчислювальн1 середовища та систоЛ!Чн! структури", Льв!в, 1989 - 1992 рр.

Публшацш,- По тем1 дисертацп опубл1ковано 26 друкованих роб1т, включаючи 14 авторських св!доцтв СРСР та р1шень про видачу патентов. Структура та обсяг -работа. Дисертащя складаеться з вступу, чоти-рьох глав, висновку та списку використовано! л!тератури з 9Л най-менувань. Робота М1 стать /£/ стор1нок машинописного тексту та «< * сторшок графимого материалу. .

В перш!й глав! проведено анал1з основних задач ЛА та метод1в !х виринення з метою визначення придатност1 останн!х до паралелъно1 реал1зац11 на НВ1С. Досл1дген1 в1дом1 метода структурного проектування СПОП на НВ1С та визначен1 основн! напрямки 1х удосконалення з точки зору безпосередньо!. практично! придатност!. В Друг1й глав! для випажу п-«=г розроблено бхлыи простий та суворо формал!зованиЯ метод синтезу часово1 компонента мдобрахення ГОГ алгоритму в структуры! схеми СПОП. яка в останн!х описуе. часову

б

розгортку обчислень. Розроблещ способи 1зоморфних та гомоморфних перетворень РФГ ряду алгоритмов ЛА для ix ефективно! паралельно! реал1заци, в тому числ1 й на HBIC. Розроблено спос1б структурного синтезу СПОП на HBIC, дозволяючий проестувати структурн1 схеыи СПОП, незалеаио вхд розм1р1в вирнаувальних задач.

В трепй глав! показан! можливосп та переваги розроблених cnoco&iB дзоморфних та гомоморфних перетворень РФГ алгоритма. ЛА та методу визначення часово! розгсртки обчислень. при синтез! структурних схем СПОП та HBlC-алгоритШв для -виршэння систем лшйних алгебра!чних р:внянь (СЛАР ), lu - та liA - розкладення матриць. ' В четвертой глаа! на основ! розробленого способу структурного проектування СПОП на HBIC синтезован! структурен схеми СПОП Фхксованого розм!ру, кожна з яких призначека для'вир!шення Щлого ряду задач ЛА незалехно в!д IX розм1р!в, - .

0СН03НИЙ ЗШСГ РОБОТИ

Ка основ! анал!зу в1домих метод!в. виршення основних задач ЛА встановлено, що б!льшосп ; з них характерн': - потреба в виконанн1 великого обсягу периодично повторюючихся обчислень, а також висока стугинь внутрйшього паралел!зму та регулярн1сть зв'язк1в шж функшональними операторами- CÍO ) алгоритм!в. Вид!лен1 Ti з них, як! найб!льше придать для ^паралельно! роал!зацП на HBIC.

На основ! вшмох процедури побудови РФГ безушвних регулярних алгоритм!в, заданих у вигляда программ на' kobí високого р1вня, побудовано наб!р базовик РФГ вид!лених алгоритма JIA та виконана IX класиф1кац1я по разм!рност1 п простору представления РФГ, типу та довжин! дуг Mis верпмнакй, " функциональному зк1сту i внутр.!ш1й будов1 вершин, довхин1 критичного шляху.

На основ! анализу !снуачих метод1в структурного проектування СПОП на HBIC для виршення задач ЛА та виког до них встановлено, що а ) синтез по будь-якому методу являеться лииз автоматизоваким, а не автоматичним, тобто вимагае участх * проектузгльника в npoueci проектування; б) лице небагато кетод!в допускають одержання стру1стур СПОП дов!льно! po3MipHocTi с незалеэю В1Д роэм!рност1 п ' РФГ алгоритму, але иазхть в них в випадку n-a>i пойук sacosoi компонента вхдобрау.ення РФГ в структуру СПОП е досить ваксим."

1снуюч1 кэтоди, як правило, базуиться на представленн! початко-вого безуиавного регулярного алгоритму А у впгляд! Pif g такого, цо логина його вераин в!дпов!дае кножин! 40 алгоритму, причону козша

sc.:,;.;.'" описуеться одним ! ?!льки одним елсиентом (точкою або вектором з початку координат- з цю точку) декартового добутку (Щлочислено! решхтки) К" = с К - 'к и .. к ]' I k <= z" u s

1 2 п 1. L I

< h >, Л1Н1ЙНИЙ npocTip, з якому знаходиться K,n. Дуги графу g

в!дпов1дають. безпосередн1М !нбормац!йним залежностям Mis його 'ГО. 3 деяких методах РФГ неявно задаеться в компакта!й форм! у вигляд! характеристично! матриц! d = t5t <i2 ... d^*- вектора -стовптз ,безпосередньо! 1нформаЩйно! залежноси (тобто дуг графа g) по зм1нних алгоритма та 1нтервал1з зм!н 1ндекс1в цих змхнних. Дал! граф g за допомогою Л1Н1йиого, монотоного та !н'ектизного оператора f з1добрахпеться в структурну схему с = <s,t,*> СПОП, де s - орграф структури, заданий з простор1 z™ (m<n), т - синхромзуюча функтя, % -. Ha6ip операций, виконуимих ПЕ. Оператор f назизаить зт-в1добрахенням, оск!льки зш складаеться з просторозо! fs та часово! f компонент, перша з яких визначае структуру s, а друга -функщю т, а обидв! - мнохину

«v -к" - fjk) = к^ ... krj\

• ^ ft: к" - ftck) = [t],

де t - дискретний пер!оц часу (машинний такт), в якому СО, в1дпов1даючий вершин! з координатами К, виконуеться ПЕ з координатам fs(K> (ззахаеться одиничний час виконання будь-якого ФО). Вказаний ПЕ в ц-эй час не може виконувати Н1яких 1нших ФО, що приводить до умови iH1 ективност!

v kt, Кг е Kn cfsiKt) =fs(Kz) =»FT(Kt) * ft(K2)). CI) в той час як монотонн!сть функцп f (точтше, - п компонента f ) визначаеться сл1дуючим чином:

FT х d. ^ 1, 1=1,2.....l. (а)

На сьогодн! методика синтезу структурних схем С для часткового випадку г=п-ш=1, в!дпов!дного як раз СП, досить добре розроблена. Зауваяимо ильки, ■ що умова (I) в цьому випадку буде виконуватись, якщо

det F >• О. - (3)

Олнак, якщо врахувати, по-перше. що для подавляючо! б!льшост1 алгоритма ЛА з ФО на plBH! сл!в п.= з, а з 40 на piBHl розряд1в п = 4, та, по-друге, що сучасн! мохливосп технологи та ширина каналу вводу-виводу HBIC дозволявть практично реал1зувати пльки одном1рн1 структури (а " I) 3 обробкою H3 УРОВН! сл!в абО ДВУМ1РН1 С ш ~ 2) 3 обробкою на piBHi розряд!&, з-являеться необх!дн!сть в розгляд!

ВИПадку, КОЛИ Г =2 .

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

Разом з тим з практики проектування в!домо,що наЯкрана структура зазначених СПОП одержують при проекци РФГ о в1Дпов!дних 1м алгоритмгв або на ос1 координат простору г". або на координата! площини. Це поз'язано з тим, що граничт вершини РФГ & алгоритма ЛА, як правило, належать гхперплощинам, паралельним координатним плотинам простору г". Тому будь-яка проекщя цих граф!в на прям! або площини. в1д!,иннх в!д коордйнатних, приводить до зб имения к1лькосп .ПЕ та/або зв'зкт м!ж ними в результувч1й структур!, а також нер!дко поПршуе часов! характеристики одержано го СПОП. В роботх показано, що прийняття до уваги зазначеного обмахення на виб!р проекци графа в значно зпроауе пошук часово! компоненти гт при г=г, та пропонуеться новий метод синтезу часов«! розгортки обчислень в СПОП на НВ1С, придатний для пошуку в цьому випадку.

У В1ДПОВ1ДНОСТ1 з ним для пошуку рт виконуеться пере:<1д в!д представления РФГ алгоритма в стандартному (що складаеться з стовпщв одинично! матриц!) ортонормованому базис! лиийного простору гГ до його представления в ортогональному базис! структур-/

В = [ г'... ?'1 V ], де вектори-стовпщ Г.....г1т е векторами-

строками "матрищ а вектори * , у2 створюють ортогональний базис ядра кчг г оператора г^. Тод!, яхш.о вектор .= [к®, ..к"] с представления в базис! структури дов1льного вектора К е КГ то сп!вв1дношення Кв = В1-К-буде залавати пэретворення координат вектора при переход! в1д одного базису до !ншого.

3 визначення базису В вит1кае, ¡до перш1 ш "координат будь-якого вектора Кв - це представлен! в новому базис! координата деякого Пг структури б. 1накше' кажучи, сп!вв!дношення = ги® к"... к"]1 З'-К, де К-е К", а В - тдматриця матрищ В, створена И першими г вектор-стовпцями. означае що 50, в1дпсв1даючий версией К

Б

в1/юнуеться ПЕ, координата якого в новому базис! доршжють Я, . Тс 1 множна R(£ ) тага, що Й(К ) - <К = В1 -К = rkD к" ... jrV" I

то вri а 1 г П- 1

kt. кг, .... = const.; кс- кп>, буде задавати в цьому s базиса координата Bcix тих вершин графу о, як! проецгаться в зазначенкй ПЕ i будуть в ньому виконуватись.

Перех!д в!д стандартного до ортогонального базису в приводить такох до трансформацн лгнхйного оператора ft в оператор fb

СЛ1ДУЮЧИМ ЧИНОК; F3 = [ fB fB . . f" 3 = F "В Т0Д1, ЯКЩО

Т т*-1,1 т*-1, 2 m*-i n Т

для будьЧяко! множнни ft(KBi) пперплощина* з нормаллю fb при будь-якому свому положеши шстить не бгльие одного елекэнту зазначено! иногини. то для будь-яких двох вершин графа g з координата?.« Кг « К"' такими, що fs(Ki ) = fs(Кг), будс

виконузатись ft(iiij * f„(K2). Отже, для будь-яких двох вершин К =

[кв к"'..'. кв ]1 та К = [кв кв ...к® з1 графа g, з одн!е!

i,i 1, г «•>"> в. г г, 1 2.2 z, nJ i- т-

... .... ... множини ¡1 ), ргзннця -м1х моментами виконання СО, як! 1м

?!дпов1дають,' складае ¿ъ = ря(к ) - ) =.' £ га ' (кв

т. В. г ТВ, 1. 1. = П-11ТТ»1,12,1.

к^ ) такт!в, тобто визначаеться т!льки двома останнпм координатами як оператора я", так 1 вершин Кп , Кв .

■На основ1 .приведении викладок в робот! доводиться сл1дуюч1 прост! укови'игективносп зт-в1добрахення для випадку г=г: ' I ^ н" . г" • г , або

!ТГ*1, П . П-1 П 1

1гв I г МВ.-ГВ - г , та обгрунтовуеться сл1дуюча процедура пошуку г » [г г

. л А Т тп+\, 1 гтт* 1, 2

пз, яка проводиться на основ1 вибраного р . а' такох в!домих

д1апазон!з зм!к и® та мшмальних пририст1в у. и=1.....п) п р1зних

1ндекс!в зм!нних по вс!м п координатам простору г":

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

2. 1з заданних значень н" та г^ вибираються значения м" та гу ' або н" та гх, як1 присвопються в!дпов1дно та х.

3. Решт1 елеконт!з г-^ ^ (1=1,....п; л^х, строки матриц! г присвоюються значения з мнохини .о,1>.

""4. 3 одертаноТ кно1Ш1 значень гт вибираються -1;, як! задовольня-ють умов! монотонност1 (2) та залишають попарно р!зними вс1 стовпц! та строки матриц! р.

На основ!.. анал!зу !снуючих метод!в структурного лроектування

СПЗП на НВ1С установлено, цо вс1 вони доззоляють одержат« деяк! кножини структур, адекватн1 саме заданому запису алгоритму вир1шення згдач1, що значно звужуе клас одерханих арх1тектур та не гарантуе одержання рниень, . В1др1зняючихся високою еФективн1стю.. Тому при структурному синтез1 СПОП на НВ1С етапу просторово-часового в!дображення РФГ алгоритму в адекватн! апаратно-програмн! засоби пропонусться ввести етап трансформац! 1 -ВЫ1 з • допомогою ц1леспрямованих !зоморфних та/або гомоморфних перетворень, 1х можно виконати, по-перше, шляхом 1зоморфного перетворення (занурення) РФГ в граф друго! структури. По-друге, дякуючи великий свобод1 в порядку передач! непереобчислюваних зкинних алгоритму М1Ж вершинами графу появляеться можливхсть тлеспрямовано. генерувати на основ! початкового запису алгоритму вирниення задач! множини його РФГ. В-трет1х, навхть для переобчислюваних зк!нних мохна 4нод1 допустити змлну поряжу 1х ' формування, використовуючи властивост1 комутативност! та асошативност! математичних операшй.

Е:доко, що трьохмарн! базисн1 РФГ ряду алгоритме виринення СЛАР ] тр/куткого розкладення, матрйць мохна- звести до двухшрного систол1чного трикутного графу- (СГГ), оскхльки вех вони.поррдауються

единою обчиелввальною схемою, на 1-му крощ яко! и = 1.г.....м: Де

n - киыасть стовпшв початково! ' матриш. а*) обробц! тдлягае зпочатку стовпець а матриц! (де а* = «"), який ,по71м взгсмод1е з ус!ма шшими стовпцями, за виключенням пергмх (1-1 ) стовпщв.

Б ЗЗ'ЯЗКу з цим, в робот! пропонусться СП0С16 1зоморфного перетворення (занурення) СТГ в систол!чний торо!дальний граф (СТОГ). Припустимо, що з любо! внутр!шьо! вершини зазначеного СТОГ виходять (а також входять в но!) ,дв1 - дуги з координатами 5^(1.1) та 5.,-= (1,-1). В крайн!х вершинах СТОГ, розшщених на його л1В!й або прав1й границях. заметь одие! з вказанних дуг з>являеться дуга 5а=(1, о). Тод! суть пропонованого занурення, яке справедливо т!льки в випадку непарних значень и моге бути описана,таким чином:.. „

1. Верамна (1,1). початкового СТГ (де 1 » 1.г.....н)

розтадювуеться в вершин! к ~ (1*^*) *? (глп; 1) СТОГ.

2. Для данного а'1нш! вершини Ц^ ) СТГ (де j - ¿+1, ¿+г.....н)

розм!щаються посл!довним образом вздовж напрямку вектора спочинаючи з вузла к. - л1 ) до зустрШ! з правою границею СТОГ. Тод1 проходить поступова,'. з участю вектора 5в=(1.о), зм1на напрямку розишення вершин на (1. -й ).

Результатом списано! трансборкацн е зменьшепня ширина початкового СТГ. ак 31 значения и вершин вдздовж ос1 до значения нк= (м+1 )/г вершин вздовж ос1 ^ в одержаному граф! в", тобто мзйже вдвое. ■ Вказане зменшення, в свою чергу, дозволяе скоротати число ПЕ та повисити 1х завантаженхсть в ■ лхнхйних СПОП. реал!зуючлх в1дпов1да1 алгоритм* ЛА. При цьому в робот! доведено, що оптимальна по пзидкост! виконання алгоритму часова разгортка в!дпов1дае значению. гт= (1,0), яке у знпадку алгоритм!в, описуваних трытирним Р1>Г, задае- разгортку уже не по тактах, а по макротактах. Кожний з естаннхх мхстить, як правило, м такт1в (де м - кхлыисть строк натрии! ■ л*), необххдних для поелементно! обробки стовпця матриц!.

.Ка основ! запропонованого способу перетворення СТГ в .робот!

синтезоваш параледьн1 ОСА та структурнх схеки лхнШних СПОП на

КЗГС, як! релхзують численно ст1йкХ метода Жордана-Гауса для'

вирхпення СЛАР та Холецького для трикутного розкладу симетричних

гатриць. Синтезован1 структурнх схеми мають н/г ПЕ кожна (де N -

порядок початкозоХ матриц!) та характеризуються аскмптотичною

завантаженхстп пси виткет вказаних задач В1ДП0В!ДН0 т?А«1 1

л

•0**0.66,- тобто вдвое б1Льшою, н1ж кращ! з вХдомих структур СПОП.. Такою ж завантаженхстю будэ характеризовались будь - яка паралельна ОС (яка мхстить таку ж кхлькхсть ПЕ та мхжпроцесорних зв'язкхв) при реалхзацхх на н!й запропонованнх ОС. Важливою особлив1стю одержаних-СПОП е такох те, що вс! складах' операцхх типу Д1лення та знаходження зворотньо1 величкни (а такоя лор1внякня) реалхзуються в первому ПЕ, в той час як хнш ПЕ. виконупть тхльки множення з додаваннян та зберхгання хнформацхх. Крхм того, з допомогой ряду щлеспрямованкх хзоморфних та гомоморфних перетворень базисного Р4>Г матрично-вектор-ного множення спроектована структурна схема СПОП на НВ1С. рсал!зуяча мотоди просто! хтераШ та Гауса-Зейделя для хтерацхонного виршеиня СЛАР, яка кае в чотири рази менший час виконання одшех хтераци цхноя !,;снш нхж дзукрзтного збхльшення апаратурних затрат в порхвнянн! з кращини з пхдогах схем СПВУ, реалХзуючих зазначен1 .'.'.етоди.

На основ! анал!зу хснувчих гзтодхв структурного проектування СПОП на КВ1С також встановлено. цо н! один з них не дозволяе проектувати СПОП фХксованого розмхру для реал!зац!Х задач довхльних розмхрхз. В то .1 ге час арххтектурн реальних паралельних ОС харак-терхзуяться рядом обгежень на снох ресурси.найМльш хстотникн з яких

являються KiJibKiсть ПЕ та об• ем локально! пам>ят! (ЛП), а такол пропускна можливасть канал!в обм!ну як Mix-ПЕ, так 1 з зовнлшьою пакяттю.

Для синтезу структурних схем СПОП на H3IC, незалежних ■ В1Д po3MipiB вирнауемих задач запропоновано викэристовувати декомлозищв (розбивку) виртуального обчислювального процесу великих po3MipiB на »/ложину взаемозв".язан/х Шдпроцес!в меньших posMipiB, та.виконувати потом водображення останн1х на структуру СПОП фОксованого розмору таким чином, що& виконання п1дпроцес!в в них здойснювалось частково паралельно або послодовно. На основ! аналогу р1внов представления обчислювального процесу (р1вня початкових-алгоритмов, РФГ та ОСА), встановлено, що кращим для використання< процедур декомпозицп е ровень РФР. ' . ' •

, Для. здойснення занурення " алгоритмов- дов1льних розм1р!в .в архотектуру СПОП з ф1ксованою колыастью ПЕ РФ-Г алгоритму .будем регулярно розбивати на Шохину п!дграфов. При цьому водображення декомпонованого графу в структурну схему з фоксованою к!льк!стыо ПЕ коже виконуватися згодно з одно ею оз "сл1дуючих дзох запропонованих. стратегов (або ох комбонацой). _ ; -

Нехай початковий РФГ, . вершини якого . розм!щен1 в п-морному простор!, за допомогою максимум n-Г с!мейств. паралельних ппер-плошин розоиваеться на множину подграф!в. Тод! зпдно з локально паралельною глобально посл1Довною (ЛПГПС) стратег! ею будь який граф в1добрахаеться в одну i ту ж результуючу. схему. При цьому одержан! тдграфи повинн! виконуватись один за другим в водповодносто з деяким -порядком. Lie означае, \щ вих!дн! данно одного шдграфу являються входними для посл1дуючих i, з-являеться необх!дн1сть буфер!зацП у зовн1Ш!й памят! пром1жних "результатов, зумовлених ОнформаШйники залехностямн шж подграфами. Таким чином,-, за рахунок додаткових обм1нов з зовн!шньою памяттю, виконання яких не завжди можно органозувати на фоно обчислень, вДасться, як'правило, уникнути додатково! (пор!вняно з виладком необыехеного паралел1зму) локально! памят1 ПЕ. Це дозволяе одержати СПОП з ПЕ, огттамозованими по об-ему ЛП. Однак, при наявност! зустрочних обм1н!в пром!хними результатами Mi ж Шдграфами вииагаемий посл!довний порядок виконання п!дграф1в мохе не кнувати, шо:обиехуе область використання данно! стратег! 1. Нак1нець, "в1дм1нност! в будов! п!дграф!в, як1 вшбрахаються в одну, i ту ж структурну схему, мохуть привести. до ; зб1дьшення. на»сладних

витрат на п реконф1гураЩю та управлхння/

Протилежт, в основному, властивостх мае локально послхдовна глобально парадельна (ЛПСГП) стратегии що припускае зидхлення сэого ПЕ для кожного одержаного тдграфу, в зв'язку з ним к1льк1сть ПЕ схеми р!вняеться числу тдграфхв, а кохний ПЕ повинен пословно виконувати оператори (зершини) в!дпов1.дного йому тдграфу. 3 результат! структура мхжпроцесорних зв'язк1в СПОП буде визначатися ШформаШйними залежностям1 м1ж тдграфами х зиникае потреба взоду в кохний ПЕ додатково! ЛП, яка призначена для зберхгання промхжних результатхз, народхених зиконанням тдграфу. Таким чином, при додержант. абме:>:ень на обсяг ЛП, а такох з урахуванням додаткових витрат на його управл1ння, ця стратетя, по-перше, дозволяе уникнути 06М1Н1В пром!хними результатами з будь-якею зовтияьо» памяттю. По-друге, з»язля5ться мотливхсть зменшити зимоги до пропус:сно1 моаливост1 канал 1 в зз'язку ПЕ, оск1льки час реал1заци тдграфу, який визначаеться загальною к!льк1стю його вершин, при збхльнент розм1р1в тдграфу росте шзидше, тх об» ем данних, передаваемих М1ж сус1дн1ми тдграфами, який визначаеться кглькХста граничних зернин тдграфу. При цьому межа використання зазначено! мохлквосп визначаеться обкэхенняии на обсяг ЛП, який залехить в!д розмхрхз тдграфу. В-трет1х, на вз.дм1ну в1д ЛПГПС, ця стратепя дозволяе оперузати з графами теоретично любого вигляду, оскгльки будь-яксму способу вибору тдграф1в вХдлозхдае тепер непорожня Онегина синхротзумчих оункшй, задавдх з чат порядок виконаккя зертан початкозого Р1Г процесорними елеуентами СПОП.

Врахозуючи зикладене, в робот1 обгрунтовуеться дощльн1сть використання узагальнено! (або 1ерарх1чно1) стратеги декомпозицп, вклпчаючо! обкдв! розглянут! висе стратеги, та на щй основ! пропонуеться сл1дулчий спос1б синтезу структурних схем СПОП на НВ1С ф!ксовгного розШру:

I. Ц1лочислена рэаИтка К", в вузлах яко1 розм1щен1 зершини репйтчатого графу в алгоритму, п способами разбизаеться на однаков! прямо;сутн! тдреш1тки, роз?.ири яких для ,]-го способу розбизки задовольнямть слхдуючим зхдношенням:

1, ' м,. ^ 2.......

I ^ ч. - м , !«={!, 2.....п>. t * j,

■■;о !? , М - росм1рн реш1ткн К" зздовх одно1мених координатных шеей простору

2. КсжШй тдрешхтт .ставиться у взаемно однознанне стввхдно-ссння В-вершина. Спхвкупнхсть всхх В-вершин для фхксованого з-го способу розбивки утворюють В-граф е;в. Вершини останнього розташова-нх в вузлах решхтки (С""1 , а дуги одержуються шляхом- проекц! 1 дуг графу о вздовж I координатно! ос! простору гп.

3. Для ¡сотого з одержаних таким чином граф1в о^ знаходиться щожкка допуститах часових розгорток, задаючих суворо посл1довний порядок; виконаиня функщональних оператор!в всерединх В-вершин. На цхй оснот зизначаються вимоги до органХзацХх та обсягу ЛП ПЕ скнтес-овакох структурно! схеми, эираженому як функцхя розмхрхв

ш лрс-Е1ток. Виходячи потхм з обмехень на орган!зацхю та обсяг ЛП ПЕ щль'ово1 ОС, знаходяться максимально допустим! розмхри , пхдреыхтск, що дозволяв мхнхтзувати вимоги до пропускнох можливост! каналхэ зв'язку ПЕ.

Кожна з одержаних рейх ток К^"1, в вузлах яко! розм1щэнх веошини графу о1, мт Ст способами Це Ст - число комбхнацхй з

^ в V п-1 п-1

п-1 по т) розбиваеться на однаковх прямокутнх пхдрешхтки, розмхри р^ яких при ш=х задаються спхввхдношенняш

I < р| < = ]№/ч|[. ЯКЩО I- =

Р^.' ЯКЩО 1*г,

)

(4)

де г - номер тхех координатно! осх простору г""1, перпендикуляр-ними до яко! являються вех розс!каючх Пперплошини единого !х с1мейства, причому г « <1. 2.....п-1>. У випадку х ш =■ 2 масмо-

I < pi < и, якщо 1

11 1- 2 - 1 (5>

1 ® <Г1' Г2>'1

1 « <г,. гг>Л

р|= I/, ЯКЩО 1 е <Г

де Г1,гг - номера тих коорданатних осей простору гГ1. перпендаку-.лярними до яких являються пперплошши в!дповхдно першого та другого

IX с1мейства, причому г , г2 е С1, 2...... -1>, г1 " г2. При цьому

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

5. 3 метою одержання альтернативно! множини структур б, описуючих топологхю мххпроцесорних зв'язк!в синтезованих ОС, для кожного фхксованого способу розбивки, задаваемого або . единим 1 ндексом г при т = I, або парою хндекс1в-<г ,>г> при ь = 2 (де г,

г. г « <1, 2..... п-1> ! г4 * гг), вс1 В-кластери графу

проецюються при т = I на г-ю координатну вхсь простору г""1, в якому розмхдена решхтка К""1, або при ш = 2 - на Г -ю та г-ю координатах

ocl цього x простору.

6. Шдставляючи задану к!лыасть ПЕ шльово! ОС заметь р' (при m *= I), або Р^.Р^ (при т= 2) в ствв! дношення (4, 5), як1 виражають к!льк1сть ПЕ в копий з результуячих структур s як функшю poràipiB fi облает! К° визначення графу е та знайдених ран1ше на крощ 3 розм1р1в qj п!дреш!ток визначаемо розм1ри В-кластер1в.

7. Для кожного ф!ксов'аного способу розбивки графу gj знахсдиться множина допустимих макророзгорток, як1 задають суворо посл!довний порядок виконання В-кластер!в в час!, i тому ютують тиьки при умов! В1Дсутност1 зустр1чних 1нформащйних обм1Шв м!ж кластерами. Для koxhoï допустимо! макророзгортки визначаеться в1дпов1дна !й м!кророзгортка, задаюча в 4aci паралельний порядок . виконання В-вершин кохного кластеру на цхльов!й ОС, а такох величини змйдення початку виконання сл!дуючого кластеру по в1дношенню до попереднього. При цьому критер!ем при- знаходженн! м!кророзгортки та змикень зикористовуеться час реальзацп алгоритму з 'урахуванням обмехень, накладених opraHi3auie» сбмшв з зовн!шнью памятю тльово! ОС, а такох наоадними витратами на реконфигураций та управл1ння..

8. Якщо множина вс!х ' схем, народжених п графами о^ та н™ способами розбивки кожного'з них на В-кластери, а.також допустимими часовими розгорткают, являеться непорожньою, серед схем зазначено1шохини вибираяться- найб!льш придатн1 з урахуванням задания вимог до результуючо! арх1тектури СПОП.

У випадку, коли допустим! макророзгортки в!дсутн! взагал1, як альтернативний п1дх!д■ До синтезу можна рекомендувати застосування винятково ЛПСГП стратеги декомпозицл. Проте при обмеченному обсяз1 ЛП це пов'язано з1 значно зростаючим кавантахенням на менш ¿зидк1сну зовнюню паи-ять, яка повинна' тепер використовуватися як б1льш швидк1сна ЛП ПЕ , цо з результат! мозге привести до простою ПЕ та до пад!ння продуктивности ОС.

На ochobI розробленого способу проектування структурних схем СПОП на HBIC ф!ксованого розм1ру синтезовано ряд apxiTeKTyp СПОП на HSIC, реал!зуючих наб!р задач ЛА з використанням алгоритму Фзддеева. Bel СПОП поряд з однотипн1стю модул1в характеризуйся однор> днига та. локальними м1эмдульними зв'язками. При цьому на основ! щлеспр'ямованих перетзорень в-графУ початкового алгоритму одержано одном1рн! СПОП ф!ксованого розм1ру зш низальною к!льк1стю канал1в нводу/виводу (1/1 ) та близькоп до одиниц! завгнтахен!стю.

Запропонована модаф!кац!я в!домого тдходу до побудови багатофункцюнальних (проблемно-орхентованих) СПОП на НВ1С, яка заклкчаеться в Шлеспрямованих !зоыорфних та/або гомоморфних перетвореннях РФГ вимагаемого набору алгоритшв до виду, близького по топологи. зв'язк1в з шлеы-::' (вибраним) РФГ. Лише пот1м застосовуеться в!домий п!дх1д, який заключаеться . в накладенщ РФГ вс1х алгоритмов один на одного, одержаны в результат! об'еднаного графу, а пот!м у синтез! задопомогою в1домих метод1в ' множини структурних схем СПОП для реал!зацп вказаних алгоритм1в.

На основ! модиф1кованого. тдходу проведено узагальнення запропонованого способу розбивки РФГ- алгоритму Фаддеева при його реал!заш! на СПОП ф!ксозаного розмхру на !Н1Ы метода НА, зокрема, метода Гаусса. Хордана-Гаусса,' Холецького, Хаусхолдера та Пвенса. Показано, що синтезованх в робот! структура' СПОП можуть.виконувати кр!м алгоритму Фаддеева вс! перерахован! ' алгоритми.. -Для цього необххдна лише попередня настройка -внутришьо!. структур« !х 'ПЕ на виконання заданого алгоритму, що у випадку нусористання в якост! ПЕ утверсальних (програмованих) ■■обчислювалоних ; пристро!в, не представ ля с особливо! складность '■''■.';■'.

Показано, що алгоритми,' як1 мають рхзш по тополог!! зв'язк1в' базисн! РФГ, можуть мати 1дентичн! або б1льш • близькГ В-графи чи В-кластери. Це св1дчить про те, що при синтез!' СПОП на НВ1С ф1ксованого розм1ру, реаЛ13уючога наб!р. алгоритм1в, описуемих р£зними базисними РФГ, перед використанням р!зних перетворень

0СТаНН1Х доц!льно розглянути вс1 можлив!' инохини . в1дп0в1дних 1м В-граф1В та В-кластер!в, ! т1льки у випадку негативного результату використовувати перетворення !х граф!в. . -

ОСНОВН1 РЕЗУЛЬТАТА РОБОТИ .

I. розроблено метод синтезу часово! компонента в!Добрахення РФГ алгоритму розм1рност! п в структурн1 схеми СПОП на НВ1С розм!рност! «=п-г, який на в1дм!ну в1д вадомихдозволяе зменшити трудом!стк1сть цього процесу та повн!стю формал1зувати Його.

2. Розроблено спос!б 1зоморфного перетворення РФГ трикутно! форми, в!дпов!даючого алгоритмам виршення ряду основних задач ЛА, в систол!чний торо!дальний РФГ, що дозволило розробити 61ЛЬШ ефективн1 НВ1С-алгоритми вир1шення них задач та за рахунок цього вдвое скоротити К1ЛЬК1СТЬ необх!дних ПЕ та Шдвивдтм завантахен1стъ паралельних ОС при реал!зац!1 вказаних задач.

3. Розроблено спос1б проектування структурнлх схем СЛОП на HBIC, який на в1ДМ1ну в1д в1домих дозволяе враховувати ф1Ксован! розмхри видхлених п1д задачу pecypciB.

4. На ochobí цього способу синтезовано ряд одном1рних СПОП ф1ксованого po3Mipy, реал1зуючих наб1р задач ЛА, як1 В1др1зняються В1д в!домих м1н!мальною к1льк1стю каналш взоду/виводу та близькою до повно! завантаженгстю обладнання.

5. Проведено узагальнення запропонованого способу розбивки РФГ алгоритму Фаддеева при його реал1зацП на СПОП ф1ксованого розмгру на iHoii метода ЛА, в тому число, метода Гауса, йордана-Гауса, Холецького, Хаусхолдера та Пвенса. Показано, що синтезозан1 структури СПОП иожуть виконувати, кр1м алгоритму Фаддееза, зс! зазначен! алгоритми, для чого несбххдна лише попередня тдстройка внутр1пньо! структури 1х ПЕ.

8. Розроблено ряд 1нших структурних схем СПОП на HBIC, як! В1др1зняються в!д bíдомих б1льш високими техн!чними параметрами.

РОБОТИ, 0ПУБЛ1К0ВАН1 ПО TEMI ДИСЕРТАЦП

1. A.c. СССР И520542 МКИ g оа г 13/347. Устройство для рзэлохения симметричных матриц/ Вьпгиковски Р., Каневский Ю.С., Масленников О. В.// - Б. И. 41, 1989г.

2. A.c. СССР Ш509933 МКИ G08f 13/347. Устройство для uj -разложения матриц/ Каневский Ю.С., Котов С.3., Масленников О.В.// -5 Л!. 35, 1989г..

3. Выжиксвски Р., Каневский Ю. С., Клименко М.К. , Масленникоз 0.В..Устройство для операций над матрицами. - решение о выдаче звт. свид. СССР по заявке ÍÍ4847777/24 от 27.09.91г.

4. A.c. СССР N4777154 МКИ о оа г 13/347. Устройство для решения систем линейных алгебраических уравнений. / Выхикозски Р. , Каневский Ю.С., Масленников О. В.//- Б Л\МЗ , 1992 г..

5. Вькиковски Р., Каневский Ю.С., Масленников О.В. Устройство для треугольного разложения матриц. - решение о выдаче авт. свид. СССР по заявке if 4774437/24 от 18. Об. 91г.

6. Выхиксвски Р., Каневский Ю.С., Масленников О.В. Устройство для решения'систем линейных алгебраических уравнений. - решение о выдаче авт. свид.С,CP по заявке ]f .4878784/24 от 16.01. 92г.

7. Вьотковски ?., Каневский ¡0. С., Клименко М.К. , Масленников 0. В/ Устройство для решения систем линейных алгебраических уравнений. - решение о выдача- азт. свид. СССР по заявке- Í?

4916907/24 от 15.01.92г.

. 3. A.c. СССР 1Я74П53 МКИ о об f ia/347. Устройство для операций над.матрицами./ Выжиковски Р., Каневский Ю.С., Клименко М.К., Масленников О.В.// - Б.И.22, 199217 t

9. A.c. СССР «=1733868 МКИ с oe f is/347. Устройство для операций над матрицами./ Выжиковски Р., Каневский Ю.С., Масленников О.В.// - Б.И.ig , 1992Г7

10. Выжиковски Р., Масленников О.В. Синтез систолических процессоров для треугольного разложения матриц различного вида// Конвейерные вычислительные системы: Тез. докл. и сообщ,, 2 Всесоюзное совещание - Киев: КПИ. 1988. - С. 79.-

II. Масленников О.В., Овраменко С. Г., Синичук И.И. Методика и программные средства автоматизированного проектирования систолических, структур // Конвейерные вычислительные системы; Тез. докл. и соосщ., 2 Всесоюзное совещание - Киев:. КПП 1988.-С. 71.

■ 12. Выжиковски Р., Каневский Ю. С., Масленников О.В. Систолический процессор для треугольного разложения ленточных матриц// Методы и ■ микроэлектронные средства 'цифрового -преобразования и обработки сигналов (siAP-ea ); Тез. докл. кон$.,

- ¿"ига:. ИЭиВТ, 1989.-T.I., - С.302.

13. Выжиковски Р., Каневский Ю.С., Масленников'0.В. Реализация алгоритма исключения Гаусса с частичным выбором■ на систолических процессорах// Тез. докл. I Всесоюзной конф. "Однородные вычислительные среды и систолические структуры" - Львов. • 1990,- т.1.- С. 41.

14. , Выжиковски Р., " Каневский Ю.С., Масленников О.В. Систолический процессор с активным управлением для решения систем линейных алгебраических уравнений// Теория и практика создания систем технического зрения : Матер, семинара МДНТП им. Дзержинского

- Москва. 1990. -С. 88.

15. Выжиковски Р., Каневский Ю.С. .Масленников О.В. Отображение алгоритма исключения Гаусса на архитектуру систолических массивов. //Электронное моделирование,-1991.-с. 14-18.

16. Выжиковски Р., Каневский Ю.С., Масленников О.В. Решение одного класса задач линейной алгебры на линейных систолических вычислителях. //Электронное моделирование. -1993. ¿(Ç — 33

Лзтор .ffl^__••