중첩 루프 최적화

Question

우리는 매우 비효율적 인 프로그램이 주어지고 더 빨리 실행되도록 코드를 최적화해야하는 과제가 있습니다. 저는이 두 가지를 제외하고는 대부분 빠르게 움직이고 있습니다. 그 버그는 아주 단순하기 때문에 버그입니다. 하나는 기본적으로 2 차원 배열의 모든 값을 동일한 값으로 설정하고 기본적으로 2 차원 배열의 값을 서로 바꿉니다. 그리고 그것이 문제입니다. 그들은 대부분의 시간을 차지하지만 너무 단순하기 때문에 함수를 깨지 않고 줄이는 방법을 알아낼 수 없습니다. 그리고 다른 학생들이 우스운 속도 향상을 얻고 있기 때문에 빠르게 실행할 수 있음을 알고 있습니다. 문제의 두 부분은 다음과 같습니다.

fSetArray(int rows, int cols, float val) 
{ 
    int i, j; 
    F2D *out; 
    out = fMallocHandle(rows, cols); 

    for(i=0; i<rows; i++) 
    for(j=0; j<cols; j++) 
     subsref(out,i,j) = val; 

    return out; 

} 

중요한 부분은 두 개의 루프뿐입니다. 기본적으로, 우리는 특정 폭 (행)과 특정 높이 (cols)를 갖는 2-D 배열을 가지며 모든 값을 val로 설정합니다. 그러나 루프 중 하나를 제거 할 수있는 방법은 없습니다 (속도를 높이는 가장 좋은 방법). 내가 명백한 것을 놓치지 않는 한. cols와 rows가 같은 수인 경우, 이것은 훨씬 더 쉬울 것입니다.

fDeepCopy(F2D* in) 
{ 
    int i, j; 
    F2D* out; 
    int rows, cols; 

    rows = in->height; 
    cols = in->width; 

    out = fMallocHandle(rows, cols); 

    for(i=0; i<rows; i++) 
    for(j=0; j<cols; j++) 
     subsref(out,i,j) = subsref(in,i,j); 

    return out; 
} 

아웃 된 배열이 배열에서 항상보다 큰, 그래서 우리는 오버 플로우 또는에 대해 걱정할 필요가 없습니다 :

다른 기능입니다. 이 함수는 기본적으로 두 배열의 값을 바꾼다. 그러나 다시 한번, 너무 단순하기 때문에 더 이상 줄일 수는 없다.

샘플 크기와 서버로 인해 병렬 처리가 수행되기 전에 실제로 스레드를 작성하는 데 필요한 오버 헤드로 인해 프로그램의 속도가 느려집니다. 난 노력 했어. 이 두 함수는 너무 짧기 때문에 스레드를 하나만 만들어서 죽일 필요가 없습니다.

참고로, 이것은 기술적으로 OpenMP 프로젝트이며 우리는 병렬화를 사용해야하지만,이 두 가지 기능을 사용하면 실제로 전체 프로그램의 속도가 느려집니다. 나는 체크하기 위해 병렬 for 루프로 시간을 잰다.

편집 : 저에게 아이디어를 주신 모든 분들께 감사드립니다! 나는 그것을 지금까지 최고 속도로 달리고있다.

Answer 1

최적화 유형 중 하나는 루프 언 롤링입니다. 인덱스를 얻고, 업데이트하고, 메모리에 다시 저장하는 작업이 많기 때문에 때때로 파이프 라인이 중지되어야합니다. 이것은 기본 멀티 스레드 구현이 잘 수행되지 않았기 때문에 모든 스레드 이 아마도인데 인덱스에 대한 액세스를 위해 싸우고있었습니다.

다중 스레드 구현을 다시 시도하려면

, 그렇지 않을 경우는 스레드 수에 따라 "오프셋"압니다, 그리고 다른 나머지 계수 부문

thread 0 works on i*rows+j % (thread count) = 0 
thread 1 works on i*rows+j % (thread count) = 1 
(and so on) 

를 통해 발견 된 각 스레드 프로세스가 각 스레드가 다중 스레드 구현을 다시 시도하려면 성능을 향상시킬 수있는 몇 가지 기술이 있습니다. 때로는 단일 스레드라도 인덱스 변수를 불필요하게 지연시킬 수 있습니다 (프로세서 파이프 라인을 비효율적으로 사용하기 때문에). 이러한 유형의 문제에 대한 수정을 시도하려면 특정 숫자만큼 인덱스를 증가시키고 루프 내에서 해당 횟수만큼 메소드를 호출하십시오.

fDeepCopy(F2D* in) 
{ 
    int i, j; 
    F2D* out; 
    int rows, cols; 

    rows = in->height; 
    cols = in->width; 

    out = fMallocHandle(rows, cols); 

    for(i=0; i<rows; i++) { 
     // rewrite to ensure we don't walk off "4 long" pads 
     int j = 0; 
     int pads = (cols/4)*4; 
     for(; j < pads; j = j + 4) { 
     subsref(out,i,j) = subsref(in,i,j); 
     subsref(out,i,j+1) = subsref(in,i,j+1); 
     subsref(out,i,j+2) = subsref(in,i,j+2); 
     subsref(out,i,j+3) = subsref(in,i,j+3); 
     } 
     // process the remainders 
     for(; j < pads; j++) { 
     subsref(out,i,j) = subsref(in,i,j); 
     } 
    } 
    return out; 
} 

지금 CPU 디자이너는 점점 나아지고, 그래서 당신이 실제로 CPU가 이미 실제로 코드를 느려질 수 있습니다 당신의, 또는 이러한 기술에 대한 이러한 최적화 작업을 수행하는지 확인하기 위해 실행 프로파일 중요한입니다.

마지막으로, leverage SSE extensions, 적절한 조건 하에서 여러 값 모두 MMX 레지스터에 저장에 같은 작업을 수행 할 수 있습니다 할 수있다. 예를 들어, 어셈블리의 인라인을 사용하여 네 개의 32 비트 단정도 부동 소수점 숫자 두 세트를 MMX 레지스터에 압축하고 한 번에 대량, 네 개의 부동 소수점으로 추가를 수행 할 수 있습니다. 그래서

(16 개 운영 최적화되지 않은) 8 개의 메모리 조회, 네 개의 추가, 4 저장을 필요로

vec_res.x = v1.x + v2.x; 
vec_res.y = v1.y + v2.y; 
vec_res.z = v1.z + v2.z; 
vec_res.w = v1.w + v2.w; 

처럼 보이는 뭔가은 세 가지가 필요

movaps xmm0, [v1]   ;xmm0 = v1.w | v1.z | v1.y | v1.x 
addps xmm0, [v2]   ;xmm0 = v1.w+v2.w | v1.z+v2.z | v1.y+v2.y | v1.x+v2.x    
movaps [vec_res], xmm0 

로 대체 될 수 있습니다 작업, 최적화되지 않은. 당신이 병목 현상을 감지하고 최소한의 적절한 성능 내에서을 가지고 코드를 조정할 수 있도록

은 다시 키, 프로파일된다.

Answer 2

memset은 첫 번째 기능에 도움이됩니다.