왜이 코드는 선형으로 스케일되지 않습니까?

Question

이 SOR 솔버 코드를 작성했습니다. 이 알고리즘이하는 일을 너무 신경 쓰지 마라. 걱정할 필요가 없다. 그러나 완전성을 위해 시스템이 얼마나 잘 조절되었는지에 따라 선형 방정식 시스템을 풀 수도 있습니다.

행당 7 개의 0이 아닌 열이있는 2097152 행의 희소 행렬 (수렴하지 않음)을 사용하여 실행합니다.

번역 : 외부 do-while 루프 10000 반복 (I는 max_iters로 전달할 값을) 수행, 중간 for는 OpenMP의 스레드 나뉘어 work_line 덩어리에 2097152 반복 분할을 수행한다. 가장 안쪽의 for 루프는 7 회 반복되지만, 적은 경우 (1 % 미만)를 제외하면 7 회 반복됩니다.

sol 값의 스레드에 데이터 종속성이 있습니다. 중간의 각 반복 for은 하나의 요소를 업데이트하지만 배열의 다른 요소 6 개까지 읽습니다. SOR은 정확한 알고리즘이 아니기 때문에 읽을 때 해당 위치의 이전 값이나 현재 값을 가질 수 있습니다 (솔버를 잘 알고 있다면 이것은 가우스 - 시델 (Gauss-Siedel)입니다. 병행). 당신이 볼 수 있듯이 그들은 항상 우리를 가르 칠 것, 그것은 100 % 병렬 문제의 종류이기

typedef struct{ 
    size_t size; 

    unsigned int *col_buffer; 
    unsigned int *row_jumper; 
    real *elements; 
} Mat; 

int work_line; 

// Assumes there are no null elements on main diagonal 
unsigned int solve(const Mat* matrix, const real *rhs, real *sol, real sor_omega, unsigned int max_iters, real tolerance) 
{ 
    real *coefs = matrix->elements; 
    unsigned int *cols = matrix->col_buffer; 
    unsigned int *rows = matrix->row_jumper; 
    int size = matrix->size; 
    real compl_omega = 1.0 - sor_omega; 
    unsigned int count = 0; 
    bool done; 

    do { 
     done = true; 
     #pragma omp parallel shared(done) 
     { 
      bool tdone = true; 

      #pragma omp for nowait schedule(dynamic, work_line) 
      for(int i = 0; i < size; ++i) { 
       real new_val = rhs[i]; 
       real diagonal; 
       real residual; 
       unsigned int end = rows[i+1]; 

       for(int j = rows[i]; j < end; ++j) { 
        unsigned int col = cols[j]; 
        if(col != i) { 
         real tmp; 
         #pragma omp atomic read 
         tmp = sol[col]; 

         new_val -= coefs[j] * tmp; 
        } else { 
         diagonal = coefs[j]; 
        } 
       } 

       residual = fabs(new_val - diagonal * sol[i]); 
       if(residual > tolerance) { 
        tdone = false; 
       } 

       new_val = sor_omega * new_val/diagonal + compl_omega * sol[i]; 
       #pragma omp atomic write 
       sol[i] = new_val; 
      } 

      #pragma omp atomic update 
      done &= tdone; 
     } 
    } while(++count < max_iters && !done); 

    return count; 
} 

는,이 병렬 지역 내부에 잠금 없기 때문에. 그건 내가 실제로 보는 것이 아니다.

내 테스트는 인텔 ® 제온 ® CPU E5-2670 v2 @ 2.50GHz, 2 프로세서, 10 코어, 하이퍼 스레드 사용, 최대 40 논리 코어에서 실행되었습니다.

첫 번째 실행시에는 work_line이 2048로 고정되었고 스레드 수는 1에서 40까지 다양했습니다 (총 40 회 실행). 이것은 각 실행의 실행 시간과 그래프 (스레드 초에서 x)

놀람 대수 곡선이고, 그래서 생각한 작업 줄 정도로 컸다 때문에, 공유 캐시 잘 사용되지 않았으므로이 프로세서의 L1 캐시가 64 바이트 (어레이의 8 배 2 배)의 업데이트를 동기화한다는 가상 파일 /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size을 파헤 쳤습니다. 그래서 나는 설정 work_line 8 : 다음

나는 8 NUMA 노점을 피하기 위해 너무 낮은 생각 work_line 16으로 설정 : 위의를 실행하는 동안

, 나는 생각 "work_line은 무엇이 좋을지 예측할 수 있습니까? 그냥 볼 수 있습니다 ..."그리고 모든 work_line이 8에서 2048, 8 단계 (즉 캐시 라인의 모든 배수, 1에서 256까지)로 실행되도록 예약되었습니다. 20에 대한 결과 및 40 개 스레드 (스레드 사이에서 나누어 중간 for 루프의 분할 초 X 크기) :

나는 더 큰 동안 낮은 work_line을 가진 경우는, 캐시 동기화에서 심하게 앓고 생각 work_line은 특정 수의 스레드를 초과하여 아무런 이점도 제공하지 않습니다 (메모리 경로가 병목 현상이라고 생각합니다).100 % 병렬로 보이는 문제가 실제 기계에서 그러한 나쁜 행동을 나타냄을 아는 것은 매우 슬픈 일입니다. 따라서 멀티 코어 시스템이 매우 잘 팔리고 있다는 확신이 들기 전에 먼저 여기에서 묻습니다.

이 코드 배율을 코어 수에 선형으로 적용하려면 어떻게해야합니까? 내가 뭘 놓치고 있니? 처음에는 보이는 것처럼 좋지 않게 만드는 문제가 있습니까?

