5. Cache Memory

Cache Memory

배경

오늘날 프로세서의 속도는 매우 빨라졌지만, 메모리는 느리다.

그래서 base CPI는 감소하였고, 이에 따라 miss penalty가 크고, 메모리에 의한 stall이 상당히 커졌다.

CPU는 굉장히 빠르지만, 메모리 때문에 프로그램 실행 속도가 느려진 것이다.

 

이를 해결하기 위해서 cache를 사용한다.

 

IO device나 network는 memory에 비해서 access speed가 훨씬 느리다.

여기에서도 문제를 해결하기 위해서 cache를 사용한다.

 

Cache Memory

Main memory access 속도를 높이기 위해서 사용한다.

CPU가 동작하는 속도에 비해 main memory는 속도가 느리기 때문에 필요하다.

 

Cache Designer의 관점

Cache를 아무리 잘 설계해도 page fault를 일어나지 않게 하거나, page fault가 일어났을 때 main memory로 page를 가져오는데 필요한 시간을 줄일 수 없다.

이는 OS와 I/O design issue이다.

 

따라서 page fault와, page fault와 관련된 performance loss를 고려하지 않는다.

모든 내용은 main memory에 있다고 가정해서 main memory를 disk의 크기로 늘리고 생각한다.

 

Operation

Read/Write를 한다.

 

read

• read hit
  • CPU가 필요한 내용이 cache에 있으면 해당 block을 찾아서 필요한 내용을 준다.
• read miss
  • cache miss가 났을 때 cache는 main memory에 가서 block을 읽어야 한다.
  • miss panalty 만큼 시간이 걸리게 된다.
  • memory stall(pipeline stall)이 발생한다.
    • cache miss에 의해 발생하는 stall
    • memory access 속도와 CPU 동작 속도가 차이가 나기 때문에 CPU가 필요한 block을 받을 때 까지 instruction이 수행되지 못하고 stall이 발생한다.
    • 메모리는 속도가 느리기 때문에 hazard에 의한 stall보다 훨씬 크다.
    • CPU(pipiline) stall이 발생 → main memory에서 block을 fetch → instruction 다시 시작

 

write

• write hit
  • write하려는 내용이 cache memory에 있을 경우
  • memory inconsistency
    • write hit이 나서 cache memory에 반영하더라도 cache memory와 main memory의 내용은 다르다.
    • cache memory가 main memory의 copy이기 때문이다.
    • 해결방법
      • write-through : CPU가 cache에 write 할 때 동시에 main memory에도 write를 한다.
      • write-back : 일단 cache에만 write하고, 나중에 main에 반영한다.
• write miss
  • CPU(pipiline) stall이 발생 → main memory에서 block을 fetch → write → instruction 다시 시작

 

---

Cache Performance

average memory access time

= hit time + miss rate x miss penalty

hit time : 원하는 것이 cache에 있는지 확인하는 시간

 

Cache memory를 사용하지 않는다면 average access time은 main memory access time과 같아지므로 miss penalty와 동일해진다.

따라서 cache를 사용함으로써 엄청난 speed up을 얻을 수 있다.

 

그러나 cache miss로 인해 stall이 많이 발생하므로 CPI는 증가하게 된다.

 

예시

cache memory access time : 1 clock cycle

miss penalty : 50 cycles

miss rate : 0.02

라고 가정하자.

 

그렇다면 average memory access time 

= hit time + miss rate x miss penalty

= 1 + 0.02 * 50

= 2 cycles

 

따라서, 모든 instruction에서의 IF stage와 DM stage에서 각각 1 cycle 씩 추가적인 pipeline stall이 발생한다.

 

lw/sw는 20%로 발생한다고 하자.

 

그렇다면 CPI

= 기본 발생하는 cycle + 모든 instruction은 IF stage에서 1 cycle loss + lw/sw는 추가적으로 1 cycle loss

= 1 + 1 + 0.2 x 1

= 2.2

 

개선

하나의 factor가 줄어들더라도 다른 factor가 늘어날 수 있다.

