Вінницький державний технічний університет

Шолота Владіслав Васильович

УДК 681.325.5

структурна Організація паралельних

спецпроцесорів для матричних задач

лінійної алгебри

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

аВтореферат

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

кандидата технічних наук

Вінниця 2000

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

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

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

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

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

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

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

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

Автореферат розісланий “ 31 ” жовтня 2000 р.

Вчений секретар

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

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

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

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

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

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

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

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

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

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

1.

2.

3.

4.

5.

6.

7.

8.

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

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

1.

2.

3.

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

1.

2.

3.

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

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

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

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

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

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

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

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

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

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

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

1.

2.

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

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

AX=B, (1)

де A – квадратна невироджена матриця коефіцієнтів розмірністю NN;

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

B – матриця векторів вільних членів розмірністю NN.

Матриці X і B обрані квадратними, вважаючи на можливість застосування запропонованих паралельних методів як для розв’язання СЛАР (X=[x(1), x(2),…, x(N)]), так і для пошуку оберненої A-1 матриці (B=E, де Е – квадратна одинична матриця).

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

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

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

(2)

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

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

(3)

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

R(t)[1:N;1:2N]=1(R(t)[1:N;1:2N]). d(t)[1:N;1:2N], (4)

де 1(R).d - оператор паралельного зсуву інформації, записаної в масиві R, вгору на один елемент з паралельним записом на вільне місце вектор-рядка d.

Сформуємо зовнішній добуток () вектор-рядка d(t) і вектор-стовпця v(t)[1:N;1], виділеного як перший стовпець матриці А(t-1),

v(t)[1:N;1]=А(t-1)[1:N;1], (5)

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

P(t)[1:N;1:2N]= v(t)[1:N;1]d(t)[1;1:2N], (6)

де p(t)[I;J]= v(t)[I,1]d(t)[1,J], ().

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

A(t)=1(1(A(t-1)-P(t)[1:N;1: N])), (7)

B(t)=1(B(t-1)-P(t)[1:N;(N+1):2N]), (8)

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

Отже, на t=N-му кроці прямого ходу отримаємо нулі в матрицях A і B та проміжний результат в матриці R, який для незалежних обчислень на прямому та зворотному ходах методу перезапишемо в масиви X1 і X2 в такій формі:

(9)

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

На кожному t=(N+i)-му кроці обчислень (і-номер кроку зворотного ходу, ) сформуємо матрицю PX як зовнішній добуток () векторів

PX(t)[1:N;1:N]=dx(t)[1:N;1]vx(t)[1;1:N], (10)

де вектор-рядок vx(t)[1;1:N] визначимо як (N-i)-й рядок матриці X2(t)

vx(t)[1;1:N]=X2(t)[(N-i);1:N], (11)

а вектор-стовпець dx(t)[1:N;1] утворимо за елементами неголовної діагоналі перетвореної матриці XM(t)[1:N;1:N]

dx(t)[k;1]=XM(t)[k;(N-k+1)], (). (12)

Матрицю XM(t) сформуємо в результаті логічного множення () матриці X1(t) і специфічної матриці М[1:N;1:N] з одиничними елементами за виключенням першого стовпця

. (13)

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

X2(t=N+i)= X2(t-1)-PX(t), (14)

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

X[1:N;1:N]=X2(t=2N-1)[1:N;1:N]. (15)

При цьому

. (16)

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

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

R(t=0)[1:N;1:N]=A, R(t=0)[1:N;(N+1):2N]=B. (17)

За ведучий елемент на кожному t-му кроці обчислень обрано елемент r[t,t]0 матриці R.

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

(18)

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

v(t)[1:N;1]= R(t-1)[1:N;t], (19)

де v(t)[t;1]=-1, сформуємо ЗДВ в вигляді матриці P за формулою (6).

Тоді процес формування проміжного результату R в часі опи-сується таким матричним співвідношенням:

R(t)=(R(t-1)MR(t))- P(t), (20)

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

MR(t) – специфічна бінарна матриця розмірності N2N елементів, будь-який елемент mr[i,j] якої дорівнює 0 при i=t і дорівнює 1 в інших випадках (j=);

P(t) – зовнішній добуток векторів.

Кінцевий результат визначається на останньому t=N-му кроці обчислень в виді

