OpenMP를 사용한 여러 수준의 병렬 처리 - 가능합니까? 똑똑한? 실용적인?

Question

저는 현재 내가 관리하는 시뮬레이션 도구를 위해 C++ 스파 스 매트릭스/수학/반복 솔버 라이브러리에서 작업하고 있습니다. 그러나 기존의 패키지를 사용하기를 원했을 것입니다. 그러나 광범위하게 조사한 후에 우리 시뮬레이터에 적합한 어떤 것도 발견되지 않았습니다 (우리는 플렉스, PetSC, 고유 및 기타 여러 가지를 보았습니다). 좋은 소식은 내 솔버와 스파 스 매트릭스 구조가 매우 효율적이고 견고하다는 것입니다. 나쁜 소식은, OpenMP를 사용하여 병렬 처리를 연구하고 학습 곡선이 약간 가파른 점입니다.

우리가 해결 한 도메인은 블록 대각선 형식으로 모여있는 하위 도메인으로 나눌 수 있습니다. 그래서 우리의 저장 방법은 서브 도메인 (예 : 압축 된 행 저장소 : CRS, 압축 대각선 저장소 : CDS, 밀도 등)에 적합한 형식으로 각각의 작은 사각형 행렬 (블록 []) 및 하위 도메인 간의 연결성을 설명하는 배경 매트릭스 (현재 CRS 사용).

대부분의 (모든?) 반복 솔버에서 "핫스팟"은 매트릭스 벡터 곱셈 연산이며 이는 내 라이브러리에도 해당됩니다. 따라서 저는 MxV 루틴을 최적화하는 데 주력했습니다. 블록 대각 구조로 될 M * X = B에 대한 의사 코드는 다음과

가

b=background_matrix*x 
start_index = 1; 
end_index = 0; 
for(i=1:number of blocks) { 
    end_index=start_index+blocks[i].numRows(); 
    b.range(start_index, end_index) += blocks[i] * x.range(start_index, end_index); 
    start_index = end_index+1; 
} 

background_matrix 백그라운드 인

은 (CRS) 행렬 블록은 서브 도메인 매트릭스 어레이 및 .range이고 시작 인덱스에서 종료 인덱스까지 벡터 부분을 반환합니다.

분명히 루프는 병렬 처리가 가능하며 루프의 다른 반복과는 독립적입니다 (범위는 겹치지 않습니다). 일반적인 시스템에 10-15 개의 블록이 있기 때문에 실제로 4+ 스레드가 큰 차이를 만듭니다.

병렬 처리가 좋은 옵션으로 여겨지는 다른 장소는 각 하위 도메인 저장소 체계 (위의 코드에서 1 번과 6 번에서 호출)에 대한 MxV 작업입니다. 병렬화 CRS, CDS 및 조밀 한 행렬 MxV 조작에는 많은 것들이 있습니다. 일반적으로 스레드 2 개를 추가하면 더 많은 스레드가 추가되므로 성능이 크게 향상됩니다.

나는 위의 코드에 대해 블록 루프에서 4 개의 스레드가 사용되고, 각 스레드는 하위 도메인 해결을 위해 2 개의 스레드를 사용한다는 계획을 세우고 있습니다. 그러나 OpenMP를 사용하여 스레드 풀을 관리하는 방법을 알 수는 없습니다. openmp for 루프에서 스레드 수를 제한 할 수 있습니까? 이 다중 레벨 병렬 처리가 실제로 의미가있는 것입니까? (마지막에 모든 방법을 읽어 주셔서 감사!) 다른 주시면 감사하겠습니다 제가 여기에 제안했습니다에 대한 생각

Answer 1

설명하는 모든 사항은 구현에 따라 다릅니다.

openmp for 루프의 스레드 수를 제한 할 수 있습니까?

예. 그렇게하는 방법에는 여러 가지가 있습니다. omp_set_nested(1);을 설정하고 바깥 쪽 루프에는 #pragma omp parallel for num_threads(4) 또는 이와 비슷한 것을 사용하고 안쪽 루프에는 #pragma omp parallel for num_threads(2) 지시문을 사용하십시오.이렇게하면 8 개의 스레드가 제공됩니다 (구현에 따라 코어가 8 개 미만인 경우 OMP_THREAD_LIMIT을 설정해야 할 수도 있음)

또는 수동으로 루프를 풀 수 있습니다.

#pragma omp parallel sections { 
    #pragma omp section 
    do your stuff for the first part, nest parallel region again 
    #pragma omp section 
    and so on for the other parts 
} 

같은 것을 사용하여 당신은 #pragma omp task와의 OpenMP 3.0 때로는 더 효율적으로 같은 일을 할 수 있습니다.

또는 8 개의 스레드를 시작하고 병렬 섹션에서 현재 스레드 번호를 가져 와서 스레드 번호를 기반으로 수동으로 예약하십시오.

마지막으로 완벽하게 중첩 된 루프가있는 경우 (루프가 완전히 중첩 된 경우 실제 할당이 가장 안쪽 루프에서만 발생하는 경우) 모든 것을 단일 루프로 다시 작성할 수 있습니다. 기본적으로 두 개의 이터레이터 i과 j을 하나의 큰 이터레이터 (i, j)에 넣으십시오. 이것은 지역성을 줄여 성능을 저하시킬 수 있습니다.

이 다중 레벨 병렬 처리는 실제로 의미가있는 것입니까?

그것은 당신 스스로 알아야합니다. 일반적으로 다중 레벨 병렬 처리는 문제를보다 확장 가능하게 만듭니다. 그러나 스케줄링은 더 복잡 할 수 있습니다. 이 paper은 흥미로울 것입니다.

스레드 수를 수동으로 설정하는 것과 관련하여 : 스레드 수를 설정하는 주요 이점은 스케줄링 할 때 문제에 대한 특정 지식을 사용할 수 있다는 것입니다. 따라서 오버 헤드를 줄이고 실행되는 코드의 지역성을 높일 수 있으므로 캐시 히트가 많아지고 주 메모리 I/O가 줄어 듭니다.

중첩 된 병렬 처리에서 스레드 수를 수동으로 설정하는 주된 단점은 추가 작업이 수행 될 수 있지만 () 가장 안쪽 루프의 스레드가 암시 적 장벽에서 대기 중일 수 있다는 것입니다. 또한 거친 병렬 처리가 잘 확장되지 않습니다. 따라서 외부 루프의 루프 내에서 실행 시간이 매우 다른 경우에는 단순히 4 개의 스레드로 분할하는 것보다 더 유연하게 예약해야합니다.

다른 생각

는 SIMD와 MXV을하고 약하지만 당신이 되세요. 아키텍처에 따라 2-4의 속도 향상이 가능합니다. 나는 당신을 위해 이것을 presentation에 빨리 googled했다.

MxV의 경우, loop tiling, register and cache blocking 및 관련 기술은 데이터 지역을 증가시키고 다른 문제를 감소시킬 수있다. 거짓 공유. 이 book, 11 장 (미리 볼 수 있음)은 데이터 액세스를 재구성하는 방법에 대한 몇 가지 추가 아이디어를 제공합니다.

Answer 2

왜

등록 OpenMP.org에서 전문가를 통해 물어에서 로그인하지 : http://openmp.org/forum/viewforum.php?f=3