Ch 6-1. Locality (1): Reference to 2D Array Data

Principle of Locality

Locality를 이해하는 것은 프로그램 내에서 메모리를 효율적으로 접근하는 데에 있어서 중요하며, 이는 같은 동작을 하는 프로그램이더라도 메모리 접근에 걸리는 실행 시간 측면에서 성능 차이를 가져올 수 있는 요소이다. Locality란 크게 다음의 2가지를 말한다.

 

첫째는 temporal locality로, 한 번 참조된 메모리 영역은 이후에 여러 번 다시 참조될 가능성이 높다는 것이다. 둘째는 spatial locality로, 한 번 참조된 메모리 영역과 인접한 영역을 다시 참조할 가능성이 높다는 것이다. Memory hierarchy 상의 logic(예를 들어 cache의 set 개념이나 replacing policy 등)을 설계하는 사람들은 프로그램의 locality를 전제로 효율적인 메모리 구조를 설계할 것이고, 프로그래머 입장에서는 locality를 최대한 활용하는 프로그램을 설계하게 된다.

 

Reference to 2D Array

여기서는 2D array의 모든 요소들을 더하는 간단한 프로그램을 대상으로 locality 개념을 익혀보기로 한다. 2D array의 요소들을 접근하는 순서를 3가지 고려할 것인데, 행이 outer loop에 위치하는 row-major, 열이 outer loop에 위치하는 column-major, 그리고 이와 결과를 비교하기 위해 무작위로 접근하는 방식이다. 물론 무작위로 접근하는 경우, 모든 요소들을 더하게 되지는 않지만, 여기서는 더한 결과보다는 메모리 접근 측면을 살펴보는 것이 목적이므로 이를 상관하지는 않는다.

 

코드의 구현은 아래와 같다.

//////////////////////////////////
// 3 Types of accessing 2D array
// 1) row-major order
// 2) col-major order
// 3) random access
//////////////////////////////////

int sumarray1(int** arr) {
	int i, j, sum;
	sum = 0;
	int d, e;
	for (i = 0; i < ROW_SIZE; i++) {
		for (j = 0; j < COL_SIZE; j++) {
			sum += arr[i][j];
			d = rand();
			e = rand();
		}
	}
	return sum;
}

int sumarray2(int** arr) {
	int i, j, sum;
	sum = 0;
	int d, e;
	for (j = 0; j < COL_SIZE; j++) {
		for (i = 0; i < ROW_SIZE; i++) {
			sum += arr[i][j];
			d = rand();
			e = rand();
		}
	}
	return sum;
}

int sumarray3(int** arr) {
	int i, j, sum;
	sum = 0;
	for (i = 0; i < ROW_SIZE; i++) {
		for (j = 0; j < COL_SIZE; j++) {
			sum += arr[rand()%ROW_SIZE][rand()%COL_SIZE];
		}
	}
	return sum;
}

무작위 접근을 위해 rand() 함수를 사용하였고, 이를 위해 C 라이브러리 중 <stdlib.h>를 include해주면 된다. 여기서 3가지 함수 간의 메모리 접근 시간을 비교하는 것이 목적이므로, 1, 2번째에도 rand() 함수를 같은 횟수만큼 호출하도록 하였다. 함수 호출의 overhead를 고려하기 위함이다.

 

Analysis with Locality & Memory Hierarchy

예를 들어, 4*4 크기의 2D array를 고려해보자. C 프로그램에서 2D array는 하나의 긴 연속적인 메모리 공간에 순차적으로 할당된다. malloc() 함수로 할당할 때 row-major로 하게 되므로, 메모리 주소를 보면 0번째 행부터 시작하여 1번째 행, 2번째 행, ... 와 같은 순서로 나열되어 있다.

 

이 때, row-major는 spatial locality를 최대로 이용하는 접근 방식이다. 하나의 캐시 블록에서 첫 번째 요소에서만 miss가 발생하고, 그 다음 요소부터는 이전에 캐시에 저장해둔 블록에 접근할 수 있으므로 hit이 발생하여 효율적으로 캐시를 활용할 수 있다.

 

