[컴퓨터 구조] 메모리[1] - 캐시(Cache)

 

 

 

 

 

 

🧐 캐시(Cache)

캐시라는 명칭은 최초에는 메인 메모리와 프로세서 사이의 메모리 계층을 나타내기 위해서 사용된 용어입니다.

오늘날에도 이러한 의미로 가장 많이 사용되기는 하지만, 데이터 접근의 지역성(Locality)을 이용해서 관리되는 모든 기억장치를 부르는 데에도 사용됩니다.

 

 

처음에는 프로세서는 하나의 워드 단위의 데이터를 필요로 하며, 블록(block) 또한 하나의 워드로 이루어진 단순한 캐시를 살펴보는 것으로 시작하겠습니다.

 

 

다음은 캐시에 없는 데이터를 요청하기 전과 후의 캐시 상태를 나타내었습니다.

요청하기 전의 캐시에는 최근에 접근한 $X_1, X_2, ..., X_{n-1}$이 존재하고, 프로세서는 캐시에 없는 워드 $X_n$을 요청하였습니다.

이 요청은 실패(Miss)를 발생시키고, 워드 $X_n$을 메모리에서 캐시로 가져오게 됩니다.

 

위의 상황을 살펴보면 두 가지 해결해야 할 의문점이 생깁니다.

1. 데이터가 캐시 내에 있는지 확인하는 방법

2. 캐시 내부에 데이터가 있을 때, 그 데이터를 찾는 방법

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

각 메모리 워드의 캐시 내에서의 위치를 할당하는 가장 간단한 방법은 해당 워드의 메모리 주소를 사용하는 것입니다.

 

 

 

 

 

 

 

 

 

 

 

 

🧐 직접 사상(Direct Mapped)

각 메모리의 위치가 캐시 내의 정확히 한 곳에만 사상되는 캐시 구조를 직접 사상(Direct Mapped)이라 부릅니다.

직접 사상 캐시가 메모리 주소를 캐시 내부의 위치(캐시 인덱스)로 변환하는 방법은 대부분 간단하며, 예시로는 다음과 같습니다.

캐시 인덱스 = 블록 주소 modulo (캐시가 포함할 수 있는 블록 수)

캐시 내의 블록 수가 2의 거듭제곱인 경우, 주소의 하위 $log_2$(캐시 내의 전체 블록 수) 개수의 비트를 취하는 것으로 modulo 연산을 수행할 수 있습니다.

따라서 8블록 캐시는 블록 주소의 하위 3(8 = $2^3$)비트를 사용합니다.

 

예를 들어 블록의 메모리 주소가 001101 이고, 블럭이 최대 8개(1000)개의 블록을 포함할 수 있다면, 

해당 블록의 캐시 내의 위치는 001101 modulo 1000 = 101이 됩니다.

 

아래 그림은 더 다양한 예시들의 매핑을 보여줍니다.

해당 각 칸들은 블록 단위입니다

 

 

 

 

 

 

 

 

 

 

🧐 태그(tag)와 유효 비트(valid bit)

각 캐시 블록(엔트리)은 여러 주소의 메모리 내용을 가지고 있을 수 있습니다.

 

그렇다면 캐시 내부의 데이터가 프로세서가 요구하는 것과 일치하는지 아닌지를 판단할 수 있는 방법이 필요합니다.

예를 들어 캐시 블록의 001에 있는 데이터는 메모리의 00001에서 온 것인지, 01001에서 온 것인지를 구분할 수 있는 방법이 필요하다는 것입니다.

이는 캐시에 태그(tag)를 추가함으로써 해결할 수 있습니다.

태그는 캐시 내의 블록이 프로세서가 요청한 것인지 아닌지를 식별하는 데 필요한 주소 정보를 포함합니다.

 

태그는 캐시 인덱스로 사용되지 않은, 즉 주소의 상위 부분 비트들로 구성됩니다.

 

위의 예시에서 001101 주소의 데이터가 캐시 내에서는 101에 위치하였습니다.

