지역성 - Locality

지역성의 원칙 - Principle of Locality

프로그램은 데이터나 명령어에 접근할 때 최근에 접근한 데이터/명령어와 시간적으로 가깝거나 주소가 인접한 것들을에 접근할 가능성이 높다.

시간적 지역성 - Temporal Locality
최근에 참조된 데이터나 명령어는 가까운 미래에 다시 참조될 가능성이 높다.

공간적 지역성 - Spatial Locality
현재 참조 중인 데이터나 명령어의 주소와 가까운 위치에 있는 것들도 곧 참조될 가능성이 높다.

코드로 이해하기

int sum = 0;
for (int i=0; i<n; i++) // 데이터(배열) 순차적 접근
{
	sum += a[i]; // 참조한 데이터(sum) 반복적으로 접근
}
return sum;

Locality가 좋은 코드

int sum_array_rows(int a[M][N])
{
	int i, j, sum = 0;
    for (i=0; i<M; i++) //row-major
    {
    	for (j=0; j<N; j++)
        {
        	sum += a[i][j];
        }
    }
    
    return sum;
}

메모리에서 2차원 배열은 row 기준으로 저장된다.
이 코드는 row 순서대로 접근하기 때문에 메모리를 순차적으로 접근한다.

Locality가 좋지 못한 코드

int sum_array_cols(int a[M][N])
{
	int i, j, sum = 0;
    for (j=0; j<N; j++) //coloumn-major
    {
    	for (i=0; i<M; i++)
        {
        	sum += a[i][j];
        }
    }
    
    return sum;
}

2차원 배열에서 열을 기준으로 참조하게 되면 메모리를 왔다갔다 하게 된다.

Locality 개선 문제
Problem.
아래의 코드는 locality가 낮은 코드이다. 개선시켜보아라.

int sum_array_3d(int a[M][N][N])
{
	int i, j, k, sum = 0;
    
    for (i=0; i<N; i++)
    	for (j=0; j<N; j++)
        	for (k=0; k<M; k++)
            	sum += a[k][i][j];
    
    return sum;
}

배열 순회가 stride-1 reference pattern을 따르도록 코드를 수정해야 한다.

• stride-1 reference pattern?
  메모리의 연속된 주소를 1칸씩 건너뛰며 순차적으로 접근하는 패턴

C에서 배열은 row-major order로 저장된다.
가장 연속적으로 변화하는 요소는 제일 안쪽에 있는 for 루프이므로 j가 제일 안쪽 루프로 들어와야 한다.
또한 k가 변할 때 메모리 주소가 가장 크게 바뀌므로 제일 바깥쪽 루프로 빠져야한다.
따라서 개선 코드는 다음과 같다.

int sum_array_3d(int a[M][N][N])
{
	int i, j, k, sum = 0;
    
    for (k=0; k<M; k++)
    	for (i=0; i<N; i++)
        	for (j=0; j<N; j++)
            	sum += a[k][i][j];
    
    return sum;
}

---

<참고자료>
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
안성용, "시스템소프트웨어", 부산대학교