Розв'язання систем алгебричних рівнянь з матрицями на паралельних обчислювальних системах

Размещено на http://www.allbest.ru/

Чортківський інститут підприємництва і бізнесу

Тернопільський національний економічний університет

Розв'язання систем алгебричних рівнянь з матрицями на паралельних обчислювальних системах

УДК 518.25

Семчишин Л.М., к.ф.-м.н

Аннотації

Запропоновано новий підхід для дослідження паралельності алгоритмів розв'язання матричних систем з _матрицями. Розглянено паралельні обчислювальні системи класу MІMD. Проаналізовано процес розв'язання систем рівнянь з матрицями на багатопроцесорній обчислювальній системі з MІMD-архітектурою. Показано ланцюговий та централізований способи передачі інформації, а також схеми діагоналізації та розрізання розв'язання матричних систем з _матрицями.

Семчишин Л.М. РЕШЕНИЕ СИСТЕМ АЛГЕБРИЧНИХ УРАВНЕНИЙ С МАТРИЦАМИ НА ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ / Чортковский институт предпринимательства и бизнеса, Тернопольский национальный экономический университет, Украина

Предложен новый подход для исследования параллельности алгоритмов решения матричных систем с матрицами. Росмотрено параллельные вычислительные системы класса MІMD. Проанализирован процесс решения систем уравнений с матрицами на многопроцессорной вычислительной системе с MІMD-архитектурой. Показано цепной и централизованный способы передачи информации, а также схемы диагонализации и вскрытие решения матричных систем с матрицами.

Ключевые слова: решение матричных систем с матрицами, параллельные вычислительные системы класса MІMD, многопроцессорная вычислительная система, цепной и централизованный способы передачи информации, схемы диагонализации и вскрытие.

Semchyshyn L.М. ТНЕ ALGEBRAIC SYSTEM EQUATION WITH MATRIX ON THE PARALLEL CALCULATIVE SYSTEMS SOLUTION / Chortkiv Institute of Business, Ternopil National Economic University, Ukraine

New approach to the severance system method solution is suggested in the work. The cellular algorythm of the numerical system of linear algebraic equation solution testing is shown. The way of some rarefied SLAR types solution testing is shown. The system of linear algebraic equation with numerical elements is characterized. Comparative characteristic of SLAR with numerical elements is conducted and the linear algebraic testing procedure in the MatLab environment is described.

Key words: severance system, cellular algorythm, system of linear algebraic equotins with numerical elements, rarefied numerical systems, linear algebraic procedure.

Вступ

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

Дослідження паралельності описаних алгоритмів розв'язання матричних систем з _матрицями проведено для двох найбільш часто використовуваних моделей - концепції необмеженого паралелізму [4], а також для комп'ютерів з конкретною архітектурою - багатопроцесорною обчислювальною системою типу MІMD [9].

Вибір MІMD-архітектури продиктований тим, що серед паралельних обчислювальних систем обчислювальні комп'ютери цього типу є одними з найбільш розповсюджених.

Аналіз останніх досліджень і публікацій. Багато відомих вітчизняних і закордонних вчених займалися проблемами розв'язування систем лінійних алгебричних рівнянь. Серед них: В. Воєводін [1,2,3], Дж.Х. Уилкинсон [8], Е. Тиртишніков [7] та ін. Однак деякі проблеми не мають однозначного розв'язання і потребують уточнення. У роботі М. Недашковського і О. Ковальчук [5] розглянуто комп'ютерні алгоритми для систем лінійних алгебричних рівнянь з матрицями. Особлива увага приділялась розв'язуванню задач обчислювальної математики на паралельних системах у працях таких вчених як: А. Хіміч, І. Молчанов [9] та ін. У роботі [6] запропоновано новий підхід до розв'язування систем лінійних алгебричних рівнянь із числовими елементами. Проведено порівняльну характеристику СЛАР з числовими елементами та описано тестування процедур лінійної алгебри в середовищі MatLab.

Мета роботи. Метою даної праці є дослідження паралельності алгоритмів розв'язання матричних систем з _матрицями. Аналіз процесу розв'язання систем рівнянь з матрицями на багатопроцесорній обчислювальній системі з MІMD-архітектурою.

Дослідження задачі та обґрунтування отриманих наукових результатів. Вибір MІMD-архітектури продиктований тим, що серед паралельних обчислювальних систем обчислювальні комп'ютери цього типу є одними з найбільш розповсюджених.

Основна частина

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

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

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

Економічністю називають відношення

Оцінимо тепер ефективність використання описаних раніше числових алгоритмів розв'язання матричних систем з -матрицями на паралельних обчислювальних системах.

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

Багатопроцесорна система має процесорів.

Для системи рівнянь виду:

На першому етапі визначаються матриці та , а тому

На наступному етапі знаходяться та , отже

