[컴퓨터 구조] 캐시 메모리 - 캐시의 특징과 사상(mapping)방식

1. 캐시 메모리

1) 캐시의 특징

캐시의 위치

캐시는 CPU와 주기억장치의 속도차이를 보완하는 기억장치입니다. CPU 칩과 인접한 곳에 위치하며, CPU 칩 내부에 포함되기도 합니다. 캐시는 명령어와 데이터를 별도의 캐시에 분리하여 저장하며, 여러 레벨의 계층적 캐시로 구성하는 방법도 널리 사용되고 있습니다.

캐시의 액세스 시간은 주 기억장치의 액세스 시간보다 상당히 더 짧지만, 칩의 가격이 그만큼 높아지고 설치할 수 있는 공간도 제한되기 때문에, 캐시의 용량은 일반적으로 주기억장치의 용량에 비해 훨씬 더 적습니다.

캐시 메모리(cache memory): CPU와 주기억장치의 속도 차이를 보완하기 위하여 그 사이에 설치하는 반도체 기억장치

 

CPU가 기억장치로부터 어떤 데이터를 읽으려고 할 때는 먼저 그 데이터가 캐시에 있는지 검사합니다. 있다면 데이터를 즉시 인출하기에 액세스 시간을 크게 단축할 수 있습니다.

만약 없다면 주기억장치로부터 데이터를 인출해오는 과정에서 캐시에도 데이터를 적재(load)합니다. 이러한 과정은 데이터뿐 아니라 명령어들에 대해서도 반복되며, 결과적으로 어느 정도 시간이 경과한 후에는 주기억장치의 내용중에서 많은 부분들이 캐시에 복사되어있는 상태가 됩니다.

CPU가 원하는 데이터가 이미 캐시에 적재되어 있는 상태를 캐시 적중(cache hit), 없는 상태를 캐시 미스(cache miss)라고 합니다. 액세스들 중에서 캐시에 적중되는 비율은 캐시 적중율(cache hit ratio)라고 하면 캐시 적중율 H는 다음과 같이 나타낼 수 있습니다.

캐시 적중률

 

캐시에 없을 확률인 미스율(miss ratio)는 $(1-H)$가 됩니다.
캐시가 사용되는 시스템에서 평균 기억장치 액세스 시간 $T_{a}$는 다음과 같이 계산할 수 있습니다.

$$T_{a} = H\times T_{c} + (1-H) \times T_{m} $$

$T_{c}$ 는 캐시 액세스 시간, $T_{m}$ 은 주기억장치 액세스 시간을 나타냅니다.

캐시 적중(cache hit): CPU가 액세스 하려는 데이터가 이미 캐시에 적재되어 있는 상태

캐시 미스(cache miss): CPU가 액세스 하려는 데이터가 캐시에 없어서 주기억장치로부터 인출해와야 하는 상태

캐시 적중률(cache hit ratio): 전체 기억장치 액세스들 중에서 캐시에 적중되는 비율

예시를 통해 적중률에 따른 액세스 시간을 보겠습니다.

// Tc = 10ns, Tm = 100ns 일때, 각 캐시 적중률(H)에서의 평균 기억장치 액세스 시간

H = 70% -> Ta = 37ns
H = 80% -> Ta = 28ns
H = 90% -> Ta = 19ns
H = 95% -> Ta = 14.5ns
H = 99% -> Ta = 10.9ns

위의 예시를 보면 캐시적중률이 높아질수록 평균 액세스 시간은 캐시의 액세스 시간에 접근한다는 것을 알 수 있습니다.

이는 CPU가 주기억장치의 특정 부분에 위치한 프로그램 코드 데이터를 빈번히 혹은 집중적으로 액세스하는 지역성에 크게 의존합니다.

지역성의 특성은 다음과 같습니다.

• 시간적 지역성(temporal locality)
  • 최근 액세스된 프로그램 코드나 데이터가 가까운 미래에 다시 액세스될 가능성이 높아지는 특성
  • 반복 루프 프로그램이나 서브루틴들은 반복적으로 호출, 공통변수들도 빈번히 액세스
• 공간적 지역성(spatial locality)
  • 기억장치 내에 서로 인접하여 저장된 데이터들이 연속적으로 액세스될 가능성이 높아지는 특성
  • 표나 배열 데이터들이 저장되어 있는 기억장치 영역은 그들에 대한 연산이 수행되는 동안에 집중적으로 액세스
