Н., Пескова Е. Е., Шаманаев П. А. Основы параллельного программирования с использованием технологий mpi и openmp учебное пособие саранск издательство свмо 2013 2
жүктеу/скачать 6.58 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- 2.7.4 Алгоритм решения СЛАУ методом Гаусса
|
Программа. Параллельная программа умножения матрицы на матрицу #include #include #include #include "mpi.h" #include const int N=4; int main(int argc, char *argv[]) { int r,q,myid,numprocs; int i0; int *b,*c,*loc_a,*loc_c; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&numprocs); MPI_Comm_rank(MPI_COMM_WORLD,&myid); MPI_Status status; q=N/numprocs; b=new int [N*N]; c=new int [N*N]; loc_c=new int[N*N]; loc_a=new int[q]; for(int i=0;i { c[i]=0; loc_c[i]=0; } if(myid==0) { 38 for (int j=0;j { for(r=0;r { loc_a[r]=1; } MPI_Send(&loc_a[0],q*N,MPI_INT,j,0,MPI_COMM_WORLD); } for(int i=0;i { b[i]=1; } } MPI_Recv(&loc_a[0],q*N,MPI_INT,0,0,MPI_COMM_WORLD,&status); for(r=0;r { MPI_Bcast(&b[r*N],N,MPI_INT,0,MPI_COMM_WORLD); i0=myid*q; for(int i=0;i { for(int j=0;j { loc_c[r*N+i0]+=loc_a[i*N+j]*b[r*N+j]; } i0++; } MPI_Reduce(loc_c,c,N*N,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD); } if(myid==0) { FILE *f=fopen("result.txt", "w"); for(int i=0;i { for(int j=0;j { fprintf(f,"%d\t",c[j*N+i]); } fprintf(f,"\n"); } fclose(f); } 39 return 0; MPI_Finalize();} 2.7.4 Алгоритм решения СЛАУ методом Гаусса Метод Гаусса – широко известный прямой алгоритм решения систем линейных уравнений, для которых матрицы коэффициентов являются плотными. Если система линейных уравнений невырожденна, то метод Гаусса гарантирует нахождение решения с погрешностью, определяемой точностью машинных вычислений. Основная идея метода состоит в приведении матрицы A посредством эквивалентных преобразований к треугольному виду, после чего значения искомых неизвестных могут быть получены непосредственно в явном виде. Метод Гаусса включает последовательное выполнение двух этапов. На первом этапе – прямой ход метода Гаусса – исходная система линейных уравнений при помощи последовательного исключения неизвестных приводится к верхнему треугольному виду c Ux . На обратном ходе метода Гаусса (второй этап алгоритма) осуществляется определение значений неизвестных. Из последнего уравнения преобразованной системы может быть вычислено значение переменной 1 n x , после этого из предпоследнего уравнения становится возможным определение переменной 2 n x и т.д. При внимательном рассмотрении метода Гаусса можно заметить, что все вычисления сводятся к однотипным вычислительным операциям над строками матрицы коэффициентов системы линейных уравнений. Как результат, в основу параллельной реализации алгоритма Гаусса может быть положен принцип распараллеливания по данным. В качестве базовой подзадачи можно принять тогда все вычисления, связанные с обработкой одной строки матрицы и соответствующего элемента вектора . Рассмотрим общую схему параллельных вычислений и возникающие при этом информационные зависимости между базовыми подзадачами. Для выполнения прямого хода метода Гаусса необходимо осуществить итерацию по исключению неизвестных для преобразования матрицы коэффициентов к верхнему треугольному виду. Выполнение итерации , , прямого хода метода Гаусса включает ряд последовательных действий. Прежде всего, в самом начале итерации необходимо выбрать ведущую строку, которая при использовании метода главных элементов определяется поиском строки с 40 наибольшим по абсолютной величине значением среди элементов столбца , соответствующего исключаемой переменной . Поскольку строки матрицы распределены по подзадачам, для поиска максимального значения подзадачи с номерами , , должны обменяться своими элементами при исключаемой переменной . После сбора всех необходимых данных в каждой подзадаче может быть определено, какая из подзадач содержит ведущую строку и какое значение является ведущим элементом. Далее для продолжения вычислений ведущая подзадача должна разослать свою строку матрицы и соответствующий элемент вектора всем остальным подзадачам с номерами , . Получив ведущую строку, подзадачи выполняют вычитание строк, обеспечивая тем самым исключение соответствующей неизвестной . При выполнении обратного хода метода Гаусса подзадачи выполняют необходимые вычисления для нахождения значения неизвестных. Как только какая-либо подзадача , , определяет значение своей переменной , это значение должно быть разослано всем подзадачам с номерами . Далее подзадачи подставляют полученное значение новой неизвестной и выполняют корректировку значений для элементов вектора . Выделенные базовые подзадачи характеризуются одинаковой вычислительной трудоемкостью и сбалансированным объемом передаваемых данных. В случае, когда размер матрицы, описывающей систему линейных уравнений, оказывается большим, чем число доступных процессоров (т.е. ), базовые подзадачи можно укрупнить, объединив в рамках одной подзадачи несколько строк матрицы. Возможно использовать ленточную циклическую схему для распределения данных между укрупненными подзадачами. В этом случае матрица делится на наборы (полосы) строк вида (рисунок 2.9): . Рис. 2.9. Пример использования ленточной циклической схемы жүктеу/скачать 6.58 Mb. Достарыңызбен бөлісу:
|