1. 개요

이번 프로젝트를 통해 수업에서 배웠던 Cache 구조와 성능을 다수의 실험을 통해 확인한다.  실험을 위해 Wisconsin 대학에서 개발한 Dinero(http://pages.cs.wisc.edu/~markhill/DineroIV/)라는 Cache Simulation 툴을 사용한다.  Dinero 툴에서 cache size, cache block size, cache associativity와 cache replacement policy를 조절할 수 있는 옵션을 제공하기 때문에 각각이 miss rate에 미치는 영향을 확인할 수 있다.  또한 Dinero IV부터는 compulsory, capacity, conflict miss 분류를 제공하기 때문에 위 여러 요소들이 어느 종류의 miss에 영향을 미치는지도 확인할 수 있다.  Instruction과 data가 분리된 L1 cache만 있는 경우와, 앞의 L1 cache에 추가로 unified L2 cache가 있는 경우에 대해서도 실험하여 two level cache의 효과에 대해서도 확인한다.

2. Simulation 준비

실험 대상으로 삼을 application은 gcc와 bzip으로 한다.  각 실행 파일은 SPEC CPU2000 benchmark(http://www.spec.org/cpu2000/)에서 제공하는 것으로 하였고, input 파일은 각각 benchmark의 expr.i와 input.graphic으로 하였다.  즉,

./cc1 expr.i

./bzip2 input.graphic

의 처리에 대해 cache profiling을 하게 된다.

Dinero에서 cache simulation을 하기 위해서는 pinatrace input이 필요하다.  Pinatrace input은 Intel에서 제공하는 pin tool로 얻을 수 있다.  Pin tool을 pinatrace.so library와 함께 쓰면 cc1과 같은 binary를 Dinero에서 읽을 수 있는 다음과 같은 trace file로 변환하는 역할을 한다:

2 3912200ab0

2 3912200ab3

1 7FFF8FD702C8

2 39122010c0

1 7FFF8FD702C0

  ./pin –t pinatrace.so – cc1 expr.i

./pin –t pinatrace.so – bzip2 input.graphic

과 같이 하여

cc1.pinatrace.out

bzip2.pinatrace.out

을 얻는다.  Trace file의 용량이 매우 큰 관계로 500MB 정도 될 때 ctrl-c로 trace를 수동 중단할 필요가 있다.  얻는 trace file로 나머지 cache simulation을 진행할 수 있으며, 다시 trace를 할 필요는 없다.

3. cc1 L1 Cache Simulation

우선 L1 cache에 대해서만 전체 simulation 결과를 요약하면 다음과 같다:

Cache	Block	Assoc	Policy	Instr	Misses	Comp	Capacity	Conflict	Data	Misses	Comp	Capacity	Conflict
8192	16	4	LRU	0.0212	7773	4365	777	2631	0.1085	14548	13024	1320	204
16384	16	4	LRU	0.0154	5634	4365	373	896	0.1038	13920	13024	769	127
32768	16	4	LRU	0.0124	4545	4365	70	110	0.1014	13591	13024	510	57
16384	8	4	LRU	0.0276	10099	8155	597	1347	0.1821	24410	23345	933	132
16384	32	4	LRU	0.0088	3229	2372	229	628	0.0562	7537	6749	632	156
16384	16	2	LRU	0.0169	6195	4365	375	1455	0.1072	14379	13024	770	585
16384	16	8	LRU	0.0132	4819	4365	373	81	0.1032	13843	13024	782	37
16384	16	4	rdm	0.0154	5634	4365	373	896	0.1087	14579	13024	835	720

하늘색으로 칠한 부분이 instruction과 data cache의 miss rate인데, instruction cache의 miss rate는 약 2%, data cache의 miss rate는 약 10% 정도임을 알 수 있다.  Instruction은 항상 loop locality가 있어서 낮은 miss rate을 보이고, cc1은 compiler이어서 instruction locality가 낮은 편일 것이다.  2%도 낮은 miss rate으로 보이지만, 나중에 data compression program인 bzip의 0.1%와 비교하면 무려 20배 높은 miss rate임을 확인할 수 있다.  반면 compiler에서 parsing과 code allocation을 할 때 같은 variable을 재사용해서 data locality가 어느 정도 있어서 miss rate이 10%대로 낮은 반면, 대용량 disk data를 처리하는 bzip은 data miss rate가 훨씬 높은 것을 확인할 수 있다.

이어서 cache size, block size, associativity, replacement policy 각각의 영향에 대해 차례대로 살펴보겠다.

1) Cache size

Cache Size	Instr	Misses	Comp	Capacity	Conflict	Data	Misses	Comp	Capacity	Conflict
8192	0.0212	7773	4365	777	2631	0.1085	14548	13024	1320	204
16384	0.0154	5634	4365	373	896	0.1038	13920	13024	769	127
32768	0.0124	4545	4365	70	110	0.1014	13591	13024	510	57

Cache size가 커짐에 따라 instruction과 data cache 둘 다 miss rate가 감소하는 것을 볼 수 있다.  또한 3개 miss 종류 중 capacity와 conflict miss가 줄어든다.  Compulsory miss는 새로운 참조 자체로 인한 cold miss이기 때문에 예상대로 cache size의 증가에 영향을 받지 않는다.  Capacity miss는 cache 자체의 공간 부족으로 인한 miss이기 때문에 감소하고, cache size가 증가하면 다시 사용되어야 할 block이 replace 될 가능성도 적어지기 때문에 conflict miss도 감소한다.

2) Block size

