어떻게 캐싱 기술과 성능을 향상시키기 위해

Question

나는 여기에 PDF 등의 캐싱 기술로 무력을 사용하여 가장 가까운 쌍을 발견하는 프로그램을 실행하려고 안녕하세요 : Caching Performance Stanford

내 원래의 코드는 다음과 같습니다

float compare_points_BF(int N,point *P){ 
    int i,j; 
    float distance=0, min_dist=FLT_MAX; 
    point *p1, *p2; 
    unsigned long long calc = 0; 
    for (i=0;i<(N-1);i++){ 
     for (j=i+1;j<N;j++){ 
      if ((distance = (P[i].x - P[j].x) * (P[i].x - P[j].x) + 
        (P[i].y - P[j].y) * (P[i].y - P[j].y)) < min_dist){ 
      min_dist = distance; 
      p1 = &P[i]; 
      p2 = &P[j]; 
      } 
     } 
    } 
    return sqrt(min_dist); 
} 

을 이 프로그램은 약 제공이 실행 시간 :

 N  8192 16384 32768 65536 131072 262144 524288 1048576  
seconds 0,070 0,280 1,130 5,540 18,080 72,838 295,660 1220,576 
      0,080 0,330 1,280 5,190 20,290 80,880 326,460 1318,631 

위의 프로그램의 캐시 버전은 다음과 같습니다

,

float compare_points_BF(register int N, register int B, point *P){ 
    register int i, j, ib, jb, num_blocks = (N + (B-1))/B; 
    register point *p1, *p2; 
    register float distance=0, min_dist=FLT_MAX, regx, regy; 

    //break array data in N/B blocks, ib is index for i cached block and jb is index for j strided cached block 
    //each i block is compared with the j block, (which j block is always after the i block) 
    for (i = 0; i < num_blocks; i++){ 
     for (j = i; j < num_blocks; j++){ 
      //reads the moving frame block to compare with the i cached block 
      for (jb = j * B; jb < (((j+1)*B) < N ? ((j+1)*B) : N); jb++){ 
       //avoid float comparisons that occur when i block = j block 
       //Register Allocated 
       regx = P[jb].x; 
       regy = P[jb].y; 
       for (i == j ? (ib = jb + 1) : (ib = i * B); ib < (((i+1)*B) < N ? ((i+1)*B) : N); ib++){ 
        //calculate distance of current points 
        if((distance = (P[ib].x - regx) * (P[ib].x - regx) + 
          (P[ib].y - regy) * (P[ib].y - regy)) < min_dist){ 
         min_dist = distance; 
         p1 = &P[ib]; 
         p2 = &P[jb]; 
        } 
       } 
      } 
     } 
    } 
    return sqrt(min_dist); 
} 

어떤 결과 : 우리는 실행 시간을 볼 수있는에서

Block_size = 256  N = 8192  Run time: 0.090 sec 
Block_size = 512  N = 8192  Run time: 0.090 sec 
Block_size = 1024  N = 8192  Run time: 0.090 sec 
Block_size = 2048  N = 8192  Run time: 0.100 sec 
Block_size = 4096  N = 8192  Run time: 0.090 sec 
Block_size = 8192  N = 8192  Run time: 0.090 sec 


Block_size = 256  N = 16384  Run time: 0.357 sec 
Block_size = 512  N = 16384  Run time: 0.353 sec 
Block_size = 1024  N = 16384  Run time: 0.360 sec 
Block_size = 2048  N = 16384  Run time: 0.360 sec 
Block_size = 4096  N = 16384  Run time: 0.370 sec 
Block_size = 8192  N = 16384  Run time: 0.350 sec 
Block_size = 16384  N = 16384  Run time: 0.350 sec 

Block_size = 128  N = 32768  Run time: 1.420 sec 
Block_size = 256  N = 32768  Run time: 1.420 sec 
Block_size = 512  N = 32768  Run time: 1.390 sec 
Block_size = 1024  N = 32768  Run time: 1.410 sec 
Block_size = 2048  N = 32768  Run time: 1.430 sec 
Block_size = 4096  N = 32768  Run time: 1.430 sec 
Block_size = 8192  N = 32768  Run time: 1.400 sec 
Block_size = 16384  N = 32768  Run time: 1.380 sec 

Block_size = 256  N = 65536  Run time: 5.760 sec 
Block_size = 512  N = 65536  Run time: 5.790 sec 
Block_size = 1024  N = 65536  Run time: 5.720 sec 
Block_size = 2048  N = 65536  Run time: 5.720 sec 
Block_size = 4096  N = 65536  Run time: 5.720 sec 
Block_size = 8192  N = 65536  Run time: 5.530 sec 
Block_size = 16384  N = 65536  Run time: 5.550 sec 

Block_size = 256  N = 131072  Run time: 22.750 sec 
Block_size = 512  N = 131072  Run time: 23.130 sec 
Block_size = 1024  N = 131072  Run time: 22.810 sec 
Block_size = 2048  N = 131072  Run time: 22.690 sec 
Block_size = 4096  N = 131072  Run time: 22.710 sec 
Block_size = 8192  N = 131072  Run time: 21.970 sec 
Block_size = 16384  N = 131072  Run time: 22.010 sec 

