OpenMP 병렬 처리 트리플에 의한 행렬 곱셈 (성능 문제)

Question

OpenMP를 사용하여 행렬 곱셈을위한 프로그램을 작성했습니다. 캐시 편의를 위해 A x B (전치 행) 행 대신 X 행을 사용합니다. A x B rows x columns. 캐시 효율을 향상시킵니다. 이렇게하는 것은 흥미로운 사실입니다.이 코드에서 extern 루프를 병렬 처리하면 프로그램에서 OpenMP 지시문을 가장 안쪽 루프에 넣는 것보다 속도가 느립니다. 컴퓨터에서 시간은 10.9 vs 8.1 초입니다. 당신이 외부 루프를 병렬화 컴파일러는 그것을 알아낼 수없는 추가 잠금 장치를 추가 할 때

//A and B are double* allocated with malloc, Nu is the lenght of the matrixes 
//which are square 

//#pragma omp parallel for 
for (i=0; i<Nu; i++){ 
    for (j=0; j<Nu; j++){ 
    *(C+(i*Nu+j)) = 0.; 
#pragma omp parallel for 
    for(k=0;k<Nu ;k++){ 
     *(C+(i*Nu+j))+=*(A+(i*Nu+k)) * *(B+(j*Nu+k));//C(i,j)=sum(over k) A(i,k)*B(k,j) 
    } 
    } 
} 

Answer 1

는 적게 결과를 타격보십시오. 이것은 캐시 라인 공유를 유도하고 작업이 병렬로 실행되는 것을 방지합니다. 대신 로컬 변수를 사용하면 대부분의 쓰기가 각 코어의 L1 캐시에서 수행됩니다.

또한 restrict을 사용하면 도움이됩니다. 그렇지 않으면 컴파일러는 C에 대한 쓰기가 A 및 B을 변경하지 않는다고 보장 할 수 없습니다.

시도 :

for (i=0; i<Nu; i++){ 
    const double* const Arow = A + i*Nu; 
    double* const Crow = C + i*Nu; 
#pragma omp parallel for 
    for (j=0; j<Nu; j++){ 
    const double* const Bcol = B + j*Nu; 
    double sum = 0.0; 
    for(k=0;k<Nu ;k++){ 
     sum += Arow[k] * Bcol[k]; //C(i,j)=sum(over k) A(i,k)*B(k,j) 
    } 
    Crow[j] = sum; 
    } 
} 

은 또한, 나는 Elalfer 당신이 가장 안쪽의 루프를 병렬화 경우 감소를 필요에 대한 권리라고 생각합니다.

Answer 2

당신은 아마 데이터의 일부 종속성을 가질 수 있습니다.

대부분 외부 루프 반복이 동일한 (C+(i*Nu+j))에 기록 할 수 있으며 액세스 잠금을 추가하여 보호합니다.

컴파일러는 두 번째 루프를 병렬화 할 경우 종속성이 없음을 알 수 있습니다. 그러나 외부 루프를 병렬화하는 의존성이 없다는 것을 알아내는 것은 컴파일러에게는 그리 간단하지 않습니다.

UPDATE

일부 성능 측정.

안녕하세요. 그것은 1000 더블 * 및 +처럼 보이지 않습니다 스레드 동기화 비용을 충당하기 위해.

필자는 몇 가지 작은 테스트를 수행했으며 간단한 벡터 스칼라 곱셈은 요소 수가 10'000보다 작지 않으면 openmp에서 효과적이지 않습니다. 기본적으로, 당신의 배열은 더 커진다. openmp를 사용하면 더 많은 성능을 얻을 수있다.

내부 루프를 병렬 처리하면 다른 스레드간에 작업을 분리하고 데이터를 1'000'000 번 수집해야합니다.

추신. 인텔 ICC를 사용해보세요. 학생과 오픈 소스 프로젝트에 무료로 사용할 수 있습니다. 그 10,000 요소 배열에 대한 openmp를 사용하는 것을 기억합니다.

업데이트 2 : 감소 예를

double sum = 0.0; 
    int k=0; 
    double *al = A+i*Nu; 
    double *bl = A+j*Nu; 
    #pragma omp parallel for shared(al, bl) reduction(+:sum) 
    for(k=0;k<Nu ;k++){ 
     sum +=al[k] * bl[k]; //C(i,j)=sum(over k) A(i,k)*B(k,j) 
    } 
    C[i*Nu+j] = sum;