[컴퓨터구조] 캐시 성능의 측정 및 향상
Memory stall cycles
= Memory accesses / Program x Miss rate x Miss penalty
= Instructions / Program x Misses / Instruction x Miss penalty
Q.
명령어 캐시 실패율 I-cache miss rate 2%
(Use instruction fetch operation, read from instruction cache memory)
데이터 캐시 실패율 D-cache miss rate 4%라고 가정해보자
(load & store operation)
메모리 지연이 없을 때 CPI가 2이고 매 실패마다 실패 손실(Miss penalty)이 100사이클이다.
실패가 발생하지 않는 완벽한 캐시를 사용한다면 시스템이 얼마나 빨라지는지 계산하라.
적재와 저장 명령어의 실행 빈도는 36%라 가정하라.
Miss cycles per instruction
I-cache: 0.02 x 100 = 2
D-cache: 0.36(load & store) x 0.04 x 100 = 1.44
Actual CPI = 2 + 2 + 1.44 = 5.44
Ideal CPU is 5.44 / 2 = 2.72 x faster
<Average Access Time>
Hit time is also important for performance
Average memory access time (AMAT)
considering the performance of accessing the cache memory only
AMAT = Hit time + Miss rate x Miss penalty
Example:
CPU with 2ns clock, hit time = 1 cycle, miss penalty = 20 cycles, I-cache miss rate = 6%
AMAT = 2ns x 100% + 20 x 2ns x 0.06 = 2ns + 2.4ns = 4.4ns
<Improving Cache Performance>
- Associativity
Drawback of a direct-mapped cache:
If frequently used addresses are mapped to the same cache index, many cache misses will happen
-> solution: multiple slots per index
multiple locations more than just one so that we can place that two cache lines together in the cache line
- Multi-level Cache
small cache has high miss rate
large cache has slow hit time
-> solution: use multiple levels of caches
- Software Optimization
solution: strategically design data access pattern
<더 유연한 블록 배치를 통한 캐시 실패 줄이기!>
1. Direct mapped
메모리 블록 주소를 상위 계층의 한 주소에 사상
one option to place our given cache memory
2. Set associative (n-way)
한 블록이 들어갈 수 있는 자리의 개수가 고정되어 있음.
provide multiple locations within a set of cache blocks / lines
a given memory address can be placed in one of multiple locations in a set.
It cannot be placed in other set.
Block number determines the set index
(Block number) modulo (#Sets in cache)
3. Fully associative
opposite of direct mapped
블록이 어느 곳에나 있을 수 있기 때문에 주어진 블록을 찾으려면 캐시 내의 모든 엔트리를 검색해야 함.
given cache line can be placed in anywhere in the cache memory.
large flexibility with higher overload
<Compare 4-block caches>
Direct mapped / 2-way set associative / fully associative
Block address access sequence: 0, 8, 0, 6, 8
1. Direct mapped
0 % 4 = 0
8 % 4 = 0
6 % 4 = 2
| Block address | Cache index | Hit/miss | Cache content after access | |||
| 0 | 1 | 2 | 3 | |||
| 0 | 0 | miss | Mem[0] | |||
| 8 | miss | Mem[8] | ||||
| 0 | miss | Mem[0] | ||||
| 6 | miss | Mem[0] | Mem[6] | |||
| 8 | miss | Mem[8] | Mem[6] | |||
실패 시 집합 내에서 교체할 엔트리의 선정을 위해서는 교체 방식을 정해야 함.
집합 연관 캐시는 대개 집합 내에서 사용한 지 가장 오래된 블록을 교체시키는 LRU (least recently used) 교체 방식 사용
가장 먼 과거에 사용된 블록이 교체됨.
2. 2-way set associative
0 % 2 = 0
8 % 2 = 0
6 % 2 = 0
-> all goes to the same set
| Block address | Cache index | Hit/miss | Cache content after access | |||
| Set 0 | Set 1 | |||||
| 0 | 0 | miss | Mem[0] | |||
| 8 | 0 | miss | Mem[0] | Mem[8] | ||
| 0 | 0 | hit | Mem[0] | Mem[8] | ||
| 6 | 0 | miss | Mem[0] | Mem[6] | ||
| 8 | 0 | miss | Mem[8] | Mem[6] | ||
블록 8이 블록 0보다 더 오랫동안 참조되지 않았기 때문에 블록8 교체
3. Fully associative
| Block address | Hit/miss | Cache content after access | ||||
| 0 | 1 | 2 | 3 | |||
| 0 | miss | Mem[0] | ||||
| 8 | miss | Mem[0] | Mem[8] | |||
| 0 | hit | Mem[0] | Mem[8] | |||
| 6 | miss | Mem[0] | Mem[8] | Mem[6] | ||
| 8 | hit | Mem[0] | Mem[8] | Mem[6] | ||
Increased associativity generally decreases miss rate
but with diminishing returns
<교체할 블록의 선택>
-Set associative
multiple possible candidates to be replaced
choose a non-valid (empty) location, if there is any.
otherwise, need to choose one of the blocks in the set as the victim
완전 연관 캐시에서는 모든 블록이 교체의 후보가 된다.
가장 널리 사용되는 방식은
LRU (least recently used)
: choose the one unused for the longest time
LRU 교체는 집합의 어떤 원소가 집합 내 다른 원소에 비해 상대적으로 언제 사용되었는지를 추적함으로써 구현 가능함.
Pseudo LRU (for 4+ ways)
Use an approximation
e.g., A tree-like structure that has an LRU bit per 2 entries
다른 방식으로는
Sequential (Round Robin)
: select the replacement victim in the circular order
Random
이 있음.
<Cache Example>
128KB data capacity, 64 bytes per block, 32bit address
2-way set associative, LRU replacement
Store policy: write-back, write-allocate
64 bytes는 2의 6승이므로 offset은 6bit
128KB / 64bytes = 2048 blocks
그런데 2-way set associative이므로 1024 sets -> 2의 10승
index는 10bit
나머지 32 - 6(offset) - 10(index) = 16bit는 tag
| tag (16-bit) | index (10-bit) | offset (6-bit) |
교안 예시대로 혼자 문제 풀어봤슴다 ~.~
<Multi-level Caches>
Level-2 cache handles misses from the L-1 cache
2차 캐시는 보통 마이크로프로세서와 같은 칩에 있으며, 1차 캐시에서 실패가 발생하면 접근함.
2차 캐시가 원하는 데이터를 갖고 있으면 실패 손실은 2차 캐시의 접근시간이 되며, 이 값은 메인 메모리 접근시간보다 훨씬 짧다.
1차 캐시와 2차 캐시 둘 다 데이터를 갖고 있지 않은 경우에는 메인 메모리 접근이 필요하게 되어 더 큰 실패 손실이 발생한다.
Some high-end systems include L-3 cache
Example.
CPU base CPI = 1, clock rate = 4GHz
Miss rate/instruction = 2%
Main memory access time = 100ns
Miss penalty = 100ns / 0.25ns = 400 cycles
1 x 100% + 400 x 2% = 1 + 8 = 9
Now add L-2 cache
Access time = 5ns
Global miss rate to main memory = 0.5%
penalty (miss with L-2 hit) = 5ns / 0.25ns = 20 cycles (It is much slower than L1 hit but much better than going to the main memory)
Extra penalty = 400 cycles
CPI = 1 x 100% + 20 x 2% + 400 x 0.5% = 3.4
Performance ratio = 9 / 3.4 = 2.6x faster with L2
<Sources of Misses>
1. Compulsory misses (cold start misses)
First access to a block
If we access a certain address / cache block for the first time, then the cache line would not be in the code (start miss)
2. Capacity misses
Due to finite cache size
A replaced block is later accessed again
3. Conflict misses (collision misses)
In a non-fully associative cache
Due to competition for entries in a set