[Computer Architecture]- Cache(1)

📕Cache

• SRAM의 종류중 하나면서, 작고 빠른 것이 특징입니다.
• Processor와 memory 사이에 위치하고 있으며, L1,L2,L3 Cache로 구성되어 있습니다.
• Processor는 Cache에서 가장 먼저 data를 찾습니다.
  • 없으면 memory로 이동

Cache를 간단하게 구조화한 사진입니다.

1. Processor가 cache에 X를 요청합니다.
2. Cache에서 X가 있는지 없는지를 체크합니다.
   1. 있다면 Cache -> Processor로 X를 전달해주고 이때를 hit라고 합니다.
      1. 여기서 우리는 그 정보가 어디있는지도 알아야 합니다.
   2. 없다면 Cache는 Memory에서 X를 찾아서 Processor에게 전달해줍니다.
      1. Cache에 요청한 data가 없다면 그 때를 miss라고 합니다.

 

📕Direct Mapped Cache

• Cache에서 위치를 할당하는 가장 간단한 방법은 메모리에 있는 word의 주소입니다.
  • 이러한 캐시 구조를 "direct mapped" 구조라고 합니다.
  • 각 메모리의 위치가 캐시 내에서 정확하게 한 곳만 가리키게 됩니다.
• Cache에 위치하게 되는 위치는 (Block Address) % (cache내에 block의 수)
• 아래 그림을 보면 이해가 쉬울 것입니다.

• 예를 들면
  • 10101(21)에 대응되는 cache에 주소는 10101(21) % 8 = 5
  • 5를 2진수로 바꾸면 101이 되고, 10101은 cache에서 101에 위치하게 됩니다.
• 그림을 보면 알수 잇듯이 memory 주소에 뒤 3글자와 cache의 3글자가 일치하는 것을 알 수 있습니다.
• 방이 겹치게 되면 들어가 있는 memory 주소를 밀어내고 새로운 주소가 들어가게 됩니다.

 

📕Tag and Valid Bits

• 캐시 안에는 여러 memory에 위치가 들어 갈 수 있는데, 그 캐시 안에 어떤 데이터가 특정되어 있는지를 찾아내는것이 중요합니다.
  • 캐시는 data 뿐만 아니라 block address도 저장합니다. 
  • 실질적으로 위치를 특정시키기 위해서는 tag라고 불리는 high-order bits가 필요합니다.
  • 위의 그림에서 10101을 예로 들면 101은 cache에 들어가게되고, 10이 tag에 들어가게됩니다.
  • 그러면 우리는 tag+cache에 들어있는 block address로 memory에 있는 주소를 식별할수 있게 됩니다.
• 하지만 이러한 tag가 유효한지 검사하기 위해서 Valid bits가 필요하다.
  • tag에 유효한 주소가 포함되어 있는지를 valid bit를 보고 판단할 수 있다.
    • valid bit가 1이라면 태그와 주소를 비교하고
    • valid bit가 0이라면 비교를 할 필요 자체가 없다.

📕Cache Access

• 가정
  • directed mapped cache
  • Cahce에는 하위 3bit가 들어가고 8 block으로 구성되어 있다.
  • 초기 cache는 empty 상태이다.
  • 왼쪽이 Cache이고, 오른쪽이 memory이다.

• 22는 이진수로 10110(2) -> cache에는 110에 해당하는 index에 위치하게 될 것이다.
• cache에는 현재 10110이라는 데이터가 없었기에, miss가 일어나게 되었고, 새로운 10110이 cahe index 110에 들어왔기에, valid를 yes로 바꿔주고, 태그와 data를 저장하게 된다. tag + index는 원래 주소 (10110)

1️⃣Address 26 accessed

• 26 = 이진수로 11010이고, 현재 cache에는 010에 해당하는 index에 위치하게 될것이다.
• cache에 없었기에 Miss이고, 새로 들어왔으니 valid를 yes로 바꿔주고, tag와 data를 저장한다.

2️⃣Address 22,26 accessed

• 22 = 10110, cache에는 110에 해당하는 index에 위치하게 될것이다.
• tag를 비교해서 tag가 같다면 data는 cache에 존재한다는 뜻이기에 hit가 일어난다.
• 26= 11010, cache에는 010에 해당하는 index에 위치하게 될것이다.
• 현재 cache 010에 index에 data가 있다. 그래서 tag를 비교해야 하는데, tag가 같기 때문에 hit가 일어난다.

3️⃣Address 18 accessed

• 18 = 10 010, cache에는 010에 해당하는 index에 위치하게 될 것입니다.
• 현재 010 index에는 정보가 있습니다. 그 때의 tag를 비교했는데 다르기에, miss가 일어나고, cache에는 새로운 정보가 업데이트 됩니다.

 

📕Address Subdivision(세분화)

• Address는 크게 3개로 세분화됩니다.
  1. Tag field 
     1. 캐시의 tag field와 address의 tag field를 비교
  2. Cache index
     1. 캐시 내에서의 위치를 식별
  3. Byte offset
     
     1. byte로 word를 식별

 

📕Cache Size

• 캐시에 필요한 총 비트 수는 캐시 크기와 주소 크기의 함수입니다.
  • Cache는 data와 tags를 포함합니다.
  • 만약 32-bit address이고, cache size : 2^n blocks, block size : 2^m words일때
    • Tag field size : 32 - (n+m+2)
    • Total bits of cache : 2^n * (block size + tag size + valid field size)
    • The number of bits : 2^n * ( 2^m * 32 + (32-n-m-2) +1 ) = 2^n * (2 ^m *32 + 31-n-m)
• 64 blocks whose size of 16 bytes cache이고,  address 1200을 cache에 access할때
  • Block address = 1200 / 16= 75
  • Block number = 75 % 64 = 11

 

📕Handling Cache Misses

• cache miss handling은 process control unit과 controller를 통해서 다뤄진다.
  1. Stall the entire CPU Pipeline
  2. Fetch a block from the next level of hierarchy
  3. Restart instruction fetch if instruction cache miss
  4. Complete data access if data cache miss

📕Handling Writes

📗write-through

• 만약 hit가 일어났다면 process는 cache에 있는 block을 업데이트 할수 있다.
  • 하지만 그때 cache와 memory 사이에 불일치가 발생한다.
  • 이러한 불일치를 해결하기 위한 간단한 방법은 cache와 memory에 데이터를 같이 작성해준다.
    • 이 방법을  write-through라고 한다.
• 하지만 write through는 그다지 좋은 방법이 아니다.
  • 그래서 write buffer를 통해서 memory에 data가 write 될때까지 data를 buffer에 저장해준다.
  • processor는 계속 진행을 하고 만약 write buffer가 꽉 차있을 경우에만 stall를 해준다.

📗write-back

• 또 다른 대안으로는 write-back이 있다.
  • write - thorugh cache의 단점을 보완
  • Cache에 데이터를 업데이트 하면 Main memory에 업데이트 하기 위해 표시(dirty bit)
  • Cache block이 교체될때 해당 cache가 가리키는 main memory에 값을 업데이트 한다.
    • 다른 tag를 가진 data가 cache block에 할당 될때
  • 쉽게 설명하면 data를 일단 cache에 쓰고, cache내에서 같은 index에 해당하고 다른 tag를 가진 데이터가 들어올 때 memory에 update