Block Size	Instr	Misses	Comp	Capacity	Conflict	Data	Misses	Comp	Capacity	Conflict
8	0.0276	10099	8155	597	1347	0.1821	24410	23345	933	132
16	0.0154	5634	4365	373	896	0.1038	13920	13024	769	127
32	0.0088	3229	2372	229	628	0.0562	7537	6749	632	156

Block size가 증가하면 하나의 miss에 더 많은 data를 caching하기 때문에 모든 miss가 감소한다.  대신 더 큰 block을 읽는 overhead 외에, write miss시 extra read overhead가 있다는 것을 고려해야 한다.  이러한 extra overhead를 고려하지 않으면, 항상 block size를 더 크게 하는 것이 유리할 것이다.

3) Associativity

Assoc	Instr	Misses	Comp	Capacity	Conflict	Data	Misses	Comp	Capacity	Conflict
2	0.0169	6195	4365	375	1455	0.1072	14379	13024	770	585
4	0.0154	5634	4365	373	896	0.1038	13920	13024	769	127
8	0.0132	4819	4365	373	81	0.1032	13843	13024	782	37

Associativity의 증가는 예상대로 conflict miss를 현저히 감소시킨다.  Fully associative인 경우에는 conflict miss가 0일 것이다.  하지만 associativity의 증가에 따라 한번에 비교해야 하는 entry 수가 증가하고 hardware complexity가 증가하므로, trade-off를 잘 고려해야 할 것이다.

4) Replacement Policy

Policy	Instr	Misses	Comp	Capacity	Conflict	Data	Misses	Comp	Capacity	Conflict
LRU	0.0154	5634	4365	373	896	0.1038	13920	13024	769	127
random	0.0154	5634	4365	373	896	0.1087	14579	13024	835	720

Replacement policy는 이미 한번 caching된 data를 어느 순서로 flushing 하는지를 정하기 때문에 주로 conflict miss에 영향을 미친다.  예상대로 random은 LRU보다 conflict miss를 증가시킨다.  하지만 완벽한 LRU를 hardware로 구현하는 것은 어렵기 때문에 실제로 random replacement를 많이 사용한다고 한다.  전체 data miss rate 차원에서 보면 random replacement를 사용해서 hardware complexity를 줄이는 것이 miss rate에 그리 큰 타격을 주지는 않음을 볼 수 있다.

참고로, page replacement에서는 page fault의 비용이 매우 크기 때문에 (millions of cycles), software로 복잡한 LRU algorithm을 구현하는 것이 충분한 가치가 있다.

4. bzip L1 Cache Simulation

