-
과제5 연습문제 10번 35번 41번, 52번 풀이정리필요2 2008. 9. 1. 23:05
7.10 Using the series of references given in Exercise 7.9, show the hits and misses and final cache contents for a direct-mapped cache with four-word blocks and a total size of 16 words.
(series of references given in Exercise 7.9 : 2, 3, 11, 16, 21, 13, 64, 48, 19, 11, 3, 22, 4, 27, 6, 11)
7.10 문제 7.9의 참조 순서를 이용하여, 4워드 블록으로 구성되고 전체크기가 16워드인 직접 사상 캐쉬에 대해 적중이나 실패를 표시하고 캐쉬의 마지막 내용을 보여라. (문제 7.9의 참조 순서 : 2, 3, 11, 16, 21, 13, 64, 48, 19, 11, 3, 22, 4, 27, 6, 11)
우선, X를 하나의 워드로 본, 4워드 블록으로 구성되고 전체크기가 16워드인 직접 사상 캐쉬는 다음과 같다.
[ X, X, X, X ]
[ X, X, X, X ]
[ X, X, X, X ]
[ X, X, X, X ]
이 캐쉬에 대해 주어진 워드주소들로 참조를 한다.
2 (miss)
[0, 1, 2, 3]
[ X, X, X, X ]
[ X, X, X, X ]
[ X, X, X, X ]
3 (hit)
[0, 1, 2, 3]
[ X, X, X, X ]
[ X, X, X, X ]
[ X, X, X, X ]
11 (miss)
[0, 1, 2, 3]
[ X, X, X, X ]
[8, 9, 10, 11]
[ X, X, X, X ]
16 (miss)
[16, 17, 18, 19]
[ X, X, X, X ]
[8, 9, 10, 11]
[ X, X, X, X ]
21 (miss)
[16, 17, 18, 19]
[20, 21, 22, 23]
[8, 9, 10, 11]
[ X, X, X, X ]
13 (miss)
[16, 17, 18, 19]
[20, 21, 22, 23]
[8, 9, 10, 11]
[12, 13, 14, 15]
64 (miss)
[64, 65, 66, 67]
[20, 21, 22, 23]
[8, 9, 10, 11]
[12, 13, 14, 15]
48 (miss)
[48, 49, 50, 51]
[20, 21, 22, 23]
[8, 9, 10, 11]
[12, 13, 14, 15]
19 (miss)
[16, 17, 18, 19]
[20, 21, 22, 23]
[8, 9, 10, 11]
[12, 13, 14, 15]
11 (hit)
[16, 17, 18, 19]
[20, 21, 22, 23]
[8, 9, 10, 11]
[12, 13, 14, 15]
3 (miss)
[0, 1, 2, 3]
[20, 21, 22, 23]
[8, 9, 10, 11]
[12, 13, 14, 15]
22 (hit)
[0, 1, 2, 3]
[20, 21, 22, 23]
[8, 9, 10, 11]
[12, 13, 14, 15]
4 (miss)
[0, 1, 2, 3]
[4, 5, 6, 7]
[8, 9, 10, 11]
[12, 13, 14, 15]
27 (miss)
[0, 1, 2, 3]
[4, 5, 6, 7]
[23, 25, 26, 27]
[12, 13, 14, 15]
6 (hit)
[0, 1, 2, 3]
[4, 5, 6, 7]
[23, 25, 26, 27]
[12, 13, 14, 15]
11 (miss)
[0, 1, 2, 3]
[4, 5, 6, 7]
[8, 9, 10, 11]
[12, 13, 14, 15]
캐쉬의 마지막 내용은 위와 같다.
7. 35 다음의 C 프로그램은 8워드 크기의 블록(32바이트)과 256바이트의 데이터를 저장할 수 있는 캐쉬를 가진 시스템에서 수행(최적화되지 않은 상태)된다:
int i, j, c, stride, array[512];
...
for (i=0; i<10000; i++)
for (j=0; j<512; j=j+stride)
c = array[j] + 17;
배열 참조를 위한 캐쉬의 동작만을 고려하고 정수는 워드크기를 갖는다고 가정할 때, 직접 사상 방식과 stride = 256으로 가정하면 예상 실패율은 얼마인가? stride = 255이면 어떠한가? 이 두 경우의 실패율은 캐쉬가 2-way 집합 연관일 경우 어떻게 되는가?
한블록은 32kb 이고 배열 array는 int로 선언되어 하나의 항목은 4byte이다.
따라서 한 블록에는 8개의 항목이 들어간다.
배열이 처음부터 차곡차곡 들어갔다면 캐쉬는 다음과 같다.
block 0 : array[0]~array[7]
block 1 : array[8]~array[15]
block 2 : array[16]~array[23]
block 3 : array[24]~array[31]
block 4 : array[32]~array[39]
block 5 : array[40]~array[47]
block 6 : array[48]~array[55]
block 7 : array[56]~array[63]
X를 1 워드로 본,
처음 빈 캐쉬의 모습은 다음과 같다.
block 0 : [ X, X, X, X, X, X, X, X ]
block 1 : [ X, X, X, X, X, X, X, X ]
block 2 : [ X, X, X, X, X, X, X, X ]
block 3 : [ X, X, X, X, X, X, X, X ]
block 4 : [ X, X, X, X, X, X, X, X ]
block 5 : [ X, X, X, X, X, X, X, X ]
block 6 : [ X, X, X, X, X, X, X, X ]
block 7 : [ X, X, X, X, X, X, X, X ]
문제의 C 코드에서 변수 stride 가 256 일때
array[0], array[256]이 차례로 각각 10000번씩 참조된다.
처음 array[0] 참조시 캐쉬의 모습,
array[0] -> miss
block 0 : array[0]~array[7]
block 1 : [ X, X, X, X, X, X, X, X ]
block 2 : [ X, X, X, X, X, X, X, X ]
block 3 : [ X, X, X, X, X, X, X, X ]
block 4 : [ X, X, X, X, X, X, X, X ]
block 5 : [ X, X, X, X, X, X, X, X ]
block 6 : [ X, X, X, X, X, X, X, X ]
block 7 : [ X, X, X, X, X, X, X, X ]
두번째 array[256] 참조시 캐쉬의 모습,
array[256] -> miss
block 0 : array[256]~array[263]
block 1 : [ X, X, X, X, X, X, X, X ]
block 2 : [ X, X, X, X, X, X, X, X ]
block 3 : [ X, X, X, X, X, X, X, X ]
block 4 : [ X, X, X, X, X, X, X, X ]
block 5 : [ X, X, X, X, X, X, X, X ]
block 6 : [ X, X, X, X, X, X, X, X ]
block 7 : [ X, X, X, X, X, X, X, X ]
두 항목 다 같은 블록에 번갈아가며 copy되어
이렇게 각각 10000번씩 20000번 전부 MISS 난다.
20000번 실패 / 20000번 접근 따라서 0 % 성공
따라서 stride 가 256일때 Miss Rate 는 100%
stride가 255 일때, 위 코드에서
array[0], array[255], array[510] 차례로 각각 10000번씩 참조가 일어난다.
첫번째 array[0] 참조시 캐쉬의 모습,
array[0] -> miss
block 0 : array[0]~array[7]
block 1 : [ X, X, X, X, X, X, X, X ]
block 2 : [ X, X, X, X, X, X, X, X ]
block 3 : [ X, X, X, X, X, X, X, X ]
block 4 : [ X, X, X, X, X, X, X, X ]
block 5 : [ X, X, X, X, X, X, X, X ]
block 6 : [ X, X, X, X, X, X, X, X ]
block 7 : [ X, X, X, X, X, X, X, X ]
두번째 array[255] 참조시 캐쉬의 모습,
array[255] -> miss
block 0 : array[0]~array[7]
block 1 : [ X, X, X, X, X, X, X, X ]
block 2 : [ X, X, X, X, X, X, X, X ]
block 3 : [ X, X, X, X, X, X, X, X ]
block 4 : [ X, X, X, X, X, X, X, X ]
block 5 : [ X, X, X, X, X, X, X, X ]
block 6 : [ X, X, X, X, X, X, X, X ]
block 7 : array[248]~array[255]
세번째 array[510] 참조시 캐쉬의 모습,
array[510] -> miss
block 0 : array[0]~array[7]
block 1 : [ X, X, X, X, X, X, X, X ]
block 2 : [ X, X, X, X, X, X, X, X ]
block 3 : [ X, X, X, X, X, X, X, X ]
block 4 : [ X, X, X, X, X, X, X, X ]
block 5 : [ X, X, X, X, X, X, X, X ]
block 6 : [ X, X, X, X, X, X, X, X ]
block 7 : array[504]~array[510], array[511]
이렇게 초기 세번의 접근시 실패후
이어서 array[0] 참조시 캐쉬의 모습
array[0] -> hit
block 0 : array[0]~array[7]
block 1 : [ X, X, X, X, X, X, X, X ]
block 2 : [ X, X, X, X, X, X, X, X ]
block 3 : [ X, X, X, X, X, X, X, X ]
block 4 : [ X, X, X, X, X, X, X, X ]
block 5 : [ X, X, X, X, X, X, X, X ]
block 6 : [ X, X, X, X, X, X, X, X ]
block 7 : array[504]~array[510], array[511]
이런식으로
array[0]은 1번 miss, 9999번 hit
array[255]는 10000번 miss
array[510]은 10000번 miss
따라서 전체 메모리 30000번 참조 중 9999 번 hit 이므로
실패율은 20001 / 30000 * 100 = 67%
위 두가지 상황이 2-way 집합연관일 경우 실패율
2-way 집합연관일 경우 캐쉬의 모습
index 0 - block 0 : [ X, X, X, X, X, X, X, X ] block 1 : [ X, X, X, X, X, X, X, X ]
index 1 - block 2 : [ X, X, X, X, X, X, X, X ] block 3 : [ X, X, X, X, X, X, X, X ]
index 2 - block 4 : [ X, X, X, X, X, X, X, X ] block 5 : [ X, X, X, X, X, X, X, X ]
index 3 - block 6 : [ X, X, X, X, X, X, X, X ] block 7 : [ X, X, X, X, X, X, X, X ]
stride = 256 일때
array[0] 참조시 캐쉬 miss
index 0 - block 0 : array[0]~array[7] block 1 : [ X, X, X, X, X, X, X, X ]
index 1 - block 2 : [ X, X, X, X, X, X, X, X ] block 3 : [ X, X, X, X, X, X, X, X ]
index 2 - block 4 : [ X, X, X, X, X, X, X, X ] block 5 : [ X, X, X, X, X, X, X, X ]
index 3 - block 6 : [ X, X, X, X, X, X, X, X ] block 7 : [ X, X, X, X, X, X, X, X ]
array[256] 참조시 캐쉬 miss
index 0 - block 0 : array[0]~array[7] block 1 : array[256]~array[263]
index 1 - block 2 : [ X, X, X, X, X, X, X, X ] block 3 : [ X, X, X, X, X, X, X, X ]
index 2 - block 4 : [ X, X, X, X, X, X, X, X ] block 5 : [ X, X, X, X, X, X, X, X ]
index 3 - block 6 : [ X, X, X, X, X, X, X, X ] block 7 : [ X, X, X, X, X, X, X, X ]
2-way집합연관일 경우 처음 miss 후 계속 hit
array[0] 참조시 캐쉬 hit
index 0 - block 0 : array[0]~array[7] block 1 : array[256]~array[263]
index 1 - block 2 : [ X, X, X, X, X, X, X, X ] block 3 : [ X, X, X, X, X, X, X, X ]
index 2 - block 4 : [ X, X, X, X, X, X, X, X ] block 5 : [ X, X, X, X, X, X, X, X ]
index 3 - block 6 : [ X, X, X, X, X, X, X, X ] block 7 : [ X, X, X, X, X, X, X, X ]
다시 array[0] 참조시 캐쉬 hit
index 0 - block 0 : array[0]~array[7] block 1 : array[256]~array[263]
index 1 - block 2 : [ X, X, X, X, X, X, X, X ] block 3 : [ X, X, X, X, X, X, X, X ]
index 2 - block 4 : [ X, X, X, X, X, X, X, X ] block 5 : [ X, X, X, X, X, X, X, X ]
index 3 - block 6 : [ X, X, X, X, X, X, X, X ] block 7 : [ X, X, X, X, X, X, X, X ]
20000번 참조시 19998번 hit 실패율은 거의 0 %다
stride = 255 일때
array[0] 참조시 캐쉬 miss
index 0 - block 0 : array[0]~array[7] block 1 : [ X, X, X, X, X, X, X, X ]
index 1 - block 2 : [ X, X, X, X, X, X, X, X ] block 3 : [ X, X, X, X, X, X, X, X ]
index 2 - block 4 : [ X, X, X, X, X, X, X, X ] block 5 : [ X, X, X, X, X, X, X, X ]
index 3 - block 6 : [ X, X, X, X, X, X, X, X ] block 7 : [ X, X, X, X, X, X, X, X ]
array[255] 참조시 캐쉬 miss
index 0 - block 0 : array[0]~array[7] block 1 : [ X, X, X, X, X, X, X, X ]
index 1 - block 2 : [ X, X, X, X, X, X, X, X ] block 3 : [ X, X, X, X, X, X, X, X ]
index 2 - block 4 : [ X, X, X, X, X, X, X, X ] block 5 : [ X, X, X, X, X, X, X, X ]
index 3 - block 6 : array[248]~array[255] block 7 : [ X, X, X, X, X, X, X, X ]
array[510] 참조시 캐쉬 miss
index 0 - block 0 : array[0]~array[7] block 1 : [ X, X, X, X, X, X, X, X ]
index 1 - block 2 : [ X, X, X, X, X, X, X, X ] block 3 : [ X, X, X, X, X, X, X, X ]
index 2 - block 4 : [ X, X, X, X, X, X, X, X ] block 5 : [ X, X, X, X, X, X, X, X ]
index 3 - block 6 : array[248]~array[255] block 7 : array[504]~array[510], array[511]
마찬가지로 위 세 항목은 처음 miss 후 계속 hit 된다.
따라서 실패율 0 %
7.41 16-엔트리 TLB와 4KB 페이지를 가지는 프로세서가 있다. 만약 프로그램이 한번에 적어도 2MB의 메모리에 접근한다고 할때 메모리 시스템의 성능은 어떻게 되는가? 성능을 향상시킬 수 있는 어떤 방법이 있는가?
풀이->
TLB 엔트리가 16개 이고 페이지 사이즈가 4KB이면
알수있는 이 시스템의 성능은 2MB 메모리중 1/31 에 해당하는 64Kb(16 X 4Kb) 만 TLB에서 바로 접근할수 있다는 것이다.
성능향상을 위해선 TLB에서 메모리로 한번에 직접접근 할수있는 크기를 늘려야 한다.
두가지 방법이 있다.
가장쉬운 첫번째 방법은 운영체제에서 페이지 사이즈를 크게 조정하는 것이다.
예를 들어 현제 4Kb의 페이지 사이즈를 128k로 크게하면,
TLB 엔트리 수 16 X 페이지 사이즈 128k = 2Mb 로 문제의 프로그램이 요구하는 성능에 부합한다.
두번째 방법은 TLB 엔트리를 늘리거나, TLB를 바꾸는 것이다. 결국에는 프로세서를 교체하는 경우가 되어 적합하지는 않다.
7.52 컴파일러가 왜 다음과 같은 최적화를 수행하였는가?
/* before */
for ( j=0 ; j<20; j++)
for( i=0; i<200; i++)
x[i][j] = x[i][j] + l;
/* after */
for( i=0; i<200; i++)
for ( j=0 ; j<20; j++)
x[i][j] = x[i][j] + l;
캐쉬 내 공간지역성을 이용하려고,
raw major 인 C 언어는 이차원 배열을 메모리에 x[0][0], x[0][1], x[0][2] 순서로 저장하기 때문에
최적화 이전코드는 20항목마다 참조가 일어나 캐쉬블록이 hit될 가능성이 거의 없다.
최적화 코드는 한 항목마도 참조가 일어나 블록 처음항목만 miss고 캐쉬로 읽어들인 블록 끝가지의 항목은 모두 hit 다