Алгоритм умножения матрицы на вектор
Алгоритм умножения матрицы (для простоты возьмем квадратную матрицу) размерности на вектор размерности можно представить как скалярных умножений векторов, получающихся из строк матрицы на вектор . Если строки матрицы слоистым образом распределены по процессорам и вектор хранится на каждом процессоре, то параллельный алгоритм можно записать следующим образом:
Шаг 1: на
Шаг 2: на
Шаг 3:
На втором шаге на каждом процессоре параллельно вычисляются соответствующие блоки результирующего вектора , затем (если это необходимо) на третьем шаге они пересылаются на первый процессор.
Предположим, что столбцы матрицы распределены слоистым образом по процессорам. В этом случае необходимо модифицировать алгоритм с учетом хранения матрицы. Результат матрично-векторного произведения можно получить, умножив каждый столбец матрицы на соответствующий элемент вектора и сложив получившиеся вектора. Степень параллелизма этого алгоритма меньше, чем в предыдущем, и обусловлена тем, что приходится осуществлять суммирование.
Условно, по шагам алгоритм записывается следующим образом:
Шаг 1: на
Шаг 2: на
Шаг 3: на
Шаг 4:
Шаг 5: на
На втором шаге осуществляется покомпонентное умножение векторов, на третьем – частичное суммирование, на четвертом – пересылка частичных сумм на первый процессор, на последнем – завершающее суммирование.
Матрично-векторное умножение обычно является частью более широкого процесса вычислений и для выбора того или иного алгоритма главную роль играет способ хранения и в момент, когда требуется их произведение. Например, если и уже находятся в памяти -го процессора, то эффективнее использовать второй алгоритм, хотя степень параллелизма в нем ниже, чем в первом. Еще один важный фактор при выборе параллельного алгоритма - желаемое расположение результата по окончании операции умножения: во втором алгоритме вектор-результат размещается в памяти одного процессора, тогда как в первом он распределен по процессорам.
program EXAMPLE
include 'mpif.h'
integer my_id, np, comm, tag, count, ierr, n,q
integer i,j,k
integer a(100,100),b(100)
integer c(100,100),a1(100,100),a2(100,100)
integer status(MPI_STATUS_SIZE)
double precision t1,tfinish
call MPI_Init(ierr)
comm=MPI_COMM_WORLD
call MPI_Comm_rank(COMM, my_id, ierr)
call MPI_Comm_size(COMM, np, ierr)
print *, 'Process ', my_id, ' of ', np, ' is alive'
! Инициализация матриц
t1=MPI_Wtime()
call MPI_Bcast(n,1,MPI_INTEGER,0,COMM,ierr)
call MPI_Bcast(b,n,MPI_INTEGER,0,COMM,ierr)
call MPI_Scatter(a,int(n*n/np),MPI_INTEGER,a1,
* int(n*n/np),MPI_INTEGER,0,COMM,ierr)
c=0
do j=1,n,1
do i=1,int(n/np),1
do k=1,n,1
c(i+int(n/np)*my_id,j)=
*c(i+int(n/np)*my_id,j)+a1(k,i)*b(k)
end do
end do
end do
call MPI_Reduce(c,a2,n*n,MPI_INTEGER,MPI_SUM,
*0, COMM,ierr)
t1=MPI_Wtime()-t1
write(*,*) 'Dim = ',n,' the time is ',t1
call MPI_Finalize(ierr)
stop
end
Задание: Алгоритм умножения матриц
Реализовать любой вариант параллельного умножения матриц.
Пример:
Приведенные параллельные алгоритмы матрично-векторного произведения естественным образом обобщаются на задачу умножения матриц. Приведенные же ниже алгоритмы будут обсуждаться с точки зрения того, как хранились матрицы до операции произведения и после нее.
Для простоты возьмем квадратные матрицы и размерности .
Первый вариант параллельного алгоритма матричного умножения будем строить, предполагая, что матрица распределена по процессорам слоистым образом по строкам, а матрица - целиком. В этом случае искомый результат можно получить, выполнив параллельно на каждом процессоре скалярных произведений.
Приведем алгоритм:
Шаг 1: на
Шаг 2: на (причем циклы по индексам расположены в следующей последовательности
Шаг 3:
Второй вариант параллельного алгоритма матричного умножения будем строить, предполагая, что матрица распределена по процессорам слоистым образом по столбцам, а матрица - целиком. В этом случае искомый результат можно получить, выполнив параллельно на каждом процессоре умножение соответствующих столбцов матрицы на соответствующие элементы строк матрицы , затем необходимо осуществить частичное суммирование получившихся произведений и на последнем шаге, переслав матрицы с частичными суммами на один процессор, закончить суммирование. Алгоритм опустим ввиду его громоздкости и очевидности.
Возможные способы хранения исходных матриц порождают другие алгоритмы. Например, матрица распределена по процессорам слоистым образом по строкам, а матрица - целиком, или распределена по процессорам слоистым образом по столбцам, а - целиком. Алгоритмы при этом схожи с рассмотренными выше.
Возможно также построение алгоритмов, которые основаны на блочном распределении матриц и по процессорам.
Если разбиения обеих матриц на блоки согласованы, то
,
где или - миноры соответствующих матриц. Это представление можно реализовать разными алгоритмами. Пусть, например, число процессоров равно (числу миноров матрицы . При условии, что матрицы и распределены соответствующим образом по процессорам, все миноры матрицы можно вычислять одновременно.