bzip 실행 파일을 L1 cache에 대해서만 simulation한 전체 결과는 다음과 같다:

Cache	Block	Assoc	Policy	Instr	Misses	Comp	Capacity	Conflict	Data	Misses	Comp	Capacity	Conflict
8192	16	4	LRU	0.0013	388	388	0	0	0.4869	101173	101138	35	0
16384	16	4	LRU	0.0013	388	388	0	0	0.4869	101173	101138	35	0
32768	16	4	LRU	0.0013	388	388	0	0	0.4869	101172	101138	34	0
16384	8	4	LRU	0.0024	702	702	0	0	0.4991	103706	103661	45	0
16384	32	4	LRU	0.0007	218	218	0	0	0.4768	99079	99049	30	0
16384	16	2	LRU	0.0014	398	388	0	10	0.4869	101174	101138	36	0
16384	16	8	LRU	0.0013	388	388	0	0	0.4869	101173	101138	35	0
16384	16	4	rdm	0.0013	391	388	0	3	0.4869	101177	101138	30	9
131072	16	4	LRU	0.0013	388	388	0	0	0.4867	101138	101138	0	0

앞서 본 cc1의 결과와는 많이 다른 모습이다.  우선 instruction cache의 miss rate이 0.1%로 cc1의 1/20 수준이다.  bzip은 data compression program이기 때문에 같은 loop를 도는 instruction locality가 compiler program보다 훨씬 크기 때문이다.  반면 data cache miss rate는 무려 거의 50%에 육박한다.  이는 기본적으로 data compression이 program 자체에서 할당한 memory를 쓰는 비중 보다, compression하는 data의 memory를 쓰는 비중이 훨씬 크기 때문이다.  그리고 compression data의 용량이 cache의 용량을 훨씬 웃돌기 때문에 (simulation에 사용한 graphic.input은 6.6MB) caching이 효과를 발휘하기 어려운 상황이다.  이 근본적인 한계는 data cache의 size, block size, associativity 증가 모두에 불구하고 miss rate가 크게 줄지 않는 사실에서 재차 느낄 수 있다.

그래도 각 요소의 세부 영향을 따로 살펴보겠다.

1) Cache size

Cache Size	Instr	Misses	Comp	Capacity	Conflict	Data	Misses	Comp	Capacity	Conflict
8192	0.0013	388	388	0	0	0.4869	101173	101138	35	0
16384	0.0013	388	388	0	0	0.4869	101173	101138	35	0
32768	0.0013	388	388	0	0	0.4869	101172	101138	34	0
131072	0.0013	388	388	0	0	0.4867	101138	101138	0	0

Cache size의 증가에 따른 영향은 거의 전무하다.  애초에 cache size 증가로 줄어들 capacity miss나 conflict miss가 없기 때문이다.  Data cache의 compulsory miss는 application의 대용량 input 자체의 한계에 기인하며, instruction cache에도 warming 이후에 새로 reference 되어야 하는 388개의 block이 있는 상황이다.  Cache size를 32KB까지 늘리면, data cache의 capacity miss가 35에서 34로 줄어드는 아주 미미한 효과만 있다.

추가로 cache size가 128KB인 경우도 실험해 보았는데, 이 때에는 data cache의 capacity miss가 0이 된다.  따라서 이 이상으로 cache size를 증가시키는 것은 현재 application에서는 확실히 더 이상 의미가 없다는 것을 알 수 있다.

2) Block size

Block Size	Instr	Misses	Comp	Capacity	Conflict	Data	Misses	Comp	Capacity	Conflict
8	0.0024	702	702	0	0	0.4991	103706	103661	45	0
16	0.0013	388	388	0	0	0.4869	101173	101138	35	0
32	0.0007	218	218	0	0	0.4768	99079	99049	30	0

Block size를 늘리면 앞서 cc1의 결과에서도 봤듯이 모든 conflict가 줄어든다.  하지만 data cache의 compulsory miss 그리 큰 영향은 없다.  (6.6MB를 32B size로 읽어도 약 2백만 번 읽어야 한다).  Block size를 늘리면 read time과 write miss시 extra read에 penalty가 있음에 유의한다.