이때 태그는 캐시 인덱스로 사용되지 않은 부분, 즉 001이 됩니다.

 

 

 

 

또한 캐시 블록이 유효한 정보를 가지고 있는지를 알아낼 방법이 필요합니다.

예를 들어 컴퓨터를 처음 켜서 프로세서가 작업을 시작할 때 캐시에는 아무런 값이 없어야 하지만 사실은 쓰레기 값들로 채워져 있을 것입니다.

이때 캐시 전체를 0으로 초기화 하여 사용하기보다(사실 이렇게 초기화 하더라도, 실제 데이터가 0000000.. 인 경우 문제가 발생합니다.), 해당 캐시가 유효한 데이터인지 아닌지를 확인하는 비트를 추가로 두어 이를 초기화하여 사용하는 방식이 더욱 효율적입니다.

 

즉 캐시 엔트리마다 유효 비트(Valid bit)를 추가해서 엔트리에 유효한 데이터를 가지고 있는지 아닌지를 표시하는 방법을 많이 사용합니다.

 

해당 비트가 0인 경우 해당 엔트리에 들어있는 데이터는 유효하지 않은 것으로 판단합니다.

 

 

 

 

 

 

 

 

 

 

 

🧐 캐시 접근 예제

비어있는 블록 8개로 구성된 캐시에 대하여, 메모리 참조에 따른 캐시 내용의 변화를 살펴보도록 하겠습니다.

블록에는 1워드의 데이터를 저장할 수 있다고 가정하겠습니다.

캐시 내의 블록이 $2^3$개 존재하므로, 메모리 주소의 하위 3비트만이 캐시 블록 번호로 사용됩니다.

 

또한 주소의 기본 단위를 바이트가 아니라 워드라 하겠습니다.

 

최초 캐시 상태는 다음과 같습니다.

최초 캐시 상태

인덱스는 총 8개의 블록이 존재하므로 000(0)부터 111(7)까지 존재하는 것을 알 수 있습니다.

 

 

처음으로 참조되는 데이터는 메모리 주소로 22번지(10110)에 존재하는 데이터입니다.

캐시에 존재하지 않으므로 실패(Miss)하며, 이후 메모리에서 해당 데이터를 가져오게 됩니다. (가지고 오는 데이터는 블럭 단위입니다)

 

 

 

 

이후 참조되는 데이터는 메모리 주소로 26번지(11010)에 존재하는 데이터입니다.

캐시에 존재하지 않으므로 실패(Miss)하며, 이후 메모리에서 해당 데이터를 가져오게 됩니다. 

 

 

 

이후 다시 메모리 주소 22와 26에 존재하는 데이터에 접근하며, 이 둘은 모두 캐시에 존재하므로 적중(hit)합니다.

 

 

 

 

이후 16, 3, 16의 순서로 참조가 발생합니다.

 

 

 

 

 

마지막으로 18, 16, 26의 순서로 참조가 발생합니다.

간단한 예시였으므로 이해하는데 큰 어려움은 없었을 것이라 생각합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 주소의 분할

위 예제를 통해 메모리 주소가 주어지면 캐시의 어느 곳을 찾아봐야 하는지를 바로 알 수 있음을 확인할 수 있습니다.

주소의 하위 비트들을 사용해서 이 주소가 사상되는 유일한 캐시 엔트리를 찾을 수 있습니다.

 

메모리 주소는 다음과 같이 분할되어 캐시에 사상됩니다.

(메모리) 주소 = (캐시) 블록 주소 + (캐시) 블록 변위(Offset)

(블록 변위는 여러 워드로 구성된 블록에서 필요한 하나의 워드를 찾아내는데 사용됩니다.)

블록 주소는 태그와 캐시 블록 인덱스로 나누어집니다.

블록 변위는 블록 내의 워드를 구별하는데 쓰이는 비트와, 워드 내의 바이트를 구별하는 데 쓰이는 비트로 나뉘어집니다.

