컴퓨터 캐시의 동작 과정

메모리 , 캐시에 대한 기본적인 내용을 모른다면 앞의 글을 참고하면 좋을것같다.

https://jghdg1234.tistory.com/4

Memory Hierarchy(컴퓨터의 메모리 구조)

CPU에서 데이터에 접근하려면 맨 처음 레지스터에 접근하여 원하는 데이터가 있는지 확인한다. 그 다음, 계속해서 아래 레벨로 내려가 원하는 데이터를 찾으면, 그 데이터를 계속해서 위로 복사하여(옮기는것이 아니라) CPU에 전달하는 방식이다. 위의 글에서 캐시는 컴퓨터 메모리 구조에서 매우 중요한 항목이라고 언급했는데, 그 이유는 메모리의 접근 시간을 단축시켜주기 때문이다.

그렇다면 캐시는 어떻게 구성되어 있을까? 간단한 예를 한번 들어보자.

 

Direct-mapped cache

위 그림에서 위에있는 블럭들은 캐시이고, 아래에 있는 더 길다란 블럭들은 메모리이다. 이 캐시는 Direct-mapped 캐시인데, 이 말은 하나의 캐시 블럭에는 단지 하나의 메모리 밖에 저장 할 수 없다. 예를들어, 현재 캐시는 8개의 블럭으로 되어있고, 각 블럭의 인덱스는 0 부터 7까지이다. 예를들어 00001주소에 있는 메모리를 프로세서가 요청했다고 가정해보자. 그러면 프로세서는 캐시를 들여다 볼 것이다. "00001"주소의 데이터가 캐시에 없다.(캐시 미스 발생[cache miss].)  그러면 이제 더 아래쪽 DRAM레벨로 내려가 메모리를 찾아와 캐시 블럭에 저장한다. 

 

그렇지만 여기서 한가지 의문점이 생긴다. 위에서 "프로세서에서 요청한 데이터를 캐시에서 찾는다" 라고 하였는데, 캐시 블럭이 8개가 아니라 800개라면, 탐색 시간은 O(n)이 소요된다. 그렇다면 원하는 캐시 블럭에 바로 접근하여 원하는 데이터가 있는지 확인하려면 어떻게 해야할까? 가장 기본적인 블럭 위치 연산법은 나머지 연산(modulo)이다. 예를들어, 16진수로 표현된 메모리 주소 0x1234ABCD를 찾으려고 한다고 가정해보자. 이때, (메모리 주소 % 캐시 블럭의 갯수)를 하면 캐시의 위치를 찾을 수 있다. 

 

위의 그림 예제로 돌아가보자. 메모리 00001은 캐시의 몇번 블록에 저장될까? 00001 % 8 은 1 이다. 그러면 이제 캐시블럭[0]은 00001의 메모리로 채워져 있는 상태이다. 그런데 여기서 만약 01001의 메모리를 참조하면 어떤 일이 벌어질까? 먼저, 나머지 연산을 수행해 캐시 블럭의 위치를 알아낸다. (01001  % 8)은 1이다. 그리고 1에는 이미 데이터가 존재한다(00001). 그러면 이것은 캐시 히트(cache hit)일까?

 

정답은 아니다.

 

이유는 간단하다. 프로세서가 요청한 데이터는 01001이지만 캐시블럭 1에 있는 데이터는 00001이기 때문이다. 그러면 여기서 또 다른 의문이 생긴다. 그렇다면 두개의 다른 메모리는 어떻게 구분될까? "Tag bit"라는 비트를 이용한다. 위의 예제에서는 간단하게 이진수로 표현된 메모리주소는 앞 두자리를 태그비트로 사용한다. 띠라서 '01' 001과 '00' 001 엄연히 다른 데이터이다. 그러면 여기서 캐시 충돌이 발생한다.(이미 캐시블럭 1번에 00001이라는 데이터가 있으므로). 이때, 원래 있던 00001을 캐시에서 내보내고 01001을 다시 캐시에 저장한다. 이런식으로 Direct-mapped cache는 캐시 블럭 하나당 하나의 데이터만 담을 수 있으므로 새로운 데이터가 이미 채워진 블록에 들어오려고 할 때마다 교체 해줘야 한다.

 

그렇지만 이런식으로 교체를 하다보면 그에 대한 비용은 무시 할 수 없다. 예를 하나 들어보자. 

아래는 프로세서가 요청한 데이터를 순서대로 나열한것이다.

 

1. 00001 (캐시 미스! 블럭 1에 이 데이터를 저장)

2. 01001 (캐시 미스! 00001을 내보내고 01001을 저장)

3. 00001 (캐시 미스! 01001을 내보내고 00001을 "다시" 저장)

 

이처럼 다시 저장은 또다른 프로세스를 요구한다. 다시 레지스터부터 DRAM까지 내려가 데이터를 가져오는 비용은 매우 비싸다(캐시의 존재 본질에 의문이 드는 시점이다).

 

그렇다면, 하나의 캐시 블럭에 여러개의 데이터를 저장 할 수 있다면 어떨까? 위의 예를 다시 들어보자.

 

1. 00001 (캐시 미스! 블럭 1에 이 데이터를 저장)

2. 01001 (캐시 미스! 00001을 내보내지 않고 블럭 1에 01001을 저장) <이 시점에서 블럭 1에는 두개의 데이터 (00001, 01001)이 들어있다.

3. 00001 (캐시 히트!)

 

이처럼 훨씬 효율적인 프로세스 처리가 가능하다. 캐시블럭 하나에 두개의 데이터를 저장할 수 있는 캐시를 (2-way set associative cache)라고 부른다.

 

하지만, n - ways set associative는 캐시 블럭을 검색할때, 모든 블럭들을 검색해야 한다. 예를들어, 4 ways set associative에서 세트 11에 해당하는 데이터를 찾으려고 한다면, 세트 11로 내려가 4개의 블럭을 일일히 모두 확인해야 한다.

 

마지막으로, 캐시 접근을 더 용이하게 하기 위해, 32비트 데이터를 여러 부분으로 나눌 수 있다.

 

valid bit, tag bit, index bit, offset bit.

1. **Valid bit (유효 비트):** 캐시 블록이 유효한 데이터를 가지고 있는지를 나타내는 비트이다. 보통 0은 비어있음을, 1은 캐시 블록에 유효한 데이터가 저장되어 있음을 나타낸다. 캐시 조회 시, 이 비트를 확인하여 캐시가 유효한 데이터를 가졌는지를 확인한다.

2. **Tag bit (태그 비트):** 동일한 캐시 블록으로 매핑된 데이터들을 식별하는 데 사용되는 비트이다. 캐시 블록에 저장된 데이터의 주소 일부로 사용되며, 캐시에서 데이터를 찾을 때 메모리 주소의 특정 부분을 나타낸다.

3. **Index bit (인덱스 비트):** 캐시 내에서 어느 블록에 위치하는지를 나타내는 비트이다. 이진수로 표현되며, 캐시 메모리의 어느 부분에 데이터가 저장될지 결정하는 데 사용된다.

4. **Offset bit (오프셋 비트):** 캐시 블럭내에서 어느 구간 사이에 데이터가 있는지 알려주는 비트이다. 예를들어, 32비트 크기의 캐시 블럭이 있다고 가정해보자. 한개의 블럭은 8개의 단어를 저장 할 수 있다(하나의 단어는 4바이트). 예를들어 오프셋 비트가 8이면, 8부터 11까지의 3비트가 우리가 알아봐야 할 곳이다.