3) Associativity

Assoc	Instr	Misses	Comp	Capacity	Conflict	Data	Misses	Comp	Capacity	Conflict
2	0.0013	388	388	0	10	0.4869	101174	101138	36	0
4	0.0013	388	388	0	0	0.4869	101172	101138	34	0
8	0.0013	388	388	0	0	0.4869	101173	101138	35	0

이미 conflict miss가 없기 때문에 associativity를 증가시키는 것은 긍정적인 효과는 없고, hardware complexity만 늘린다.

4) Replacement Policy

Policy	Instr	Misses	Comp	Capacity	Conflict	Data	Misses	Comp	Capacity	Conflict
LRU	0.0013	388	388	0	0	0.4869	101173	101138	35	0
rdm	0.0013	391	388	0	3	0.4869	101177	101138	30	9

cc1에서와 마찬가지로 random policy는 LRU보다 성능이 나빠서 conflict miss를 약간 증가시킨다.  하지만 증가 폭은 매우 작으므로 random replacement의 simpler hardware를 위해 충분히 감수할만한 정도로 보인다.

5. cc1 L2 Unified Cache Simulation

앞선 실험의 L1 cache에 unified L2 cache를 붙여서 실험한 결과는 다음과 같다:

Cache	Block	Unified			Instruction			Data
		Rate	Miss	Try	Rate	Miss	Try	Rate	Miss	Try
1048576	16	0.6307	17389	27573	0.7748	4365	5634	0.5936	13024	21939
2097152	16	0.6307	17389	27573	0.7748	4365	5634	0.5936	13024	21939
4194304	16	0.6307	17389	27573	0.7748	4365	5634	0.5936	13024	21939
2097152	8	0.6307	34778	55146	0.7748	8730	11268	0.5936	26048	43878
2097152	32	0.3307	9119	27573	0.4027	2370	5634	0.3076	6749	21939
2097152	64	0.1777	4899	27573	0.2396	1350	5634	0.1618	3549	21939

우선 L2 cache의 size를 증가시키는 것은 효과가 없음을 확인할 수 있다.  이는 대부분의 L1 cache miss가 compulsory miss이기 때문에 다음 단계에 L2 cache가 있다고 하더라도, L2 cache 안에 그 내용이 있을 수 없기 때문인 것으로 예상된다.  즉 이미 1MB의 L2 cache는 L1 cache에서 처리하지 못하는 capacity miss나 conflict miss를 처리하기에 충분한 크기이고, compulsory miss만 흘리고 있는 상황이다.  이는 L1 cache의 miss 종류에서 보다 분명히 확인할 수 있다:

Cache Size	Instr	Misses	Comp	Capacity	Conflict	Data	Misses	Comp	Capacity	Conflict
16384	0.0154	5634	4365	373	896	0.1038	13920	13024	769	127

파란색으로 표시한 L1 cache의 전체 miss와 compulsory miss가 L2 cache의 instruction try와 L2 cache instruction miss와 정확히 일치한다.  Data cache의 경우에도 miss는 L1 cache의 compulsory miss와 정확히 일치한다.  L2 cache instruction try가 L1 data cache의 total miss보다 다소 큰 이유는 잘 모르겠다.

오히려 L2 cache size 증가에 따른 miss rate 감소는 1MB보다 작은 size에서 확인할 수 있다:

Cache	Block	Unified			Inst			Data
		Rate	Miss	Try	Rate	Miss	Try	Rate	Miss	Try
32768	16	0.8552	23580	27573	0.8976	5057	5634	0.8443	18523	21939
65536	16	0.666	18364	27573	0.8431	4750	5634	0.6205	13614	21939
131072	16	0.6398	17642	27573	0.8021	4519	5634	0.5982	13102	21939
1048576	16	0.6307	17389	27573	0.7748	4365	5634	0.5936	13024	21939

