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

ВІННИЦЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ О Д

■і .......-

ШОЛОТА ВЛАДІСЛАВ ВАСИЛЬОВИЧ

УДК 681.325.5

СТРУКТУРНА ОРГАНІЗАЦІЯ ПАРАЛЕЛЬНИХ СПЕЦПРОЦЕСОРІВ ДЛЯ МАТРИЧНИХ ЗАДАЧ ЛІНІЙНОЇ АЛГЕБРИ

Спеціальність 05.13.13 — “Обчислювальні машини, системи та мережі”

АВТОРЕФЕРАТ

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

Вінниця 2000

Дисертацією є рукопис.

Робота виконана у Вінницькому державному технічному університеті Міі терства освіти і науки України.

Науковий керівник: доктор технічних наук, професор Кожем’яко Володт Прокопович, Вінницький державний технічний універ тет, завідувач кафедри лазерної та оптоелектронної т ніки

Офіційні опоненти: доктор технічних наук, професор Тарасенко Володт Петрович, Національний технічний університет Укра “КПІ”, завідувач кафедри спеціалізованих комп’ютері систем

кандидат технічних наук Козлов Леонід Григорович, статут кібернетики ім. В.М.Глушкова НАН України, і діл управляючих машин і систем, старший наукої співробітник

Провідна установа: Державний науково-дослідний інститут інформацій інфраструктури Державного комітету зв’язку та інфор тизації та НАН України, відділ перспективних інфорі ційних технологій, м.Львів

J л

Захист відбудеться “ й. ” 2000 р. о -У годині на засіда

спеціалізованої вченої ради Д 05.052.01 у Вінницькому державному технічному у верситеті за адресою: 21021, м.Вінниця, Хмельницьке шосе, 95.

З дисертацією можна ознайомитись у бібліотеці Вінницького державні технічного університету за адресою: 21021, м.Вінниця, Хмельницьке шосе, 95.

Автореферат розісланий 2000 p.

Вчений секретар xg —_______________

спеціалізованої вченої ради ---------------- —Захарченко С.М.

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

