Программирование для многопроцессорных систем в стандарте MPI - Шпаковский Г.И., Серикова Н.В.. Программирование для многопроцессорных систем в стандарте MPI -. Организация вычислений в многопроцессорных системах
 Скачать 1.61 Mb.
|
|
Глава 7. МАТРИЧНЫЕ ЗАДАЧИ Задача умножения матриц является базовой операцией для многих приложений. В этой главе рассматриваются различные методы парал- лельного решения этой задачи [4]. 7.1. САМОПЛАНИРУЮЩИЙ АЛГОРИТМ УМНОЖЕНИЯ МАТРИЦ Рассмотрим задачу вычисления произведения матрицы на вектор, которая естественным образом обобщается на задачу умножения мат- риц. Для решения задачи используем самопланирующий алгоритм, в котором один процесс (главный) является ответственным за коорди- нацию работы других процессов (подчиненных). Cоответствующая программа представлена ниже. Для наглядности единая программа матрично-векторного умножения разбита на три части: общую часть, код главного процесса и код подчиненного процесса. В общей части программы описываются основные объекты задачи: матрица А, вектор b, результирующий вектор с, определяется число процессов (не меньше двух). Задача разбивается на две части: главный процесс (master) и подчиненные процессы. В задаче умножения матрицы на вектор единица работы, которую нужно раздать процессам, состоит из скалярного произведения стро- ки матрицы A на вектор b. program main use mpi integer MAX_ROWS, MAX_COLS, rows, cols parameter (MAX_ROWS = 1000, MAX_COLS = 1000) ! матрица А, вектор b, результирующий вектор с double precision a(MAX_ROWS,MAX_COLS), b(MAX_COLS), c(MAX_ROWS) double precision buffer (MAX_COLS), ans integer myid, master, numprocs, ierr, status (MPI_STATUS_SIZE) integer i, j, numsent, sender, anstype, row call MPI_INIT( ierr ) call MPI_COMM_RANK( MPI_COMM_WORLD, myid, ierr ) call MPI_COMM_SIZE( MPI_COMM_WORLD, numprocs, ierr ) ! главный процесс – master master = 0 ! количество строк и столбцов матрицы А rows = 10 174 cols = 100 if ( myid .eq. master ) then ! код главного процесса else ! код подчиненного процесса endif call MPI_FINALIZE(ierr) stop end Рис. 7.1. Программа умножения матрицы на вектор: общая часть Код главного процесса представлен на рис. 7.2. Сначала главный процесс передает вектор b в каждый подчиненный процесс. Затем главный процесс пересылает одну строку матрицы A в каждый подчи- ненный процесс. Главный процесс, получая результат от очередного подчиненного процесса, передает ему новую работу. Цикл заканчива- ется, когда все строки будут розданы и от каждого подчиненного про- цесса получен результат. ! инициализация А и b do 20 j = 1, cols b(j) = j do 10 i = 1, rows a(i,j) = i 10 continue 20 continue numsent = 0 ! посылка b каждому подчиненному процессу call MPI_BCAST(b, cols, MPI_DOUBLE_PRECISION, master, MPI_COMM_WORLD, ierr) ! посылка строки каждому подчиненному процессу; в TAG – номер строки = i do 40 i = 1,min(numprocs-l, rows) do 30 j = I, cols buffer(j) = a(i,j) 30 continue call MPI_SEND(buffer, cols, MPI_DOUBLE_PRECISION, i, i, MPI_COMM_WORLD, ierr) numsent = numsent + l 40 continue ! прием результата от подчиненного процесса do 70 i = 1, rows ! MPI_ANY_TAG – указывает, что принимается любая строка call MPI_RECV(ans, 1, MPI_DOUBLE_PRECISION, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, status, ierr) sender = status (MPI_SOURCE) 175 anstype = status (MPI_TAG) ! определяем номер строки c(anstype) = ans if (numsent .lt. rows) then ! посылка следующей строки do 50 j = 1, cols buffer(j) = a(numsent+l, j) 50 continue call MPI_SEND (buffer, cols, MPI_DOUBLE_PRECISION, sender, numsent+l, MPI_COMM_WORLD, ierr) numsent = numsent+l else ! посылка признака конца работы call MPI_SEND(MPI_BOTTQM, 0, MPI_DOUBLE_PRECISION,sender, 0, MPI_COMM_WORLD, ierr) endif 70 continue Рис. 7.2. Программа для умножения матрицы на вектор: код главного процесса При передаче данных из главного процесса в параметре tag ука- зывается номер передаваемой строки. Этот номер после вычисления произведения вместе с результатом будет отправлен в главный про- цесс, чтобы главный процесс знал, где размещать результат. Подчиненные процессы посылают результаты в главный процесс и параметр MPI_ANY_TAG в операции приема главного процесса ука- зывает, что главный процесс принимает строки в любой последова- тельности. Параметр status обеспечивает информацию, относящуюся к полученному сообщению. В языке Fortran это – массив целых чисел размера MPI_STATUS_SIZE . Аргумент SOURCE содержит номер процесса, который послал сообщение, по этому адресу главный про- цесс будет пересылать новую работу. Аргумент TAG хранит номер обработанной строки, что обеспечивает правильное размещение полу- ченного результата. После того как главной процесс разослал все строки матрицы А, на запросы подчиненных процессов он отвечает сообщением с отметкой 0. На рис. 7.3. представлена программа под- чиненного процесса. ! прием вектора b всеми подчиненными процессами call MPI_BCAST(b, cols, MPI_DOUBLE_PRECISION, master, MPI_COMM_WORLD, ierr) ! выход, если процессов больше количества строк матрицы if (numprocs .gt. rows) goto 200 ! прием строки матрицы 176 90 call MPI_RECV(buffer, cols, MPI_DOUBLE_PRECISION, master, MPI_ANY_TAG, MPI_COMM_WORLD, status, ierr) if (status (MPI_TAG) .eq. 0) then go to 200 ! конец работы else row = status (MPI_TAG) ! номер полученной строки ans = 0.0 do 100 i = 1, cols ! скалярное произведение векторов ans = ans+buffer(i)*b(i) 100 continue ! передача результата головному процессу call MPI_SEND(ans,1,MPI_DOUBLE_PRECISION,master,row, MPI_COMM_WORLD, ierr) go to 90 ! цикл для приема следующей строки матрицы endif 200 continue Рис. 7.3. Программа для матрично-векторного умножения: подчиненный процесс Каждый подчиненный процесс получает вектор b. Затем организу- ется цикл, состоящий в том, что подчиненный процесс получает оче- редную строку матрицы А, формирует скалярное произведение строки и вектора b, посылает результат главному процессу, получает новую строку и так далее. Обобщим вышеописанный алгоритм для умножения матриц. На рис. 7.4. представлена программа главного процесса. program main use mpi integer MAX_AROWS, MAX_ACOLS, MAX_BCOLS parameter (MAX_AROWS = 20, MAX_ACOLS = 1000, MAX_BCOLS = 20) ! матрицы А,В,С double precision a(MAX_AROWS,MAX_ACOLS), double precision b(MAX_ACOLS,MAX_BCOLS) double precision с (MAX_AROWS, MAX_BCOLS) double precision buffer (MAX_ACOLS), ans (MAX_ACOLS) double precision starttime, stoptime integer myid, master, numprocs, ierr, status (MPI_STATUS_SIZE) integer i, j , numsent, sender, anstype, row, arows, acols, brows, bcols, crows, ccols call MPI_INIT( ierr ) call MPI_COMM_RANK( MPI_COMM_WORLD, myid, ierr ) call MPI_COMM_SIZE( MPI_COMM_WORLD, numprocs, ierr ) 177 ! количество строк и столбцов матрицы A arows = 10 acols = 20 ! количество строк и столбцов матрицы В brows = 20 bcols = 10 ! количество строк и столбцов матрицы С crows = arows ccols = bcols if ( myid .eq. 0 ) then ! код главного процесса else ! код починенного процесса endif call MPI_FINALIZE(ierr) stop end Рис. 7.4. Программа умножения матриц: общая часть Программа на рис. 7.4. отличается от программы общей части на рис. 7.1. описанием основных объектов: матриц А,В,С и их размерно- стей. На рис. 7.5. представлена программа главного процесса. ! инициализация А и B do 10 j = 1, acols do 10 i = 1, arows a(i,j) = i 10 continue do 20 j = 1, bcols do 20 i = 1, brows b(i,j) = i 20 continue ! посылка матрицы В каждому подчиненному процессу do 25 i = l,bcols 25 call MPI_BCAST(b(l,i), brows, MPI_DOUBLE_PRECISION, master, MPI_COMM_WORLD, ierr) numsent = 0 ! посылка строки каждому подчиненному процессу; ! в TAG – номер строки = i для простоты полагаем arows >= numprocs – 1 do 40 i = l,numprocs-1 do 30 j = 1, acols 30 buffer(j) = a(i,j) call MPI_SEND (buffer, acols, MPI_DOUBLE_PRECISION, i, i, MPI_COMM_WORLD, ierr) 40 numsent = numsent+l 178 do 70 i = 1, crows call MPI_RECV(ans, ccols, MPI_DOUBLE_PRECISION, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, status, ierr) sender = status (MPI_SOURCE) anstype = status (MPI_TAG) do 45 j = 1, ccols 45 с(anstype, j) = ans(j) if (numsent .lt. arows) then do 50 j = 1, acols 50 buffer(j) = a(numsent+l,j) call MPI_SEND (buffer, acols, MPI_DOUBLE_PRECISION, sender, numsent+l, MPI_COMM_WORLD, ierr) numsent = numsent+l else ! посылка признака конца работы call MPI_SEND(MPI_BOTTQM, 1, MPI_DOUBLE_PRECISION, sender, 0, MPI_COMM_WORLD, ierr) endif 70 continue Рис.7.5. Умножение матриц: программа главного процесса. В главном процессе можно выделить следующие основные этапы: передачу матрицы В в каждый процесс, посылку строки матрицы A после каждого получения результирующей строки матрицы С от про- цессов. На рис. 7.6. представлена программа подчиненного процесса про- граммы умножения матриц. ! прием матрицы В каждым подчиненным процессом do 85 i = l,bcols call MPI_BCAST(b(l,i), brows, MPI_DOUBLE_PRECISION, master, MPI_COMM_WORLD, ierr) 85 continue ! прием строки матрицы А каждым подчиненным процессом 90 call MPI_RECV (buffer, acols, MPI_DOUBLE_PRECISION, master, MPI_ANY_TAG, MPI_COMM_WORLD, status, ierr) if (status (MPI_TAG) .eq. 0) then go to 200 else row = status (MPI_TAG) do 100 i = l,bcols ans(i) = 0.0 do 95 j = 1, acols ! вычисление результатов 179 ans(i) = ans(i) + buffer(j)*b(j,i) 95 continue 100 continue ! посылка результата call MPI_SEND(ans, bcols, MPI_DOUBLE_PRECISION, master, row, MPI_COMM_WORLD, ierr) go to 90 endif 200 continue Рис. 7.6. Умножение матриц: программа подчиненного процесса В подчиненном процессе основными этапами являются: получение матрицы В (операция широковещания), получение строки A, вычис- ление строки C, посылка строки результирующей матрицы C главной программе. 7.2. КЛЕТОЧНЫЙ АЛГОРИТМ УМНОЖЕНИЯ МАТРИЦ Рассмотрим другой алгоритм умножения матриц, получивший на- звание клеточного [8]. В отличие от самопланирующего алгоритма, описанного в параграфе 7.1, этот алгоритм демонстрирует использо- вание основных особенностей MPI относительно большинства других систем передач сообщений: коммуникаторов и топологии. 7.2.1. Клеточный алгоритм Пусть матрицы А = (a ij ) и B = (b ij ) имеют порядок n, число процес- сов p является полным квадратом, n нацело делится на q: p = q 2 , n ' = n/q. В клеточном алгоритме матрица распредляется по процессам по принципу шахматной доски. Будем рассматривать процессы как вир- туальную двумерную сетку размером q ×q, и каждый процесс связан с подматрицей n' × n'. Более формально можно определить так: имеется взаимно однозначное соответствие между числом процессов и частя- ми матриц: { } ( ) { } 1 , 0 : , 1 ,..., 1 , 0 : − ≤ ≤ → − q t s t s p φ Это соответствие определяет сетку процессов: процесс i работает со строками и столбцами, номера которых определяет φ (i). Процесс с номером φ -1 (s, t) назначен подматрице 180 ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ = − + − + − + − + 1 ' * ) 1 ( , 1 ' * ) 1 ( 1 ' * ) 1 ( ,' * ' * , 1 ' * ) 1 ( ' * ,' * n t n s n t n s n t n s n t n s st a a a a A и подматрице B st , определенной аналогично. В клеточном алгоритме подматрицы A rs и В st при s = 0, 1, …, q -1, перемножаются и сохраня- ются в процессе φ -1 (r; t). Например, если р=9; φ (x) = (x/3; x mod 3) и n = 6, то А будет разделена следующим образом: Процесс 0 ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ = 11 10 01 00 00 a a a a A Процесс 1 ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ = 13 12 03 02 01 a a a a A Процесс 2 ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ = 15 14 05 04 02 a a a a A Процесс 3 ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ = 31 30 21 20 10 a a a a A Процесс 4 ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ = 33 32 23 22 11 a a a a A Процесс 5 ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ = 35 34 25 24 12 a a a a A Процесс 6 ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ = 51 50 41 40 20 a a a a A Процесс 7 ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ = 53 52 43 42 21 a a a a A Процесс 8 ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ = 55 54 45 44 22 a a a a A Алгоритм клеточного умножения матриц представлен ниже: for(step = 0; step < q; step++) { 1. Выбрать подматрицу из А в каждой строке процессов. Подмат- рица, выбранная в r-й строке, есть A ru , где u = (r + step) mod q. 2. Для каждой строки процессов переслать всем другим процессам той же строки выбранную подматрицу. 3. Каждый процессе умножает полученную подматрицу из А на подматрицу из B, в настоящее время находящуюся в процессе. 4. Для каждого процесса переслать подматрицу из B в процесс, на- ходящийся выше. (В процессах первой строки осуществляется пересылка подматрицы в последнюю строку.) } 181 7.2.2. Способы создания коммуникаторов Из клеточного алгоритма следует, что было бы удобным трактовать каждую строку и каждый столбец процессов как новый коммуника- тор. Это можно организовать несколькими способами. MPI_COMM_WORLD'>Способ 1. Для иллюстрации создадим коммуникатор, который со- ставляет группа из процессов первой строки виртуальной сетки. Предположим, что MPI_COMM_WORLD состоит из p процессов, где q 2 = p. Предположим, что φ (x) = (x/q; x mod q). Тогда первая стро- ка процессов состоит из процессов с номерами 0, 1,..., q-1. Чтобы создать группу нового коммуникатора, необходимо вос- пользоваться функциями, описанными в главе 5, для создания новой группы и коммуникатора, например так, как это сделано в следующем фрагменте программы. MPI_Group MPI_GROUP_WORLD; MPI_Group first_row_group; MPI_Comm first_row_comm; int row_size; int* process_ranks; /* Создание списка процессов в новом коммуникаторе */ process_ranks = (int*) malloc(q*sizeof(int)); for (proc = 0; proc < q; proc++) process_ranks[proc] = proc; /* Получение группы MPI_COMM_WORLD */ MPI_Comm_group(MPI_COMM_WORLD, &MPI_GROUP_WORLD); /* Создание новой группы */ MPI_Group_incl(MPI_GROUP_WORLD, q, process_ranks, &first_row_group); /* Создание нового коммуникатора */ MPI_Comm_create(MPI_COMM_WORLD, first_row_group,&first_row_comm); Этот фрагмент демонстрирует способ построения нового комму- никатора. Сначала создается список процессов для нового коммуни- катора. Затем создается группа, состоящая из этих процессов. На это необходимо три команды: получение группы, связанной с MPI_COMM_WORLD ; создание группы – MPI_Group_incl; созда- ние коммуникатора – MPI_Comm_create. Результатом является ком- муникатор первой строки comm. Теперь процессы в первой строке comm могут совершать коллективные операции связи. Например, процесс 0 (в группе первой строки) может передавать A 00 другим про- цессам своей группы. Фрагмент кода программы для выполнения кол- лективной операции представлен ниже. 182 int my_rank_in_first_row; float* A_00; /* my_rank есть номер процесса в MPI_GROUP_WORLD */ if (my_rank < q) { MPI_Comm_rank( first_row_comm, &my_rank_in_first_row); /* Выделяем память для A_00, order = n_bar */ A_00 = (float*) malloc (n_bar*n_bar*sizeof(float)); if (my_rank_in_first_row == 0) { … } /* Инициализация A_00 */ MPI_Bcast(A_00, n_bar*n_bar, MPI_FLOAT, 0, first_row_comm); } В программе умножения матриц необходимо создать несколько ком- муникаторов: по одному для каждой строки процессов и по одному для каждого столбца. Это чрезвычайно трудоемко, если количество процессов большое. Используя функцию MPI_Comm_split, которая может создавать несколько коммуникаторов одновременно, можно упростить решение задачи. В качестве примера использования этой функции создадим один коммуникатор для каждой строки процессов. MPI_Comm my_row_comm; int my_row; /* my_rank есть номер процесса в MPI_COMM_WORLD. q*q = p */ my_row = my_rank/q; MPI_Comm_split( MPI_COMM_WORLD, my_row, my_rank, &my_row_comm); Единственный вызов MPI_Comm_split создает q новых коммуника- торов, имеющих одно и то же имя my_row_comm. Способ 2. В клеточном алгоритме удобно идентифицировать про- цессы в MPI_COMM_WORLD координатами квадратной сетки, то есть для каждой строки и каждого столбца сетки следует сформи- ровать собственный коммуникатор. Для этого необходимо связать квадратную сетку с MPI_COMM_WORLD. Чтобы сделать это, нуж- но определить: 1. Число размерностей сетки (равно двум). 2. Размер каждого измерения (q строк и q столбцов). 3. Периодичность каждого измерения. Эта информация определяет, является ли первая входящая величина в каждой строке или столб- це смежной с последней входящей величиной в той же строке или столбце. Так как по алгоритму необходимо циклическое смеще- 183 ние подматриц в каждом столбце, то периодичность второго изме- рения нужна. 4. MPI дает пользователю возможность выбрать систему так, чтобы оптимизировать наложение сетки процессов на структуру физиче- ских процессоров, обеспечивая в том числе и возможность пере- упорядочивания процессов в группе, лежащей в основе коммуни- катора. Из этого следует, что не обязательно сохранять порядок процессов в MPI_COMM_WORLD, нужно допустить, что сис- тема может быть переупорядочена. Чтобы создать новый коммуникатор, необходимо прежде всего вызвать функцию MPI_Cart_create с соответствующими параметра- ми. Это показано в следующм фрагменте программы. MPI_Comm grid_comm; int dimensions[2]; int wrap_around[2]; int reorder = 1; dimensions[0] = dimensions[1] = q; wrap_around[0] = wrap_around[1] = 1; MPI_Cart_create(MPI_COMM_WORLD,2,dimensions,wrap_around,reorder, grid_comm); После выполнения этого фрагмента сеточный коммуникатор comm будет содержать все процессы из MPI_COMM_WORLD (воз- можно, переупорядоченные) и иметь двумерную декартову связан- ную систему координат. Чтобы определить координаты процесса, не- обходим вызов функций – MPI_Comm_rank и MPI_Cart_coords. MPI_Cart coords: int coordinates[2], my_grid_rank; MPI_Comm_rank(grid_comm, &my_grid_rank); MPI_Cart_coords(grid_comm, my_grid_rank, 2,coordinates); MPI_Cart_rank возвращает номер в декартовом коммуникаторе процесса с декартовыми координатами. MPI_Cart_coords является обратной функцией по отношению к MPI_Cart_rank: она возвращает координаты процесса с номером rank в декартовом коммуникаторе comm Можно разбить сетку на коммуникаторы более низкого порядка. Чтобы создать коммуникатор для каждой строки сетки, можно вос- пользоваться функцией MPI_Cart_sub с соответствующими парамет- рами, что и показано ниже. 184 int varying_coords[2]; MPI_Comm row_comm; varying_coords[0] = 0; varying_coords[1] = 1; MPI_Cart_sub(grid_comm, varying_coords, row_comm); Вызов MPI_Cart_sub создает q новых коммуникаторов. Перемен- ная Varying_coords есть массив булевых элементов. Она определяет, принадлежит ли каждое измерение новому коммуникатору. Так как создаются коммуникаторы для строк сетки, каждый новый коммуни- катор состоит из процессов, полученных при фиксировании номера строки и изменения номеров столбцов. В каждом процессе новый коммуникатор возвращается в row_comm. Чтобы создать коммуника- торы для столбцов, значения для varying_coords подаются в другом порядке. Вызов функции тогда будет таким. MPI_Comm col_comm; varying_coords[0] = 1; varying_coords[1] = 0; MPI_Cart_sub(grid_comm, varying_coord, col_comm); Заметим схожесть функций MPI_Cart_sub и MPI_Comm_split. Они выполняют похожие действия, то есть разбивают коммуникатор на несколько новых. Однако MPI_Cart_sub может использоваться с коммуникатором, который имеет связанную декартову топологию, и новые коммуникаторы могут быть созданы только в том случае, ко- гда происходит фиксирование (или изменение) одного или больше размерностей старого коммуникатора. 7.2.3. Параллельная программа для клеточного алгоритма Выберем 2-й способ создания коммуникаторов для решения зада- чи умножения матриц. Опишем функцию, которая создает различные коммуникаторы и связанную с ними информацию. Так как это требует большого количества переменных и эта информация будет использо- ваться в других функциях, введем следующую структуру : typedef struct { int p; /* общее количество процессов */ MPI_Comm comm; /* коммуникатор сетки */ MPI_Comm row_comm; /* коммуникатор строки */ MPI_Comm col_comm; /* коммуникатор столбца */ int q; /* порядок сетки */ int my_row; /* номер строки */ int my_col; /* номер столбца */ 185 int my_rank; /* номер в коммуникаторе сетки */ } GRID_INFO_TYPE; Тогда подпрограмма создания коммуникаторов для решения задачи будет иметь следующий код: void Setup_grid(GRID_INFO_TYPE* grid) { int old_rank, dimensions[2], periods[2], coordinates[2], varying_coords[2]; /* определение параметров сетки */ MPI_Comm_size(MPI_COMM_WORLD, &(grid->p)); MPI_Comm_rank(MPI_COMM_WORLD, &old_rank); grid->q = (int) sqrt((double) grid->p); dimensions[0] = dimensions[1] = grid->q; periods[0] = periods[1] = 1; /*создание коммуникатора с картезианской топологии размерности 2 */ MPI_Cart_create(MPI_COMM_WORLD, 2, dimensions, periods,1, &(grid->comm)); MPI_Comm_rank(grid->comm, &(grid->my_rank)); MPI_Cart_coords(grid->comm, grid->my_rank, 2,coordinates); grid->my_row = coordinates[0]; grid->my_col = coordinates[1]; /* создание коммуникатора строки */ varying_coords[0] = 0; varying_coords[1] = 1; MPI_Cart_sub(grid->comm, varying_coords,&(grid->row_comm)); /* создание коммуникатора столбца */ varying_coords[0] = 1; varying_coords[1] = 0; MPI_Cart_sub(grid->comm, varying_coords,&(grid->col_comm)); } Ниже представлен текст обобщающей программы клеточного умно- жения матриц. LOCAL_MATRIX_TYPE – тип элементов умножае- мых матриц, DERIVED_LOCAL_MATRIX – тип перемножаемых матриц. void Mult_Matr (int n, GRID_INFO_TYPE* grid, LOCAL_MATRIX_TYPE* local_A, local_B, local_C) { LOCAL_MATRIX_TYPE* temp_A; /* порядок подматриц = n/q */ int step, bcast_root, n_bar; int source, dest, tag = 43; MPI_Status status; n_bar = n/grid->q; Set_to_zero(local_C); /* обнуление элементов результирующей матрицы */ /* вычисление адресов для циклического смещения B */ source = (grid->my_row + 1) % grid->q; dest = (grid->my_row + grid->q – 1) % grid->q; /* выделение памяти для пересылки блоков A */ temp_A = Local_matrix_allocate(n_bar); 186 for (step = 0; step < grid->q; step++) { bcast_root = (grid->my_row + step) % grid->q; if (bcast_root == grid->my_col) { MPI_Bcast(local_A,1,DERIVED_LOCAL_MATRIX,bcast_root, grid->row_comm); /* умножение подматриц */ Local_matrix_multiply(local_A, local_B,local_C); } else { MPI_Bcast(temp_A,1,DERIVED_LOCAL_MATRIX,bcast_root, grid->row_comm); /* умножение подматриц */ Local_matrix_multiply(temp_A, local_B, local_C); } /* пересылка подматриц В*/ MPI_Send(local_B, 1, DERIVED_LOCAL_MATRIX, dest, tag, grid->col_comm); MPI_Recv(local_B,1,DERIVED_LOCAL_MATRIX,source,tag, grid->col_comm, &status); } } КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ К ГЛАВЕ 7 Контрольные вопросы к 7.1 1. Объясните понятие “самопланирующий алгоритм”. 2. Можно ли в главном процессе программы умножения матрицы на вектор за- менить коллективную операцию MPI_Bcast на обычный межпроцессный об- мен MPI_Send/MPI_Recv? Как изменится код подчиненного процесса? 3. Какую функцию выполняют параметры status, tag при передаче данных в про- грамме умножения матрицы на вектор? 4. Как изменится код программы умножения матрицы на вектор, если необхо- димо умножить вектор на матрицу? 5. Можно ли в программе умножения матриц использовать другие виды комму- никаций? Контрольные вопросы к 7.2 1. В чем преимущества и недостатки двух способов создания коммуникаторов для алгоритма клеточного умножения? 2. Как определить тип DERIVED_LOCAL_MATRIX средствами MPI? 3. Чему равны значения source, tag в операциях обмена процедуры Mult_Matr ? 4. Каково минимальное количество процессов для клеточного алгоритма? 5. Проведите анализ эффективности для алгоритма клеточного умножения. 187 Задания для самостоятельной работы 7.1. Напишите программу, реализующую самопланирующий алгоритм умно- жения матрицы на вектор. Исследуйте зависимость ускорения от размеров векто- ра и матрицы и разных способов коммуникаций. 7.2. Напишите программу, реализующую самопланирующий алгоритм умно- жения матриц. Исследуйте зависимость ускорения от размеров умножаемых мат- риц и разных способов коммуникаций. 7.3. Напишите программу, реализующую алгоритм умножения матриц, при котором происходит равномерное распределение частей матрицы А по процессам, а затем независимо вычисляются части результирующей матрицы. Сравните эф- фективность этого и предыдущего алгоритмов. 7.4. Напишите программу, реализующую клеточный алгоритм умножения матриц. 7.5. Напишите программу, реализующую клеточный алгоритм умножения матриц, используя первый способ создания коммуникаторов, описанный в пара- графе 7.2. |