L2 cache size가 16KB이면 L1 cache size와 동일하기 때문에 L2 cache가 없는 것과 마찬가지이다.  L2 cache size가 32KB와 64KB가 되면 L1 cache의 capacity miss와 conflict miss를 보완하기 때문에 miss rate가 감소하는 것을 볼 수 있다.  하지만 L2 cache size가 128KB가 되면 이미 1MB일 때와 miss rate의 개선 폭은 매우 좁을 것이라고 예상할 수 있다.  1MB일 때는 앞서 보았듯이 모든 capacity miss와 conflict miss를 처리하고, compulsory miss만 흘리는 경우이다.

L2 cache의 block size 조정은 miss rate에는 긍정적인 효과를 발휘한다.  이는 한번의 miss에 보다 많은 data를 read하기 때문에 당연한 현상이다.  대신 read time이 길어지고, write miss시 extra penalty가 있음은 앞서 2번이나 언급하였다.  Block size 조정의 한 가지 특이 사항은 위 표에 녹색으로 표시한 부분이다.  L1 cache의 block size가 16인데, L2 cache의 block size가 8이 되면, L1 cache 1회 miss에 L2 cache에 2회 read가 필요하게 된다.  따라서 miss rate는 동일하지만, try와 miss 횟수는 모두 block size가 16일 때보다 2배 증가하는 것을 확인할 수 있다.

6. bzip L2 Unified Cache Simulation

bzip에 대해 마찬가지로 앞선 실험의 L1 cache에 unified L2 cache를 붙여서 실험한 결과는 다음과 같다:

Cache	Block	Unified			Inst			Data
		Rate	Miss	Try	Rate	Miss	Try	Rate	Miss	Try
1048576	16	0.5111	101526	198647	1	388	388	0.5101	101138	198259
2097152	16	0.5111	101526	198647	1	388	388	0.5101	101138	198259
4194304	16	0.5111	101526	198647	1	388	388	0.5101	101138	198259
2097152	8	0.5111	203052	397294	1	776	776	0.5101	202276	396518
2097152	32	0.4997	99271	198647	0.5619	218	388	0.4996	99053	198259
2097152	64	0.494	98136	198647	0.3557	138	388	0.4943	97998	198259

bzip의 L2 cache simulation 결과 역시 cc1의 L2 cache simulation 결과와 크게 다르지 않다.  Block size 증가에 따른 miss rate가 감소하되, L2 cache block size가 L1 cache block size보다 작아지면 그만큼 try와 miss 횟수가 배가 된다 (녹색으로 표시).  그리고 bzip application에서 L1 cache miss는 대부분 compulsory miss이기 때문에 L2 cache size를 늘린다고 해결되지 않는다.  특히 instruction의 경우에는 L1 instruction cache의 miss가 전부 compulsory miss이기 때문에 L2 cache에서 100% miss 날 수 밖에 없다.  bzip의 경우에도 L2 cache size를 L1 cache size와 가깝게 가져가면 L2 cache size 증가에 따라 capacity miss, conflict miss를 처리해서 miss rate가 약간 줄긴 할 것이다.  하지만 bzip application의 capacity miss, conflict miss가 전체 miss의 0.1%도 안 되기 때문에 그 효과는 극히 미미할 것이다.

7. Summary

이상 Dinero cache simulation을 통해 cache size, block size, associativity와 replacement policy가 각각 compulsory miss, capacity miss, conflict miss에 어떤 영향을 미치는지 실험적으로 증명할 수 있었다.  Dinero는 단지 cache miss rate만 산출하는데, 위 4개 특성의 변화에 따라 hit time, miss time과 hardware complexity가 변화한다는 것을 염두에 두고, 최적의 설계를 선택해야 할 것이다.

또한 cc1과 bzip의 비교에서 보았듯이, application에 따라 cache의 성능이 많이 달라진다는 것 역시 실험적으로 확인하였다. 전반적으로 수업에서 배웠던 cache 지식들을 재차 확인하고, application에 따라 어떻게 달라지는지 느낄 수 있는 유익한 실험이었다.

8. References

http://pages.cs.wisc.edu/~markhill/DineroIV/

http://rogue.colorado.edu/pin/

http://www.spec.org/cpu2000/