컴퓨터구조 12장 - Memory 2 : Associative Caches
Associative Caches
Direct mapped은 Main Memory의 data가 cahce로 올라올 때 정해진 곳(one-way)으로 가야한다.
Asoociative 여러 곳(n-way)에 들어갈 수 있다.
Fully associative
- 주어진 블록이 모든 캐시 항목에 들어가도록 한다.
- 모든 항목을 검색해야한다. (동시에)
- 항목 당 comparator가 필요해서 비싸다.
n-way set associative
- set을 만들어서 묶는다. (n이 커질 수록 block , set 수가 적어진다)
- block의 수는 set에 의해 결정되고 이 수로 modulo한다.
- 주어진 set의 모든 항목을 검색해야한다.
- n개의 comparators가 필요하다 (적을 수록 싸다)
- two way일 경우 2개씩 확인해야하고(둘 중 하나에 있음), four way일 경우 4개씩, fully는 다 확인해야한다.
- associative가 클수록 (fully가 best) 좋지만(miss ratio 감소) hardware가 많아지면 속도가 느려지므로 최적의 포인트를 찾아야한다.
- n이 커질수록 적중률이 높아진다.
- cache가 CPU에 가까울수록 높은 associative를 사용한다. (multi level을 사용해서 점점 연관성을 낮춘다.)
z.B)
4-way set associative의 구성
address [31-0]
Byte offset [1-0] : 00, word단위여서 00이므로 신경 x
Word offset [9-2] : 8bit로 set index에 접근, 4
Tag or Index [31-10] : 상위 22bit는 4개의 Tag와 동시에 병렬적으로 비교한다.
hit와 miss를 판별하고 hit의 경우 multiplexor에 의해 선택되어서 출력된다.
set + associativity = A(일정)
Tag : associativity가 증가하면 증가한다. direct mapped는 하나만 비교해도 되므로 작은 tag를 가진다.
Index : associativity가 증가하면 줄어든다. n의 수
Word offset : Fully인 경우 byte offset과 block을 제외하고 모든 bits가 Tag이다.
Replacement Policy
지역성의 원리에 따라 miss가 발생하면 해당 data로 cache를 교체한다.
- Direct mapped는 갈 곳이 하나 밖에 없으므로 선택지가 없다. only one
- Associative는 non-valid entry(V)가 있으면 먼저 교체 그렇지 않으면 set항목 중에서 선택
Least-Recently Used(LRU)
- access 기록을 추적하여 가장 오래 사용하지 않는 것을 선택한다.
- 2-way는 쉽고 4-way는 할수 있고, 그 이상은 힘들다.
- software적으로는 쉽지만 hardware구현은 어렵다. 그래서 잘 안쓴다 ...
- pointer가 하나의 cache를 가리키고 있다가 접근되면 다음으로 이동. pointer가 가리키는 것을 제거
Random
- hardward가 임의로 선택하여 cache제거
- 높은 연관성으로 LRU와 거의 동일한 성능을 제공
Associativity and Multilevel Caches
associativity를 증가시키면 miss rate감소, 그러나 커질수록 감소 폭이 작아진다.
comparitor가 늘어나서 gate delay가 늘어나 성능이 떨어짐..
cache가 클수록 성능이 좋아짐
1-way : 10.3%
2-way : 8.6%
4-way : 8.3%
8-way : 8.1%
multilevel caches
- 메인 cache는 CPU에 붙어 있다. 작고 빠르고 비싸다.
- Level 2 cache는 Level 1 cache의 miss 해결, 좀 더 크고, 느리지만 그래도 Main memory보단 빠름
- 좋은 system은 Level 3,4...가 포함되어있다. 마지막 cache가 miss면 Main memory가 처리.
Multilevel Caches
CPU base CPI(Cycle per Instruction) = 1
clock rate = 4GHz(1ns에 4번)
Miss rate/instruction = 2%
Main memory access time = 100ns
->
with just Primary cache
- Miss penalty = 100ns/0.25ns = 400 cycles
- Effective CPI = 1 + 0.02 * 400 = 9
Now add L-2 cache
- Access time = 5ns
- Global miss rate to main memory = 0.5%
Primary miss with L-2 hit
- Penalty = 5ns/0.25ns = 20cycles
Primary miss with L-2 miss
- Extra penalty = 500cycles
->
CPI = 1 + 0.02 * 20 + 0.05 * 400 = 3.4
Performance ratio = 9 /3.4 = 2.6 (Level 1 / Level 2, Level 2 cache 추가 시 성능 비교)
잘모르겠어요Primary miss with L-2 miss부터 이해안돼
Cache Design Space
- Cache Size**
- Block Size(묶어서 한번에, 너무 크면 안쓰는거 가져옴)
- Associativity(hardware cost, delay)
- Replacement policy
- Write-through vs. Write-back*
- Write-allocation
- CPU와 Main Memory 사이의 속도차이가 커서 Level cache를 추가하여 gap을 줄인다.
- 위의 조건을 모두 고려하여최적의 조건으로 타협해야한다.
z.B) cache를 늘리는 거랑 associativity를 늘리는 것과 같은 효과를 냈다 - > 적은 비용으로 좋은 성능
- 접근 특성(작업량, 사용)에 따라 다르다?
- 단순한게 종종 승리한다.