SystemSoftware - Cache Memory #3

SystemSoftware - Cache Memory #2

 

Cache 최적화에 대해서 알아보자

 

 

miss rate : cache에 찾고자 하는 정보가 없는경우.

예를 들어 hit 상태일 때 cache에서 정보를 가져오는 경우 1Cycle이 걸린다고 하면,

miss 상태라면 memory를 참조해서 정보를 가져오게 되고, 이 때 약 100Cycle걸린다. (단순 비교를 위한 cycle 수)

 

따라서 hit가 많이 발생하는 것 보다 miss가 적게 발생하는것이 훨씬 중요하다고 볼 수 있다.

---

행렬의 곱을 cache에 대해서 최적화를 시켜보자

 

행렬의 곱 예제코드

for (i=0; i<n; i++) {
	for (j=0; j<n; j++) {
		sum = 0.0;
		for (k=0; k<n; k++) 
			sum += a[i][k] * b[k][j];
		c[i][j] = sum;
	}
} 

 

 

최적화를 위해 알아야 할 것들

1. C 배열은 한 행에 있는 순서들을 순차적으로 접근한다.(row-major)
2. 하나의 행에 있는 열을 순차적으로 접근하기 좋다.

 

 

for (i = 0; i < N; i++) 
	sum += a[0][i];

위와 같은 코드는 a[0][0]  ~  a[0][N-1]까지 접근하는 동안 메모리가 서로 순차적으로 있기 때문에 처음 cache에 들어갈 때의 cold miss를 제외하고는 cache의 지역성을 활용할 수 있다.

 

---

Matrix 곱(ijk)

for (i=0; i<n; i++) {
	for (j=0; j<n; j++) {
		sum = 0.0;
		for (k=0; k<n; k++) 
			sum += a[i][k] * b[k][j];
		c[i][j] = sum;
	}
} 

3번째 for문을 돌 때

A의 miss rate는 0.25 -> 첫 번째 cold miss빼고 지역성 활용.

B의 miss rate는 1 -> 행이 이동하므로 지역성 활용 불가

 

---

Matrix 곱(ijk)

 

 

C[0][0] = A[0][0] * B[0][0] + A[0][1] * B[1][0] + A[0][2] * B[2][0]

C[0][1] = A[0][0] * B[0][1] + A[0][1] * B[1][1] + A[0][2] * B[2][1]

 

기존의 경우는 C[0][0]를 구하고, C[0][1]을 구하면서 B 배열에대한 cache의 지역성을 사용하지 못했다.

 

색깔을 구분해놓았더니 공통점이 보인다.

위 아래의 A배열이 같다는 점이고, B배열이 하나의 행에서 열이 순차적으로 증가하기 때문에 지역성을 활용할 수 있을 것 같다는 느낌이 든다.

 

for (k=0; k<n; k++) {
	for (i=0; i<n; i++) {
		r = a[i][k];
		for (j=0; j<n; j++)
			c[i][j] += r * b[k][j];
	}
}

 

위 코드는 3번째 for문을 한바퀴 돈다고 해서 C[i][j]가 완성되지 않는다.

하지만 지역성을 개선해서 B의 miss rate를 0.25로 줄일 수 있게 되었다.