[컴퓨터 구조] 5.3 캐시(cache)

'컴퓨터 구조 및 설계 MIPS edition 제 6판' 교재와 국민대학교 임은진 교수님의 강의를 바탕으로 정리 및 요약한 글입니다.
정리 과정에서의 오류 및 오타가 있을 수 있습니다 :)

[ Lecture 23 / 교재 5.3 ] 캐시 (cache)

5.1에서는 메모리 계층구조에 대해 알아보았다. (참고 -  2023.11.22 - [컴퓨터구조] - [컴퓨터 구조] 5.1 메모리 계층 구조 )

[컴퓨터 구조] 5.1 메모리 계층 구조

책상과 책장에 비유하여 지역성에 대해 설명할 수 있었는데, 이 비유에서 책상은 캐시(cache)를 의미한다. 책상에 공부해야 할 책들을 보관하였듯이 메모리에서 읽을 값들을 캐시에 보관할 수 있다.

위 이미지가 캐시이다. 프로세서가 캐시에 없는 워드 Xn을 요청하여(왼쪽 그림), 워드 Xn이 메모리에서 캐시로 온 것(오른쪽 그림)이다. 왼쪽 그림을 보면 캐시에는 최근에 접근한 X1, X2 ... Xn-1이 존재했다. 프로세서가 요청한 워드 Xn은 캐시에 없으므로 이 요청은 실패를 발생시키고 워드 Xn을 메모리에서 캐시로 가져오게 된다.

그러면 여기서 의문이 발생한다. 워드 Xn이 캐시 내에 없는지 어떻게 알았는가?
두가지로 나누어 정리하면 다음과 같다.

1. 데이터가 캐시 내에 있는지 어떻게 알 수 있는가?
2. 알 수 있다면, 어떻게 찾을 수 있는가?

각 워드가 캐시 내의 딱 한 장소에만 있을 수 있다면, 워드가 캐시 내에 있는지 없는지를 바로 알 수 있다.

이를 해결하기 위한 캐시의 구조 중 하나는 Direct Mapped Cache이다. '직접 사상'이라는 뜻 그대로 각 메모리의 위치가 캐시 내의 정확히 한 곳에만 사상되는 캐시 구조이다.

그렇다면 Direct Mapped Cache는 어떻게 메모리 주소를 캐시 위치로 바꿀까?

cache index = ( memory address ) % ( the number of blocks in the cache )

메모리 주소를 캐시 내에 존재하는 전체 캐시 블록 수로 나눈 나머지로 캐시 인덱스를 사용한다.

 

위의 그림을 보자. 그림의 캐시는 8 block 캐시이다. 8 = 2^3 이므로 캐시인덱스로 블록 주소의 하위 3비트를 사용할 것이다. 예를 들어 메모리 주소가 29(이진수로 11101)이면 하위 3비트가 101이므로 101의 인덱스에 해당하는 캐시블록에 사상될 것이다.

하지만 모듈러 연산의 결과는 같은 값이 나올 수 있다. 예를 들어 메모리 주소가 5(이진수로 00101)이면 하위 3비트가 똑같이 101이다. 따라서 각 캐시 엔트리는 여러 주소의 메모리 내용을 갖고 있을 수 있다. 그러므로 같은 캐시 인덱스에 저장되는 것이라도 그 저장된 값이 프로세서가 요구하는 값이 아닌 다른 메모리 주소 값일 수도 있다. 그러면 그것을 어떻게 확인할 수 있을까?

캐시에 태그(tag)를 추가하여 이를 해결할 수 있다. 태그는 캐시 내의 워드가 요청한 것인지 아닌지를 식별하는데 필요한 주소 정보를 담고 있는 필드이다. 태그는 캐시 인덱스로 사용되지 않은 주소의 상위 부분 비트들로 구성된다. 앞서 들은 예시에서 메모리 주소가 29인 경우 이진수로 11101이므로 하위 3비트는 캐시 인덱스로 사용되며, 캐시 인덱스로 사용되지 않은 상위 2비트 11은 태그가 된다.

또한 캐시 블록이 가지고 있는 값이 유효한지를 알려주는 비트도 하나 필요하다. 캐시 엔트리에서는 유효비트(Valid bit)를 통해서 유효한 주소가 있는지를 나타낸다. Valid bit가 0이면 해당 캐시는 비어있는 것이고, Valid bit가 1이면 유효한 값이 저장되어 있는 것이다.

만약 Valid bit가 0이라면, 더 볼 것도 없이 캐시에는 찾고자하는 메모리 주소 값이 없으므로 메인메모리에서 가져와야 할 것이다. 
그러나 Valid bit가 1이라면, 태그 필드까지 비교하여 정말 자신이 찾고자 하는 메모리 주소가 맞는지를 더 확인해보아야 할 것이다.

---

우리가 살펴본 위의 예시에서 캐시는 한 블록의 크기가 1 word였다. 그런데 일반적으로 캐시의 블록 크기는 여러 워드이다.
블록이 크면 공간적 지역성을 더 잘 활용할 수 있으므로 실패율이 낮아진다.

블록을 크게 하면 공간적 지역성을 더 잘 활용할 수 있으므로(책장에서 한꺼번에 책을 많이 가져올 수 있으므로) 실패율이 낮아진다. 하지만 아래 그래프를 보면 블록 사이즈가 늘어남에 따라 실패율이 줄어들지만, 어느 지점부터는 오히려 실패율이 증가하는 추세가 나타난다. 캐시의 용량은 정해져 있으므로 블록 사이즈가 너무 커지면 블록의 개수는 줄어들기 때문에 cache conflict가 더 많이 일어나기 때문이다. 블록의 개수가 너무 적어서 블록에 대한 경쟁이 심해진다. 

그렇다면 제어 유닛은  Cache miss를 어떻게 처리할까?

• Read 해야하는 경우
  
  • hit -> 원하던 것. 가져다가 사용
  • miss -> CPU stall 후 메인 메모리에서 블록 fetch, 캐시로 가져와서 restart
• Write 해야하는 경우
  • hit -> cache coherence problem 발생, 캐시는 메인메모리의 복제본이어야하는데 내용이 달라지는 문제 발생
    • write through(즉시 쓰기)
      항상 데이터를 메모리와 캐시에 같이 쓰는 것.
      항상 두 계층의 데이터가 일치함을 보장해주지만, 프로세서의 성능을 심하게 저하시킬 수 있다.
      -> Solution ) write buffer 이용하기!
      쓰기 버퍼는 데이터가 메모리에 써질 때까지 기다리는 동안 이 데이터를 저장한다. 데이터를 캐시와 쓰기버퍼에 쓰고 난 후에 프로세서는 바로 수행을 계속할 수 있으며 메인메모리에 쓰기를 완료하면 쓰기버퍼의 엔트리는 지워진다.
      하지만 쓰기버퍼의 용량이 다 찼을 경우에는 Stall을 피할 수 없다.
    • write back(나중 쓰기)
      쓰기가 발생했을 때 새로운 값은 캐시에만 업데이트하고 메인메모리에는 써주지 않다가, 캐시에서 쫓겨날 때 이 블록을 하위 메모리 계층에 써주는 방식.
      block에서 쓰기가 발생하면 dirty bit를 1로 만들고 그 dirty bit 를 keep track해야한다.
      성능을 향상시킬 수 있으나 구현이 복잡하다.