НОУ ІНТУЇТ | лекція | Множення розріджених матриць

1. Результати обчислювальних експериментів Обчислювальні експерименти для оцінки ефективності паралельного...
2. послідовний алгоритм
3. Організація паралельних обчислень
4. Результати обчислювальних експериментів

Результати обчислювальних експериментів

Обчислювальні експерименти для оцінки ефективності паралельного варіанта методу верхньої релаксації проводилися за умов, зазначених у вступі. З метою формування симетричною позитивно певної матриці елементи подматріци генерувалися в діапа-зоні від 0 до 1, значення елементів подматріци виходили з симетрії матриць і , А елементи на головній діагоналі (подматріца ) Генерувалися в діапазоні від до , де - розмір матриці.

Як критерій зупинки використовувався критерій зупинки по точності (7.51) з параметром а ітераційний параметр . У всіх експериментах метод знайшов рішення з необхідною точністю за 11 ітерацій. Як і для попередніх експериментів, прискорення будемо фіксувати в порівнянні з паралельною програмою, запущеної в один потік.

Таблиця 7.20. Результати експериментів (метод верхньої релаксації) n 1 потік Паралельний алгоритм 2 потоку 4 потоку 6 потоків 8 потоків TSTSTSTS 2500 0,73 0,47 1,57 0,30 2,48 0,25 2,93 0,22 3,35 5000 3,25 2,11 1,54 1,22 2,67 0,98 3,30 0,80 4,08 7500 7,72 5,05 1,53 3,18 2,43 2,36 3,28 1 , 84 4,19 10000 14,60 9,77 1,50 5,94 2,46 4,52 3,23 3,56 4,10 12500 25,54 17,63 1,45 10,44 2,45 7 , 35 3,48 5,79 4,41 15000 38,64 26,36 1,47 15,32 2,52 10,84 3,56 8,50 4,54

Експерименти показують непогане прискорення (близько 4 на 8-й потоках).

Метод сполучених градієнтів

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

в просторі . Справді, функція досягає свого мінімального значення тоді і тільки тоді, коли її градієнт наближається до нуля. Таким чином, рішення системи (7.49) можна шукати як рішення задачі безумовної мінімізації (7.56).

послідовний алгоритм

З метою вирішення завдання мінімізації (7.56) організовується наступний ітераційний процес.

Підготовчий етап ( ) Визначається формулами

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

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

Таким чином, виконання ітерацій методу зажадає

операцій. Можна показати, що для знаходження точного рішення системи лінійних рівнянь з позитивно певної симетричною матрицею необхідно виконати не більше n ітерацій, тим самим, складність алгоритму пошуку точного рішення має порядок . Однак з огляду на помилок округлення даний процес зазвичай розглядають як ітераці- ційний, процес завершується або при виконанні звичайного умови зупинки (7.51), або при виконанні умови малості відносної норми нев'язки

Організація паралельних обчислень

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

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

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

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

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

де - довжина вектора, - число потоків, - накладні витрати на ство- ня і закриття паралельної секції.

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

де - число ітерацій методу.

Результати обчислювальних експериментів

Обчислювальні експерименти для оцінки ефективності паралельного варіанта методу сполучених градієнтів для вирішення систем лінійних рівнянь з симетричною позитивно певної матрицею прово дилися за умов, зазначених у вступі. Елементи на головній діагоналі матриці ) Генерувалися в діапазоні від до , де - розмір матриці, інші елементи генерувалися симетрично в діапазоні від 0 до 1. В якості критерію зупинки використовувався критерій зупинки по точності (7.51) з параметром

Результати обчислювальних експериментів наведені в таблиці 7.21 (Час роботи алгоритмів зазначено в секундах).

Таблиця 7.21. Результати експериментів (метод сполучених градієнтів) n 1 потік Паралельний алгоритм 2 потоку 4 потоку 6 потоків 8 потоків TSTSTSTS 500 0,02 0,01 1,64 0,01 2,56 0,01 2,56 0,01 2,56 1000 0,21 0,16 1,26 0,10 2,09 0,07 2,88 0,05 3,83 1500 0,65 0,48 1,36 0,27 2,41 0,19 3,42 0 , 15 4,20 2000 1,32 0,94 1,41 0,53 2,51 0,38 3,48 0,29 4,50 3000 3,42 2,34 1,46 1,33 2,58 0 , 96 3,56 0,74 4,63 4000 6,49 4,54 1,43 2,53 2,56 1,80 3,60 1,40 4,62 5000 11,02 7,41 1,49 4 , 17 2,65 2,98 3,70 2,31 4,78

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

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