4 중첩 된 "for"루프 최적화

Question

저는 C++로 2D 수치 모델을 개발하고 있습니다. 코드 속도를 늦추는 특정 멤버 함수의 속도를 높이고 싶습니다. 이 함수는 모델의 모든 i,j 격자 점을 반복하고 모든 격자 점에서 l 및 m을 초과하는 값으로 이중 합계를 수행해야합니다. 함수는 다음과 같습니다 :

int Class::Function(void) { 
    double loadingEta; 
    int i,j,l,m; 

    //etaLatLen=64, etaLonLen=2*64 
    //l_max = 12 

    for (i=0; i<etaLatLen; i++) { 
     for (j=0; j < etaLonLen; j++) { 
      loadingEta = 0.0; 
      for (l=0; l<l_max+1; l++) { 
       for (m=0; m<=l; m++) { 
        loadingEta += etaLegendreArray[i][l][m] * (SH_C[l][m]*etaCosMLon[j][m] + SH_S[l][m]*etaSinMLon[j][m]); 
       } 
      } 
      etaNewArray[i][j] = loadingEta; 
     } 
    } 

    return 1; 
} 

저는 루프 순서를 변경하여 속도를 높이려고했지만 아무 소용이 없었습니다. 어떤 도움이라도 대단히 감사 할 것입니다. 고맙습니다! 이러한 1 차원 배열 대신 다차원 인 경우

etaLegendreArray = new double**[etaLatLen]; 
for (int i=0; i<etaLatLen; i++) { 
    etaLegendreArray[i] = new double*[l_max+1]; 
    for (int l=0; l<l_max+1; l++) { 
     etaLegendreArray[i][l] = new double[l_max+1]; 
    } 
} 

SH_C = new double*[l_max+1]; 
SH_S = new double*[l_max+1]; 
for (int i=0; i<l_max+1; i++) { 
    SH_C[i] = new double[l_max+1]; 
    SH_S[i] = new double[l_max+1]; 
} 

etaCosMLon = new double*[etaLonLen]; 
etaSinMLon = new double*[etaLonLen]; 
for (int j=0; j<etaLonLen; j++) { 
    etaCosMLon[j] = new double[l_max+1]; 
    etaSinMLon[j] = new double[l_max+1]; 
} 

은 아마도 더 나은 것 :

편집 1 : 다음과 같이

다섯 개 배열 내 클래스의 생성자에서 할당?

Answer 1

여기에서 X-Y 지역으로 도약합니다. 알고리즘 속도를 높이기보다는 데이터 액세스 속도를 높이겠습니다.

etaLegendreArray = new double**[etaLatLen]; 
for (int i=0; i<etaLatLen; i++) { 
    etaLegendreArray[i] = new double*[l_max+1]; 
    for (int l=0; l<l_max+1; l++) { 
     etaLegendreArray[i][l] = new double[l_max+1]; 
    } 
} 

double의 3D 배열을 만들지 않습니다. double 배열에 대한 포인터 배열에 대한 포인터 배열을 만듭니다. 각 배열은 자체 메모리 블록이며 저장소에 저장 될 위치를 알고 있습니다. 결과적으로 "poor spacial locality"이라는 데이터 구조가 생성됩니다. 구조체의 모든 조각이 그 곳곳에 흩어져있을 수 있습니다.3D 배열에서는 가치가있는 곳을 찾기 위해 세 가지 다른 장소로 건너 뜁니다.

3D 배열을 시뮬레이션하는 데 필요한 많은 스토리지 블록이 서로 가깝지 않을 수 있기 때문에 CPU가 캐시 (고속 메모리)를 효과적으로로드하지 못하고 유용한 작업을 중단해야 할 수 있습니다 더 느린 저장소, 아마도 RAM을 훨씬 더 자주 액세스하려고하고 있습니다. 다음은 좋은 수준의 article on how much this can hurt 성능입니다.

반면에 전체 배열이 하나의 메모리 블록에 있고 "인접"이라면 CPU는 더 큰 메모리 덩어리를 읽을 수 있습니다. 아마도 모든 것을 캐시 할 수 있습니다. 프로그램이 사용할 메모리를 컴파일러가 아는 경우 플러스 하나의 큰 블록에서 모든 종류의 그루비 최적화를 수행하여 프로그램을 더 빠르게 만들 수 있습니다.