따라서 전체의 계산이 작아지는 방향으로 개선을 해야 한다.

 

Cache Size

Total cache size를 키우면, 더 많은 내용을 caching할 수 있으므로 miss rate는 감소한다.

반면에 더 많은 내용 중에서 원하는 것을 찾아야 하므로 hit time은 증가하게 된다.

 

Block Size

Cost를 높이지 않으면서 성능을 바꿀 수 있는 요인이다.

 

Cache의 크기를 바꾸지 않으므로 cost(비용)은 동일하다.

그러나 성능에는 큰 영향을 주기 때문에 중요한 요소이다.

 

벤치마크를 분석해서 가장 낮은 miss rate를 보이는 최적의 block size를 찾아낼 수 있다.

 

Block size에 따른 miss rate는 U자형 커브를 보이게 된다.

그리고 cache의 크기가 클 수록 U자형의 모양이 잘 나타나지 않게 된다.

즉 cache size가 클 수록 block size에 둔감해진다.

 

• Block size = 1 word
  • spatial locality를 이용할 수 없다.
  • 따라서 이는 좋은 방법이 아니다.
• Block size를 키우면
  • spatial locality를 이용할 수 있게 되고, 그에 따라 miss rate는 감소한다.
  • 그러나 block의 내용이 너무 많기 때문에 miss penalty는 증가하게 된다.
• Block size를 너무 크면
  • cache에 들어가는 block의 수가 적다.
  • 이는 working set이 적게 들어가게 하기 때문에 miss rate가 오히려 증가한다.

 

위 그래프에서 볼 수 있는 정보는 다음과 같다.

• Cache size ↑ → miss rate ↓
• Cache size ↑ → U자형 모양이 두드러지지 않음(block size에 둔감해짐)
• Block size ↑ → miss rate가 감소했다가 다시 증가한다. (U자형 모양을 보인다.)

 

Miss Penalty

아래 penalty time은 bus cycle을 단위로 사용한다.

Bus cycle은 clock cycle과 다를 수 있다.

 

Miss penalty는 다음으로 이루어져있다.

• address transfer : 메인 메모리가 주소를 받는 시간
• DRAM access : main memory에서 한 word를 찾는데 걸리는 시간
• data transfer : 찾은 word를 cache로 보내주는 시간

 

예를 들어, 1-word-wide DRAM에서 4 word block 1개를 가져오는데 조건이 다음과 같다고 하자.

(address transfer = 1 bus cycle, DRAM access = 15 bus cycle, data transfer = 1 bus cycle)

 

main memory에 한번 가서 4개의 word를 가져와야 하므로,

miss penalty = address transfer + DRAM access + data transfer

= 1 + 4 * (15 + 1) = 65 bus cycles

이다.

 

한 cycle에 몇 byte를 가져오는지를 나타내는 bandwidth

= 16 bytes(4word) / 65 cycles

= 0.25 byte / cycle

이 된다.

 

실제로는 block의 4 word는 연속되어있기 때문에 하나의 word를 찾으면 그 다음 word를 찾는데 걸리는 시간은 적어진다.

여기서는 최악의 상황을 가정한 것이다.

 

Bandwidth

• wide bus (wider memory organization)
  • 한번에 여러 개의 word를 가져올 수 있도록 bus의 폭을 키운 것
  • 예시 : 4-word wide memory
    • miss penalty
      = address transfer + DRAM access + data transfer
      = 1 + 15 + 1
      = 17 bus cycles
    •  bandwidth
      = 16bytes / 17 cycles
      = 0.94 bytes / cycle
• interleaved memory organization
  • memory를 여러 개의 independent memory로 구성하여, 각 bank에서 한 cycle 당 한 word 씩 보내도록 한 것
  • bank : 나눠진 각각의 independent memory
    

    

  • 예시 : 4-bank interleaved memory
    • miss penalty
      = address transfer + DRAM access + data transfer
      = 1 + 15 + 1 + ( 1 + 1 + 1 )
      = 20 bus cycles
    • bandwidth
      = 16 bytes / 20 cycels
      = 0.8 byte / cycle