JoOnG's StOrY

#include  <stdio.h>
#include  <time.h>
#define  N 2048

main(){
      int  **a,  **b,  **c;
      register int  s,  e,  i,  j,  k, sum,  sum_col1 = 0, sum_col2 = 0;

 a = (int **)calloc(N, sizeof(int));
 b = (int **)calloc(N, sizeof(int));
 c = (int **)calloc(N, sizeof(int));

 for ( i = 0; i < N; i++ )
 {
  a[i] = (int *)calloc(N, sizeof(int));
  b[i] = (int *)calloc(N, sizeof(int));
  c[i] = (int *)calloc(N, sizeof(int));
 }

      printf("Program  Starting....\n");

      for  (i  =  0;  i  <  N;  i++){
            for  (j  =  0;  j  <  N;  j++){
                  a[i][j]  =  1;
                  b[i][j]  =  2;
                  c[i][j]  =  0;
            }
      }

    s  =  clock();
 sum = 0;
   for ( j = 0; j < N; j++ )
      {
            for ( k = j; k < N; k++ )
     {
    if ( j != k)
    {
       sum = b[j][k];
       b[j][k] = b[k][i];
       b[k][i] = sum;
    }
     }
      }
 
      for  (i  =  0;  i  <  N/2;  i++)
   {
            for  (j  =  0;  j  <  N;  j++)
   {
    sum_col1 = 0;
    sum_col2 = 0;

                  for  (k  =  0;  k  <  N/2;  k++)
      {
                       sum_col1 += (a[i*2][k*2]*b[j][k*2]) + (a[i*2][k*2+1]*b[j][k*2+1]);
        sum_col2 += (a[i*2+1][k*2]*b[j][k*2]) + (a[i*2+1][k*2+1]*b[j][k*2+1]);
      }
      c[i*2][j] = sum_col1;
      c[i*2+1][j] = sum_col2;
   }
 }
 
      e  =  clock();
      printf("time  :  %d  clocks \n",  (e-s));
      printf("time  :  %d  seconds \n",  (e-s)/CLOCKS_PER_SEC);
      printf("c[1][1]  :  %d\n",  c[1][1]);
      printf("Program  End....\n");

   for(i = 0; i < N; i++)
  {
   free(a[i]);
   free(b[i]);
   free(c[i]);
     }

     free(a);
     free(b);
     free(c);

}

[보고서 다운로드]

#include  <stdio.h>

#include  <time.h>

#define  N  512

main(){

      int  a[N][N],  b[N][N],  c[N][N];

      int  s,  e,  i,  j,  k,  sum;

      printf("Program  Starting....n");

      for  (i  =  0;  i  <  N;  i++){

            for  (j  =  0;  j  <  N;  j++){

                  a[i][j]  =  1;

                  b[i][j]  =  2;

                  c[i][j]  =  0;

            }

      }

    s  =  clock();

    //  수정해야할  코드  시작

      sum = 0;

      for ( j = 0; j < N; j++ )

      {

            for ( k = 0; k < N; k++ )

          {

                  sum = b[j][k];

                  b[j][k] = b[k][i];

                  b[k][i] = sum;

          }

      }

      for  (i  =  0;  i  <  N;  i++)

      {

            for  (j  =  0;  j  <  N;  j++)

          {

                  for  (k  =  0;  k  <  N/2;  k++)

                {

                        c[i][j]  += (a[i][k*2]*b[j][k*2]) + (a[i][k*2+1]*b[j][k*2+1]);

                }

          }

      }

      //  수정해야할  코드  끝

      e  =  clock();

      printf("time  :  %d  clocksn",  (e-s));

      printf("time  :  %d  secondsn",  (e-s)/CLOCKS_PER_SEC);

      printf("c[1][1]  :  %dn",  c[1][1]);

      printf("Program  End....n");

}

2. 설명

▷ strategy 1

1) b행렬의 가로와 세로행을 바꾼다.

이유 : b행렬을 행방향 증가로 바꾸는 이유를 예로 들어 설명하면

만약 a[0][0]을 불러오면 캐쉬에서 miss 가 나면서 메모리에서 불러온다.

이때 캐쉬에는 a[0][0]부터 a[0][512] 까지 행단위로 캐쉬에 잡히게 된다.

(컴퓨터마다 캐쉬의 크기가 조금씩 다르다.)

그래서 행단위로 읽으면 캐쉬에서 miss 가 나지 않기 때문에 좀더 빨리 읽어들일 수 있다.

하지만 열단위로 읽으면 행을 바꿀때마다 miss 가 나면서 캐쉬를 비우고 새로운 행을 캐쉬에 담게 되기 때문이다.

▷ strategy 2

1) k 값을 1/2 로 줄인다.

2) for 문을 반만큼 도는 대신에 행을 2개씩 계산한다.

이유 : loop-unrolling 기법으로 for문의 반복횟수를 줄이는 방법이다. for문은 branch의

대표적인 경우로, for문을 반으로 돌리는 대신에 같은 명령을 paste한다면 분기 예측 할

필요를 없애주기 때문에 혹시 있을지 모를 분기 예측 실패율을 막아준다.

(캐쉬와는 크게 상관은 없지만 캐쉬에 담긴 행을 2개씩 계산한다는 점에서 볼 수도 있다.)