Лабораторная работа №5 Решение систем линейных алгебраических уравнений методом Гаусса




Скачать 50.19 Kb.
Дата28.09.2016
Размер50.19 Kb.

Основы параллельного программирования

Лабораторная работа № 5

Решение систем линейных алгебраических уравнений методом Гаусса



Цель - практическое освоение методов решения систем линейных алгебраических уравнений прямыми методами. В лабораторной работе дано объяснение двух способов параллельного решения СЛАУ методом Гаусса, связанных с разными способами распределения данных по компьютерам. В этом разделе приведена последовательная программа решения СЛАУ методом Гаусса.
Требуется найти решение системы линейных алгебраических уравнений:

a11x1 + a12x2 + … + a1nxn = f1

a21x2 + a22x2 + … + a2nxn = f2

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

an1x1 + an2x2 + … + annxn = fn

Метод Гаусса основан на последовательном исключении неизвестных. Здесь рассматриваются два алгоритма решения СЛАУ методом Гаусса. Они связаны с разными способами представления данных (матриц коэффициентов и правых частей) в распределенной памяти мультикомпьютера. Схемы распределения данных по компьютерам для обоих примеров приведены ниже. Хотя данные распределены в памяти мультикомпьютера в каждом алгоритме по разному, но оба они реализуются на одной и той же топологии связи компьютеров - "полный граф".


ПРИМЕР 5.1. Решение СЛАУ методом Гаусса. Алгоритм первый
В алгоритме, представленном в данном пункте, исходная матрица коэффициентов A и вектор правых частей F разрезаны горизонтальными полосами, как показано на рис. 5.1. Каждая полоса загружается в соответствующий компьютер: нулевая полоса – в нулевой компьютер, первая полоса – в первый компьютер, и т. д., последняя полоса – в p1-1 компьютер. Здесь, в примере, каждая ветвь генерирует свои части матрицы коэффициентов A и вектор правых частей F.


p1

A F
Рис. 5.1.  Разрезание данных для параллельного алгоритма 1 решения СЛАУ методом Гаусса


При прямом ходе матрица приводится к треугольному виду последовательно по компьютерам. Вначале к треугольному виду приводятся строки в нулевом компьютере, при этом нулевой компьютер последовательно, строка за строкой, передает свои сроки остальным компьютерам, начиная с первого. Затем к треугольному виду приводятся строки в первом компьютере, передавая свои строки остальным компьютерам, начиная со второго, т.е. компьютерам с большими номерами, и т. д. Процесс деления строк на коэффициенты при xi не требует информации от других компьютеров.

После прямого хода полосы матрицы A в каждом узле будут иметь вид (рис. 5.2)






Рис. 5.2.  Вид полос после прямого хода в алгоритме 1 решения СЛАУ методом Гаусса. Пример приведен для четырех узлов; $ – вещественные числа.
Аналогично, последовательно по компьютерам, начиная с последнего по номеру компьютера, осуществляется обратный ход.

Особенностью этого алгоритма является то, что как при прямом, так и при обратном ходе, компьютеры, завершившие свою часть работы, переходят в состояние ожидания, пока не завершат эту работу другие компьютеры. Таким образом, вычислительная нагрузка распределяется по компьютерам неравномерно, не смотря на то, что данные изначально распределяются по компьютерам приблизительно одинаково. Простои компьютеров значительно уменьшаются при распределении матрицы циклическими горизонтальными полосами. Этот метод представлен в п. 3.4.2.


ПРИМЕР 5.2. Решение СЛАУ методом Гаусса. Алгоритм второй
В алгоритме, представленном здесь, исходная матрица коэффициентов распределяется по компьютерам циклическими горизонтальными полосами с шириной полосы в одну строку, как показано ниже на рис. 5.3.


A F
Рис. 5.3.  Разрезание данных для параллельного алгоритма 2 решения СЛАУ методом Гаусса