Третій етап потребує розв'язання щільної системи порядку і тому

Четвертий етап полягає у визначенні та і, отже, Отже, , , .

Обчислювальна система складається з процесорів.

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

На наступному етапі знаходяться матриці та , отже,

Третій етап вимагає розв'язання щільної лінійної системи порядку , внаслідок чого .

На четвертому етапі матриці та можна обчислити за тактів.

Отже, .

Остаточно,

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

Паралельні обчислювальні системи класу MІMD. Подальші міркування проведемо для машин класу MІMD [9] за умов обмеженості обчислювальних ресурсів і технічних можливостей. Припускається, що багатопроцесорна система має таку структуру.

Нехай є деякий універсальний серійний комп'ютер, розміщений на периферії. Він здійснює обслуговування паралельної обчислювальної системи і управління зовнішніми пристроями. У системі існує комутатор зв'язку, до каналів якого під'єднані управляючі пристрої (УП), арифметичні процесори (АП) і спеціальні процесори (СП).

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

Комутаційні процесори (КП) здійснюють з'єднання модулів для обміну даними. Передача інформації проводиться в напівдуплексному режимі. Можливі попарні з'єднання довільної кількості АП.

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

Керуючий комп'ютер проводить управління всіма периферійними пристроями (дисководами, моніторами, принтерами і т. д.) та виконує роль своєрідного буфера при обмінах інформацією між АП і зовнішньою пам'яттю (під ЗП надалі матимемо на увазі магнітні носії інформації або пристрої, аналогічні за швидкодією). На відміну від АП, управляюча машина може проводити обмін даними одночасно з АП. Тут - кількість каналів зв'язку між АП і периферійною ЕОМ. Крім того, є кілька каналів для зв'язку з периферійними пристроями, що можуть бути залучені одночасно.

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

Використовуватимемо такі позначення:

M - об'єм оперативної пам'яті АП (у словах); N - об'єм оперативної пам'яті управляючої машини (у словах),

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

- середній час комутаційних затримок при встановленні зв'язку між двома модулями;

- час передачі одного слова між двома модулями;

- середній час виконання однієї арифметичної операції і нехай.

Обмін інформацією ПОС може проводитися одним з описаних нижче способів [9].

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

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

Централізований принцип передачі даних - процес передачі інформації з управляючої машини одночасно в r АП .

Магістральна обробка даних - процедура перетворення наборів даних , що знаходяться в АП, за допомогою наборів даних , які викликаються або з універсальної ЕОМ, або із зовнішньої пам'яті. При виконанні даної процедури набір даних передається після за такою схемою

Розглянемо тепер особливості застосування описаних процедур передачі даних. Нехай необхідно передати набір даних з допоміжного АП в усі АП групи, кількість яких дорівнює p. За ланцюгової процедури передачі даних треба переривань обміну. Можна також спочатку передати вказаний набір в універсальний комп'ютер, а потім скористатися централізованим принципом пересилання інформації.

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

Проаналізуємо тапер процес розв'язання систем рівнянь з матрицями на багатопроцесорній обчислювальній системі з MІMD-архітектурою.

Рядкова схеми розв'язання. За даним алгоритмом розв'язується рядкова система порядку з шириною рядка . Для її розв'язання скористаємося рядковою модификацiєю другого алгоритму вiдсiчених систем. Як показано ранiше, на однопроцесорнiй ЕОМ потрiбно виконати множень і таку ж кількість додавань. Для оцінки часу виконання алгоритму на -процесорній системі класу MIMD розглянемо декілька способів обміну даними між АП.

Припустимо, що розміри матриці такі, що всі початкові коефіцієнти поліномів , а також коефіцієнти проміжних величин розміщені у пам'яті арифметичних процесорів, тобто .

Припустимо, що в кожному з арифметичних процесорів розміщено по стовпців матриці , тобто . Для мінімізації часу простою АП треба розподiлити данi так, щоб у ому АП мiстилися -тi вектор-стовпцi матрицi . Крiм того, необхiдно зарезервувати в кожному АП масив розмiрностi для зберiгання промiжних результатiв.

Пiсля зроблених припущень перейдемо до розгляду обчислювальних схем, зорієнтованих на рiзнi способи передачi даних.

Ланцюговий спосiб передачi iнформацiї. Нехай обчислювальний процес знаходиться на -ому кроцi. На цьому етапi для обчислення полiномiв i промiжних невiдомих i необхiдно обчислити скалярнi добутки -ого порядку. Припускаємо, що всi необхiднi для обчислень елементи початкової матрицi знаходяться у вiдповiдних АП. Визначення промiжних невiдомих i , а також величин вимагає пересилки в кожний процесор по невiдомих i , а також по значень . За обраного способу передачi даних на це потрiбний час ]До того ж, на виконання всiх обчислень затратимо час, рiвний