반면, column-major는 spatial locatliy를 활용하지 못한다. 캐시 블록이 행의 크기보다 크다면 같은 column에 대해 앞 쪽 몇 개 row를 접근할 때까지는 hit이 일부 발생하겠지만, 대부분의 경우 miss가 나서 새로운 블록을 가져오게 될 것이다.

 

Experiment Code

먼저, malloc() 함수를 통해 2D array의 메모리 공간을 할당하고, 모든 값을 임의로 1로 초기화시켰다. 그 후, 10회 씩 반복하여 실행 시간을 측정하였다. 시간 측정을 위해 <time.h> 라이브러리를 사용하였고, clock() 함수를 통해 얻은 시작과 끝 시점의 차이를 구하는 방식으로 걸린 시간을 측정하였다.

#include <stdio.h>
#include <time.h>		// clock()
#include <stdlib.h>		// rand()

#define ROW_SIZE 2000
#define COL_SIZE 2000

int main() {
	int it_cnt;
	clock_t c1, c2;
	int t1, t2, t3;
	int** arr;
	
	t1 = 0;
	t2 = 0;
	t3 = 0;
	
	// dynamically allocate 2D array using malloc()
	arr = (int**)malloc(ROW_SIZE * sizeof(int*));
    for (int i = 0; i < ROW_SIZE; i++)
        arr[i] = (int*)malloc(COL_SIZE * sizeof(int));
	
	printf("Enter iterating count: ");
	scanf("%d", &it_cnt);
	
	// Initialize array a
	for (int i = 0; i < ROW_SIZE; i++) {
		for (int j = 0; j < COL_SIZE; j++) {
			arr[i][j] = 1;
		}
	}

	// Experiment repeatedly with it_cnt times
	for (int i = 0; i < it_cnt; i++) {
		c1 = clock();
		sumarray1(arr);
		c2 = clock();
		t1 += c2 - c1;
		
		c1 = clock();
		sumarray2(arr);
		c2 = clock();
		t2 += c2 - c1;
		
		c1 = clock();
		sumarray3(arr);
		c2 = clock();
		t3 += c2 - c1;
	}

	
	printf("\n\n---------------------------------\n");
	printf("Experiment with %d, %d 2D array.\n", ROW_SIZE, COL_SIZE);
	printf("Iterating %d.\n", it_cnt);
	printf("Row-major: %d\n", t1/it_cnt);
	printf("Col-major: %d\n", t2/it_cnt);
	printf("Random access: %d\n", t3/it_cnt);

	// memory deallocation
	for (int i = 0; i < ROW_SIZE; i++)
        free(arr[i]);
 
    free(arr);
}

 

Result

2D array의 크기를 변화시키면서 실험을 반복할 수 있다.

2D array의 크기가 클수록 접근 방식에 따른 성능 차이가 더 커지는 것을 확인할 수 있다. 이는 크기가 작을 때는 캐시에 대부분의 데이터가 저장되어 있으므로, 접근 방식에 따라 cache miss의 penalty가 크게 다르지 않기 때문이다.

 

또한, random 방식이 column-major보다 더 오래 걸리는데, 그 이유는 column 방식도 아주 부분적으로는 locality를 활용하고 있기 때문이다. 같은 column에 대해 row를 순차적으로 접근하므로 여기서 일부 locality를 활용할 여지가 있기 때문에, 아예 무작위로 접근하는 random 방식보다는 더 빠르게 측정되었다.

 

참고로 위의 설명에서는 캐시-main memory의 2중 메모리 구조를 가정하였지만, 실제 memory system의 hierarchy는 더 다중화되어 있다. 따라서 정확한 설명이 될 수는 없으나, 여기서는 locality에 대한 분석을 하기 위해 간단한 2중 메모리 구조를 가정하였다.

 

참고 링크

- rand() 함수: https://www.geeksforgeeks.org/generating-random-number-range-c/

Generating random number in a range in C - GeeksforGeeks

- clock() 함수: https://www.ibm.com/docs/ko/i/7.3?topic=functions-clock-determine-processor-time 

clock() — 프로세서 시간 판별

- malloc() 함수 & 2D array 할당: https://www.geeksforgeeks.org/dynamically-allocate-2d-array-c/

How to dynamically allocate a 2D array in C? - GeeksforGeeks