Концепції та підходи до побудови спецпроцесорів для ітераційного розв’язання систем лінійних алгебраїчних рівнянь

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2008
Hauptverfasser:	Заболотна, Н.І., Мусійчук, І.В., Костюк, С.В.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України 2008
Schriftenreihe:	Оптико-електронні інформаційно-енергетичні технології
Schlagworte:	Методи та системи оптико-електронної і цифрової обробки зображень та сигналів
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/32176
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Концепції та підходи до побудови спецпроцесорів для ітераційного розв’язання систем лінійних алгебраїчних рівнянь / Н.І. Заболотна, І.В. Мусійчук, С.В. Костюк // Оптико-електронні інформаційно-енергетичні технології. — 2008. — № 2 (16). — С. 34-41. — Бібліогр.: 23 назв. — укp.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-32176
record_format	dspace
spelling	irk-123456789-321762012-04-14T12:11:35Z Концепції та підходи до побудови спецпроцесорів для ітераційного розв’язання систем лінійних алгебраїчних рівнянь Заболотна, Н.І. Мусійчук, І.В. Костюк, С.В. Методи та системи оптико-електронної і цифрової обробки зображень та сигналів Досліджено концепцію та підходи до побудови обчислювальних структур, що спеціалізуються на розв'язанні систем лінійних алгебричних рівнянь за допомогою ітераційних методів. Зроблено порівняння основних характеристик висвітлених структур. The article is devoted to an opportunity research of concepts and ways for construction special processors for the iteratic solving of the systems of the linear algebraic equations. It is made the comparation of the main characteristics of the shown structures. 2008 Article Концепції та підходи до побудови спецпроцесорів для ітераційного розв’язання систем лінійних алгебраїчних рівнянь / Н.І. Заболотна, І.В. Мусійчук, С.В. Костюк // Оптико-електронні інформаційно-енергетичні технології. — 2008. — № 2 (16). — С. 34-41. — Бібліогр.: 23 назв. — укp. 1681-7893 http://dspace.nbuv.gov.ua/handle/123456789/32176 681.325.2 uk Оптико-електронні інформаційно-енергетичні технології Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Методи та системи оптико-електронної і цифрової обробки зображень та сигналів Методи та системи оптико-електронної і цифрової обробки зображень та сигналів
spellingShingle	Методи та системи оптико-електронної і цифрової обробки зображень та сигналів Методи та системи оптико-електронної і цифрової обробки зображень та сигналів Заболотна, Н.І. Мусійчук, І.В. Костюк, С.В. Концепції та підходи до побудови спецпроцесорів для ітераційного розв’язання систем лінійних алгебраїчних рівнянь Оптико-електронні інформаційно-енергетичні технології
description	Досліджено концепцію та підходи до побудови обчислювальних структур, що спеціалізуються на розв'язанні систем лінійних алгебричних рівнянь за допомогою ітераційних методів. Зроблено порівняння основних характеристик висвітлених структур.
format	Article
author	Заболотна, Н.І. Мусійчук, І.В. Костюк, С.В.
author_facet	Заболотна, Н.І. Мусійчук, І.В. Костюк, С.В.
author_sort	Заболотна, Н.І.
title	Концепції та підходи до побудови спецпроцесорів для ітераційного розв’язання систем лінійних алгебраїчних рівнянь
title_short	Концепції та підходи до побудови спецпроцесорів для ітераційного розв’язання систем лінійних алгебраїчних рівнянь
title_full	Концепції та підходи до побудови спецпроцесорів для ітераційного розв’язання систем лінійних алгебраїчних рівнянь
title_fullStr	Концепції та підходи до побудови спецпроцесорів для ітераційного розв’язання систем лінійних алгебраїчних рівнянь
title_full_unstemmed	Концепції та підходи до побудови спецпроцесорів для ітераційного розв’язання систем лінійних алгебраїчних рівнянь
title_sort	концепції та підходи до побудови спецпроцесорів для ітераційного розв’язання систем лінійних алгебраїчних рівнянь
publisher	Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України
publishDate	2008
topic_facet	Методи та системи оптико-електронної і цифрової обробки зображень та сигналів
url	http://dspace.nbuv.gov.ua/handle/123456789/32176
citation_txt	Концепції та підходи до побудови спецпроцесорів для ітераційного розв’язання систем лінійних алгебраїчних рівнянь / Н.І. Заболотна, І.В. Мусійчук, С.В. Костюк // Оптико-електронні інформаційно-енергетичні технології. — 2008. — № 2 (16). — С. 34-41. — Бібліогр.: 23 назв. — укp.
series	Оптико-електронні інформаційно-енергетичні технології
work_keys_str_mv	AT zabolotnaní koncepcíítapídhodidopobudovispecprocesorívdlâíteracíjnogorozvâzannâsistemlíníjnihalgebraíčnihrívnânʹ AT musíjčukív koncepcíítapídhodidopobudovispecprocesorívdlâíteracíjnogorozvâzannâsistemlíníjnihalgebraíčnihrívnânʹ AT kostûksv koncepcíítapídhodidopobudovispecprocesorívdlâíteracíjnogorozvâzannâsistemlíníjnihalgebraíčnihrívnânʹ
first_indexed	2025-07-03T12:42:26Z
last_indexed	2025-07-03T12:42:26Z
_version_	1836629672180318208
fulltext	5 УДК 681.325.2 Н.І. ЗАБОЛОТНА, І.В. МУСІЙЧУК, С.В. КОСТЮК КОНЦЕПЦІЇ ТА ПІДХОДИ ДО ПОБУДОВИ СПЕЦПРОЦЕСОРІВ ДЛЯ ІТЕРАЦІЙНОГО РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ Вінницький національний технічний університет, Хмельницьке шосе, 95, м. Вінниця, Україна, E-mail: svk@vstu.vinnica.ua Анотація. Стаття присвячена дослідженню концепцій та підходів до побудови обчислювальних структур, що спеціалізуються на розв’язанні систем лінійних алгебраїчних рівнянь ітераційними методами. Зроблене порівняння основних характеристик висвітлених структур. Аннотация. Статья посвящена исследованию концепций и подходов к построению вычислительных структур для решения систем линейных алгебраических уравнений итерационными методами. Приведено сравнение основных характеристик структур. Abstract. The article is devoted to an opportunity research of concepts and ways for construction special processors for the iteratic solving of the systems of the linear algebraic equations. It is made the comparation of the main characteristics of the shown structures. Ключеві слова: обчислювальні структури, системи лінійних алгебраїчних рівнянь, ітераційні методи. ВСТУП Досягнення сучасної елементної бази відкрило нові можливості для розвитку високопродуктивних обчислювальних систем. Це досягається завдяки розпаралелюванню обчислювального процесу. Збільшення обчислювальної потужності мотивується в основному числовими моделюваннями складних систем для таких прикладних областей, як: передбачення погоди, клімату, та глобальних змін в атмосфері; структурна біологія; генетика людини; астрономія; розпізнавання та синтез мови; розпізнавання зображень. Незважаючи на належність названих задач до різних предметних областей і розходження в прийнятих способах опису явищ і термінологій, методи розв’язання їх на ЕОМ подібні [1-6]. Необхідними, як правило, є алгоритми формування матриць спеціального виду, об’єднання, переформування матриць і виконання певного набору алгебраїчних операцій, зокрема, розв’язання систем лінійних алгебраїчних рівнянь(СЛАР). Тому розробка високопродуктивних спеціалізованих процесорів для розв’язання матричних задач лінійної алгебри, зокрема, розв’язання СЛАР високих порядків в реальному часі, є актуальною. ОГЛЯД ОБЧИСЛЮВАЛЬНИХ СТРУКТУР ДЛЯ ІТЕРАЦІЙНОГО РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ Розв’язання систем лінійних алгебраїчних рівнянь (СЛАР) покладено в основу використання математичних моделей в різних областях науки і техніки [7]. Для цього використовуються не тільки прямі, але й ітераційні паралельні методи та алгоритми, які на перший погляд є суттєво послідовними. Відомо багато пристроїв та обчислювальних структур, що можуть бути використані або ж прямо призначені для розв’язання СЛАР ітераційними методами. Головною привабливою особливістю цих методів [8, 9] є можливість зведення всього обчислювального процесу до послідовності порівняно простих дій (ітераційних кроків), що повторюються, які представляють собою множення матриці на вектор або матриці на матрицю. Суть ітераційних методів полягає в тому, що рішення системи © Н.І. ЗАБОЛОТНА, І.В. МУСІЙЧУК, С.В. КОСТЮК, 2008 ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО- ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ 6 fAx = , (1) знаходиться як границя послідовних наближень x (n) при n→∞, де n −номер ітерації. Застосування ітераційних методів вимагає завдання початкового значення невідомих х(0) і точності обчислень εεεε>0. Обчислення проводяться до тих пір, поки не буде виконана оцінка еxx (n) <− . (2) Основна перевага ітераційних методів полягає в тому, що точність шуканого рішення задається. Число ітерацій n=n(ε), яке необхідно виконати для отримання заданої точності ε, є основною оцінкою якості методу. За цим числом проводиться порівняння різних методів за часовими характеристиками. Головним недоліком цих методів є те, що питання збіжності ітераційного процесу вимагає окремого дослідження. Доведені в даний час теореми про збіжність ітераційних методів мають місце для систем, на матриці яких накладені обмеження. Прикладом звичайних ітераційних методів можуть служити метод Якобі (метод простих ітерацій), метод Зейделя, метод верхніх релаксацій. До особливого класу ітераційних методів слід віднести варіаційні ітераційні методи: метод мінімальної нев'язності, метод швидкого спуску і т.д. Ітераційні методи також діляться на однокрокові, коли для визначення рішення на (j+1)-ій ітерації використовуються значення рішення, знайдені на j-й ітерації, і багатокрокові, коли для визначення рішення на( j+1)--ій ітерації використовується декілька попередніх ітерацій. Серед відомих ітераційних методів розв’язання СЛАР, які добре підлягають розпаралелюванню, слід виділити метод Якобі (простої ітерації) [10, 11], за яким розв’язання СЛАР (1) m-го порядку здійснюється за формулою i jjj m k i kjkj i j xaxafx +      −= ∑ = + 1 1 (3) За методом Якобі побудовано досить багато пристроїв, які певним чином намагаються розпаралелити процес розв’язання СЛАР. Так, наприклад, відомий пристрій для розв’язання СЛАР методом Якобі (рис. 1), що запропонований в роботі [12] і містить n блоків 1 обчислень, де n – порядок СЛАР, входи 2 матриці коефіцієнтів СЛАР пристрою, вхід 3 вільних членів СЛАР пристрою, блок 4 аналіза, блок 5 синхронізації та блок 6 формування імпульсів. Недоліком зазначеного пристрою є значне збільшення часу виконання однієї ітерації за рахунок додавання затримок на кожному n блоків обчислень. Рис. 1. Схема пристрою для розв’язання СЛАР методом Якобі Існують ітераційні методи, що володіють кращою швидкістю збіжності, ніж методи Якобі. У цих методах при обчисленні (i+1)-ої ітерації 1+i jx компоненти вектора рішення використовуються, знайдені (i+1)-і ітерації компоненти рішення з номерами 1+i lx l=1,2,...,j-1. Найбільш поширеним методом подібного ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО- ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ 7 типу є метод Зейделя. Загальна формула має вигляд i k m jk jj jki k j k jj jk j i j x a a x a a fx ∑∑ += − = + −−= 1 1 1 1 . (4) Прикладом апаратної реалізації розв’язання СЛАР методом Зейделя може слугувати пристрій, представлений в [13] (рис. 2), що виконує поставлену задачу, використовуючи конвеєрний тип паралелізації. Однак загальна синхронізація не дозволяє отримати високу швидкодію пристрою, а також використання аналогових елементів не дає необхідної точності. Пристрій містить входи 1 коефіцієнтів СЛАР пристрою, вхід 2 вільних членів СЛАР пристрою, вхід 3 значень точності розв’язання пристрою, вхід 4 синхронізації пристрою, n операційних блоків 5, регістр 6, блок 7 аналізу, виходи 8 результату розв’язання пристрою і виходи 9 ознаки закінчення розв’язання пристрою. Рис. 2. Схема пристрою для розв’язання СЛАР методом Зейделя Представлені вище структури мають ряд недоліків, оскільки не відповідають вимогам до точності та часу виконання задача розв’язання СЛАР. А отже виникає необхідність розробки відповідних спеціалізованих обчислювальних структур, що поєднують в собі високу продуктивність і точність з низькими енергоспоживанням і габаритними показниками. Саме до таких структур можна віднести основані на перевагах використання НВІС систолічні масиви (СМ). Їх основними властивостями є: конвеєрність і розпаралелювання обчислень, локальність і регулярність зв’язків, однотипність процесорних елементів (ПЕ), введення-виведення тільки через граничні ПЕ і багатократне використання кожного елемента даних [14, 15]. Відомо класичний лінійний СМ для матрично-векторного множення з зустрічними потоками даних [14], в основу роботи якого покладено розв’язання СЛАР методом Якобі, в якому використовується вже не N, а (2N-1) ПЕ множення з додаванням (де n – розмір матриці системи), однак даний систолічний масив не дозволяє зменшити час реалізації К ітераційних кроків нижче значення KNTc 2min = . Підвищення ефективності використання обладнання у два рази запропоновано в іншому СМ, представленому в роботі [16]. Це досягається при аналогічному часі розв’язання однієї СЛАР за рахунок ущільнення потоку вхідних даних при двозадачному режимі роботи. Зменшення часу виконання К ітераційних кроків до значення ( )1+= NKTF , а також досягнення близької до одиниці (в однозадачному режимі) завантаженості ПЕ стає можливим у випадку лінійного СМ [17] з N ПЕ при умові фіксації в пам’яті кожного із них однієї із компонент вектора невідомих 1−k x (рис. 3). Проте це пов’язано із появою глобального міжпроцесорного зв’язку, що потрібний для передачі вказаних компонент, обчислених на k-му кроці (k=1,2,...,К), з виходу масиву на вхід будь-якого ПЕ. Схема містить n блоків 1 обчислень, де n – порядок СЛАР, блок 2 підсумовування, n входів 3 коефіцієнтів СЛАР пристрою, вхід 4 вільних членів СЛАР пристрою, блок 5 аналіза, блок 6 синхронізації, перший 7 і другий 8 елементи затримки. ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО- ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ 8 1 1 12 7 5 8 6 4 3 3 „0” „0” „0” Рис. 3. Схема систолічного пристрою для розв’язання СЛАР методом Гаусса-Зейделя В роботі [18] запропонований лінійний СМ з повністю локальними зв’язками, що вирішує проблему попереднього СМ зниження робочої частоти і ускладнення нарощування обчислювальної потужності через використання глобального міжпроцесорного зв’язку. Час розв’язання СЛАР на ньому складає ( ).5+= KNTL Серйозним недоліком вказаного розв’язання, яке є синтезованим на основі оптимізації погодженого виконання сусідніх кроків, є надмірна кількість ПЕ рівна 3N-1, які використовуються досить неефективно з коефіцієнтом завантаженості близьким до 1/3. Також відомий підхід до архітектурного проектування СМ за формальними описами обчислювальних алгоритмів [18, 19] таким чином, що початковий алгоритм представляється у вигляді решітчатого функціонального графа (РФГ). З врахуванням умови локальності зв’язків в результуючих СМ безпосередній алгоритм обчислення матрично-векторного множення, до якого зводиться довільний крок ітераційного процеса описується в [18] найпростішим плоским РФГ з NN × вершинами (функціональними операторами), координати дуг між якими утворюють ортонормований базис, причому кожна вершина інтерпретується як множення з додаванням. Таким чином, у синтезованому в [18] лінійному СМ, не вдаючись до яких-небудь глобальних міжпроцесорних зв'язків і обмежуючи застосуванням лише N помножувачів і N суматорів, при майже повній завантаженості апаратури мінімізовано час виконання К ітераційних кроків до значення )1( += KNTG тактів. Однак, можна синтезувати СМ з кільцевидною структурою зв’язків, що зможе виконувати весь ітераційний процес за час 2/)2( += KNTR тактів, дозволяючи тим самим практично в два рази збільшити продуктивність обчислень в порівнянні з попереднім. Розглянуті дотепер СМ виконують пошук розв’язку СЛАР з одним вектором b вільних членів. У той же час у ряді випадків доводиться вирішувати СЛАР більш загального виду ВАХ = , (5) тобто з однією і тією же матрицею коефіцієнтів А, але з М різними векторами невідомих ix , кожний з яких відповідає векторові bі вільних членів, причому [ ] [ ] Miii ,...,2,1,, === bBxX . Система (5), у свою чергу, породжує ітераційний процес [ ] ,,...,2,1,,1 Mii kk ==+= − fFFPXX (6) який зводиться до послідовності вже не матрично-векторних, а матрично-матричних множень. Перехід до використання операції множення двох матриць у якості базової дозволяє перейти до реалізації ітераційних алгоритмів на основі двовимірних СМ, оскільки саме вони забезпечують максимально доцільне розпаралелювання обчислень у систолічному режимі і тим самим – досягнення надвисокої продуктивності. Разом з тим відомі проекти таких СМ [15, 20, 21] не забезпечують ефективної завантаженості обчислювального ресурсу при реалізації процесу (6). Наприклад, класичний прямокутний CM [15], що обчислює добуток послідовності матриць і містить )12( −NM ПЕ множення з додаванням, витрачає на реалізацію К ітераційних кроків час 3)1(20 −++= MKNT такти, тобто працює з ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО- ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ 9 низьким коефіцієнтом використання ПЕ 4/10 =η . Інший прямокутний СМ [21], спроектований вже з урахуванням погодженого виконання сусідніх кроків, дозволяє зменшити час реалізації алгоритму до значення 4)5( +++= MNKTS , але при цьому містить )13( −NM ПЕ, приблизно 1/3 з яких в кожному такті вимушені виконувати два множення і два додавання. У результаті коефіцієнт використання ПЕ, як і раніше, близький до 1/4. Така двовимірна структурна схема зображена на рис. 4. Тут 1С - лінійний СМ зі зворотнім зв’язком. Отже, структурні схеми двовимірних СМ, що містять по N 2 ПЕ множення з додаванням, реалізують К кроків процесу (6) за час ( ) ( )   >++ ≤+ = ,,1 ,,2 NMякщоNKM NМякщоKN TT (7) де М – кількість векторів невідомих xi; N – розмірність матриці. k x1 k x2 k Mx Рис. 4. Двовимірний систолічний масив Час (7) враховує фазу надходження елементів матриці Р у відповідні ПЕ. В результаті, на відміну від описаних раніше рішень-аналогів [21, 27], синтезовані СМ у сталому режимі дозволяють досягти повної завантаженості ПЕ за умови, що NM ≥ . Але навіть при 2/NM = маємо 2/1≈ T η , і тільки при 4/NM = коефіцієнт використання ПЕ знижується до значення 4/1≈ T η , що характерно для аналогів. Перехід до використання операції множення двох матриць у якості базової дозволяє реалізувати ітераційні алгоритми рішення СЛАР на основі двовимірних систолічних масивів, оскільки вони забезпечують максимально доцільне розпаралелювання обчислень у систолічному режимі і тим самим забезпечують досягнення надвисокої продуктивності. Для їхнього синтезу можна використовувати або об'єднання отриманих раніше лінійних масивів, або синтезувати нові структурні схеми. Перший із зазначених підходів дає можливість зберегти всі переваги лінійних систолічних структур, але разом з тим приводить до залежності кількості процесорних елементів у структурі від числа векторів правих частин розв'язуваної СЛАР. Другий підхід дозволяє усунути вказаний недолік, проте для нього характерна залежність ефективності використання процесорних елементів від співвідношення розмірів розв'язуваної СЛАР. Серед пристроїв, в яких суттєве прискорення процесу обробки інформації досягається за рахунок реалізації принципу розпаралелювання алгоритмів обчислень слід виділити високопродуктивний спеціалозований процесор для розв’язання СЛАР з теплицевими матрицями. В роботі [22] запропоновано спосіб апаратної реалізації паралельного алгоритму розв’язання СЛАР з матрицями типу теплицевих (на діагоналях, паралельних головній, розміщені рівні елементи [23]) основаної на модифікованому ітераційному методі Гаусса-Зейделя. Системи рівнянь з теплицевими матрицями зустрічаються часто при розв’язуванні краєвих задач з диференційними рівняннями в частинних похідних [24]. Один із можливих відомих шляхів ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО- ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ 10 прискорення обчислення лежить у виборі або побудові ефективного, основаного на принципі паралелізму алгоритму обчислення апаратними засобами, що містять додаткове обладнання, яке виключає проміжні пересилання та спрощує функції місцевого керування. В роботі розглядається блочний варіант алгоритму розв’язання СЛАР, для реалізації якого пропонується спеціальний обчислювальний пристрій з регістрово-табличною структурою, що допускає блочно-паралельну обробку інформації. Функціональна схема блочного пристрою показана на рис. 5. Продуктивність пристрою, побудованого на такій основі і описаного в [22], суттєво залежить від тривалості операції зчитування числової інформації з блоку частинних сум, часу роботи суматорів обох рівнів та запису інформації в регістри. У випадку застосування в пристрої емітерно-зв’язаної логіки час одної ітерації невідомої компоненти розв’язання СЛАР, при N=100-1000 не буде перевищувати декількох десятків наносекунд. При вирішенні даної системи на високопродуктивній універсальній ЕОМ з матричним процесором наприклад, ЕС2700, призначеним для роботи з великими масивами час виконання однієї ітерації буде обчислюватися в мілісекундах, оскільки час виконання лише однієї операції множення векторів розмірністю 10 складе 3,6 мс. [22]. Рис. 5. Функціональна схема блочного пристрою для розв’язання СЛАР Отже, загальний порівняльний аналіз описаних вище структур можна побачити в табл. 1. Таблиця 1. Порівняльна таблиця структур для розв’язання СЛАР паралельними методами Тип структури Прискорення паралельного алгоритму S T T i i = 0 Час виконання алгоритму (в кількості тактів базової операції) Ті Коефіцієнт апаратурної завантаженоті ηi iS P = Літ- ра КЛСМ 2 1 N S = KNT 21 = 4 1 24 1 ≈ − = N N η [14] ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО- ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ 11 КЛСМУПД 2 2 N S ≈ KNT 22 = 2 1 2 ≤η [16] СМФВН 1 2 3 + ≈ N N S ( )13 += NKT 1 1 3 ≈ + = N N η [17] ЛСМЛЗ 5 4 + ⋅ ≈ K KN S ( )54 += KNT ( )( ) 3 1 135 4 < −+ ⋅ = NK KN η [18] КПСМ 3)1(2 2 5 −++ ⋅⋅ ≈ MKN MKN S 3-M1)2N(K5 ++=T 4 1 5 ≈η [19] СПМТТ 00017 ≈S .5.01.07 нсT −≈ - [24] В таблиці використані такі скорочення: КЛСМ - класичний лінійний СМ із зустрічними потоками даних для векторно-матричного помноження; КЛСМУПД - класичний лінійний СМ для векторно-матричного помноження із зустрічними потоками даних з ущільненим потоком даних; СМФВН - СМ для векторно-матричного помноження з фіксацією в пам’яті кожного ПЕ однієї із компонент вектора невідомих хк-1; ЛСМЛЗ - лінійний СМ для векторно-матричного помноження з повністю локальними зв’язками; КПСМ - класичний прямокутний CM для обчислення добутку послідовності матриць; СПМТТ - спецпроцесор з матрицями типу теплицевих, оснований на модифікованому ітераційному методі Гауса-Зейделя. В таблиці в структурах для розв’язання СЛАР використовуються ітераційні методи Якобі та Гаусса-Зейделя. Всі структури виконують обчислення з цифровою точністю. ВИСНОВОК Аналіз основних характеристик алгоритмів і структур, наведених в табл. 1, за такими критеріями, як прискорення паралельного алгоритму, час його виконання та коефіцієнт апаратурної завантаженості дозволив зробити такі висновки: час виконання алгоритму (Ті) на паралельній системі – одна із найважливіших характеристик в паралельних методах, однак, як видно з таблиці, в усіх структурах він залежить від порядку СЛАР, що при великих значеннях значно збільшує цей час. А тому виникає необхідність створення структур, що змогли б забезпечити паралельне розв’язання СЛАР навіть надвисоких порядків без залежності від цього порядку. Такі структури можуть бути побудованими, використовуючи техніку цифрових оптичних обчислень, що дозволить значно підвищити швидкодію і точність розв’язання СЛАР. СПИСОК ЛІТЕРАТУРИ Заболотна Н.И. Организация вычислительных структур высокопроизводительных линейно- алгебраических процессоров паралельной обработки матриц.: Дис. канд. техн. наук: 05.13.08. – Винница, 1996. – С.11-12. 1. Демидович Г.Е., Марон Г.А. Основы вычислительной математики. – М.: Наука, 1970. – 664с. 2. Пухов Г.Е. и др. Вычислительные устройства на скаляторах. – Киев: Техніка, 1983. – 144с. 3. Гофман М.А. Многоканальний поиск информации в некогерентных оптических системах памяти // Автометрия. – 1976. – №6. –С.48-54. 4. Колфилд Дж. и др. Оптические нейронные сети // ТИИЭР. – Т.77. – №10. –1989. – С.193-202. 5. Кожемяко В.П., Красиленко В.Г., Заболотная Н.И., Билык В.И. Анализ быстродействующих цифрових методов и устройств вычисления площадей бинарных дискретизированых изображений // В кн.: Оптоелектронные методы и средства обработки информации. – Винница, 1988. – С.50-54. 6. Райс Дж. Матричные вычисления и математическое обеспечение. – М.: Мир, 1984. – 264 с. 7. Фаддеев Д. К., Фаддеева Н. В. Вычислительные методы линейной алгебры. – М., Л.: Физматгиз, 1963. – 734 с. 8. Молчанов И. Н. Машинные методы решения прикладных задач. Алгебра, приближение функций. – Киев: Наук. думка, 1987. – 288 с. 9. Бурман З.И., Артюхин Г.А., Зархин Б.Я. Программное обеспечение матричных алгоритмов и ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО- ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ 12 метода конечных элементов в инженерных расчетах. – М.: Машиностроение, 1988. – 256 с. 10. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем: Пер. с англ.– М.: Мир, 1991. –364с. 11. А.с. 1566367 СССР. Устройство для решения систем линейных алгебраических уравнений // В.Я. Михальчишин, И.В. Михальчишин. – Опубл. 23.05.90, Бюл. №19. 12. А.с. 1633422 СССР. Устройство для решения систем линейных алгебраических уравнений // В.П. Якуш, Н.А Лиходед, В.В. Косьянчук, П.И. Соболевский, В.И. Мостовой. – Опубл. 07.03.91, Бюл. №9. 13. Kung H.T., Leiserson C.E. Systolic arrays (for VLSI) // Sparse Matrix Processing. 1978. – Philadelphia: SIAM. 1979. – P. 256-282. 14. Ульман Д. Вычислительніе аспекты СБИС. – М.: Радио и связь, 1990. – 480 с. 15. Грицык В.В., Михальчишин В.Я. Линейные систолические алгоритмы для решения систем линейных алгебраических уравнений // Тр. 1-го Всесоюзного семинара «Логические методы построения однородных и систолических структур». – М., 1988. – с. 71-77. 16. А.с. 1688257 СССР. Устройство для решения систем линейных алгебраических уравнений // В.Я. Михальчишин. – Опубл. 30.10.91, Бюл. №40. 17. Лиходед Н.А., Соболевский П.И. О реализации на систолических структурах некоторых итерационных алгоритмов // Тез. докл. 1-й Всесоюз. конф. «Однородные вычислительные среды и систолические структуры» – Львов: Ин-т прикл. пробл. Механики и математики, 1990. – С. 95- 100. 18. Выжиковский Р., Елфимова Л.Д., Каневский Ю.С. Реализация на систолических массивах некоторых итерационных алгоритмов решения СЛАУ // Кибернетика и системный анализ. – 1992. - №5. – С.145-157. 19. Соболевский П.И., Лихоед Н.А. Внешняя стыковка при реализации одношаговых итерационных процессов на систолических структурах. – Минск, – 1990. – 60с. 20. Джагадиш Х.В., Рао С.К., Кайлат Т. Матричные структуры для реализации итерационных алгоритмов// ТИИЭР. – 1987. – 75, №9.–с.184-201. 21. Головатый А.П., Деркач В.П., Мержвинский А.А., Панчук В.И. Высокопроизводительный специализированный процессор для решения систем линейных алгебраических уравнений с теплицевыми матрицами // УСиМ. – 1991. - №4. –С.29-36. 22. Kung-Shiuh Huang, B.Keith Tenkins, Alexander A.Sawchuk. Image algebra representation of parallel optical binary arithmetic // Aplied Optics.– 1989.– Vol. 28, N6. – P.1263-1278. 23. Денисов В.М. и др. Структура цифрового оптоэлектронного процессора многоуровневых изображений по пространственно-непрерывным разрядным срезам // Электронное моделирование. – 1984. – №6. – С.99-106. Надійшла до редакції 14.11.2008р. ЗАБОЛОТНА Н.І. – к.т.н., доцент, декан факультету функціональної електроніки та лазерної техніки, Вінницький національний технічний університет, Вінниця, Україна. МУСІЙЧУК І.В. – аспірант кафедри лазерної та оптоелектронної техніки, Вінницький національний технічний університет, Вінниця, Україна. КОСТЮК С.В. - здобувач кафедри лазерної та оптоелектронної техніки, Вінницький національний технічний університет, Вінниця, Україна.

Концепції та підходи до побудови спецпроцесорів для ітераційного розв’язання систем лінійних алгебраїчних рівнянь

Institution

Ähnliche Einträge