일반적으로 나타내면 다음과 같습니다.

• 64비트 주소를 사용합니다.
• 직접 사상 캐시입니다.
• 캐시에는 $2^n$ 개의 블록이 있어서 (메모리) 주소의 n비트가 캐시 블록의 인덱스로 사용됩니다.
• 캐시 블록 하나의 크기는 $2^m$ 워드($2^{m+2}$ 바이트)입니다.
  • 따라서 (메모리) 주소의 m비트는 하나의 캐시 블록 내에서 워드들을 구분하는 데 쓰이며, 2비트는 하나의 워드 내에서 바이트를 구별하는 역할을 합니다.
  • 따라서 m+ 2비트는 캐시에 접근하는 경우에는 사용되지 않습니다.

 

위에서 마지막 이유 때문에, 위의 예시에서 주소의 단위를 바이트 단위가 아니라 워드 단위로 가정한 것입니다.

바이트 단위를 사용하는 것이 올바르지만, 이해하는데에는 워드 단위를 사용하는 것이 좋기 때문입니다.

이제부터 다시 주소는 워드 단위가 아닌 바이트 단위로 사용하도록 하겠습니다.

 

 

캐시에서 태그 필드의 크기는 다음과 같습니다.

64 - (n + m + 2)

 

 

직접 사상 캐시의 전체 비트 수는 다음과 같습니다. (크기의 단위는 모두 비트입니다.)

$2^n$ $\times$ (블록 크기 $+$ 태그 크기 $+$ 유효 비트 크기) 
=
$2^n$ $\times$ ($2^{m+5}$ $+$ ($64 - (n +m + 2)$) $+$ $1$)

(블록의 크기는 $2^m$ 워드 = $2^{m+2}$ 바이트 = $2^{m+5}$ 비트 입니다)

 

 

 

 

 

 

 

 

 

 

🧐 여러 워드 블록을 갖는 캐시의 주소 사상

블록 주소는 다음과 같이 구할 수 있습니다.

메모리 주소 / 블록 크기(블록당 바이트 수)

해당 블록 주소는

$\left \lfloor \frac{바이트 \;주소}{블록당\;바이트\;수} \right \rfloor \times 블록당\;바이트\;수$ ~ $\left \lfloor \frac{바이트 \;주소}{블록당\;바이트\;수} \right \rfloor \times 블록당 \; 바이트\; 수+ (블록당\;바이트\;수-1)$  사이의 모든 주소를 포함하는 블록에 해당합니다.

 

 

블록 변위는 다음과 같이 구할 수 있습니다.

메모리 주소 modulo 블록 크기(블록당 바이트 수)

 

 

블록 번호(캐시 인덱스)는 다음과 같이 구할 수 있습니다.

블록 주소 modulo 캐시 내 블록 수

 

 

태그는 다음과 같이 구할 수 있습니다.

블록 주소 / 캐시 내 블록 수

 

 

 

하나의 예시를 살펴보겠습니다.

• 64비트 주소를 사용합니다.
• 직접 사상 캐시입니다.
• 캐시에는 64($2^6$)개의 블록이 존재합니다.
• 1개의 블록의 크기는 16 바이트(= 4워드)입니다.

 

메모리 주소 1204는 다음과 같이 사상됩니다.

• 블록 주소 : 1204 / 16 =75
• 블록 변위 : 1204 modulo 16 = 4
• 블록 번호 (캐시 인덱스) : 75 modulo 64 = 11
• 태그 : 75 / 64 = 1

 

 

 

 

 

 

 

 

아래 그림은 블럭의 크기가 1 워드인 1024개의 블럭을 가질 수 있는 캐시에 대해 주소를 어떻게 분할하여 사용하는지 보여줍니다.

(Data = Block)

 

 

 

 

 

아래 그림은 블럭의 크기가 16 워드인 256개의 블럭을 가질 수 있는 캐시에 대해 주소를 어떻게 분할하여 사용하는지 보여줍니다.

