병렬 알고리즘-행렬 곱셈

행렬은 고정 된 수의 행과 열로 배열 된 숫자 및 비 숫자 데이터 집합입니다. 행렬 곱셈은 병렬 계산에서 중요한 곱셈 설계입니다. 여기서는 메쉬 및 하이퍼 큐브와 같은 다양한 통신 네트워크에서 행렬 곱셈의 구현에 대해 설명합니다. 메시와 하이퍼 큐브는 네트워크 연결성이 높기 때문에 링 네트워크와 같은 다른 네트워크보다 빠른 알고리즘을 허용합니다.

메시 네트워크

노드 집합이 p 차원 그리드를 형성하는 토폴로지를 메시 토폴로지라고합니다. 여기에서 모든 모서리는 그리드 축에 평행하고 모든 인접 노드는 서로 통신 할 수 있습니다.

총 노드 수 = (행의 노드 수) × (열의 노드 수)

메쉬 네트워크는 다음 요소를 사용하여 평가할 수 있습니다.

Diameter
이등분 너비

Diameter − 메시 네트워크에서 가장 긴 distance두 노드 사이의 지름이 있습니다. p 차원 메쉬 네트워크kP 노드의 지름은 p(k–1).

Bisection width − Bisection width는 메쉬 네트워크를 두 개의 절반으로 나누기 위해 네트워크에서 제거해야하는 최소 가장자리 수입니다.

메시 네트워크를 사용한 행렬 곱셈

랩 어라운드 연결이있는 2D 메시 네트워크 SIMD 모델을 고려했습니다. 특정 시간에 n ² 프로세서를 사용하여 두 개의 n × n 어레이를 곱하는 알고리즘을 설계합니다 .

행렬 A와 B에는 각각 요소 a _ij 와 b _ij가 있습니다. 처리 요소 PE _ij 는 a _ij 및 b _ij를 나타냅니다 . 모든 프로세서가 곱할 요소 쌍을 갖도록 행렬 A와 B를 배열하십시오. 행렬 A의 요소는 왼쪽 방향으로 이동하고 행렬 B의 요소는 위쪽 방향으로 이동합니다. 행렬 A와 B의 요소 위치에서의 이러한 변화는 곱할 새로운 값 쌍인 각 처리 요소 PE를 나타냅니다.

알고리즘의 단계

두 행렬을 엇갈리게 만듭니다.
모든 제품 계산, a _ik × b _kj
2 단계가 완료되면 합계를 계산합니다.

연산

Procedure MatrixMulti

Begin
   for k = 1 to n-1
	
   for all Pij; where i and j ranges from 1 to n
      ifi is greater than k then
         rotate a in left direction
      end if
		
   if j is greater than k then
      rotate b in the upward direction
   end if
	
   for all Pij ; where i and j lies between 1 and n
      compute the product of a and b and store it in c
   for k= 1 to n-1 step 1
   for all Pi;j where i and j ranges from 1 to n
      rotate a in left direction
      rotate b in the upward direction
      c=c+aXb
End

Hypercube 네트워크

하이퍼 큐브는 가장자리가 서로 수직이고 길이가 같은 n 차원 구조입니다. n 차원 하이퍼 큐브는 n 큐브 또는 n 차원 큐브라고도합니다.

^2k 노드 가있는 Hypercube의 기능

지름 = k
이등분 너비 = ^2k–1
모서리 수 = k

Hypercube 네트워크를 사용한 행렬 곱셈

Hypercube 네트워크의 일반 사양 −

허락하다 N = 2^m총 프로세서 수입니다. 프로세서를 P _0, P ₁ … ..P _N-1이라고 합니다.
i와 i ^b 를 두 개의 정수 (0 <i, i ^b <N-1)로 지정하고 이진 표현은 위치 b, 0 <b <k–1에서만 다릅니다.
두 개의 n × n 행렬, 행렬 A와 행렬 B를 고려해 보겠습니다.
Step 1− 행렬 A와 행렬 B의 요소는 위치 i, j, k의 프로세서가 _ji 및 b _ik를 갖도록 n ^{3 개의} 프로세서에 할당됩니다 .
Step 2 − (i, j, k) 위치에있는 모든 프로세서가 제품을 계산합니다.

C (i, j, k) = A (i, j, k) × B (i, j, k)
Step 3 − 0 ≤ i ≤ n-1 (0 ≤ j, k <n-1)에 대한 합 C (0, j, k) = ΣC (i, j, k).