Lect_6_24112015 (811483), страница 2
Текст из файла (страница 2)
Terminating.\n",SIZE);MPI_Finalize(); }Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201531Блочные параллельные алгоритмыматричного умноженияЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201532Матричное умножениеСуществует множество вариантов решения этой задачи намногопроцессорных системах.Алгоритм решения существенным образом зависит от того,производится или нет распределение матриц по процессорам,и какая топология процессоров при этом используется.Лекции спецкурс "Пар.
прогр. длявысокопроизводительных систем",24.11.201533Распределение матриц по процессамКаждая из трех матриц (A,B и С) может быть распределенаодним из способов:копии матриц находятся в каждом процессе;распределена по столбцам на одномерную сетку;распределена по строкам на одномерную сетку;распределена на двумерную или трехмернуюпроцессную сетку.Могут использоваться и различные комбинации. Всезависим от решаемой задачи.Лекции спецкурс "Пар. прогр.
длявысокопроизводительных систем",24.11.201534Распределение матриц по процессамВозможное распределение матриц:- матрица A и C – 1D распределение (ленточное, построкам)- Матрица В – 1D (ленточное, по столбцам)Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201535Умножение матрицУмножение матрицС= A * B, гдеA - n x l матрица and B l x m матрицаci,j (0 <= i < n, 0 <= j < m) вычисляются :Лекции спецкурс "Пар.
прогр. длявысокопроизводительных систем",24.11.201536Умножение матриц: C = A x BЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201537Умножение матрицы на векторc=AxbЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201538Блочное умножение матрицЛекции спецкурс "Пар.
прогр. длявысокопроизводительных систем",24.11.201539Последовательный алгоритмfor (i = 0; i < n; i++)for (j = 0; j < n; j++) {c[i][j] = 0;for (k = 0; k < n; k++)c[i][j] = c[i][j] + a[i][k] * b[k][j];}n3 операций умножения и n3 операций сложенияСложность алгоритма O(n3).Легко распараллеливаетсяЛекции спецкурс "Пар.
прогр. длявысокопроизводительных систем",24.11.201540Блочный алгоритмДелим матрицы на подматрицыПусть матрицы разделены на s^2 подматриц.Каждый блок содержит n/s x n/s элементов.Обозначим Ap,q - блок матрицы Afor (p = 0; p < s; p++)for (q = 0; q < s; q++) {Cp,q = 0;/* обнуление блоков */for (r = 0; r < m; r++)/*блочное умножение &*/Cp,q = Cp,q + Ap,r * Br,q; /*и сложение блоков*/}СтрокаCp,q = Cp,q + Ap,r * Br,q;означает умножение блоков Ap,r и Br,q, используя матричное умножениеЛекции спецкурс "Пар. прогр.
длявысокопроизводительных систем",24.11.201541Блочные алгоримы матричногоумноженияАлгоритм ФоксаАлгоритм КеннонаЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201542Параллельный алгоритм/* distribute matrices by rows. */void Parallel_matrix_mult(MATRIX_T A, MATRIX_T B, MATRIX_T C, int n){for each column of B {Allgather(column);Compute dot product of my row of A with column;}/* can distribute matrices by blocks of rows.
Also B could be distributed by* columns*/Parallel Processing43Идея алгоритма КеннонаАлгоритм Кеннона определяет порядоксуммирования членов во внутреннем циклеC(i,j) = s-1 A(i, (i j k) mod s) * B( (i j k) mod s, j )k 0таким образом, чтобы в каждом процессе на каждомшаге алгоритма находился один из блоков матриц Aи B.
Предусматривается первоначальноераспределение блоков матриц таким образом, чтобыминимизировать обмены блоками в процессевыполнения алгоритма.Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201544Алгоритм Кеннона матричного умноженияfor all (i=0 to s-1)// начальное распределение блоков матрицы AЦиклический сдвиг влево строки i матрицы A на jтак, чтобы на место A(i,j) была записана подматрица A(i,(i+j) mod s) endfor for all (i=0 to s-1) // начальное распределение блоков матрицы BЦиклический сдвиг вверх столбца j матрицы B на jтак, чтобы на место B(i,j) была записана подматрица B((i+j) mod s,j)endfor for k=0 to s-1for all (i=0 to s-1, j=0 to s-1)C(i,j) = C(i,j) + A(i,j)*B(i,j)Лекции спецкурс "Пар.
прогр. длявысокопроизводительных систем",24.11.201545Алгоритм Кеннона матричного умноженияЦиклический сдвиг влево каждой строки матрицы A на 1так,чтобы на место A(i,j) была записана подматрица A(i,(j+1) mod s)Циклический сдвиг вверх каждого столбца матрицы B на 1так,чтобы на место B(i,j) была записана подматрица B((i+1) mod s,j)end forend forЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201546Алгоритм КеннонаЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201547Схема алгоритма Кеннонаfor all (i=0 to s-1)// начальное распределение блоков матрицы AЦиклический сдвиг влево строки i матрицы A на jтак, чтобы на место A(i,j) была записана подматрица A(i,(i+j) mod s)endfor for all (i=0 to s-1) // начальное распределение блоков матрицы BЦиклический сдвиг вверх столбца j матрицы B на jтак, чтобы на место B(i,j) была записана подматрица B((i+j) mod s,j)endfor for k=0 to s-1for all (i=0 to s-1, j=0 to s-1)C(i,j) = C(i,j) + A(i,j)*B(i,j)Лекции спецкурс "Пар.
прогр. длявысокопроизводительных систем",24.11.201548Схема алгоритма КеннонаЦиклический сдвиг влево каждой строки матрицы A на 1так,чтобы на место A(i,j) была записана подматрица A(i,(j+1) mod s)Циклический сдвиг вверх каждого столбца матрицы B на 1так, чтобы на место B(i,j) была записана подматрица B((i+1)mod s,j)end forend forЛекции спецкурс "Пар. прогр.
длявысокопроизводительных систем",24.11.201549Алгоритм Кеннона: основной циклdims[0] = dims[1] = sqrt(P);periods[0] = periods[1] = 1;MPI_Cart_Create(comm,2,dims,periods,1,&comm_2d);MPI_Comm_rank(comm_2d, &my2drank);MPI_Cart_coords(comm_2d, my2drank, 2, mycoords);MPI_Cart_shift(comm_2d, 0, -1, &rightrank, &leftrank);MPI_Cart_shift(comm_2d, 1, -1, &downrank, &uprank);nlocal = n/dims[0];Лекции спецкурс "Пар.
прогр. длявысокопроизводительных систем",24.11.201550Алгоритм Кеннона: основной цикл/* Initial Matrix Alignment */MPI_Cart_shift(comm_2d, 0, -mycoords[0], &shiftsource,&shiftdest);MPI_Sendrecv_replace(a, nlocal*nlocal, MPI_DOUBLE,shiftdest, 1, shiftsource, 1, comm_2d, &status);MPI_Cart_shift(comm_2d, 1, -mycoords[1], &shiftsource,&shiftdest);MPI_Sendrecv_replace(b, nlocal*nlocal, MPI_DOUBLE,shiftdest, 1, shiftsource, 1, comm_2d, &status);Лекции спецкурс "Пар.
прогр. длявысокопроизводительных систем",24.11.201551Алгоритм Кеннона: основной цикл/* Main Computation Loop */for(i=0; i<dims[0]; i++){MatrixMultiply(nlocal,a,b,c); /* c=c+a*b*//* Shift matrix a left by one */MPI_Sendrecv_replace(a, nlocal*nlocal, MPI_DOUBLE,leftrank, 1, rightrank, 1, comm_2d, &status);/* Shift matrix b up by one */MPI_Sendrecv_replace(b, nlocal*nlocal, MPI_DOUBLE,uprank, 1, downrank, 1, comm_2d, &status);}Лекции спецкурс "Пар.
прогр. длявысокопроизводительных систем",24.11.201552Алгоритм Кеннона: основной цикл/* Restore original distribution of a and b */MPI_Cart_shift(comm_2d, 0, +mycoords[0], &shiftsource,&shiftdest);MPI_Sendrecv_replace(a, nlocal*nlocal, MPI_DOUBLE,shiftdest, 1, shiftsource, 1, comm_2d, &status);MPI_Cart_shift(comm_2d, 1, +mycoords[1], &shiftsource,&shiftdest);MPI_Sendrecv_replace(b, nlocal*nlocal, MPI_DOUBLE,shiftdest, 1, shiftsource, 1, comm_2d, &status);Лекции спецкурс "Пар. прогр.
длявысокопроизводительных систем",24.11.201553Алгоритм ФоксаЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201554Алгоритм ФоксаЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201555Алгоритм ФоксаШаг 1. Широковещательная рассылка диагонального элемента каждойстроки матрицы A по всем процессорам своей строки.Каждый процессор (i,j) выполняетC(i,j) = A(i,i)*B(i,j)Столбец матрицы B циклически сдвигается вверх по своемустолбцу, замещая элемент B(i,j).Шаг 2. Широковещательная рассылка элемента матрицы A,находящегося справа от диагонального, по всем процессорамсвоей строки.Каждый процессор (i,j) выполняетC(i,j) = C(i,i)+A(i+1,i)*B(i+1,j)Столбец матрицы B циклически сдвигается вверх по своемустолбцуШаг k. Широковещательная рассылка очередного (i+k) mod sэлемента строки матрицы A по всем процессорам своей строки.Каждый процессор (i,j) выполняет:C(i,j) = C(i,j) + A(i,(i+k) mod s)*B((i+k) mod s,j)Столбец матрицы B циклически сдвигается вверх по своемустолбцу, замещая собой текущий элемент B(i,j)Лекции спецкурс "Пар.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