Отже, на довiльному -ому етапi загальний час, затрачений обчислювальною системою на обчислення i обмiн iнформацiєю, складатиме

Тому загальний час T на реалізацію всіх етапів дорівнює:

і, відповідно, прискорення

за ефективності .

Централізований спосіб передачі даних. Нехай обчислювальний процес знаходиться на -му кроці. Тоді на цьому етапі для обчислення поліномів і проміжних невідомих i потрібно обчислити скалярні добутки -го порядку. Вважаємо, що всі необхідні для обчислень елементи початкової матриці знаходяться у відповідних АП. Визначення проміжних невідомих i , а також величин вимагає пересилання в кожний процесор по невідомих і , а також по значень . За вибраного способу передачі даних на це потрібний буде час

Крім того, на виконання всіх обчислень затратимо час, рівний

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

.

Отже, загальний час на реалізацію всіх етапів

і, відповідно, прискорення

за ефективності .

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

Систолічні масиви для розв'язання систем із прямокутними -матрицями. За схемою діагоналізації задача зводиться до розв'язання числових систем з клітково-тепліцевим заповненням. Безперечна перевага такого підходу - можливість застосування добре розроблених векторних T-алгоритмів, які допускають ефективну реалізацію на так званих систолічних масивах.

Так, для системи числових лінійних алгебричних рівнянь з тепліцевою матрицею порядку N введення даних і виведення результатів обчислень можна виконати [9] за такою схемою:

. . . . . . . . . . . . . . . . . . . .

.

Систолічний масив складається з N комірок, позначених відповідно . Використовується лише два типи комірок: перший відповідає коміркам для , інший - лише комірці, яка дещо відрізняється від решти.

Комірка першого типу має вигляд прямокутника, що приймає та передає інформацію через ліву та праву межі:

Зліва є три входи і п'ять виходів . Справа розміщені п'ять входів та три виходи для приймання і передавання відповідно величин і . Комірка має три регістри для зберігання даних між послідовними тактами роботи.

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

Згідно з [18], загальний час роботи такого систолічного масиву для розв'язання системи складатиме 5(nl+1)(n+1)-6 тактів.

Отже, розглянуті алгоритми розв'язання систем лінійних алгебричних рівнянь можна успішно використовувати на багатопроцесорних обчислювальних комплексах. Для -процесорних ЕОМ при досягається повна завантаженість усіх процесорів для кожного алгоритму. Характерно, що ефективність і прискорення практично збігаються для концепції необмеженого паралелізму та ЕОМ з MІMD-архітектурою.

Висновки

У статті розглянено новий підхід до розв'язування систем алгебричних рівнянь з _матрицями на паралельних обчислювальних системах. Запропоновано новий підхід для дослідження паралельності алгоритмів розв'язання матричних систем з _матрицями. Розглянено паралельні обчислювальні системи класу MІMD. Проаналізовано процес розв'язання систем рівнянь з матрицями на багатопроцесорній обчислювальній системі з MІMD-архітектурою. Показано ланцюговий та централізований способи передачі інформації, а також схеми діагоналізації та розрізання розв'язання матричних систем з _матрицями.

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

Література

1. Воеводин В.В. Математические модели и методы в параллельных процессах / В.В. Воеводин. - М.: Наука, 1986. - 296 с.

2. Воеводин В.В. Матрицы и вычисления / В.В. Воеводин, Ю.А. Кузнецов. - М.: Наука, 1984. - 320 с.

3. Воеводин В.В. Параллельные вычисления / В.В. Воеводин, Вл.В. Воеводин. - С.-П.: БХВ-Петербург, 2002. - 608 с.

4. Гольштейн Е.Г. Методы оптимизации в экономико-математическом моделировании / Е.Г. Гольштейн. - М.: Наука, 1991. - 448 с.

5. Недашковський М.О. Обчислення зматрицями / М.О. Недашковський, О.Я. Ковальчук. - К.: Наук. думка, 2007. - 294 с.

6. Семчишин Л. М. Застосування методу відсічених систем у середовищі MАTLAB. / Л.М. Семчишин, В.Б. Поселюжна. Вісник Запорізького національного університету. Випуск 2, Запоріжжя, 2011. С. 86-96.

7. Тыртышников Е.Е. Матричный анализ и линейная алгебра / Е.Е. Тыртышников. - М.: Физматлит, 2007. - 480 с.

8. Уилкинсон Дж.Х. Алгебраическая проблема собственных значений / Дж.Х. Уилкинсон. - М.: Наука, 1970. - 564 с.

9. Химич А.Н. Параллельные алгоритмы решения задач вычислительной математики / [Химич А.Н., Молчанов И.Н. и др.]. - К.: Наукова думка, 2008. - 248 с.

Размещено на Allbest.ru