6.2-Locality

잘 작성된 프로그램은 좋은 지역성(Locality)를 가지는 경향이 있다.
그 말은, 프로그램이 데이터를 참조할 때, 이미 전에 참조한 데이터 자체 혹은 그 근처로 접근하는 경향성이 있다는 의미이다.
이 경향성은 라고 알려져있다.
이는 수많은 하드웨어, 소프트웨어의 디자인과 성능에 영향을 끼친 중요한 개념이다.

Locality 는 크게 2가지의 형태로 구분된다.
로 구분된다.

좋은 Temporal Locality 를 가지면, 한번 참조된 메모리 위치가 가까운 미래에 여러번 참조된다.
좋은 Spatial Locality를 가지면, 한번 참조된 메모리 위치와 가까운 곳에 참조된다.

좋은 Locality 를 지닌 프로그램은 일반적으로 더 빠른 경향이 있다.

하드웨어, OS, 프로그램까지 모든 단계에서의 설계는 Locality 를 고려하게 된다.
하드웨어는 Cache Memory 의 도입을 통해,
OS는 Main Memory에 Caching 의 기능 도입을 통해,
애플리케이션 단계에서는 예를 들어, 웹 브라우저는 최근의 문서를 로컬 Disk 에 임시로 저장하곤한다.

6.2.1 Locality of References to Program Data

다음 코드의 Locality 를 판단해보자.

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

sum 변수의 경우, 매 Loop 에서 1번씩 참조되므로, Temporal Locality 가 높다.
반면에 Scalar, 즉 주변 메모리 위치를 참조하지 않기 때문에, Spatial Locality 는 낮다.

vector v 에는 각 원소가 순서대로 메모리에 저장되어있다.
그리고 해당 vector 를 앞에서 순차적으로 접근하므로,
함수는 Spatial Locality 가 높다.
하지만, 각 원소는 한번만 접근되기 때문에, Temporal Locality 는 낮다.

해당 함수는 각 변수가 Locality 를 잘 만족하기 때문에, 좋은 Locality 를 갖는 함수라고 결론지을 수 있다.

sumvec 처럼 배열의 원소를 순차적으로 접근하는 것을,
이라고 한다.
이 패턴은 가장 흔하면서, Spatial Locality 에서 중요한 역할을 한다.
Stride-1 Rerference Pattern 은 종종 라고도 불린다.
순차적이 아닌, 매 번째 원소를 접근하는 것은 이라고 불린다.

Stride 는 다차원 배열을 다룰 때 중요하게 작용한다.
다음의 2가지 C언어 예제를 살펴보자.

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

	int sumarraycols(int a[M][N]) {
		int sum = 0;

		for(int j = 0; j < N; j++) { // !! i, j 의 순서가 바뀜 !!
			for(int i = 0; i < M; i++)
				sum += a[i][j];
		}
		return sum;
	}

첫번째 예제(sum_array_rows) 는 높은 Locality 를 가지고 있다.
왜냐하면, C언어는 row-wise 방식의 배열을 처리하기 때문에,
주소가 0, 4, 8, 12, 16, 20 으로 Stride-1 Reference Pattern 을 지니고 있다.

반면에 두번째 예제(sum_array_cols) 는 낮은 Locality 를 가지고 있다.
row-wise 이기 때문에, 주소에 대한 접근이 0, 12, 4, 16, 8, 20 으로 Spatial Locality 가 낮다.

6.2.2 Locality of Instruction Fetches

명령어는 Memory 에 저장되어 있고, 이를 CPU가 Read(Fetch) 해야 하므로,
이에 대한 Locality 를 판단할 수 있다.

sumvec 함수에 대해,
for loop가 메모리를 연속된 순서로 실행되기 때문에, Spatial Locality 가 높다.
Loop 내부의 명령어가 여러번 실행되기 때문에, Temporal Locality 또한 높다.

코드가 데이터와 구별되는 특징은, 코드는 run-time에는 잘 변하지 않는다는 점이다.
run-time 에 CPU는 Memory 의 명령어를 읽게 되는데,
이 때, CPU는 이 명령어를 변화시키는 경우가 거의 없다.

6.2.3 Summary of Locality

이 챕터에서는 Locality 에 대한 근본적인 아이디어와 그것을 평가할 수 있는 간단한 방법을 알아봤다.

같은 변수에 대해 여러번 참조하는 프로그램은 좋은 Temporal Locality 를 가진다.
Stride-k Reference Pattern 은 k가 낮을수록, Spatial Locality 가 높다.
Loop 는 명령어 Read 관점에서, Temporal, Spatial Locality 를 모두 가진다.
Loop Body 에 명령어가 적을수록, Loop Iteration의 수가 많을수록 Locality 가 높다.

뒤에서 Cache Memory 에 대해 배우고 나서, Cache Hit 과 Miss 관점에서 다시 평가해볼 것이다.
또한 왜 높은 Locality 가 빠른 속도를 가지는지 알아본다.

Practice Problem 6.8
p[N] 은 vel 에서 3개, 그 이후로 acc 3개가 오는 것이 가장 가깝다.
따라서, d, c, b 순서로 Locality 가 높다.