(32비트 주소 사용)

 

 

 

 

 

 

 

 

 

 

 

🧐 블록의 크기와 실패율

블록이 크다면 공간적 지역성(Spatial Locality)을 잘 활용하기 때문에 실패율(miss rate)이 감소합니다.
그러나 전송해야 할 블럭의 양의 많아지기 때문에 miss penalty가 증가합니다.

블록이 작다면 miss rate가 증가합니다.
그러나 전송해야 할 블럭의 양의 적어지므로 miss penalty가 감소합니다.

 

위 그림에서 보이는 것처럼 블록 크기를 늘리면 대게 실패율(miss rate)은 줄어듭니다.

 

하지만 블록이 너무 커져 블록 하나가 캐시의 상당 부분을 차지하게 된다면 실패율이 오히려 커질 수 있습니다.

왜냐하면 캐시 내의 블록 개수가 적어지기 때문에, 블록에 대한 경쟁이 심화되기 때문입니다.

 

결과적으로 블록 내의 워드를 별로 사용하지도 못했는데 그 블록이 캐시에서 쫒겨나는 상황이 발생합니다.

바꿔 말하면 블록의 크기가 너무 커질 경우 오히려 공간적 지역성이 감소하여 실패율(miss rate)이 증가하게 됩니다.

 

 

블록 크기가 증가하면 발생하는 더 심각한 문제는 miss penalty가 증가하는 것입니다.

miss penalty는 메모리 계층구조의 다음 하위 계층에서 블록을 가져와서 캐시에 적재하는데 걸리는 시간에 의해 결정됩니다.

 

블록을 가져오는데 걸리는 시간은 두 부분으로 나누어 볼 수 있습니다.

 

첫 번째 워드를 가져오는 데 걸리는 접근 지연(latency)과, 블록의 나머지 부분에 대한 전송시간입니다.

 

블록 크기가 커지면 커질수록 전송시간이 증가하는 것은 자명합니다. 즉 실패 손실 역시 증가할 것이 자명합니다.

 

결과적으로 블록이 너무 커지면 실패 손실의 증가가 실패율 감소를 압도하게 되고, 캐시의 성능 또한 감소하게 됩니다.

 

 

 

 

 

 

👉 조기 재시작(early restart)

큰 블록의 실패 페널티 중 지연시간(latency) 부분에 대해서는 조치를 취하기 어렵지만, 전송시간은 일부를 보이지 않게 해서 실패 페널티를 효과적으로 줄일 수 있습니다.

이렇게 하는 가장 간단한 방법으로 조기 재시작이 있습니다.

이는 블록 전체를 기다리지 않고 블록 내의 요청된 워드가 도달하면 곧바로 실행을 시작하는 것입니다.

많은 시스템들이 명령어 접근에 이 기법을 이용하고 있으며, 그 효과가 매우 좋습니다.

 

그러나 이러한 방법은 데이터 캐시에 대해서는 덜 효과적인데, 블록 내의 워드 요청이 예측하기 어려운 방식으로 이루어지는 경향이 있고, 데이터 전송이 다 끝나기도 전에 다른 캐시 블록의 워드를 필요로 할 가능성이 높기 때문입니다.

 

전송이 진행 중이라 프로세서가 데이터 캐시에 접근할 수 없으면 프로세서는 지연될 수밖에 없습니다.

 

 

 

 

 

👉 요구 워드 우선(requested word first)

좀 더 정교한 기법으로 요청한 워드가 메모리에서 캐시로 제일 먼저 전송되도록 메모리를 구성하는 방법이 있습니다.

이후 요청된 워드의 다음 주소부터 순서대로 전송하고, 블록 끝까지 전송한 후에는 다시 블록의 처음 워드부터 남은 워드들을 순차적으로 전송합니다.

이 기법을 요구 워드 우선 방식 또는 중요 워드 우선 방식이라 부르며, 조기 재시작 방식보다는 조금 빠르지만 여전히 조기 재시작이 가진 한계점을 가지고 있습니다.