Актуальність. Організація паралельних обчислень для матричних задач лі-[іої алгебри (ЛА) є предметом теоретичних і експериментальних досліджень для альшого зростання продуктивності обробки великорозмірних інформаційних ма-ів в приладобудуванні, робототехніці, біомедицині. Зокрема, однією із базових ричних операцій ЛА в системах розпізнавання образів, аналізу і оброблення зо-жень, системах реконструктивної томографії є розв’язання систем лінійних алге-їчних рівнянь (СЛАР) високих порядків та обернення великорозмірних матриць, і цьому велика обчислювальна складність матричних операцій, а також високі юги до точності і часу виконання обумовлюють доцільність їх реалізації на пара-ьних спеціалізованих обчислювальних системах (спецпроцесорах СП).

Досягнення в виробництві надвеликих інтегральних схем (НВІС) відкрили но-южливості в побудові високопродуктивних СП з масовим паралелізмом (систо-тх, хвильових, трансп’ютерних), забезпечуючи рівень обчислювальної швидко, наприклад, при оберненні матриць розмірністю 100x100 елементів до 400 LOP. Проте властиві технології НВІС локальність і регулярність інформаційних керуючих потоків, мінімізація ширини каналів введення-виведення і обміну да-[и між процесорними елементами (ПЕ) обумовлюють лінійну структурну органі-ію паралельних СП для задач ЛА ,зменшуючи при цьому потенційно можливий алелізм матричних обчислень в N разів. Організація електронного СП, утворена вимірними зв’язками між ПЕ, при значних розмірностях NxN матриць, що облаються, представляє лише теоретичний інтерес. Навіть при N=1000 технологія [С не здатна забезпечити реалізацію СП з кількістю ПЕ рівня 106 та множинний гуп до даних.

Недоліки електронних цифрових схем усуваються використанням оптичних одів обробки. Вирішуючи проблему паралельного введення-виведення оптичної ормації та організації багатовимірних зв’язків між ПЕ, акустооптичні СП для ричних задач ЛА мають обмеження, викликані точністю аналогових обчислень.

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

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційні нідження проводились згідно з напрямками досліджень: державної науково-іічної програми №06.003.01, проекту 06.03.01/02692 “Відео-комп’ютер око-цесорного типу з нетрадиційними способами кодування інформації”; наукового екту 67-Д-148 “Принципи організації і структури оптоелектронних комп’ютерів щнорідних логіко-часових середовищах” (№ держ. реєстрації 0196U015323); на-вого проекту 50-Д-180 “Створення оптоелектронних комп’ютерних технологій пізу стану серцево-судинної системи” (№ держ. реєстрації 0197U012663), які ви-

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

Мета і задачі дослідження.

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

Задачі дослідження:

1. Аналіз та систематизація концепцій та підходів до створення паралельних спе роцесорів для матричних задач лінійної алгебри.

2. Модифікація прямих методів розв’язання СЛАР високих порядків та оберне матриць великої розмірності на основі природного паралелізму цифрових от них обчислень.

3. Розробка паралельних алгоритмів виконання базових матричних арифметич операцій в формі з плаваючою комою.

4. Відображення модифікованих методів паралельного розв’язання СЛАР та об нення матриць на структурну організацію спецпроцесора.

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

6. Оцінювання ефективності варіантів структурної організації СП для паралельн розв’язання СЛАР та обернення матриць в залежності від розмірності матриць.

7. Проведення комп’ютерного моделювання модифікованих методів паралельн розв’язання СЛАР.

8. Дослідження аспектів технічної реалізації паралельного СП для матричних за лінійної алгебри на оптоелектронній елементній базі.

Об ‘єкт дослідження - архітектура високопродуктивних обчислювальних с тем для паралельної обробки великорозмірних матриць. Предмет дослідженн структурна організація обчислювальних систем для паралельного розв'язання \ ричних задач ЛА в реальному часі. Методи дослідження базуються на основ положеннях системного аналізу і теорії паралельної обробки інформації, теорії горитмів, теорії проектування обчислювальних систем і теорії цифрової оптич обробки зображень.

Наукова новизна отриманих результатів:

1. Одержано нові паралельні інтерпретації методів Гаусса і Гаусса-Жордана , розв’язання СЛАР високих порядків та обернення великорозмірних матриць основі обчислення зовнішнього добутку векторів за принципами багатовимірі цифрових обчислень, які відрізняються покращеними часовими характер тиками.

2. Вперше розроблено структурну організацію паралельних СП з плаваючою кол для матричних задач ЛА: для паралельного розв’язання СЛАР високих порях та обернення великорозмірних матриць, які характеризуються підвищенням сі

з

пурної швидкодії, багатофункціональністю та розширеною областю застосуван-ш. Це досягається за рахунок таких чинників: здатності багатовимірної структу->и підтримувати максимально можливий паралелізм обчислень, забезпечуючи >рганізацію розрядно-зрізового введення-виведення та обробки матриць; введен-ш до розгляду як локальних, так і глобальних зв’язків між ПЕ з властивістю пе-»етинатись без перешкод.

їперше запропоновано цифрові паралельні структури для матричної арифметики і формі з плаваючою комою: арифметичного суматора обробки матриць; поділю-іача вектора на число; обчислювача зовнішнього добутку векторів, які відрізняю-ься покращеними часовими характеристиками, підвищеною точністю і розши->еною областю застосування. Такі переваги отримано за рахунок використання юзрядно-зрізового подання матриць в формі з плаваючою комою і цифрового ча-;ового інтегрування та відсутності залежності часових характеристик структур (ід розмірності матричних операндів.

Практичне значення одержаних результатів:

підставі запропонованої паралельної інтерпретації методів Гаусса і Гаусса-■Кордана створено принципово нові апаратно-орієнтовані паралельні алгоритми іля матричних задач ЛА. Показано, що швидкодія запропонованих алгоритмів іеревищує аналогічні показники відомих алгоритмів приблизно в 7 разів, їапропоновані паралельні алгоритми та структурна організація паралельного СП ці я матричних операцій ЛА з плаваючою комою, реалізовані на оптоелектронній :лементній базі, можуть бути використані в системах прикладної обробки І аналі-іу зображень та розпізнавання образів, реконструкції біомедичних зображень, іапроионовано програмний комплекс для розв’язанім матричних задач ЛА, який ¡икористовується при вивченні дисципліни “Комп’ютерне моделювання при-ягроїв і технологій в оптоелектроніці” у Вінницькому державному технічному університеті.

Впровадження результатів підтверджується відповідними актами.

Особистий внесок здобувача. Всі основні результати дисертаційної роботи имані автором особисто. У публікаціях, написаних у співавторстві, здобувачеві ежать: структурна організація та алгоритм роботи паралельного поділювача век-і на число в формі з плаваючою комою на основі принципів обробки за розрядні зрізами [3]; структурна організація та алгоритм роботи цифрового паралельно-:уматора обробки великорозмірних матриць в формі з плаваючою комою на осі принципів обробки за розрядними зрізами [4]; оцінка параметрів оптоелектрон-реалізації вузлів паралельного процесора для множення знакозмінних мать [5]; аналіз багаторівневої моделі паралельних інформаційно-обчислювальних >бів [6]; оптоелектронна реалізація базових вузлів логічної паралельної обробки риць з покращеними характеристиками [7]; структурна організація та її оптоеле-знна реалізація паралельного спецпроцесора для розв’язання СЛАР та обернення риць за методом Гаусса на основі зовнішнього добутку векторів [8] і на основі

паралельного перемножувача картин зображень [9].

Апробація результатів дисертації. Основні положення і наукові резуліл доповідались і обговорювались на: НТК з міжнародною участю “Прил; будування-95” (м. Львів, 1995); 111 Всеукраїнській міжнародній конфере “Обробка сигналів і зображень та розпізнавання образів” (УкрОбраз-96) (м. К 1996), наукових семінарах інституту комп’ютерних технологій і комп’ютерних < тем при Вінницькому державному технічному університеті.

Публікації. За матеріалами дисертації опубліковано 9 друкованих робі яких 6 статей в наукових журналах, що входять до відповідного переліку Е України, 1 патент на винахід та 2 статті у збірниках праць.

Об’єм і структура дисертації. Дисертаційна робота складається з вступу, тирьох розділів, загальних висновків, списку використаних джерел і 6 додатків, гальний обсяг дисертації 165 сторінки, з яких основний зміст викладено на 141 кушах друкованого тексту, 31 рисунків, 2 таблиці. Список використаних джерел раховує 104 найменування. Повний обсяг дисертації 205 сторінки.

ОСНОВНИЙ ЗМІСТРОБОТИ

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

В першому розділі проведено аналіз основних матричних операцій ЛА в формаційно-обчислювальних системах реального часу з метою встановлення б: вик операцій спецпроцесора паралельної обробки матриць.

Основна увага приділена методам та засобам реалізації операцій паралельн розв’язання СЛАР високих порядків та обернення великорозмірних матрь оскільки ефективна реалізація інших паралельних операцій (наприклад, вектор матричного множення, матрично-матричного множення) була детально пропраї вана попередниками. Проаналізовано ряд відомих прямих методів розв’яза СЛАР, основною причиною звернення до яких порівняно з непрямими метод; стала фіксованість числа кроків обчислень, яка не залежить від типу даних і м( бути визначена заздалегідь. Методи Гаусса і Гаусса-Жордана, як представники 1 методів для розв’язання СЛАР, що втричі швидші, ніж група ОЯ-методів, визнав найпридатнішими для розпаралелювання обчислювальних процесів на СП.

Проведено аналітичний огляд обчислювальних структур для паралельн розв’язання СЛАР і обернення матриць, серед яких виявлено два перспективних прямки розвитку паралельних СП. Перший напрямок пов’язаний з розвитком ц рових локально-зв’язаних систем (систолічних, хвильових, трансп’ютерні орієнтованих на технологію НВІС. Другий напрямок пов’язаний з оптичною ана говою і аналогово-цифровою обробкою, яка знімає обмеження швидкодії арсеї галієвих НВІС, але має низьку точність.

На основі проведеного аналізу зроблено такі висновки.

Є доцільним розробка паралельного СП для матричних задач ЛА, який би задовольняв системним вимогам по забезпеченню: цифрової точності обчислень та представлення даних в формі з плаваючою комою; швидкодії на рівні 103 МРЬОР; поєднання паралельної обробки з паралельним введенням-виведенням інформації; відсутності теоретичних обмежень на розмірність матриць.

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

У другому розділі запропоновано нові паралельні інтерпретації методів Гаусі Гаусса-Жордана для розв’язання СЛАР високих порядків та обернення велико-імірних матриць на основі зовнішнього добутку векторів (ЗДВ).

Необхідно розв’язати СЛАР, подану в матричній формі такого виду:

А - квадратна невироджена матриця коефіцієнтів розмірністю Ь'хІЧ;

X - матриця шуканих векторів невідомих розмірністю КхЫ;

В - матриця векторів вільних членів розмірністю КхЬІ.

Матриці X і В обрані квадратними, вважаючи на можливість застосування за->понованих паралельних методів як для розв’язання СЛАР (Х=[х(|), х*^]),

: і для пошуку оберненої А'1 матриці (В=Е, де Е - квадратна одинична матриця).

За використаною методикою проектування цифрових процесорів паралельної юбки матриць математичні моделі паралельного процесу розв’язання СЛАР ма-ь визначатись за своїми вхідними, вихідними та проміжними даними в матричній змі. Отже, класичні методи Гаусса і Гаусса-Жордана, виражені у скалярних реку-ітних співвідношеннях, повинні бути модифіковані за матричною формою.

Позначимо як Щ1:1Ч;1:2К] розширену матрицю проміжних результатів.

Початкові дані для паралельного методу Гаусса, визначені на нульовому кроці З ) обчислень, подано у вигляді:

Прямий хід паралельного методу Гаусса містить такі дії.

Черговий рядок <І[1;1:2ІУ] проміжного результату, утворений на І:-му кроці обілень в результаті паралельного ділення векторів на ведучий елемент

АХ=В,

(1)

А[і: N,-1: /V]('=0) = А, В[і: N.-1: Лг]('=0) = В, Х[і: ¿V;!: Л/]М) = 0, К[і; N;1: 2М\(,Н)} = 0.

(2)

/У]= А('ч)[і,і : Л']/а(' ,)[і;і], (/ = 1,7У) а(,)[і;(Л^ + і): 2ЛГ]= ВИ)[і;1:

запишемо в матрицю Гі(0 під час виконання паралельного зсуву таким чином:

К(0[1:ДГ;1:2Л^]=фТ,(К(')[1:Л/,;1:2Л]). с!{,,[ 1 :Л'; 1:2ЛЧ, (

♦ і

де ф - оператор паралельного зсуву інформації, записаної в масиві К, вгору

один елемент з паралельним записом на вільне місце вектор-рядка <1.

Сформуємо зовнішній добуток (0) вектор-рядка сі1'' і вектор-стовп виділеного як перший стовпець матриці

у(/)[1 :М; 1 ]=А(М)[ 1 :ІУ; 1 ], (

в вигляді матриці Р(,) за формулою:

Р('}[1 :ІУ; 1:2Щ= у(,)[1 :ЛГ; 1]<8Ш(0[ 1; 1:2Щ, (

де І ]хсі(,;£ 1(/ = Ї.Л',/ = Ї,2А/).

Тоді процес чергового виключення змінної х, із СЛАР на кожному Г-му крс прямого ходу визначимо в результаті таких перетворень для і =

А(')=ф<_1(фТі(А(

В(/ЧрТ^В(м)-Р(')[1:Аг;(ЛЧ-1):2Л']), (

де ф4-1, фТі - оператори паралельного зсуву відповідно вліво і вгору на 1 елемен записом нулів в вивільнені відповідно стовпець і рядок.

Отже, на 1=Ы-му кроці прямого ходу отримаємо нулі в матрицях А і В та пр міжний результат в матриці К, який для незалежних обчислень на прямому та зі ротному ходах методу перезапишемо в масиви XI і Х2 в такій формі:

Х1(,=л,)[іN,-1: ЛГ]=П<'“">[і; ІУ;1: ІУ}

Х2('=л,)[і: N,-1: #] = [і: (# + і): 2ЛГ}

Зворотній хід паралельного методу Гаусса містить такі дії.

На кожному і=(К+і)-му крюці обчислень (і-номер кроку зворотного хо;

і = 1,(Л'-і)) сформуємо матрицю РХ як зовнішній добуток (®) векторів

РХ(/)[ 1 -./V; 1 :Л’]=ах<')[ 1 :ІУ; 1 ]®ух(,)[ 1; 1 :Л'1, (1

де вектор-рядок \'х<',)[ 1; 1://] визначимо як (іУ-/)-й рядок матриці Х2*0

УХ(0[ 1; 1 :ЛГ1=Х2<0[(ЛГ-/); 1 :Л^, (]

а вектор-стовпець (1хм[1:Л^;1] утворимо за елементами неголовної діагоналі персті реної матриці ХМ(,|[1 :/У; 1 :,У]

гіх(')[А:;1]=ХМ(')[А:;(^-Ус+1)], (к = ЦУ). (1

Матрицю ХМ(<) сформуємо в результаті логічного множення (л) матриці Х1(/> і гцифічної матриці TVI[ ] :/V; 1 :Л/] з одиничними елементами за виключенням першо-стовпця

ХМ(,)[і: N; 1 : ЛГ] = Xl[l: N;l ; N]л M[l ; N; 1 : ЛГ]. (13)

Тоді значення матриці проміжного результату на /=(№-/)-му кроці обчислень рмуватиметься за формулою виду

X2('=*H)= Х2('-°-РХ(,>, (14)

а останньому t=2N-1 кроці обчислень набуватиме значень матриці невідомих X

Х[ 1 :N; 1 :ЛП=Х2('=2Л'-,>[1 :N; 1 :N], (15)

При цьому

Х1(,) = ^’(хі('ч))о (t = N,(2N~-\)). (16)

Таким чииом, час виконання обчислень за паралельним методом Гаусса скла: 2N кроків в однозадачному режимі і N кроків в потоковому режимі.

Паралельна інтерпретація методу Гауса-Жордана на основі ЗДВ передба-: таке формування початкових даних:

R{,‘0)[ 1 :N; 1 :iV]=A, R("0>[ 1 :N;(N+1 ):2N]=B. ( 17)

За ведучий елемент на кожному /-му кроці (/ = 1, Л/') обчислень обрано елемент /]/0 матриці R.

Розділивши одночасно коефіцієнти t-го рівняння системи, що є елементами t-рядка матриці R, на ведучий елемент, отримаємо вектор-рядок d[l;l:2/V], а саме:

Визначивши вектор-стовпець v(,,[ 1 :N; І ] як виділений t-й стовпець матриці зміжного результату із одиничним значенням елемента, що знаходиться в 1-му <ку,

vw[1:jV;1]= 1 :Лг;Г], (19)

vw[i;l]=-l, сформуємо ЗДВ в вигляді матриці Р за формулою (6).

Тоді процес формування проміжного результату R в часі (i = l./v) описується :им матричним співвідношенням:

R(,>=(R(,‘1)aMR(,))- Pw, (20)

л - оператор логічного множення (кон’юнкція);

МИ*''1 — специфічна бінарна матриця розмірності Му,2Ы елементів, будь-який є; мент тг[іЛ якої дорівнює 0 при г- І і дорівнює 1 в інших випадках (і=1,2Лг );

Р(1> — зовнішній добуток векторів.

Кінцевий результат визначається на останньому г^Л'-му кроці обчислень в ві

Х[1:ЛГ;1:Л^=К('=';У)[1:Л,;(//+1):2Л0. (2

Час обчислень за паралельним методом Гаусса-Жордана для розв’язан СЛАР складає N кроків як в однозадачному, так і в потоковому режимі обчислень.

Встановлено базові матричні операції запропонованих паралельних мето; Гаусса і Гаусса-Жордана і на основі застосування принципів розрядно-зрізової с робки і цифрового часового інтегрування розроблено нові паралельні алгоритми виконання, а саме: паралельний алгоритм додавання знакозмінних матриць; пара) льний алгоритм ділення вектора на число; паралельний алгоритм обчислення ЗДВ Зазначені алгоритми наділені високою точністю обчислень за рахунок вико£ стання подання і обробки знакозмінних УУх//-вимірних матриць операндів та мі риць результату в формі з плаваючою комою в прямому коді у вигляді наборів Б=(М+Р+2) бінарних розрядних зрізів (РЗ), що мають розмірність відповідних м; риць. Наприклад, маємо таке подання першого операнду — матриці А:

А„^=1,...,АЯ )=л/ .А^=м+2,...,А р_1=і-), (2

де .УЦя _0 і А(„,л) - знаковий і інформаційні РЗ мантиси матриці А;

і А(/Іі) - знаковий і інформаційні РЗ порядку матриці А;

Ма 'Ра — порядкові номери РЗ просторових кодів мантиси і порядку матриці А; МІР — число інформаційних РЗ мантис і порядків матриць А і В.

Розрядний зріз - це бінарна матриця, утворена із значень (0 або 1) одноімі них кодів елементів матриць.

Особливістю запропонованих паралельних алгоритмів є також відсутність : лежкості їх часових характеристик {тах{г™ ) Т™-, Т”з£і) від розмірності ог рандів, в чому переконують такі отримані співвідношення:

тах(7',:;;- )=(4Р+4М+МР + П)-АГ",

КГ = (м2 + ЇМ + 2Р + 12). ДГ", (2

Пт =(м2+ЗМ+2Р + з).АТ£д,

де - тривалість кроку обробки одного РЗ, яка не залежить від N для параде.»

них процесів і може бути оцінена за сумою часу паралельного запису РЗ в мас часу (/„„„) паралельного перетворення РЗ з прямого коду в доповняльний код часу паралельного повного додавання РЗ операндів з урахуванням матриці і

зносу в такому вигляді:

Отримані співвідношення (23) дають змогу уточнити часові параметри пара-лтьних методу Гаусса і методу Гаусса-Жордана для розв’язання СЛАР як в одноза-ічному режимі (Гг, Тр-ж)> так і в режимі обробки потоку задач (Т'г, Т'г-ж), за такими ормулами:

Розроблені паралельні методи і алгоритми для матричних задач ЛА орієнтова-і на довільні розміри задачі (Ы — довільне число) при забезпеченні найкращого часу і конання обчислень порівняно з відомими. Проте остаточні висновки про їх пере-іги зроблено після розгляду адекватних їм паралельних обчислювальних структур, ї основним є питання про співвідношення фізичного розміру (числа ПЕ) системи і ззміру задачі, які розв’язуються.

В третьому розділі розроблено нову структурну організацію паралельних СП ія матричних задач ЛА: для паралельного розв’язання СЛАР високих порядків та 5ернення великорозмірних матриць за методом Гаусса і Гаусса-Жордана на основі Ц.В, а також їх апаратно-орієнтовані паралельні алгоритми. Особливостями назва-іх структурних організацій є такі: матричний тип обчислювальної структури, пательне введення та виведення матричних операндів, яке здійснюється відомим іалого-цифровим картинним перетворювачем з паралельними входами-виходами,

0 перетворює числові матриці в набори бінарних РЗ; наявність в структурах доїльних і глобальних зв’язків між ПЕ з властивістю перетинатись без перешкод.

Базовими блоками обох структур СП є виконані для паралельних обчислень з іаваючою комою арифметичний суматор обробки матриць, поділювач вектора на ісло, обчислювач ЗДВ. їхнє функціональне призначення і структурні зв’язки про-:монстровано, наприклад, на схемі структурної організації СП для паралельного >зв’язання СЛАР за методом Гаусса-Жордана (рис.1).

Початкові дані в вигляді матриць А, В та Е, поданих в формі з плаваючою ко-эю відповідно до вигляду (22) за наборами Б бінарних РЗ, поступають з паралель-їх входів СП через паралельні матричні комутатори МК1 і МК4 і паралельний ре-стр РгЕ на перші 5 та другі 5 паралельні двовимірні ТУхЛ' входи цифрового матрично накопичуванльного суматора НСм, який працює в режимі паралельного запису.

1 допомогою матричного комутатора МК2 формується вектор діленого, який вступає на 5 перші та 5 другі /У-канальні входи діленого поділювана ПОД.

Перші 5 і другі 5 А'-канальні входи дільника поділювача ПОД з’єднані із 5 ;ршими і 5 другими /У-канальними виходами матричного комутатора МКЗ, який в >жний /-й момент часу обирає відповідно /-й елемент у рядку, який визначив кому-

Тг =(2ІУ-1 )■ (2М2+МР+14М+8Р+29), Т'Г=Т'Г.Ж =7>.ж =Щ2М2+МР+14М+8Р+2&).

(25)

(26)

татор МК2. Інформація на паралельні входи комутатора МК2 поступає з відповід паралельних виходів суматора НСм.

Отже, поділювач формує вектор-рядок для ЗДВ відповідно до виразу (18).

Паралельний блок формування вєктор-стовпця БФВС реалізує співвідноше (19), визначаючи вектор-стовпець для ЗДВ.

Виділені вектор-рядок і вектор-стовпець, поступаючи на перші 5 та друї паралельні ЛГ-канальні рядкові входи і 5 паралельні 7/—канальні стовпцеві вх1 блоку ЗДВ, утворюють на його перших Я та других .V ЛГхМ вимірних виходах і ширену матрицю відповідно до виразу (6). Проінвертувавши знаковий РЗ утвор£ го ЗДВ, виконаємо його алгебраїчне додавання з попередньою інформацією, запі ною в НСм, обнуливши перед цим його 1-й рядок відповідно до виразу (20) за до могою схеми матричного кон’юнктора і вмісту двовимірного регістру специфіч матриці Ф1.

Матричний комутатор МК4, що має три групи перших Б і других Б двовт них NxN входів, здійснює комутацію інформації на вхід НСм від трьох джерел: чаткової інформації, інформації з БЗДВ та з матричного кон’юнктора. Результат де сформований за N тактів роботи СП на 5 двовимірних Л'хЛ' виходах НСм.

Розроблена структурна організація паралельного СП для розв’язання СЛА1 методом Гаусса містить крім названих базових паралельних блоків ще ряд парі льних блоків, номенклатура і відповідні зв’язки між якими ширше і складніше, ні наведеної структури.

Для порівняння апаратурних витрат 7, пропрацьовано реалізацію встановлю го набору паралельних блоків і вузлів обох варіантів структурних організацій для розв’язання СЛАР до рівня базового логічного паралельного елементу роз» ності А'хЛ'.

Запропоновано нові цифрові паралельні структури для матричної арифмет в формі з плаваючою комою: арифметичного суматора обробки матриць НСм, п< лювача вектора на число ПОД, обчислювача ЗДВ, які відрізняються підвищеною чністю, покращеними часовими характеристиками, розширеною областю заст( вання. Це досягнуто за рахунок використання вищевказаних особливостей струї рної організації СП.

Виходячи із синтезованої схеми повного паралельного суматора для додаї ня відповідних РЗ матричних операндів на базових матричних логічних елемен час , визначений алгоритмічно за формулою (24), оцінено так:

ДГД=8тл„, (

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

Рис.1. Структурна організація матричного розрядно-зрізового СП для розв’язання СЛАР за методом Гаусса-Жордана

Підставивши значення АТ^3д із (27) в формулу (23) і враховуючи адекватніс фізичних розмірів структур НСм, ПОД, блоку ЗДВ розмірам паралельних алгорі мів відповідних операцій, очевидною є відсутність залежності часу обробки стр> тур від розмірності матричних операндів. Це приводить до зростання швидкодії н званих паралельних структур пропорційно до збільшення числа елементів матриці

Було розглянуто два основних аспекти задачі оцінювання структурної ефект вності паралельних СП для матричних задач ЛА: порівняння ефективності розря но-зрізових СП з традиційними архітектурами подібних СП і порівняння ефекти ності різних структурних варіантів розрядно-зрізового СП.

За окремі критерії ефективності відповідно до першого аспекту взято характ ристику прискорення 5, розв’язання задачі паралельною структурою по відношень до послідовної та коефіцієнт т], завантаженості апаратури, що визначається так:

5Г, =7'0/7;, V, -5,//’, (2

де Т0 і Ті - час обчислення відповідно за послідовним і паралельним і-м алгори мом, виражений в тактах;

Р — число процесорів.

За результатами досліджень прискорення розрядно-зрізового СП росте в ква ратичній залежності від розмірності матриць і перевищує найкращі відомі показн ки, як мінімум, в 7 разів, а його інший коефіцієнт г],~\. Проте така методика оціні вання ефективності паралельних структур СП вносить суттєве припущення, що тр валість кроку обчислень в різних структурах однакова.

Цей недолік знято при оцінюванні ефективності різних структурних варіант розрядно-зрізового СП за окремим критерієм, який визначає значення швидко; К'"’", віднесеної до величини затримки т розповсюдження сигналів використанії елементної бази, за формулою:

ув/г)н _ ^

т'

де V - швидкодія паралельного СП.

В роботі оцінено швидкодію паралельного арифметичного суматора НСм, п ралельного поділювача ПОД, паралельного блоку ЗДВ, а також віднесену швидк дію ) розрядно-зрізових СП для розв’язання СЛАР за паралельним м

тодом Гаусса і Гаусса-Жордана на основі таких формул:

МРЬОР

(2!

тгвідп

У Г

2Аг(м2 + ЇМ + 2Р +12)+ ЗИг(м2 + ЗМ +2Р + з)

__________4М+МР + 4Р + 11

ЩШ^ТМР + Ї4М + 8Р + 29)г

+ ЗІУ2

(ЗІ

2N {м2 f ЇМ + 2Р + u)+2N2(m2 + ЗМ + 2Р + з)

_____________AM + МР + АР + 11______

8(2А/2 + МР + 14Л/ + 8Я + 28)г

+ 2jV3

Зроблено висновки стосовно запропонованих структурних рішень, які показа-і доцільність їх використання.

Так, на рис.2 показано переваги в швидкодії порівняно з відомими запропоно-іних розрядио-зрізових СП обернення матриць за методом Гаусса (СПГ) і за мето-зм Гаусса-Жордана (СПГ-Ж), визначені для розрядності 5=64, розмірності N=100 і =1 не, характерних для реалізації розроблених СП на бістабільних пристроях з са-энаведеним електрооптичним ефектом (SEED-пристроях). Швидкодію одноплатно процесора SKY mn К прийнято за одиницю, що відповідає чисельному значен-

о 1 MFLOP.

Остаточний вибір ефективнішої структурної організації паралельного СП зро-іено на основі узагальненого критерію, який оцінює показник ефективності (Е,) за видкодією СП (F,), віднесеною до умовного вузла апаратурних витрат (Z,), де за /іовний вузол обрано матричний логічний елемент розмірності NxN.

Ej = Vt /Z, [MFLOP/ум. вузол].

(32)

Встановлено, що коефіцієнт ефективності розрядно-зрізового СП за методом іусса-Жордана перевищує в 2,6 рази ефективність СП за методом Гаусса .

В четвертому розділі з метою підтвердження теоретичних результатів дослі-кення розроблено програмний комплекс для розв'язання СЛАР, арифметичних та

(с.2. Діаграма швидкодії матричних процесорів при обчисленні оберненої матриці розмірністю 100x100 елементів

інших спеціальних перетворень над матрицями в відповідності до запропоновані: паралельних алгоритмів обчислень, що імітують процес обробки інформації в пар: дельному СП з плаваючою комою. Даний програмний продукт використовуєтьс при вивченні дисципліни “Комп‘ютерне моделювання пристроїв і технологій в оі тоелектроніці” для моделювання паралельних оптоелектронних тривимірних струї тур паралельної обробки зображень, про що свідчить відповідний акт впроваджені результатів дисертаційної роботи в учбовий процес.

Досліджено аспекти технічної реалізації базових вузлів паралельного СП до задач ЛА на оптоелектронній елементній базі. Оцінено швидкодію запропонован структурної організації паралельного СП, реалізованої на оптично-керовані транспарантах, бістабільних еталонах Фабрі-Перо, елементах на БЕЕО-пристроя що дало змогу встановити значення потенційно досягненої швидкодії на рівні Iі МРЬОР при практичних обмеженнях розмірності на рівні 1000x1000.

Доцільність розробленої структурної організації паралельних СП для матри1 них задач ЛА підтверджено актом впровадження результатів дисертаційної роботи розробку структурної організації сопроцесора обробки матричної інформації ді персональної ЕОМ, що працює в складі швидкодіючих систем обробки зображень розпізнавання образів в реальному часі.

Зазначено подальший напрямок досліджень в області створення розрядні зрізових СП для матричних задач ЛА - вирішення фізичних та технологічних про1 лем, пов'язаних з розробкою та створенням оптоелектронних тривимірних 3-0 інт гральних схем.

ВИСНОВКИ

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

1. Модифіковано методи Гаусса і Гаусса-Жордана для паралельного розв’язані СЛАР високих порядків та обернення великорозмірних матриць на основі обчи лень зовнішнього добутку векторів за принципами багатовимірних цифрових оі тичних обчислень та проведено їх комп’ютерне моделювання. Застосування ро рядно-зрізового способу подання та обробки матриць в сукупності з цифрови часовим інтегруванням проміжних результатів дозволило отримати нові парал льні форми апаратно-орієнтованих алгоритмів Гаусса і Гаусса-Жордана, які хар ктеризуються найвищим коефіцієнтом прискорення (/V2) порівняно з відомий (М2П), підвищенням точності обчислень та розширеною областю застосувані

завдяки використанню подання даних в формі з плаваючою комою.

На основі використанім властивостей природного паралелізму оптичних цифрових обчислень запропоновано нові паралельні цифрові алгоритми операцій додавання знакозмінних матриць, ділення вектора на число, зовнішнього добутку векторів, поданих в формі з плаваючою комою, проведено їх комп’ютерне моделювання. Паралельні алгоритми дозволили підвищити точність подання і обробки великорозмірних даних в поєднанні із зростанням обчислювальної швидкодії. їх особливістю є відсутність залежності часових характеристик від розмірності операндів. Розроблено нову структурну організацію паралельних спецпроцесорів з плаваючою комою для матричних задач ЛА: для паралельного розв’язання СЛАР високих порядків та обернення великорозмірних матриць, які характеризуються суттєвим підвищенням коефіцієнта прискорення в поєднанні з підвищенням коефіцієнта завантаженості апаратури. Це досягається за рахунок таких чинників: здатності матричної архітектури підтримувати максимальний паралелізм методів обчислень, забезпечуючи організацію розрядно-зрізового введення-виведення та обробки матриць; наявності локальних і глобальних зв’язків між ПЕ з властивістю перетинатись без перешкод. Швидкодія розроблених спеціалізованих структур для задач ЛА зростає пропорційно збільшенню розмірності /Ух/У матриць, перевищуючи, як мінімум, на порядок швидкодію відомих аналогів. При оптоелек-тронній реалізації структур паралельних СП вона досягає потенційного значення 105 \4FLOP, що дозволяє використовувати розроблені СП в високопродуктивних системах обробки зображень розмірністю іУхуУ = 1000x1000.

Запропоновано нові цифрові паралельні структури для матричної арифметики в формі з плаваючою комою: арифметичного суматора обробки матриць; поділю-вача вектора на число; обчислювача зовнішнього добутку векторів, які характеризується підвищеною точністю і розширеною областю застосування. Це досягнуто за рахунок використання розрядно-зрізового подання матриць в формі з плаваючою комою і цифрового часового інтегрування. Запропоновані структури підтримують максимальний паралелізм алгоритмів матричної обробки, властивий оптичним цифровим обчисленням, тим самим орієнтуючи схемотехнічні рішення розроблених СП на оптоелектронну елементну базу.

Виконано оцінювання структурної ефективності паралельних матричних СП на основі окремого критерію визначення швидкодії, віднесеної до величини затримки розповсюдження сигналів найповільніших базових паралельних елементів. На основі узагальненого критерію ефективності встановлено, що ефективність розрядно-зрізового СП для розв’язання СЛАР за паралельним методом Гаусса-Жордана на основі обчислення ЗДВ перевищує в 2,6 рази ефективність СП за паралельним методом Гаусса.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Шолота В.В. Концепції та підходи до синтезу обчислювальних структур високі продуктивних процесорів для паралельного обернення матриць та розв’язань систем лінійних рівнянь // Вимірювальна та обчислювальна техніка в технологі1 них процесах (Технологічний університет Поділля, м.Хмельницький). - 1998. №2. — С.84-90.

2. Шолота В.В. Високопродуктивний процесор для паралельного розв’язання си тем лінійних рівнянь та обернення матриць // Вимірювальна та обчислювали техніка в технологічних процесах (Технологічний університет Поділл м.Хмельницький). - 1999. — №1. -С.86-91.

3. Кожем’яко В.П., Шолота В.В., Зволейко A.B. Паралельний поділювач вектора і число в формі з рухомою комою // Вісник Вінницького політехнічного інститут - 1998. - №4. — С.56-61.

4. Кожем’яко В.П., Заболотна Н.І., Шолота В.В. Цифровий оптоелектронний сум тор обробки матриць в формі з плаваючою комою // Вимірювальна та обчислі вальна техніка в технологічних процесах (Технологічний університет Поділл м.Хмельницький).- 1997.— №2.- С. 136-142.

5. Заболотная Н.И., Шолота В.В. Организация параллельного перемножения знаю переменных матриц в цифровом оптоэлектронном процессоре многоуровневь изображений // Электронное моделирование (Институт проблем моделирования энергетике ПАНУ). - 1997. - Т.19., №5. - С.41-49.

6. Мартинюк Т.Б., Заболотна Н.І., Шолота В.В. Оцінювання структури інформаційної складності алгоритму паралельного додавання чисел // Вісні Вінницького політехнічного інституту. - 1996. -№3. — С.21-26.

7. Пат. 23431А Україна, МКІ G06F 15/66, G06E 1/04. Цифровий паралельний проц сор багаторівневих зображень: Пат. 23431А Україна, МКІ G06F 15/66, G06E 1/( / Кожем’яко В.П., Буда А.Г., Мартинюк Т.Б., Заболотна Н.І., Ліщинська Л.І Шолота В.В.- №96072786; Заявл. 11.07.96; Опубл. 31.08.98, Бюл. №4 - 6 с.

8. Кожем’яко В., Заболотна H., Шолота В. Паралельні обчислювальні структури да розв’язку систем лінійних рівнянь та обернення матриць // Праці 3 Всеукраїнс кої конференції “Обробка сигналів і зображень та розпізнавання образів”. - Киї Українська асоціація з оброблення інформації та розпізнавання образів. - 1996. С.233-234.

9. Заболотна H., Шолота В., Зволейко А. Реалізація обернення матриць на структу паралельного перемножувача картин-зображень / Праці 3 Всеукраїнської конф ренції “Обробка сигналів і зображень та розпізнаванім образів”.- Київ: Україно ка асоціація з оброблення інформації та розпізнавання образів. — 1996 С.230-231.

АНОТАЦІЇ

Шолота В.В. Структурна організація паралельних спецпроцесорів для матрич-ніх задач лінійної алгебри. — Рукопис.

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

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

Запропоновано нові паралельні інтерпретації методів Гаусса і Гаусса-Жордана дя розв’язання систем лінійних алгебраїчних рівнянь та обернення матриць на особі зовнішнього добутку векторів з покращеними часовими характеристиками.

На основі методів розроблено нову структурну організацію паралельних спец-роцесорів, що в поєднанні з оптоелектронною реалізацією дає, щонайменше, на орядок вищу швидкодію від відомих і досягає потенційного значення 105 MFLOP ри розмірності 1000x1000.

Розроблено нову структурну організацію і цифрові паралельні алгоритми об-ислень паралельних арифметичних блоків в формі з плаваючою комою: суматора іатриць, поділювача вектора на число та блоку зовнішнього добутку векторів, часо-

і характеристики яких не залежать від розмірності операндів.

Ключові слова: обернення матриць, структурна організація, паралельний спе-процесор, метод Гаусса.

Sholota V.V. Structure Organization of Parallel Job-oriented Processor for Matrix roblems of Linear Algebra. - Manuscript.

Thesis for the candidate’s degree by the specialty 05.13.13 - computing machines ^sterns and nets. - Vinnitsa State Technical University, Vinnitsa, 2000.

The Thesis is devoted to the development of the parallel methods of the computa-on, algorithms and structures of high-performs parallel job-oriented processor for matrix roblems of liner algebra.

The new parallel interpretation of methods of Gaussa and GaussaJordana are of-:red. These methods are used for solution of high order system of the liner algebra and iatrix inversion. They on external vector’s multiplication are based. This New parallel iterpretation improves better temporary characteristic.

The new structure organization of parallel processors is designed on base of new irallel interpretation of methods. The potential performance of this processors is 10s IFLOP with dimension 1000x1000. There are possible with optoelectronic realization.

New parallel structure organization of floating-point matrix adder, divider of the ;ctor on number and block of external vector’s multiplication are proposed. They tempo-;ry characteristics are independent of operand’s dimension.

The Keywords: matrix inversion, structure organization, parallel job-oriented proc essor, method Gaussa.

Шолота B.B. Структурная организация параллельных спецпроцессоров дл матричных задач линейной алгебры. - Рукопись.

Диссертация на соискание научной степени кандидата технических наук п специальности 05.13.13 - вычислительные машины, системы и сети. - Винницки государственный технический университет, Винница, 2000.

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

В результате анализа основных матричных операций линейной алгебры в ш формационно-вычислительных системах реального времени установлена целесооС разность разработки быстродействующих спецпроцессоров для параллельного р< шения систем линейных алгебраических уравнений высоких порядков и обращени матриц большой размерности. Определен комплекс системных требований к таки; спецпроцессорам по достижению быстродействия не ниже 103 MFLOP и цифрово точности вычислений; представлению данных в форме с плавающей запятой;; соч< танию параллельной обработки с параллельным вводом-выводом.

Предложены новые параллельные интерпретации методов Гаусса и Гаусс; Жордана для решения систем линейных алгебраических уравнений высоких поряд ков и обращения матриц большой размерности на основе внешнего произведет; векторов с улучшенными временными характеристиками. Их характерной oco6ei ностью является матричная форма представления входных, выходных и промеж) точных данных.

На основе методов разработана новая структурная организация параллельны спецпроцессоров, которая характеризуется повышением точности, структурного бь стродействия, многофункциональностью и в сочетании с оптоэлектронной реализ; цией дает, как минимум, на порядок выше быстродействие, чем известные, и доен гает потенциального значения 105 MFLOP при размерности 1000x1000. Это достип ется за счет способности многомерной архитектуры поддерживать максимальн возможный параллелизм вычислений, обеспечивая организацию разрядно-срезовог параллельного ввода-вывода и обработки матриц, а также за счет организации ка локальных, так и глобальных связей между процессорными элементами со способ ностью пересекаться без помех.

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

Рассмотрены два основных аспекта задачи оценивания структурной еффек--[вности параллельных спецпроцессоров для матричных задач линейной алгебры: эавнение эффективности разрядно-срезовых спецпроцессоров с традиционными груктурами подобных спецпроцессоров и сравнение различных структурных реше-ий разрядно-срезового спецпроцессора.

За частные критерии эффективности в соответствии с первым аспектом взяты зрактеристика ускорения решения задачи параллельной структурой по отношению последовательной и коэффициент загруженности аппаратуры. Ускорение разряд-э-срезового спецпроцессора растет в квадратической зависимости от размерности атриц, превышая лучшие известные показатели, как миниму, в 7 раз, а его другой ээффициент »1.

В соответствии со вторым аспектом показана целесообразность оценки струк-фной эффективности параллельных спецпроцессоров на основе частного критерия тределения быстродействия, отнесенного к значению задержки распространения тгалоп самых медленных базовых логических элементов. На основе обобщенного жтерия эффективности установлено, что эффективность спецпроцессора для ре-ения систем линейных уравнений и обращения матриц методом Гаусса-Жордана

1 основе внешнего произведения векторов в 2,6 раза больше, чем эффективность 1ецпроцессора, реализующего метод Гаусса.

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

Для подтверждения теоретических результатов исследования разработан про-1аммный комплекс для решения систем линейных алгебраических уравнений, )ифметических и других специальных преобразований с матрицами в соответствии предложенными параллельными алгоритмами вычислений, имитирующими про-:сс обработки информации в параллельном спецпроцессоре с плавающей запятой.

Исследованы аспекты технической реализации базовых узлов параллельного гецпроцессора для задач линейной алгебры на оптоэлектронной элементной базе, ценено быстродействие предложенной структурной организации параллельного гецпроцессора, реализованного на оптически-управляемых транспарантах, биста-щьных эталонах Фабри-Перо и элементах на квантово-размерных приборах ПЕВ-приборах).

Дальнейший путь исследований в области создания разрядно-срезовых спец-юцессоров для матричных задач линейной алгебры нацелен на решение физиче-их и технологических проблем, связанных с разработкой и созданием оптоэлек-онных трехмерных 3-0 интегральных схем.

Ключевые слова: обращение матриц, структурная организация, параллельный [ецпроцессор, метод Г аусса.