X[1:N;1:N]=R(t=N)[1:N;(N+1):2N]. (21)

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

Встановлено базові матричні операції запропонованих паралельних методів Гаусса і Гаусса-Жордана і на основі застосування принципів розрядно-зрізової обробки і цифрового часового інтегрування розроблено нові паралельні алгоритми їх виконання, а саме: паралельний алгоритм додавання знакозмінних матриць; паралельний алгоритм ділення вектора на число; паралельний алгоритм обчислення ЗДВ.

Зазначені алгоритми наділені високою точністю обчислень за рахунок використання подання і обробки знакозмінних NN–вимірних матриць операндів та матриць результату в формі з плаваючою комою в прямому коді у вигляді наборів із S=(M+P+2) бінарних розрядних зрізів (РЗ), що мають розмірність відповідних матриць. Наприклад, маємо таке подання першого операнду – матриці A:

, (22)

де SgmA=0 і A(mA) – знаковий і інформаційні РЗ мантиси матриці A;

SgpA=M+1 і A(pA) – знаковий і інформаційні РЗ порядку матриці A;

mA і pA – порядкові номери РЗ просторових кодів мантиси і порядку матриці A;

M і P – число інформаційних РЗ мантис і порядків матриць A і B.

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

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

(23)

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

. (24)

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

ТГ =(2N-1)·(2M2+MP+14M+8P+29), (25)

ТГ =ТГ-Ж =ТГ-Ж =N·(2M2+MP+14M+8P+28). (26)

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

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

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

Початкові дані в вигляді матриць A, B та E, поданих в формі з плаваючою комою відповідно до вигляду (22) за наборами S бінарних РЗ, поступають з паралельних входів СП через паралельні матричні комутатори МК1 і МК4 і паралельний регістр РгЕ на перші S та другі S паралельні двовимірні NN входи цифрового матричного накопичуванльного суматора НСм, який працює в режимі паралельного запису. За допомогою матричного комутатора МК2 формується вектор діленого, який поступає на S перші та S другі Nканальні входи діленого поділювача ПОД.

Перші S і другі S N-канальні входи дільника поділювача ПОД з’єднані із S першими і S другими N-канальними виходами матричного комутатора МК3, який в кожний t-й момент часу обирає відповідно t-й елемент у рядку, який визначив комутатор МК2. Інформація на паралельні входи комутатора МК2 поступає з відповідних паралельних виходів суматора НСм.

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

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

Виділені вектор-рядок і вектор-стовпець, поступаючи на перші S та другі S паралельні N–канальні рядкові входи і S паралельні N–канальні стовпцеві входи блоку ЗДВ, утворюють на його перших S та других S NN вимірних виходах розширену матрицю відповідно до виразу (6). Проінвертувавши знаковий РЗ утвореного ЗДВ, виконаємо його алгебраїчне додавання з попередньою інформацією, записаною в НСм, обнуливши перед цим його t-й рядок відповідно до виразу (20) за допомогою схеми матричного кон’юнктора і вмісту двовимірного регістру специфічної матриці Ф1.

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

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

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

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

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

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

, (27)

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

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

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

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

, (28)

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

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

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

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

, (29)

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

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

, (30)

. (31)

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

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

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

[MFLOP/ум. вузол]. (32)

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

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

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

Досліджено аспекти технічної реалізації базових вузлів паралельного СП для задач ЛА на оптоелектронній елементній базі. Оцінено швидкодію запропонованої структурної організації паралельного СП, реалізованої на оптично-керованих транспарантах, бістабільних еталонах Фабрі-Перо, елементах на SEED-пристроях, що дало змогу встановити значення потенційно досягненої швидкодії на рівні 105 MFLOP при практичних обмеженнях розмірності на рівні 10001000.

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

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

висновки

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

1.

2.

3.

4.

5.

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

анотації

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

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

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

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

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

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

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

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

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

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

The new parallel interpretation of methods of Gaussa and Gaussa_Jordana are offered. These methods are used for solution of high order system of the liner algebra and matrix inversion. They on external vector’s multiplication are based. This New parallel interpretation improves better temporary characteristic.

The new structure organization of parallel processors is designed on base of new parallel interpretation of methods. The potential performance of this processors is 105 MFLOP with dimension 10001000. There are possible with optoelectronic realization.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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