Amdahl의 법칙 : 행렬 곱셈

Question

Amdahl의 법칙을 적용하고 이론적 인 최대 속도 향상을 관찰하기 위해 병렬화 할 수있는 코드의 분수 P를 계산하려고합니다.

내 코드는 (라이브러리 Eigen을 사용하여) 행렬을 곱하는 데 대부분의 시간을 소비합니다. 이 부분을 완전히 병렬화 할 수 있을까요?

Answer 1

매트릭스가 충분히 크다면 60보다 크고 OpenMP를 사용하여 컴파일 할 수 있습니다 (예 : -fopenmp with gcc). 그러면 제품이 자동으로 병렬 처리됩니다. 그러나 행렬이 그리 크지 않은 경우 가능한 한 최고 수준에서 병렬화하는 것이 더 나은 경우가 많습니다. 그런 다음 알고리즘에서 독립적 인 작업을 식별 할 수 있는지 여부에 따라 다릅니다.

Answer 2

먼저 고유 라이브러리가 행렬 곱셈을 처리하는 방법을 고려하는 것이 적절할 것입니다.

그런 다음, 아이겐없이 매트릭스 (MXN) - 벡터 (NX1) 곱셈은 다음과 같이 작성할 수 있습니다 :

1 void mxv(int m, int n, double* a, double* b, double* c) 
2 { //a=bxc 
3 int i, j; 
4 
5 for (i=0; i<m; i++) 
6 { 
7  a[i] = 0.0; 
8  for (j=0; j<n; j++) 
9  a[i] += b[i*n+j]*c[j]; 
10 } 
11 } 

당신이 볼 수 있듯이, 두 개의 제품이 결과 벡터 a의 동일한 요소를 계산하지 않기 때문에 [] 그리고 i = 0 ... m에 대한 원소 a [i]에 대한 값의 순서가 답의 정확성에 영향을 미치지 않기 때문에 이러한 계산은 i의 색인 값에 대해 독립적으로 수행 될 수 있습니다.

그러면 앞의 루프와 같은 루프가 완전히 병렬 처리가 가능합니다. 이러한 루프에서 병렬 구현을 위해 OpenMP를 사용하면 비교적 간단합니다.