Реализация метода Гаусса. Решения СЛАУ в системе MPI

МOРФ

НГТУ

Кафедра ПВТ

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

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

Тема: «Метод Гаусса»

Факультет:          ПМИ

Группа:        ПМ-92

Студенты:           Терещенко Т., Вамбуева Т., Че Т.

Преподаватель:      Медведев М.Ю.

Новосибирск

2003

1.Цель работы

Реализовать метод Гаусса решения СЛАУ в системе MPI двумя способами. Первый заключается в том, что соседние строки матрицы хранятся не далее, чем в соседних компьютерах. Например:

Номер строки Номер компьютера

1              0

2              0

3              1

4              1

Второй заключается в том, что принадлежность строк процессорам меняется с каждой строкой:

Номер строки Номер компьютера

1              0

2              1

3              0

4              1

2.Реализация

Программа 1 имеет следующий алгоритм работы:

• Нулевой процессор:
• Считывание и пересылка размерности матрицы, расчёт распределения строк по процессорам и пересылка этой информации.
• Считывание своей части матрицы
• Считывание остальной части матрицы и пересылка соответствующим процессорам
• Ненулевые процессоры:
• Получить размерность от нулевого компьютера и распределение строк по процессорам.
• Получить свои строки матрицы от нулевого процессора.
• Для каждого процессора:
• Для каждой строки i процессора:
• Получить все строки с меньшими номерами, обработать их, занулив соответствующую компоненту (с номером i).
• Переслать строку i всем процессорам, с номером, большим, чем rank.
• Обработать свои ниже стоящие строки, занулив в них i-ю компоненту.
• Получить строку с вектором – результатом от компьютера с номером, большим, чем rank.
• Для каждой строки i процессора:
• Вычислить i-ю компоненту вектора результата
• Переслать вектор-результат компьютерам с ранком, меньшим, чем rank
• Нулевой процессор замеряет время и пишет результат в файл.

В программе 2 использовались следующие соотношения:

Глобальный номер строки i процессора с ранком rank: rank+1+(i-1)*size

Строка с номером str находится у процессора (str-1)%size

Компьютер с ранком rank содержит строки (rank+1+size*n)%dim, n=0,…

Программа 2 имеет следующий алгоритм работы:

• Нулевой процессор:
• Считывание и пересылка размерности матрицы, расчёт числа строк в каждом процессоре и пересылка этой информации.
• Для каждой строки
• Если это своя строка, то считать и записать в свою матрицу
• Иначе считать и переслать соответствующему процессору.
• Ненулевые процессоры:
• Получить размерность от нулевого компьютера и число строк в каждом процессоре.
• Получить свои строки матрицы от нулевого процессора.
• Для каждого процессора:
• Для каждой строки i процессора:
• Получить все строки с меньшими номерами, обработать их, занулив соответствующую компоненту (с номером i).
• Переслать строку i всем процессорам, с номером, большим, чем rank.
• Обработать свои ниже стоящие строки, занулив в них i-ю компоненту.
• Для каждой строки i процессора:
• Получить строку с вектором – результатом от компьютера, содержащего следующую строку (i+1).
• Вычислить i-ю компоненту результата
• Переслать строку – результат процессору, содержащему строку (i-1)
• Нулевой процессор замеряет время и пишет результат в файл.

Очевидно, что данная реализация также работает на любом числе процессоров. В каждой реализации учтено следующее: если обнуляемый элемент – уже нуль, то никаких преобразований с данной строкой не происходит.

В случае вырожденной матрицы выдаётся соответствующее сообщение.

I.  Программа 1

#include <mpi.h>

#include <time.h>

#include <stdio.h>

int main(int argc, char* argv[]){

int rank,i,j,j1,k,k1,pr,compID,size,sendtag=11,recvtag=11,nd=1,tag=11;

int   dims[1],per[1],reord=0,sour,dest,dim,*comp;

float *A,*B, *res,c;

double time_;

time_t *tp1,*tp2;

MPI_Status st;

MPI_Comm ring;

MPI_Request req1,req2;

FILE *inp, *outp;

tp1=(time_t *)malloc(sizeof(time_t));

tp2=(time_t *)malloc(sizeof(time_t));

MPI_Init(&argc,&argv);

sendtag=recvtag=11;

MPI_Comm_size(MPI_COMM_WORLD,&size);

dims[0]=size;

per[0]=1;

MPI_Cart_create(MPI_COMM_WORLD,nd,dims,per,reord,&ring);

MPI_Comm_rank(ring, &rank);

MPI_Cart_shift(ring,0,1,&sour,&dest);

comp=(int *)malloc(size*sizeof(int));