Нулевая строка матрицы помещается в компьютер 0, первая строка – в компьютер 1, и т. д., (p1-1)-я строка в компьютер p1-1 (где p1 количество компьютеров в системе). Затем, p1–я строка, снова помещается в компьютер 0, p1+1-я строка – в компьютер 1, и т. д.

При таком распределении данных, соответствующим этому распределению должен быть и алгоритм. Строку, которая вычитается из всех остальных строк (после предварительного деления на нужные коэффициенты), назовем текущей строкой. Алгоритм прямого хода заключается в следующем. Сначала текущей строкой является строка с индексом 0 в компьютере 0, затем строка с индексом 0 в компьютере 1 (здесь не нужно путать общую нумерацию строк во всей матрице и индексацию строк в каждом компьютере; в каждом компьютере индексация строк в массиве начинается с нуля) и т. д., и наконец, строка с индексом 0 в последнем по номеру компьютере. После чего цикл по компьютерам повторяется и текущей строкой становится строка с индексом 1 в компьютере 0, затем строка с индексом 1 в компьютере 1 и т. д. После прямого хода полосы матрицы в каждом компьютере будут иметь вид, показанный на рис. 5.4. Пример приведен для четырех узлов; $ – вещественные числа.

Аналогично, последовательно по узлам, начиная с последнего по номеру компьютера, осуществляется обратный ход.

Особенностью этого алгоритма является то, что как при прямом, так и при обратном ходе компьютеры являются более равномерно загруженными, чем в первом методе. Значит, и вычислительная нагрузка распределяется по компьютерам более равномерно, чем в первом методе. Например, нулевой компьютер, завершив обработку своих строк при прямом ходе, ожидает, пока другие компьютеры обработают только по одной, оставшейся у них не обработанной строке, а не полностью обработают полосы, как в первом алгоритме.






Рис. 5.4.  Вид полос после прямого хода в алгоритме 2 решения СЛАУ методом Гаусса

Ниже приведена программа решения СЛАУ методом Гаусса для последовательного алгоритма:


#include

#include


#define M 100
double MA[M][M+1], MAD;
int main()

{ int i, j, v, k;

/* Переменные для замера времени решения */

struct timeval tv1, tv2;

long int dt1;
/* Генерация данных */

for(i = 0; i < M; i++)

{ for(j = 0; j < M; j++)

{ if(i == j)

MA[i][j] = 2.0;

else


MA[i][j] = 1.0;

}

MA[i][M] = 1.0*(M)+1.0;



}
gettimeofday(&tv1,NULL);
/* Прямой ход */

for(k = 0; k < M; k++)

{ MAD = 1.0/MA[k][k];

for(j = M; j >= k; j--)

MA[k][j] *= MAD;

for(i = k+1; i < M; i++)

for(j = M; j >= k; j--)

MA[i][j] -= MA[i][k]*MA[k][j];

}
/* Обратный ход */

for(k = M-1; k >= 0; k--)

{ for(i = k-1; i >= 0; i--)

MA[i][M] -= MA[k][M]*MA[i][k];

}
/* Засечение времени и печать */

gettimeofday(&tv2,NULL);

dt1 = (tv2.tv_sec - tv1.tv_sec)*1000000 + tv2.tv_usec - tv1.tv_usec;

printf("Time = %ld\n",dt1);


/* Печать первых восьми корней */

printf(" %f %f %f %f\n",MA[0][M],MA[1][M],MA[2][M],MA[3][M]);

printf(" %f %f %f %f\n",MA[4][M],MA[5][M],MA[6][M],MA[7][M]);
return(0);

}
Обратите внимание на функцию замера времени gettimeofday(&tv,NULL). Эту функцию можно использовать и для параллельных программ.


ЗАДАНИЕ

Тщательно изучить программы примеров. Скомпилировать и запустить все программы примеров на одном компьютере.


База данных защищена авторским правом ©infoeto.ru 2016
обратиться к администрации
Как написать курсовую работу | Как написать хороший реферат
    Главная страница