Структурна організація паралельних спецпроцесорів для матричних задач лінійної алгебри
Розробка паралельних методів обчислень, алгоритмів і структур швидкодіючих паралельних спецпроцесорів для матричних задач лінійної алгебри. Нові паралельні інтерпретації методів Гаусса і Гаусса-Жордана для розв'язання систем лінійних алгебраїчних рівнянь.
| Рубрика | Математика |
| Вид | автореферат |
| Язык | украинский |
| Дата добавления | 10.01.2014 |
| Размер файла | 100,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Вінницький державний технічний університет
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Спеціальність 05.13.13 - “Обчислювальні машини, системи та мережі”
структурна Організація паралельних спецпроцесорів для матричних задач лінійної алгебри
Шолота Владіслав Васильович
Вінниця 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 рік за рахунок коштів державного бюджету за узгодженням Міністерства освіти України.
Мета і задачі дослідження.
Метою дослідження є розробка паралельних методів обчислень, алгоритмів та структур швидкодіючих паралельних спецпроцесорів для матричних задач ЛА на основі принципів природного паралелізму цифрових оптичних обчислень.
Задачі дослідження:
Аналіз та систематизація концепцій та підходів до створення паралельних спецпроцесорів для матричних задач лінійної алгебри.
Модифікація прямих методів розв'язання СЛАР високих порядків та обернення матриць великої розмірності на основі природного паралелізму цифрових оптичних обчислень.
Розробка паралельних алгоритмів виконання базових матричних арифметичних операцій в формі з плаваючою комою.
Відображення модифікованих методів паралельного розв'язання СЛАР та обернення матриць на структурну організацію спецпроцесора.
Розробка цифрових паралельних структур для виконання матричних арифметичних операцій в формі з плаваючою комою.
Оцінювання ефективності варіантів структурної організації СП для паралельного розв'язання СЛАР та обернення матриць в залежності від розмірності матриць.
Проведення комп'ютерного моделювання модифікованих методів паралельного розв'язання СЛАР.
Дослідження аспектів технічної реалізації паралельного СП для матричних задач лінійної алгебри на оптоелектронній елементній базі.
Об`єкт дослідження - архітектура високопродуктивних обчислювальних систем для паралельної обробки великорозмірних матриць. Предмет дослідження - структурна організація обчислювальних систем для паралельного розв`язання матричних задач ЛА в реальному часі. Методи дослідження базуються на основних положеннях системного аналізу і теорії паралельної обробки інформації, теорії алгоритмів, теорії проектування обчислювальних систем і теорії цифрової оптичної обробки зображень.
Наукова новизна отриманих результатів:
Одержано нові паралельні інтерпретації методів Гаусса і Гаусса-Жордана для розв'язання СЛАР високих порядків та обернення великорозмірних матриць на основі обчислення зовнішнього добутку векторів за принципами багатовимірних цифрових обчислень, які відрізняються покращеними часовими характеристиками.
Вперше розроблено структурну організацію паралельних СП з плаваючою комою для матричних задач ЛА: для паралельного розв'язання СЛАР високих порядків та обернення великорозмірних матриць, які характеризуються підвищенням структурної швидкодії, багатофункціональністю та розширеною областю застосування. Це досягається за рахунок таких чинників: здатності багатовимірної структури підтримувати максимально можливий паралелізм обчислень, забезпечуючи організацію розрядно-зрізового введення-виведення та обробки матриць; введення до розгляду як локальних, так і глобальних зв'язків між ПЕ з властивістю перетинатись без перешкод.
Вперше запропоновано цифрові паралельні структури для матричної арифметики в формі з плаваючою комою: арифметичного суматора обробки матриць; поділювача вектора на число; обчислювача зовнішнього добутку векторів, які відрізняються покращеними часовими характеристиками, підвищеною точністю і розширеною областю застосування. Такі переваги отримано за рахунок використання розрядно-зрізового подання матриць в формі з плаваючою комою і цифрового часового інтегрування та відсутності залежності часових характеристик структур від розмірності матричних операндів.
Практичне значення одержаних результатів:
На підставі запропонованої паралельної інтерпретації методів Гаусса і Гаусса-Жордана створено принципово нові апаратно-орієнтовані паралельні алгоритми для матричних задач ЛА. Показано, що швидкодія запропонованих алгоритмів перевищує аналогічні показники відомих алгоритмів приблизно в 7 разів.
Запропоновані паралельні алгоритми та структурна організація паралельного СП для матричних операцій ЛА з плаваючою комою, реалізовані на оптоелектронній елементній базі, можуть бути використані в системах прикладної обробки і аналізу зображень та розпізнавання образів, реконструкції біомедичних зображень.
Запропоновано програмний комплекс для розв'язання матричних задач ЛА, який використовується при вивченні дисципліни “Комп'ютерне моделювання пристроїв і технологій в оптоелектроніці” у Вінницькому державному технічному університеті.
Впровадження результатів підтверджується відповідними актами.
Особистий внесок здобувача. Всі основні результати дисертаційної роботи отримані автором особисто. У публікаціях, написаних у співавторстві, здобувачеві належать: структурна організація та алгоритм роботи паралельного поділювача вектора на число в формі з плаваючою комою на основі принципів обробки за розрядними зрізами [3]; структурна організація та алгоритм роботи цифрового паралельного суматора обробки великорозмірних матриць в формі з плаваючою комою на основі принципів обробки за розрядними зрізами [4]; оцінка параметрів оптоелектронної реалізації вузлів паралельного процесора для множення знакозмінних матриць [5]; аналіз багаторівневої моделі паралельних інформаційно-обчислювальних засобів [6]; оптоелектронна реалізація базових вузлів логічної паралельної обробки матриць з покращеними характеристиками [7]; структурна організація та її оптоелектронна реалізація паралельного спецпроцесора для розв'язання СЛАР та обернення матриць за методом Гаусса на основі зовнішнього добутку векторів [8] і на основі паралельного перемножувача картин зображень [9].
Апробація результатів дисертації. Основні положення і наукові результати доповідались і обговорювались на: НТК з міжнародною участю “Приладобудування-95” (м. Львів, 1995); ІІІ Всеукраїнській міжнародній конференції “Обробка сигналів і зображень та розпізнавання образів” (УкрОбраз-96) (м. Київ, 1996), наукових семінарах інституту комп'ютерних технологій і комп'ютерних систем при Вінницькому державному технічному університеті.
Публікації. За матеріалами дисертації опубліковано 9 друкованих робіт, з яких 6 статей в наукових журналах, що входять до відповідного переліку ВАК України, 1 патент на винахід та 2 статті у збірниках праць.
Об'єм і структура дисертації. Дисертаційна робота складається з вступу, чотирьох розділів, загальних висновків, списку використаних джерел і 6 додатків. Загальний обсяг дисертації 165 сторінки, з яких основний зміст викладено на 141 аркушах друкованого тексту, 31 рисунків, 2 таблиці. Список використаних джерел нараховує 104 найменування. Повний обсяг дисертації 205 сторінки.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі розглянуто актуальність проблеми досліджень, зазначено зв`язок роботи з науковими програмами, темами. Обґрунтовано мету та задачі досліджень. Приведено характеристику наукової новизни та практичного значення одержаних результатів, а також описано їх апробацію, публікації та впровадження.
В першому розділі проведено аналіз основних матричних операцій ЛА в інформаційно-обчислювальних системах реального часу з метою встановлення базових операцій спецпроцесора паралельної обробки матриць.
Основна увага приділена методам та засобам реалізації операцій паралельного розв'язання СЛАР високих порядків та обернення великорозмірних матриць, оскільки ефективна реалізація інших паралельних операцій (наприклад, векторно-матричного множення, матрично-матричного множення) була детально пропрацьована попередниками. Проаналізовано ряд відомих прямих методів розв'язання СЛАР, основною причиною звернення до яких порівняно з непрямими методами стала фіксованість числа кроків обчислень, яка не залежить від типу даних і може бути визначена заздалегідь. Методи Гаусса і Гаусса-Жордана, як представники LU-методів для розв'язання СЛАР, що втричі швидші, ніж група QR-методів, визначені найпридатнішими для розпаралелювання обчислювальних процесів на СП.
Проведено аналітичний огляд обчислювальних структур для паралельного розв'язання СЛАР і обернення матриць, серед яких виявлено два перспективних напрямки розвитку паралельних СП. Перший напрямок пов'язаний з розвитком цифрових локально-зв'язаних систем (систолічних, хвильових, трансп'ютерних), орієнтованих на технологію НВІС. Другий напрямок пов'язаний з оптичною аналоговою і аналогово-цифровою обробкою, яка знімає обмеження швидкодії арсенід-галієвих НВІС, але має низьку точність.
На основі проведеного аналізу зроблено такі висновки.
Є доцільним розробка паралельного СП для матричних задач ЛА, який би задовольняв системним вимогам по забезпеченню: цифрової точності обчислень та представлення даних в формі з плаваючою комою; швидкодії на рівні 103 MFLOP; поєднання паралельної обробки з паралельним введенням-виведенням інформації; відсутності теоретичних обмежень на розмірність матриць.
Обробка даних на основі принципів природного паралелізму цифрових багатовимірних оптичних обчислень дозволить розробити паралельні математичні методи обчислень, алгоритми та структури швидкодіючих паралельних СП для матричних задач ЛА.
У другому розділі запропоновано нові паралельні інтерпретації методів Гаусса і Гаусса-Жордана для розв'язання СЛАР високих порядків та обернення великорозмірних матриць на основі зовнішнього добутку векторів (ЗДВ).
Необхідно розв'язати СЛАР, подану в матричній формі такого виду:
A·X=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.
Матричний комутатор МК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 рази ефективність СП за методом Гаусса.
В четвертому розділі з метою підтвердження теоретичних результатів дослідження розроблено програмний комплекс для розв`язання СЛАР, арифметичних та інших спеціальних перетворень над матрицями в відповідності до запропонованих паралельних алгоритмів обчислень, що імітують процес обробки інформації в паралельному СП з плаваючою комою. Даний програмний продукт використовується при вивченні дисципліни “Комп`ютерне моделювання пристроїв і технологій в оптоелектроніці” для моделювання паралельних оптоелектронних тривимірних структур паралельної обробки зображень, про що свідчить відповідний акт впровадження результатів дисертаційної роботи в учбовий процес.
Досліджено аспекти технічної реалізації базових вузлів паралельного СП для задач ЛА на оптоелектронній елементній базі. Оцінено швидкодію запропонованої структурної організації паралельного СП, реалізованої на оптично-керованих транспарантах, бістабільних еталонах Фабрі-Перо, елементах на SEED-пристроях, що дало змогу встановити значення потенційно досягненої швидкодії на рівні 105 MFLOP при практичних обмеженнях розмірності на рівні 10001000.
Доцільність розробленої структурної організації паралельних СП для матричних задач ЛА підтверджено актом впровадження результатів дисертаційної роботи в розробку структурної організації сопроцесора обробки матричної інформації для персональної ЕОМ, що працює в складі швидкодіючих систем обробки зображень і розпізнавання образів в реальному часі.
Зазначено подальший напрямок досліджень в області створення розрядно-зрізових СП для матричних задач ЛА - вирішення фізичних та технологічних проблем, пов`язаних з розробкою та створенням оптоелектронних тривимірних 3-D інтегральних схем.
ВИСНОВКИ
паралельний матричний лінійний алгебра
В дисертаційній роботі наведене теоретичне обґрунтування і нове вирішення наукової задачі підвищення швидкодії паралельних спецпроцесорів, що виявляється в застосуванні принципів природного паралелізму цифрових оптичних обчислень до синтезу більш ефективних структурних організацій паралельних спецпроцесорів для розв'язання матричних задач лінійної алгебри в високопродуктивних системах обробки зображень і сигналів. Зокрема, в дисертації отримано такі теоретичні та практичні результати.
Модифіковано методи Гаусса і Гаусса-Жордана для паралельного розв'язання СЛАР високих порядків та обернення великорозмірних матриць на основі обчислень зовнішнього добутку векторів за принципами багатовимірних цифрових оптичних обчислень та проведено їх комп'ютерне моделювання. Застосування розрядно-зрізового способу подання та обробки матриць в сукупності з цифровим часовим інтегруванням проміжних результатів дозволило отримати нові паралельні форми апаратно-орієнтованих алгоритмів Гаусса і Гаусса-Жордана, які характеризуються найвищим коефіцієнтом прискорення (N2) порівняно з відомими (N2/7), підвищенням точності обчислень та розширеною областю застосування завдяки використанню подання даних в формі з плаваючою комою.
На основі використання властивостей природного паралелізму оптичних цифрових обчислень запропоновано нові паралельні цифрові алгоритми операцій додавання знакозмінних матриць, ділення вектора на число, зовнішнього добутку векторів, поданих в формі з плаваючою комою, проведено їх комп'ютерне моделювання. Паралельні алгоритми дозволили підвищити точність подання і обробки великорозмірних даних в поєднанні із зростанням обчислювальної швидкодії. Їх особливістю є відсутність залежності часових характеристик від розмірності операндів.
Розроблено нову структурну організацію паралельних спецпроцесорів з плаваючою комою для матричних задач ЛА: для паралельного розв'язання СЛАР високих порядків та обернення великорозмірних матриць, які характеризуються суттєвим підвищенням коефіцієнта прискорення в поєднанні з підвищенням коефіцієнта завантаженості апаратури. Це досягається за рахунок таких чинників: здатності матричної архітектури підтримувати максимальний паралелізм методів обчислень, забезпечуючи організацію розрядно-зрізового введення-виведення та обробки матриць; наявності локальних і глобальних зв'язків між ПЕ з властивістю перетинатись без перешкод. Швидкодія розроблених спеціалізованих структур для задач ЛА зростає пропорційно збільшенню розмірності NN матриць, перевищуючи, як мінімум, на порядок швидкодію відомих аналогів. При оптоелектронній реалізації структур паралельних СП вона досягає потенційного значення 105 MFLOP, що дозволяє використовувати розроблені СП в високопродуктивних системах обробки зображень розмірністю NN = 10001000.
Запропоновано нові цифрові паралельні структури для матричної арифметики в формі з плаваючою комою: арифметичного суматора обробки матриць; поділювача вектора на число; обчислювача зовнішнього добутку векторів, які характеризується підвищеною точністю і розширеною областю застосування. Це досягнуто за рахунок використання розрядно-зрізового подання матриць в формі з плаваючою комою і цифрового часового інтегрування. Запропоновані структури підтримують максимальний паралелізм алгоритмів матричної обробки, властивий оптичним цифровим обчисленням, тим самим орієнтуючи схемотехнічні рішення розроблених СП на оптоелектронну елементну базу.
Виконано оцінювання структурної ефективності паралельних матричних СП на основі окремого критерію визначення швидкодії, віднесеної до величини затримки розповсюдження сигналів найповільніших базових паралельних елементів. На основі узагальненого критерію ефективності встановлено, що ефективність розрядно-зрізового СП для розв'язання СЛАР за паралельним методом Гаусса-Жордана на основі обчислення ЗДВ перевищує в 2,6 рази ефективність СП за паралельним методом Гаусса.
СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
Шолота В.В. Концепції та підходи до синтезу обчислювальних структур високопродуктивних процесорів для паралельного обернення матриць та розв'язання систем лінійних рівнянь // Вимірювальна та обчислювальна техніка в технологічних процесах (Технологічний університет Поділля, м.Хмельницький). - 1998. - №2. - С.84-90.
Шолота В.В. Високопродуктивний процесор для паралельного розв'язання систем лінійних рівнянь та обернення матриць // Вимірювальна та обчислювальна техніка в технологічних процесах (Технологічний університет Поділля, м.Хмельницький). - 1999. - №1. - С.86-91.
Кожем'яко В.П., Шолота В.В., Зволейко А.В. Паралельний поділювач вектора на число в формі з рухомою комою // Вісник Вінницького політехнічного інституту. - 1998. - №4. - С.56-61.
Кожем'яко В.П., Заболотна Н.І., Шолота В.В. Цифровий оптоелектронний суматор обробки матриць в формі з плаваючою комою // Вимірювальна та обчислювальна техніка в технологічних процесах (Технологічний університет Поділля, м.Хмельницький).- 1997.- №2.- С.136-142.
Заболотная Н.И., Шолота В.В. Организация параллельного перемножения знакопеременных матриц в цифровом оптоэлектронном процессоре многоуровневых изображений // Электронное моделирование (Институт проблем моделирования в энергетике НАНУ). - 1997. - Т.19., №5. - С.41-49.
Мартинюк Т.Б., Заболотна Н.І., Шолота В.В. Оцінювання структурно-інформаційної складності алгоритму паралельного додавання чисел // Вісник Вінницького політехнічного інституту. - 1996. - №3. - С.21-26.
Пат. 23431А Україна, МКІ G06F 15/66, G06E 1/04. Цифровий паралельний процесор багаторівневих зображень: Пат. 23431А Україна, МКІ G06F 15/66, G06E 1/04 / Кожем'яко В.П., Буда А.Г., Мартинюк Т.Б., Заболотна Н.І., Ліщинська Л.Б., Шолота В.В.- №96072786; Заявл. 11.07.96; Опубл. 31.08.98, Бюл. №4.- 6 с.
Кожем'яко В., Заболотна Н., Шолота В. Паралельні обчислювальні структури для розв'язку систем лінійних рівнянь та обернення матриць // Праці 3 Всеукраїнської конференції “Обробка сигналів і зображень та розпізнавання образів”. - Київ: Українська асоціація з оброблення інформації та розпізнавання образів. - 1996. - С.233-234.
Заболотна Н., Шолота В., Зволейко А. Реалізація обернення матриць на структурі паралельного перемножувача картин-зображень / Праці 3 Всеукраїнської конференції “Обробка сигналів і зображень та розпізнавання образів”. - Київ: Українська асоціація з оброблення інформації та розпізнавання образів. - 1996.- С.230_231.
Размещено на Allbest.ru
...Подобные документы
Вивчення теорії наближених обчислень і чисельних методів лінійної алгебри. Опис прямих і ітераційних методів вирішення систем лінійних рівнянь, алгоритмізація і точність наближених обчислень функції. Чисельна інтеграція звичайних диференціальних рівнянь.
лекция [103,6 K], добавлен 06.02.2014Основні поняття чисельних методів розв’язання систем лінійних алгебраїчних рівнянь. Алгоритм Гаусса зведення системи до східчастого виду послідовним застосуванням елементарних перетворень. Зворотній хід методу Жордана-Гаусса. Метод оберненої матриці.
курсовая работа [165,1 K], добавлен 18.06.2015Історія створення теорії алгебраїчних рівнянь. Сутність системи лінійних алгебраїчних рівнянь в лінійній алгебрі. Повна характеристика методів розв'язання рівнянь: точні, ітераційні та ймовірнісні. Особливості теорем Гауса-Жордана та Габріеля Крамера.
реферат [543,7 K], добавлен 23.04.2015Розв’язання систем лінійних рівнянь методом Жордана-Гауса. Еквівалентні перетворення системи, їх виконання як елемент методів розв’язування системи рівнянь. Базисні та вільні змінні. Лінійна та фундаментальна комбінації розв’язків, таблиці коефіцієнтів.
контрольная работа [170,2 K], добавлен 16.05.2010Вивчення методів розв'язання лінійної крайової задачі комбінуванням двох задач Коші. Переваги та недоліки інших методів: прицілювання, колокацій, Гальоркіна, найменших квадратів та ін. Пошук єдиного розв'язку звичайного диференціального рівняння.
курсовая работа [419,2 K], добавлен 29.08.2010Системи лінійних алгебраїчних рівнянь, головні означення. Коротка характеристика головних особливостей матричного способу, методу Жордано-Гаусса. Формули Крамера, теорема Кронекера-Капеллі. Практичний приклад розв’язання однорідної системи рівнянь.
курсовая работа [690,9 K], добавлен 25.04.2013Розв'язання системи лінійних рівнянь методом повного виключення змінних (метод Гаусса) з використанням розрахункових таблиць. Будування математичної моделі задачі лінійного програмування. Умови для застосування симплекс-методу. Розв'язка спряженої задачі.
практическая работа [42,3 K], добавлен 09.11.2009Огляд складання програми на мові програмування С++ для обчислення чотирьох лінійної системи рівнянь матричним методом. Обчислення алгебраїчних доповнень до елементів матриці. Аналіз ітераційних методів, заснованих на використанні повторюваного процесу.
практическая работа [422,7 K], добавлен 28.05.2012Прийоми розв’язання задач в першому і другому степені на Далекому Сході та Греції. Досягнення арабських математиків в області алгебраїчних рівнянь. Розв'язання похідного кубічного рівняння. Найвидатніші теореми про радикали вищих степенів, їх розв’язання.
курсовая работа [536,1 K], добавлен 23.02.2014Сумісність лінійних алгебраїчних рівнянь. Найвищий порядок відмінних від нуля мінорів матриці. Детермінант квадратної матриці. Фундаментальна система розв’язків та загальний розв'язок системи лінійних однорідних рівнянь. Приклади розв’язання завдань.
курсовая работа [86,0 K], добавлен 15.09.2008Чисельні методи розв’язання систем нелінійних рівнянь: лінійні і нелінійні рівняння, метод простих ітерацій, метод Ньютона. Практичне використання методів та особливості розв’язання систем нелінійних рівнянь у пакеті Mathcad, Excel та на мові С++.
курсовая работа [2,0 M], добавлен 30.11.2010Класичні та сучасні наближені методи розв'язання диференціальних рівнянь та їх систем. Класифікація наближених методів розв'язування. Розв'язування трансцендентних, алгебраїчних і диференціальних рівнянь, методи чисельного інтегрування і диференціювання.
отчет по практике [143,9 K], добавлен 02.03.2010Аналіз найвідоміших методів розв’язування звичайних диференціальних рівнянь і їх систем, користуючись рекомендованою літературою. Розробка відповідної схеми алгоритму. Розв’язання системи звичайних диференціальних рівнянь в за допомогою MathCAD.
лабораторная работа [412,4 K], добавлен 21.10.2014Визначення системи лінійних рівнянь та її розв’язання. Поняття рангу матриці, правило Крамера та види перетворень з матрицею. Способи знайдення оберненої матриці А–1 до невиродженої матриці А. Контрольні запитання та приклади розв’язування задач.
задача [73,5 K], добавлен 25.03.2011Класифікація та типи чисельних методів розв’язування систем лінійних рівнянь і обернення звернення матриць точні, ітераційні та комбіновані. Їх порівняльна характеристика та умови використання в окремих випадках. Вектори та операції над ними, норми.
презентация [85,6 K], добавлен 06.02.2014Застосування систем рівнянь хемотаксису в математичній біології. Виведення системи визначальних рівнянь, розв'язання отриманої системи визначальних рівнянь (симетрій Лі). Побудова анзаців максимальних алгебр інваріантності математичної моделі хемотаксису.
дипломная работа [1,9 M], добавлен 09.09.2012Метод простої ітерації Якобі і метод Зейделя. Необхідна і достатня умова збіжності методу простої ітерації для розв’язання системи лінейних рівнянь. Оцінка похибки. Діагональне домінування матриці як умова збіжності ітерації. Основні переваги цих методів.
презентация [79,9 K], добавлен 06.02.2014Теоретичні матеріали щодо визначення методів дослідження лінійної залежності та незалежності функцій, проведення дослідження лінійної залежності систем функцій однієї змінної за визначенням і з використанням визначників матриць Вронського та Грама.
курсовая работа [235,2 K], добавлен 15.06.2013Означення спільного перпендикуляра до двох мимобіжних прямих, відстані між ними. Методика обчислення відстані між діагоналями несуміжних граней куба; діагоналлю основи та несуміжним до неї бічним ребром. Побудова паралельних та перпендикулярних площин.
презентация [149,5 K], добавлен 25.10.2014Системи лінійних рівнянь з двома змінними з параметром. Тригонометричні рівняння та системи тригонометричних рівнянь з параметрами. Лінійні та квадратні нерівності. Застосування графічних методів паралельного переносу в розв’язанні задач з параметрами.
дипломная работа [1,3 M], добавлен 16.06.2013
