Locality

Locality의 종류

1. temporal locality : 한번 접근한 메모리 위치를 계속해서 반복적으로 접근하는 것

2. spatial locality : 한번 접근한 메모리 위치의 주변 메모리 위치를 접근하는 것

Locality의 예시

• hardware level : 컴퓨터 디자이너가 캐시 메모리를 도입하여 최근에 참조한 instruction과 데이터를 가지고 있음에 따라 메인메모리에 대한 액세스를 빠르게 하였음

• os level
• 메인 메모리를 virtual address space에 대한 캐시로 사용
• 디스크 파일 시스템에 대해 메인 메모리를 캐시로 사용

• application program level : 웹 브라우저가 최근에 참조한 문서에 대해 로컬 디스크에 저장함에 따라 temporal locality를 이용함

int sumvec(int v[N])
{
	int i, sum = 0;
	
	for (i=0; i< N; i++)
			sum += v[i];
	return sum;
}

• 위 함수에서 sum은 temporal locality를 잘 활용하고 있음. 계속해서 똑같은걸 사용하고있으니

• sum은 scalar값이기에 spatial locality에 대한 개념은 없음

• vector v에 대해서는 순차적으로 읽기 작업을 수행하고 있고 메모리에 저장된 순서대로 접근하고 있기에 spatial locality를 잘 활용하고 있음
• 이렇게 vector의 각 요소를 순차적으로 접근하는 것을 stride-1-reference pattern(or sequential reference patterns)이라 함
• stride의 값이 커질수록 spatial locality가 줄어들게 됨

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

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

• 왼쪽의 sumarrayrows는 2차원 배열의 메모리 순서대로 접근하는 반면, sumarraycols는 메모리 순서대로 접근하지 않고 띄엄띄엄 접근하기 때문에 stride-1이 아닌 stride-N 참조 패턴이 되어버림