Алгоритм Кэннона для распределенного умножения матриц

Материал из HNKN
Перейти к навигации Перейти к поиску

Алгоритм Кэннона - это распределенный алгоритм умножения матриц для двумерных сеток. Это особенно подходит для компьютеров, выложенных в сетке N × N. В то время как алгоритм Кэннона хорошо работает в однородных 2D-сетках, расширение его до гетерогенных 2D-сеток оказалось сложным.

Алгоритм[править | править код]

Главным преимуществом алгоритма является то, что его требования к хранению остаются постоянными и не зависят от количества процессоров.

  1. Рассмотрим две матрицы n × n A и B, разбитые на p блоков.
  2. A (i,j) и B(i,j) (0 ≤ i,j ≤ √p) размером (n/√p)×(n/√p) каждый.
  3. Процесс P(i,j) изначально хранит A(i,j), А B(i,j) вычисляет блок C(i,j) матрицы результатов.
  4. Начальный шаг алгоритма касается выравнивания матриц.
  5. Выровняйте блоки A и B таким образом, чтобы каждый процесс мог самостоятельно начать умножение своих локальных подматриц.
  6. Это делается путем сдвига всех подматриц A (i, j) влево (циклично) на I шагов и всех подматриц B(i , j) вверх (циклично) на j шагов.
  7. Каждый блок A перемещается на один шаг влево, а каждый блок B перемещается на один шаг вверх (циклично).
  8. Выполните следующее умножение блоков, добавьте к частичному результату, повторите, пока все блоки не будут умножены.


Cannonalgoritm.svg

Масштабирование и распределение подзадач между процессорами[править | править код]

  1. Размеры блоков матриц можно выбрать так, чтобы количество подзадач совпадало с количеством доступных процессоров p.
  2. Наиболее эффективное выполнение параллельного алгоритма Канона может быть обеспечено, когда топология сети связи представляет собой двумерную сетку.
  3. В этом случае подзадачи могут быть распределены между процессорами естественным образом:подзадача (i,j) должна быть помещена в процессор p(i,j).

Псевдокод[править | править код]

* forall i=0 to √p-1
       CShift-left A [i; :] by i 
* forall j=0 to √p-1
       Cshift-up B[: ,j] by j 
* for k=0 to √p-1
       forall i=0 to √p-1 and j=0 to √p-1
           C[i,j] += A[i,j] * B[i,j] 
           CShift-leftA[i; :] by 1 
           Cshift-up B[: ,j] by 1 
       end forall
 end for

Пример[править | править код]

Пусть A и B - две размерные квадратные матрицы размером 3*3.

Cannonexample.png

Сложность[править | править код]

1. На начальном этапе выравнивания максимальное расстояние, на которое смещается блок, равно √?-1 2.На начальном этапе выравнивания максимальное расстояние, на которое смещается блок, равно √? -1 3. Циклические операции сдвига в направлениях строк и столбцов занимают время:?????=2(ТС+twn2∕п) 4. Каждый из них? одноступенчатые сдвиги в фазе вычисления и сдвига takestime:ts+twn2∕p 5. Умножение √? подматрицы размера (n/√?)×(Н/√?) занимает время: n3/?.

Параллельное время:[править | править код]

Cannonscomlexity.png

6. Функция изоэффективности алгоритма Кэннона равна O (p^3/2).

Реализация C++[править | править код]

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <mpi.h>
#include <iostream>
int main(int argc, char* argv[])
{
	MPI_Comm cannon_comm;
	MPI_Status status;
	int rank, size;
	int shift;
	int i, j, k;
	int dims[2];
	int periods[2];
	int left, right, up, down;
	double* A, * B, * C;
	double* buf, * tmp;
	double start, end;
	unsigned int iseed = 0;
	int Nl, N;
	
	sscanf_s(argv[1],"%d",&N);
	
	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &size);
	srand(iseed);
	dims[0] = 0; dims[1] = 0;
	periods[0] = 1; periods[1] = 1;
	MPI_Dims_create(size, 2, dims);
	if (dims[0] != dims[1]) {
		if (rank == 0) printf("The number of processors must be a square.\n");
		MPI_Finalize();
		return 0;
	}
	Nl = N / dims[0];
	A = new double[N * N];
	B = new double[N * N];
	buf = new double[Nl * Nl];
	C = new double[Nl * Nl];
	for (i = 0; i < Nl; i++)
		for (j = 0; j < Nl; j++) {
			A[i * Nl + j] = 5 - (int)(10.0 * rand() / (RAND_MAX + 1.0));
			B[i * Nl + j] = 5 - (int)(10.0 * rand() / (RAND_MAX + 1.0));
			C[i * Nl + j] = 0.0;
		}
	MPI_Cart_create(MPI_COMM_WORLD, 2, dims, periods, 1, &cannon_comm);
	MPI_Cart_shift(cannon_comm, 0, 1, &left, &right);
	MPI_Cart_shift(cannon_comm, 1, 1, &up, &down);
	start = MPI_Wtime();
	for (shift = 0; shift < dims[0]; shift++) {
		// Matrix multiplication
		for (i = 0; i < Nl; i++)
			for (k = 0; k < Nl; k++)
				for (j = 0; j < Nl; j++)
					C[i * Nl + j] += A[i * Nl + k] * B[k * Nl + j];
		if (shift == dims[0] - 1) break;
		// Communication
		MPI_Sendrecv(A, Nl * Nl, MPI_DOUBLE, left, 1, buf, Nl * Nl, MPI_DOUBLE, right, 1, cannon_comm, &status);
		tmp = buf; buf = A; A = tmp;
		MPI_Sendrecv(B, Nl * Nl, MPI_DOUBLE, up, 2, buf, Nl * Nl, MPI_DOUBLE, down, 2, cannon_comm, &status);
		tmp = buf; buf = B; B = tmp;
	}
	MPI_Barrier(cannon_comm);
	end = MPI_Wtime();
	if (rank == 0) printf("Time: %.4fs\n", end - start);
	delete[] A;
	delete[] B;
	delete[] buf;
	delete[] C;
	MPI_Finalize();
	return 0;
}

Список используемых источников[править | править код]

  1. Cannon’s algorithm for distributed matrix multiplication // OpenGenis IQ URL (дата обращения: 20.10.2019).