Block_size = 256  N = 262144  Run time: 90.220 sec 
Block_size = 512  N = 262144  Run time: 92.140 sec 
Block_size = 1024  N = 262144  Run time: 91.181 sec 
Block_size = 2048  N = 262144  Run time: 90.681 sec 
Block_size = 4096  N = 262144  Run time: 90.760 sec 
Block_size = 8192  N = 262144  Run time: 87.660 sec 
Block_size = 16384  N = 262144  Run time: 87.760 sec 

Block_size = 256  N = 524288  Run time: 361.151 sec 
Block_size = 512  N = 524288  Run time: 379.521 sec 
Block_size = 1024  N = 524288  Run time: 379.801 sec 

가 캐시되지 않은 코드보다 느립니다. 이것은 컴파일러 최적화 때문입니까? 코드가 좋지 않거나 단순히 타일링을 제대로 수행하지 못하는 알고리즘 때문입니까? 32 비트 실행 파일로 컴파일 된 VS 2010을 사용합니다. 미리 감사드립니다!

Answer 1

이것은 흥미로운 사례입니다. 컴파일러는 두 개의 내부 루프에서 루프 불변 호이 스팅 작업을 수행하지 못했습니다. 즉, 각각의 반복에서 다음 상태에 대한 두 개의 내부 루프 검사 :

(j+1)*B) < N ? ((j+1)*B) : N 

및

(i+1)*B) < N ? ((i+1)*B) : N 

계산 및 분파 모두 고가이고; 그러나 그들은 실제로 두 개의 내부 for-loops에 대해 루프 불변입니다. 일단 두 개의 내부 for-loops에서 수동으로 끌어 올리면 최적화되지 않은 버전 (N = 524288 일 때 10 %, N = 1048576 일 때 30 %)보다 캐시 최적화 된 버전을 더 잘 수행 할 수있었습니다.

//break array data in N/B blocks, ib is index for i cached block and jb is index for j strided cached block 
//each i block is compared with the j block, (which j block is always after the i block) 
for (i = 0; i < num_blocks; i++){ 
    for (j = i; j < num_blocks; j++){ 
     int u1 = (((j+1)*B) < N ? ((j+1)*B) : N); 
     int u2 = (((i+1)*B) < N ? ((i+1)*B) : N); 
     //reads the moving frame block to compare with the i cached block 
     for (jb = j * B; jb < u1 ; jb++){ 
      //avoid float comparisons that occur when i block = j block 
      //Register Allocated 
      regx = P[jb].x; 
      regy = P[jb].y; 
      for (i == j ? (ib = jb + 1) : (ib = i * B); ib < u2; ib++){ 
       //calculate distance of current points 
       if((distance = (P[ib].x - regx) * (P[ib].x - regx) + 
         (P[ib].y - regy) * (P[ib].y - regy)) < min_dist){ 
        min_dist = distance; 
        p1 = &P[ib]; 
        p2 = &P[jb]; 
       } 
      } 
     } 
    } 
} 

Answer 2

Tiling은 오래된 개념 일 수 있지만 오늘날에도 여전히 관련이 있습니다. 원래 코드에서 각각의 i에 대해, 내부 루프의 길이가 거기에 들어갈만큼 작 으면 캐시 된 상태에서 P [j] 요소의 대부분을 재사용 할 수 있습니다. 실제 크기는 타일링을 위해 목표로 삼을 캐시 레벨에 따라 결정되어야합니다. L1은 가장 빠른 성능을 제공하지만 L1은 작은 블록을 필요로하므로 타일링 오버 헤드가 너무 많을 수 있습니다. L2는 더 큰 타일을 허용하지만 sligthly 감소 된 성능 등등.

여기서 2 차원 타일링을 사용할 필요가 없다는 것을 유의하십시오. 이것은 매트릭스 곱셈이 아니므로 동일한 배열을 가로 지르고있는 것입니다. 일단 내부 루프를 바둑판 식으로 배열 할 수 있습니다. 일단 캐시를 오버 플로우하면 외부 루프 (i)가 캐시 된 내부 루프 요소의 현재 블록에서 끝까지 실행할 수 있습니다. 아무도 바깥 고리의 요소를 재사용하지 않기 때문에 실제로는 아무런 의미가 없습니다. (매트릭스 멀과는 대조적으로)

따라서 Point이 64 비트라고 가정하면 배열의 이러한 요소를 안전하게 맞출 수 있습니다 32k L1 또는 256k L2의 4096 개 요소에서 현재 j 블록의 범위를 벗어나면 각 블록에서 P [i]에 대해 한 번 빠뜨리지 않으면되지만 무시해도됩니다.

하지만이 설명은 여전히 ​​쓸모가 없을 수도 있습니다. 왜냐하면 충분히 좋은 컴파일러가이 모든 것을 당신을 위해 시도 할 수도 있기 때문입니다. 그래도 꽤 복잡하기 때문에 어떤 사람들이 시도해 볼 지 의심 스럽지만 재정렬이 안전하다는 것을 여기서 쉽게 증명할 수 있어야합니다. "충분히 좋은 컴파일러"는 패러독스라고 논쟁 할 수도 있지만, 그것은 논쟁의 여지가 없습니다 ...