업데이트

에 따라 제안, 나는 static과 dynamic 일정으로 모두를 테스트하지만, 아토 배열 sol에 읽기/쓰기 제거. 참고로 파란색과 주황색 선은 이전 그래프와 동일합니다 (최대 work_line = 248;까지). 노란색과 녹색 선이 새로운 선입니다. 내가 볼 수있는 것 : 은 낮은 work_line의 중요한 차이를 만듭니다. 그러나 96 후에는 dynamic의 이점이 오버 헤드를 능가하므로 속도가 빠릅니다. 원자 적 연산은 전혀 차이가 없습니다.

Answer 1

스파 스 매트릭스 벡터 곱셈은 메모리 바인딩 (here 참조)이며 간단한 루프 라인 모델로 표시 할 수 있습니다. 메모리 바운드 문제는 멀티 소켓 NUMA 시스템의 더 높은 메모리 대역폭의 이점을 얻습니다. 단, 데이터 초기화가 두 NUMA 도메인간에 분산되는 방식으로 수행되어야합니다. 행렬을 직렬로로드하고 있기 때문에 모든 메모리가 단일 NUMA 노드에 할당되어 있다고 믿을만한 이유가 있습니다. 이 경우 듀얼 소켓 시스템에서 사용할 수있는 이중 메모리 대역폭의 이점을 누릴 수 없으며 schedule(dynamic) 또는 schedule(static)을 사용하면 실제로 상관 없습니다. NUMA 노드간에 메모리 할당이 분산되도록 메모리 인터리빙 NUMA 정책을 활성화 할 수 있습니다. 따라서 각 스레드는 두 번째 CPU의 모든 스레드에 100 % 원격 메모리 액세스가되는 대신 50 %의 로컬 메모리 액세스와 50 %의 원격 메모리 액세스로 끝납니다. 정책을 사용하는 가장 쉬운 방법은 numactl을 사용하는 것입니다 :

$ OMP_NUM_THREADS=... OMP_PROC_BIND=1 numactl --interleave=all ./program ... 

OMP_PROC_BIND=1 스레드 피닝을 가능하게하고 성능을 조금 개선해야한다.

나는이 점을 지적하고 싶습니다 : 그것은 사이에 띄는 성능 차이가없는 것

done = true; 
#pragma omp parallel reduction(&:done) 
{ 
    // ... 
     if(residual > tolerance) { 
      done = false; 
     } 
    // ... 
} 

:

done = true; 
#pragma omp parallel shared(done) 
{ 
    bool tdone = true; 

    // ... 

    #pragma omp atomic update 
    done &= tdone; 
} 

이의 아마하지 매우 효율적인 재 구현입니다 두 개의 구현은 내부 루프에서 수행되는 작업의 양 때문에 발생하지만, 이식성과 가독성을 위해 기존 OpenMP 프리미티브를 다시 구현하는 것은 좋지 않습니다.

Answer 2

귀하의 내부 루프는 omp atomic read이 있고, 당신의 중간 루프는 가 (가) 읽는 중 하나에 의해 판독 된 동일 하나가 될 수있는 위치에 omp atomic write있다. OpenMP는 동일한 위치에 대한 원자 쓰기 및 읽기가 직렬화되도록 보장해야하므로 실제 명시 적 잠금이 없더라도 잠금을 도입해야 할 필요가 있습니다.

어느 것이 읽음과 충돌할지 모르는 경우가 아니면 실제로 sol 배열 전체를 잠글 필요가 있습니다. 실제로 OpenMP 프로세서가 반드시 똑똑 할 필요는 없습니다.

코드는 절대적으로 선형으로 늘어나지 않지만 코드보다 훨씬 선형 적으로 확장하는 코드가 많이 있습니다.

Answer 3

캐싱 문제가 의심됩니다. 한 스레드가 sol 배열의 값을 업데이트하면 동일한 캐시 라인을 저장하고있는 다른 CPU의 캐시를 손상시킵니다. 이렇게하면 캐시가 업데이트되어 CPU가 작동하지 않게됩니다.

Answer 4

IPCM (Intel Performance Counter Monitor)을 실행 해보십시오. 메모리 대역폭을 볼 수 있고 더 많은 코어로 최대 대역폭을 사용할 수 있는지 확인할 수 있습니다. 내 직감은 당신이 메모리 대역폭이 제한되어 있다는 것입니다.

엔벨로프 계산의 재빨리, 캐시되지 않은 읽기 대역폭은 Xeon에서 약 10GB/s입니다. 클럭이 2.5GHz 인 경우 클록 사이클 당 32 비트 워드입니다. 내부 루프는 기본적으로 루프가 오버 헤드를 발생시키는 사이클을 한 번 더 계산할 수있는 다중 추가 연산입니다. 10 개의 스레드 이후에 성능 향상을 얻지 못한다는 사실이 놀랍지는 않습니다.

Answer 5

코드에 명시 적 뮤텍스 잠금이 없어도 프로세스간에 공유 리소스가 하나 있습니다. 메모리와 버스입니다. 코드는 CPU의 모든 다른 요청을 처리하는 하드웨어이기 때문에 표시되지 않지만 그럼에도 불구하고 공유 리소스입니다.

따라서 프로세스 중 하나가 메모리에 쓸 때마다 해당 메모리 위치를 사용하는 다른 모든 프로세스에서 주 메모리에서 해당 메모리 위치를 다시로드해야하며 동일한 메모리 버스를 사용해야합니다. 메모리 버스가 포화 상태에 빠지게되는 추가 CPU 코어로 인해 성능이 향상되지 않습니다.