6.36

 이 문제는 C코드가 실행될 때, CPU 캐시(Cache)가 어떻게 동작하는지 예측하는 능력을 평가한다.

 분석을 위해 다음 코드가 주어진다.

int x[2][128];
int i;
int sum = 0;

for(i = 0; i < 128; i++) {
   sum += x[0][i] * x[1][i];
}

 

 

다음과 같은 조건 하에 이 코드를 실행한다고 가정한다.

• int 타입의 크기는 4바이트이다.
• 배열 x의 메모리 주소 0x0에서 시작하며, 행 우선 순위(row-major order)로 저장된다.
• 아래의 모든 경우에서, 캐시는 처음에 비어 있는 상태이다.
• 메모리 접근은 배열 x의 요소들에 대해서만 발생한다. 그 외의 모든 변수들은 레지스터에 저장된다.

 

다음 가정들을 바탕으로, 각 케이스별 미스율(Miss rate)을 추정하십시오.

• A. 케이스 1: 캐시 크기는 512바이트, 직접 사상(Direct-mapped) 방식이며, 캐시 블록 크기는 16바이트라고 가정합니다. 이 경우 미스율은 얼마입니까?
• B. 케이스 2: 캐시 크기를 두 배인 1,024바이트로 늘린다면 미스율은 얼마입니까?
• C. 케이스 3: 캐시 크기는 512바이트, LRU(최근 최소 사용) 교체 알고리즘을 사용하는 2-way 세트 연관(Two-way set associative) 방식이며, 캐시 블록 크기는 16바이트라고 가정합니다. 이 캐시의 미스율은 얼마입니까?
• D. 케이스 3의 경우, 캐시 크기를 더 키우는 것이 미스율을 줄이는 데 도움이 될까요? 그 이유는 무엇입니까?
• E. 케이스 3의 경우, 더 큰 블록 크기(Block size)를 사용하는 것이 미스율을 줄이는 데 도움이 될까요? 그 이유는 무엇입니까?

 

 

 

추론

---

기본 데이터 분석

• 배열 크기 : int x[2] [128]

1행 : 128, 2행 : 128, 128 + 128 = 총 256

• 데이터 크기 : int 타입의 크기는 4바이트이다.

	0	1	...	126	127
x[0]	int	int	...	int	int
x[1]	int	int	...	int	int

 

한 행은 int가 총 128개가 있는 거와 마찬가지이니까. 4Byte * 128 = 512Byte이다.

• 메모리 배치 : x[0][0]은 0x0에서 시작하며 행 우선 순위로 지정

x[0] 행은 메모리 상에서 0 ~ 511Byte를 소유.

x[1] 행은 메모리 상에서 512 ~ 1023Byte를 소유.

• 접근 패턴 : 

1. x[0][0] * x[1][0]
2. x[0][1] * x[1][1]
3. x[0][2] * x[1][2]
4. x[0][3] * x[1][3]
5. x[0][4] * x[1][4]
6. x[0][5] * x[1][5]
...
위와 같은 순서로 두 행을 번갈아 가며 접근

---

A. 케이스 1:

조건 : 캐시 크기 512Byte, 직접 사상 방식, 캐시 블록 크기 16Byte

문제 : 미스율은 얼마인가?

 

조건 정의 : 

• 캐시 크기 512Byte

 

• 직접 사상 (Direct-mapped) 방식

직접 사상 방식의 정의 : 메모리의 특정 주소가 캐시의 정해진 단 한곳에서만 저장될 수 있도록 1:1로 매칭시켜둔 가장 단순한 캐시 매핑 구조를 의미한다.

• 캐시 블록 크기 16Byte