Дніпропетровський Національний Університет

Факультет Фізики, Електроніки та Комп’ютерних Систем

Кафедра Електро-Обчислювальних Машин 
 
 
 

Курсова робота

З дисципліни «Паралельні та розподіленні обчислення»

на тему: Рішення системи лінійних алгебраїчних рівнянь 
 
 
 
 

Виконавець   

студент КІ-08-1  

Кононович О.Є.   
 

Керівник   

доцент Литвинов О. А.  
 
 
 
 
 

Дніпропетровськ 2011р. 

Зміст

 

1. Зміст            2
2. Реферат           3
3. Завдання           3
4. Теоретичне рішення          4
1. Суть метода Гауса         4
2. Основні положення послідовного рішення      5
3. Основні положення паралельного рішення      5
4. Оцінка приросту та затрат        6
5. Реалізація алгоритму         9
1. Послідовний код          9
2. Паралельний код         11
3. Тестування          16
6. Висновок           16
7. Література           16

 

Реферат

 

     В курсовій роботі розглянуто класичний  метод рішення системи алгебраїчних рівнянь, що має назву «метод Гауса». Було розглянуто загальний підхід рішення в послідовному та паралельному методі, проведена оцінка приросту швидкості та затрат. Також було реалізовано обидва алгоритми на мові програмування С++, паралельний метод розглядався в розгалужені на процеси (Message Passing Interface технологія) та проведено тестування алгоритмів та масивах даних різного об’єму.

     Програмне забезпечення Microsoft Visual Studio 2010

     Тип використовуваних проектів Win32 Console Aplocation

     Використовуємо  бібліотеки Microsoft HPC Pack 2008 SDK

Завдання

 
---

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

 

Теоретичне  рішення

Суть  метода Гауса

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

     Нехай в нас є система наступного виду.

( 1 )

     Матриця A називається основною матрицею системи, b - стовпцем вільних членів. Тоді відповідно до властивості елементарних перетворень над рядками основну матрицю цієї системи можна привести до східчастого виду (ці ж перетворення потрібно застосовувати до стовпця вільних членів):

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

       Тоді змінні називаються головними змінними. Всі інші називаються вільними.

     Якщо хоча б одне число де, то розглянута система несумісна.

     Нехай число для будь-яких .

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

      ( 2 )

     

     Якщо вільним змінним системи (2) надавати всі можливі значення і вирішувати нову систему щодо головних невідомих знизу вгору (тобто від нижнього рівняння до верхнього), то ми отримаємо всі рішення цієї СЛАР. Так як ця система отримана шляхом елементарних перетворень над вихідною системою (1), то по теоремі про еквівалентність при елементарних перетвореннях системи (1) і (2) еквівалентні, тобто безлічі їх рішень збігаються.

Основні положення послідовного рішення

     Будь  яка реалізація метода Гауса включає в себе два послідовних етапи: прямий хід та зворотній хід. На першому етапі ми формуємо верхній трикутник. В послідовному методі ми просто проходимо матрицю разів. На кожному проходженні ми виключаємо з кожного рядка нову зміну. Отже ми вже маємо два вкладених цикли: проходження матриці від другого рядка до останнього і внутрішній (від до ). Також нам потрібний цикл для обробки поточного рядка. В сумі прямий хід має три вкладених цикли. На другому етапі ми просто проходимо з кінця і підставляємо знайдені значення. Тут можливі два підходи: кожне знайдене значення підставляється лише при обробці поточного рядка, або відразу підставляється в усі рядки. На кількість виконуваних операцій це не впливає. Кожне знайдене значення невідомого відразу записується в масив результату.

Основні положення паралельного рішення

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

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

     Другий  етап трохи складніше: наступний  крок залежить від попереднього. Ми не можемо обробити весь рядок, поки не будуть відомі всі необхідні невідомі. Але ми можемо підставити вже знайденні невідомі для обчислення добутку коефіцієнту на невідоме. Нажаль тут теж випливає попередня проблема: на самому початку всі процеси завантажені на повну, при просуванні до вершини ми або просто постійно множимо на нуль (при цьому ця операція абсолютно позбавлена сенсу, але такий підхід найпростіший), або знову маємо «стоячі» процеси. Цього також можливо позбутися способом описаним вище.

Оцінка  приросту та затрат

     Оцінимо трудомісткість розглянутого паралельного варіанта методу Гаусса. Нехай, як і раніше, n є порядок розв'язуваної системи лінійних рівнянь, а p, p <n, означає число використовуваних процесорів. Тим самим, матриця коефіцієнтів А має розмір n × n і, відповідно, n / p є розмір смуги матриці А на кожному процесорі.

     Перш за все, нескладно показати, що загальний час виконання послідовного варіанта методу Гаусса становить:

     

     Визначимо тепер складність паралельного варіанта методу Гаусса. При виконанні прямого ходу алгоритму на кожній ітерації для вибору провідної рядки кожен процесор має здійснити вибір максимального значення в стовпці з исключаемой невідомої в межах своєї смуги. Початковий розмір смуг на процесорах дорівнює n / p, але в міру виключення невідомих кількість рядків у смугах для обробки поступово скорочується. Поточний розмір смуг приблизно можна оцінити як (ni) / p, де i, 0 ≤ i <n-1, є номер виконуваної ітерації прямого ходу методу Гаусса. Далі після збору отриманих максимальних значень, визначення та розсилки провідною рядки, кожен процесор має виконати віднімання провідною рядки з кожного рядка решти рядків своєї смуги матриці A. Кількість елементів рядка, що підлягають обробці, також скорочується при виключенні невідомих, і поточне число елементів рядка для обчислень оцінюється величиною (ni). Тим самим, складність процедури вирахування рядків оцінюється як 2 · (ni) операцій (перед вирахуванням провідна рядок множиться на масштабуючі величину aik / aii). З урахуванням виконуваного кількості ітерацій, загальне число операцій паралельного варіанта прямого ходу методу Гаусса визначається виразом:

     

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

     

     Підсумувавши  отримані вирази можна отримати

     

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

     Отримані  співвідношення мають досить складний вид для оцінювання. Разом з  тим можна показати, що складність паралельного алгоритму має порядок ~ (2n / 3) / p3, і, тим самим, балансування обчислювального навантаження між  процесорами в цілому є досить рівномірною.

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

     

     де, як і раніше, α - латентність мережі передачі даних, β - пропускна здатність  мережі, w - розмір пересилається елемента даних.

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

     

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

     

     Підводячи підсумок, з урахуванням всіх отриманих  виразів, трудомісткість паралельного варіанта методу Гаусса становить:

     

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

 

Реалізація  алгоритму

Послідовний метод

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

#include "stdafx.h"

#include <stdio.h>

#include <stdlib.h>

#define fileIn "D:/temp/tmp/ListNoZero.txt"

#define fileOut "D:/temp/tmp/result_noParallel.txt"