Н., Пескова Е. Е., Шаманаев П. А. Основы параллельного программирования с использованием технологий mpi и openmp учебное пособие саранск издательство свмо 2013 2
жүктеу/скачать 6.58 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- 2.7.3 Алгоритм умножения матриц
| Программа. Параллельная программа умножения матрицы на вектор
#include #include #include "mpi.h" using namespace std; int main(int argc, char *argv[]) { int numprocs,myid; int *a,*b,*c; int n,p,l; int N=10, M=10; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&numprocs); MPI_Comm_rank(MPI_COMM_WORLD,&myid); MPI_Status status; if (myid==0) { a=new int[N*M]; b=new int[M]; c=new int[N]; for (int i=0;i b[i]=1;} for (int j=0;j 33 a[j]=1; } n=int(N/numprocs); for (int k = 1; k MPI_Send(&n, 1, MPI_INT, k,0,MPI_COMM_WORLD); MPI_Send(&a[k*n*M],n*M, MPI_INT, k,1,MPI_COMM_WORLD); MPI_Send(&b[0],M, MPI_INT, k,2,MPI_COMM_WORLD); } } else { MPI_Recv(&n, 1, MPI_INT,0,0,MPI_COMM_WORLD,&status); a=new int[n*M]; b=new int[M]; c=new int[n]; MPI_Recv(a, n*M, MPI_INT,0,1,MPI_COMM_WORLD,&status); MPI_Recv(b, M, MPI_INT,0,2,MPI_COMM_WORLD,&status); } MPI_Barrier(MPI_COMM_WORLD); for (int i=0;i c[i]=0; } MPI_Barrier(MPI_COMM_WORLD); for (int i=0;i for (int j=0;j c[i]+=a[j+i*n]*b[j]; } } MPI_Barrier(MPI_COMM_WORLD); if (myid==0) { for (int i=1; i MPI_Recv(&c[i*n], n, MPI_INT,i,3,MPI_COMM_WORLD,&status); } } else { MPI_Send(c, n, MPI_INT, 0,3,MPI_COMM_WORLD); } if (myid==0) { FILE *f=fopen("result.txt", "w"); for (int i=0; i fprintf(f,"%d\n",c[i]); } fclose(f); 34 } return 0; } 2.7.3 Алгоритм умножения матриц Умножение матрицы размера и матрицы размера приводит к получению матрицы размера , каждый элемент которой определяется в соответствии с выражением: . Как следует из выражения, каждый элемент результирующей матрицы есть скалярное произведение соответствующих строки матрицы и столбца матрицы . Этот алгоритм предполагает выполнение операций умножения и столько же операций сложения элементов исходных матриц. Будем предполагать далее, что все матрицы являются квадратными и имеют размер . Последовательный алгоритм умножения матриц представляется тремя вложенными циклами: double MatrixA[Size][Size]; double MatrixB[Size][Size]; double MatrixC[Size][Size]; int i,j,k; for (i=0; i for (j=0; j MatrixC[i][j] = 0; for (k=0; k MatrixC[i][j] = MatrixC[i][j] + MatrixA[i][k]*MatrixB[k][j]; } } } Этот алгоритм является итеративным и ориентирован на последовательное вычисление строк матрицы . Действительно, при выполнении одной итерации внешнего цикла (цикла по переменной ) вычисляется одна строка результирующей матрицы (рисунок 2.7). 35 Рис. 2.7. Вычисление строки матрицы На первой итерации цикла по переменной используется первая строка матрицы и все столбцы матрицы для того, чтобы вычислить элементы первой строки результирующей матрицы . Рассмотрим ленточную схему разделения данных. Из определения операции матричного умножения следует, что вычисление всех элементов матрицы может быть выполнено независимо друг от друга. Как результат, возможный подход для организации параллельных вычислений состоит в использовании в качестве базовой подзадачи процедуры определения одного элемента результирующей матрицы . Для проведения всех необходимых вычислений каждая подзадача должна содержать по одной строке матрицы и одному столбцу матрицы . Общее количество получаемых при таком подходе подзадач оказывается равным (по числу элементов матрицы ). Рассмотрев предложенный подход, можно отметить, что достигнутый уровень параллелизма является в большинстве случаев избыточным. Обычно при проведении практических расчетов такое количество сформированных подзадач превышает число имеющихся процессоров и делает неизбежным этап укрупнения базовых задач. В этом плане может оказаться полезной агрегация вычислений уже на шаге выделения базовых подзадач. Возможное решение может состоять в объединении в рамках одной подзадачи всех вычислений, связанных не с одним, а с несколькими элементами результирующей матрицы . Для дальнейшего рассмотрения определим базовую задачу как процедуру вычисления всех элементов одной из строк матрицы . Такой подход приводит к снижению общего количества подзадач до величины . Для выполнения всех необходимых вычислений базовой подзадаче должны быть доступны одна из строк матрицы и все столбцы матрицы . Простое решение этой проблемы – дублирование матрицы во всех подзадачах – является, как правило, неприемлемым в силу больших затрат памяти для хранения данных. Поэтому организация вычислений должна быть построена таким образом, чтобы в каждый текущий момент времени подзадачи содержали лишь часть данных, необходимых для проведения расчетов, а доступ к остальной части данных обеспечивался бы при помощи передачи данных между процессорами. 36 Для вычисления одной строки матрицы необходимо, чтобы в каждой подзадаче содержалась строка матрицы , и был обеспечен доступ ко всем столбцам матрицы . Алгоритм представляет собой итерационную процедуру, количество итераций которой совпадает с числом подзадач. На каждой итерации алгоритма каждая подзадача содержит по одной строке матрицы и одному столбцу матрицы . При выполнении итерации проводится скалярное умножение содержащихся в подзадачах строк и столбцов, что приводит к получению соответствующих элементов результирующей матрицы . По завершении вычислений в конце каждой итерации столбцы матрицы должны быть переданы между подзадачами с тем, чтобы в каждой подзадаче оказались новые столбцы матрицы и могли быть вычислены новые элементы матрицы . При этом данная передача столбцов между подзадачами должна быть организована таким образом, чтобы после завершения итераций алгоритма в каждой подзадаче последовательно оказались все столбцы матрицы . Возможная простая схема организации необходимой последовательности передач столбцов матрицы между подзадачами состоит в представлении топологии информационных связей подзадач в виде кольцевой структуры. В этом случае на каждой итерации подзадача , , будет передавать свой столбец матрицы подзадаче с номером (в соответствии с кольцевой структурой подзадача передает свои данные подзадаче с номером ) – рисунок 2.8. После выполнения всех итераций алгоритма необходимое условие будет обеспечено – в каждой подзадаче поочередно окажутся все столбцы матрицы . На рисунке 2.8 представлены итерации алгоритма матричного умножения для случая, когда матрицы состоят из четырех строк и четырех столбцов . В начале вычислений в каждой подзадаче , , располагаются -я строка матрицы и -й столбец матрицы . В результате их перемножения подзадача получает элемент результирующей матрицы . Далее подзадачи осуществляют обмен столбцами, в ходе которого каждая подзадача передает свой столбец матрицы следующей подзадаче в соответствии с кольцевой структурой информационных взаимодействий. Далее выполнение описанных действий повторяется до завершения всех итераций параллельного алгоритма [4,7]. 37 Рис. 2.8. Общая схема передачи данных для первого параллельного алгоритма матричного умножения при ленточной схеме разделения данных жүктеу/скачать 6.58 Mb. Достарыңызбен бөлісу:
|