• 순차적 지역성(sequential locality)
  • 분기가 발생하지 않는 한 명령어들은 기억장치에 저장된 순서대로 인출되어 실행
  • 순차적 실행과 비순차적 실행의 비율이 대략적으로 5:1 정도

이러한 지역성들 때문에 캐시에 저장되어 있는 정보들은 CPU에 의해 다시 사용되는 경우가 많습니다.

2) 캐시 용량

캐시의 크기, 즉 용량이 커질수록 캐시 적중률이 높아집니다.

하지만 그에따라 비용이 증가하고, 주소 해독 및 정보 인출을 위한 주변회로가 더 복잡해지는 문제도 발생합니다. 

캐시 용량은 칩 혹은 주기판(main board)의 공간에 의해서도 제한을 받습니다.

즉, 캐시의 용량을 증가시키는 것은 필요하지만, 최적의 캐시용량을 결정하는 것은 쉬운일이 아닙니다.

3) 캐시의 인출 방식

캐시를 인출해오는 방식도 캐시 적중률에 많은 영향을 줍니다.

요구 인출(demand fetch) 방식은 필요한 정보만 인출해 오는 방법이고, 선인출(prefetch) 방식은 필요한 정보 외에 앞으로 필요한 것으로 예측되는 정보도 미리 인출해 오는 방법입니다. 즉, CPU가 원하는 정보를 인출할 떄 그 정보와 근접한 위치에 있는 정보들을 함께 인출하여 캐시에 적재합니다. 이를 통해 지역성의 특성을 이용하여 캐시 적중률을 높일 수 있습니다.

요구 인출(demand fetch): 캐시 미스가 발생한 경우에, CPU가 필요한 정보만 주기억장치로부터 캐시로 인출해오는 방식

선인출(prefetch): CPU가 필요한 정보 외에도 그와 인접해 있는 정보들을 함께 캐시로 인출해오는 방식

이와 같이 주기억장치를 액세스할 때 함께 인출되는 정보들의 그룹을 블록(block)이라고 합니다.

블록이 커지면 한 번에 더 많은 정보를 읽어올 수 있지만, 인출 시간이 그만큼 더 길어집니다.

따라서 선인출 방식은 지역성이 높은 경우에는 효과가 있지만, 그렇지 않은 경우에는 인출 시간 떄문에 비효율적일 수 있습니다.

 

주기억장치와 캐시의 조직

주기억장치는 $2^{n}$개의 단어(word)들로 구성되며, 각 단어는 n비트의 주소에 의해 지정됩니다.

선인출을 위하여 주기억장치를 K개의 단어들로 이루어진 블록으로 나눌 경우에 전체 블록들의 개수는 $2^{n}/K$가 됩니다.

캐시는 m개의 라인(line)들로 구성되는데, 각 라인에는 주기억장치 블록과 같은 크기인 K개의 단어들이 저장됩니다.

CPU가 주기억장치들로부터 어떤 단어를 읽으면, 그 단어를 포함하고 있는 블록 전체가 캐시라인들 중의 어느 하나에 적재됩니다.

캐시 라인의 수는 주기억장치 블록의 수보다 훨씬 더 적기 때문에, 기억장치 블록들 중 일부분만이 캐시에 적재됩니다.

캐시의 각 라인은 여러 개의 블록들에 의해 공유되고, 현재 자신을 공유하는 블록들 중의 어느것이 적재되어있는지를 태그(tag)를 통해 구분합니다.

캐시 라인(cache line): 주기억장치로부터 캐시로 인출되는 단위인 한 블록(block)이 적재되는 캐시내 공간

태그(tag): 캐시 라인을 공유하는 블록들 중에서 어느 것이 적재되어 있는지를 가리키는 비트들

 

2. 캐시의 사상 방식(mapping)

1) 사상 방식

어떤 주기억장치 블록들이 어느 캐시 라인을 공유할 것인지를 결정해주는 방법을 주기억장치와 캐시간의 사상방식(mappinng schema)라고 합니다. 이는 캐시 적중률에도 많은 영향을 미치는 주요 설계요소이고, 캐시의 내부조직은 사상방식에 의해 결정됩니다.