그렇다면 우리는 어떻게 하나의 메모리 블록 인 3D 배열을 얻을 수 있습니까? 크기가 정적 인 경우,이

double etaLegendreArray[SIZE1][SIZE2][SIZE3]; 

이 사건으로 보이지 않는이 메모리를 하나 개의 연속 블록되기 때문에, 그래서 당신이 원하는 무엇을, 1 차원 배열을 할당입니다 쉽다.

double * etaLegendreArray= new double [SIZE1*SIZE2*SIZE3]; 

및

etaLegendreArray[(x * SIZE2 + y) * SIZE3 + z] = data; 

가 응 모든 여분의 수학에 속도가 느려질 수한다고 같은데 손으로 배열 인덱싱 수학을? 컴파일러가 []을 사용할 때마다 그 것처럼 보이는 수학을 숨기고 있습니다. 당신은 거의 아무것도 잃지 않으며, 확실히 당신이 잃는 것만 큼 많이 쓸모가 없습니다. cache miss.

하지만 가독성을 떨어 뜨리면 처음에는 죽음을 바라지 않아도 조만간 망가질 것입니다. 그래서 1D 배열을 도우미에게 보내는 수업은 수학을 처리합니다. 그리고 일단 그렇게하면, 그 클래스가 할당과 할당 해제를 처리하도록하여 all that RAII goodness을 이용할 수 있습니다. 더 이상 for의 루프는 new 및 delete입니다. 그것은 모두 싸서 활과 묶었습니다.

Here is an example of a 2D Matrix class easily extendable to 3D. 이는 예측 가능하고 캐시 친화적 인 방식으로 필요한 기본 기능을 처리합니다.

Answer 2

CPU가이를 지원하고 컴파일러가 충분히 최적화되어 있다면 the C99 fma (융합 곱셈 - 덧셈) 함수에서 약간의 이득을 얻고 두 단계 작업 중 일부를 변환 (곱하기, 추가) 한 단계로 전환 할 수 있습니다 작업. 또한 융합 연산을 위해 부동 소수점 반올림을 한 번만 경험하기 때문에 곱셈과 덧셈에 한 번만 적용되지 않으므로 정확도가 향상됩니다.

loadingEta = fma(etaLegendreArray[i][l][m], fma(SH_C[l][m], etaCosMLon[j][m], SH_S[l][m]*etaSinMLon[j][m]), loadingEta); 

:

loadingEta += etaLegendreArray[i][l][m] * (SH_C[l][m]*etaCosMLon[j][m] + SH_S[l][m]*etaSinMLon[j][m]); 

에 (지금,이 fma에 통합 것 += 전혀 사용에주의 없음) :

가정 나는 바로 그것을 읽고 있어요, 당신은에서 가장 안쪽의 루프의 발현을 변화시킬 수 마법 같은 성능을 기대하지는 않지만 조금만 더 도움이 될 것입니다. (컴파일러가 하드웨어 명령어를 인라인 화하여 작업을 수행하기에 충분할 정도로 최적화 된 경우에만 해당합니다. 라이브러리 함수를 호출하면 컴파일러에서 개량 함수 호출 오버 헤드). 다시 말하면 두 번의 반올림 단계를 피함으로써 약간의 정확도를 향상시켜야합니다.

안녕하십니까, some compilers with appropriate compilation flags, they'll convert your original code to hardware FMA instructions for you에 있습니다. 그 옵션이 있다면, 나는 (당신이 볼 수 있듯이) fma 함수가 코드의 가독성을 감소시키는 경향이 있기 때문에 그렇게 할 것입니다.

컴파일러에서 부동 소수점 명령어의 벡터화 된 버전을 제공 할 수도 있습니다. 이는 성능을 의미있게 향상시킬 수 있습니다 (이전 링크에서 FMA로 자동 변환 참조).

대부분의 다른 개선점에는 목표, 사용되는 입력 배열의 특성 등에 대한 추가 정보가 필요합니다. 간단한 스레딩이 도움이 될 수 있습니다. OpenMP pragma는 루프 병렬 처리를 단순화하는 방법으로 볼 수 있습니다. 에스).