가장 널리 사용되고 있는 사상 방식으로는 세 가지가 있는데 직접 사상(direct mapping), 완전-연관 사상(fully-associative mapping), 세트-연관 사상(set-associatvie mapping) 방식입니다. 각 방식의 설계 원리와 내부 조직을 살펴보겠습니다.

사상 방식(mapping schema): 주기억장치 블록이 어느 캐시라인에 적재될 수 있는지를 결정해주는 알고리즘

2) 직접 사상(direct mapping)

직접 사상(direct mapping) 방식에서는 주기억장치의 블록들이 지정된 어느 한 캐시 라인으로만 사상될 수 있습니다.

이 방식을 구현하기 위해, 주기억장치 주소는 다음과 같이 세 개의 필드들로 구성된 것으로 해석합니다.

 

이 주소의 상위 $(t+l)$ 비트들은 주기억장치의 $2^{t+l}$개의 블록들 중의 하나를 지정해줍니다.

최하위 $w$ 비트들은 $2^{w}$개의 단어들로 구성된 각 블록 내의 단어들을 구분하는 데 사용됩니다.

캐시제어기(cache controller)는 최상위 t개의 비트들을 태그(tag)번호로 해석하고, 그 다음 $l$개의 비트들은 라인 번호로 해석합니다.

라인 번호는 캐시의 $m = 2^{l}$개의 라인들 중에서 그 블록이 적재될 수 있는 라인을 지정해줍니다. 태그번호는 같은 캐시라인을 공유하는 주기억장치 블록들을 서로 구분하는데 사용합니다.

이 방식에서 주기억장치의 블록 $j$가 적재될 수 있는 캐시 라인의 번호 $i$는 다음과 같은 모듈로(modulo)함수에 의해 결정됩니다.

$$i  = j \ mod \ m$$

예를들어 캐시 라인의수 $m = 4$ 라면, 주기억장치의 여섯 번째 블록$(j = 6)$은 $6  \%  4 = 2$이므로 캐시의 2번 라인에 적재됩니다.

이를 표로 나타내면 다음과 같습니다.

 

각 캐시 라인을 공유하는 주기억장치 블록들

 

각 캐시라인은 $2^{t}$개의 블록들에 의해 공유됩니다.

캐시의 각 라인에는 태그와 데이터 블록이 함께 저장되며, 캐시 적중 여부는 주소의 태그비트들과 라인에 저장된 태그를 비교함으로써 결정됩니다.

직접 사상 캐시의 조직

직접 사상방식을 이용한 캐시의 내부 조직은 위의 그림과 같습니다.

이 조직에서 읽기 동작은 다음과 같이 진행됩니다.

1. 캐시로 기억장치 주소가 보내짐
2. 주소 비트들 중에서 라인필드의 $l$비트들에 의해 캐시의 해당 라인이 선택
3. 선택된 라인의 태그 비트들이 읽혀져서 주소의 태그 비트들과 비교
   1. 일치 시 캐시 적중
      
      1. 주소의 $w$개의 비트들을 이용하여 라인 내의 단어들 중에서 하나가 선택되고, 그 단어는 인출되어 CPU로 보내짐
   2. 불일치 시 캐시 미스
      1. 기억장치 주소 전체가 주기억장치로 보내져서 한 블록을 인출
      2. 인출된 블록은 지정된 캐시 라인에 적재, 주소의 태그 비트들이 라인의 태그 필드에 저장
      3. 만약 라인을 공유하는 다른 블록이 이미 그 라인에 적재되어 있다면, 원래의 블록은 지워지고 새로운 블록 적재

직접 사상방식은 간단하고, 구현하는 비용이 적게 든다는 장점을 가지고 있지만,
각 주기억장치 블록이 적재될 수 있는 캐시라인이 한 개 뿐이라는 단점 또한 가지고 있습니다.

따라서 만약 어떤 프로그램의 수행 과정에서 같은 라인에 사상되는 두 개의 블록들로부터 데이터들을 번갈아 읽어와야한다면, 블록들은 캐시에서 반복적으로 교체되고, 적중률은 낮아집니다.

3) 완전-연관 사상(fully-associative mapping)

완전-연관 사상방식은 주기억장치 블록이 캐시의 어떤 라인으로든 적재될 수 있도록 허용함으로써 직접 사상 방식의 단점을 보완한 것 입니다. 이 방식에서는 아래와 같이 태그 필드와 단어 필드로만 구성된 것으로 해석합니다.

 

결과적으로, 태그값이 주기억장치 블록 번호와 같아집니다. 따라서 어떤 블록이 캐시로 적재될 때, 그 주소의 태그 필드의 모든 비트들이 그 라인의 태그 부분에 저장되어야 합니다.

 

완전-연관 사상 캐시의 조직

그림에서 보는것과 같이 기억장치 주소의 태그 비트들은 모든 캐시라인의 태그들과 비교되어야 합니다.

비교를 하나씩 순차적으로 진행하려면 많은 시간이 걸릴것이므로 연관기억장치 등을 이용하여 병렬로 수행될 수 있도록 합니다.

이 방식에서는 주기억장치로부터 인출된 데이터 블록을 캐시의 어느 라인에 적재할 것인지를 결정해야 합니다.

만약 캐시에 빈 라인들이 있다면, 라인 번호에 따라 차례대로 적재하면 됩니다.
하지만 비어있는 라인이 없다면 적절한 교체 알고리즘(replacement algorithm)을 이용하여 라인들 중의 하나를 새로 선택한 다음에 블록을 적재합니다.

완전-연관 사상에서는 새로운 블록이 캐시로 적재될 때 라인의 선택이 자유롭기 때문에, 프로그램 세그먼트나 데이터 배열 전체가 캐시로 적재될 수 있습니다. 이 경우에 지역성이 높다면, 적중률 또한 매우 높아집니다.

하지만 완전-연관 사상 방식은 모든 태그들을 병렬로 검사하기 위해 복잡하고 비용이 높은 하드웨어를 포함해야 한다는 단점 때문에 실제로는 거의 사용되지 않습니다.

4) 세트-연관 사상(set-associative mapping)

세트-연관 사상 방식은 직접 사상 방식과 완전-사상 방식의 장점만을 취하기 위한 절충안입니다.

주기억장치 블록이 지정된 어느 한 세트로만 적재될 수 있으며, 각 세트는 두 개 이상의 라인들로 구성된 사상방식 입니다.

이 경우에 캐시는 먼저 $v$개의 세트(set)들로 나누어지며, 각 세트는 $k$개의 라인들로 구성됩니다.

전체 캐시라인의 수 $m$과 그 변수들간의 관계는 다음과 같습니다.

 

$$m = v \times k$$

$$ i = j \ mod \ v$$

 

$m$ : 캐시 라인의 전채 개수

$i$ : 세트 번호

$j$ : 주기억장치의 블록 번호

세트당 라인이 $k$개씩 있으면 k-way 세트-연관 사상 이라고 부릅니다.

 

여기서 $s$개의 세트 비트들은 캐시의 $v=2^{s}$개 세트들 중에서 해당 주기억장치 블록이 적재될 수 있는 세트를 선택하는데 사용되고, 태그 필드의 t 비트들은 그 세트 내에 있는 라인들의 태그들과 비교되어 캐시 적중 여부를 확인하는데 사용됩니다.

 

세트-연관 사상 캐시의 조직

위의 그림은 캐시의 각 세트가 두 개의 라인들로 구성된 경우, 즉 2-way 세트-연관 사상 캐시의 조직을 보여주고 있습니다.

먼저 지정된 세트에 포함된 라인의 태그들이 기억장치 주소의 태그와 비교됩니다.
만약 일치되는 태그가 있다면, 캐시가 적중된 것이므로 $w$개의 비트에 의해 그 라인 내 $2^{w}$개의 단어들 중 하나가 선택되어 인출됩니다.
세트 내 어느 라인의 태그와도 일치하지 않는다면 주기억장치 액세스가 시작됩니다.

이 방식을 사용하면 주기억장치 블록은 지정된 어느 한 세트에 적재될 수 있습니다.
각 세트에는 다수의 라인이 있으므로, 직접 사상 방식에 비하여 기억장치 블록이 적재될 수 있는 공간이 더 많아집니다.

하지만 캐시의 전체 용량은 고정되어 있기 때문에 세트의 수는 그만큼 감소합니다.

 

---

지쳐가는 5월입니다. 화이팅!!!