Cache

Caches

캐시는 CPU 칩 안에 들어가는 작고 빠른 메모리다. (그리고 비싸다.) 프로세서가 매번 메인 메모리에 접근해 데이터를 받아오면 시간이 오래 걸리기 때문에 캐시에 자주 사용하는 데이터를 담아두고, 해당 데이터가 필요할 때 프로세서가 메인 메모리 대신 캐시에 접근하도록해 처리 속도를 높인다.

CPU 칩에는 여러 개의 캐시가 들어가며, 각각의 캐시는 각자의 목적과 역할을 가지고 있다.

+-------------+------+------+     +---------------+     +--------+
|             |  I$  |      | <-- |               | <-- |        |
+  Processor  +------+  L2  |     |  Main Memory  |     |  Disk  |
|             |  D$  |      | --> |               | --> |        |
+-------------+------+------+     +---------------+     +--------+

• L1 Cache: 프로세서와 가장 가까운 캐시. 속도를 위해 I$와 D$로 나뉜다.
  • Instruction Cache (I$): 메모리의 TEXT 영역 데이터를 다루는 캐시.
  • Data Cache (D$): TEXT 영역을 제외한 모든 데이터를 다루는 캐시.
• L2 Cache: 용량이 큰 캐시. 크기를 위해 L1 캐시처럼 나누지 않는다.
• L3 Cache: 멀티 코어 시스템에서 여러 코어가 공유하는 캐시.

Principle of Locality

캐시 메모리는 속도가 빠른 장치와 느린 장치간의 속도차에 따른 병목 현상을 줄이기 위한 범용 메모리이다. 이러한 역할을 수행하기 위해서는 CPU 가 어떤 데이터를 원할 것인가를 어느 정도 예측할 수 있어야 한다. 캐시의 성능은 작은 용량의 캐시 메모리에 CPU 가 이후에 참조할, 쓸모 있는 정보가 어느 정도 들어있느냐에 따라 좌우되기 때문이다.

이 때 적중율(Hit rate)을 극대화 시키기 위해 데이터 지역성(Locality)의 원리를 사용한다. 지역성의 전제조건으로 프로그램은 모든 코드나 데이터를 균등하게 Access 하지 않는다는 특성을 기본으로 한다. 즉, Locality란 기억 장치 내의 정보를 균일하게 Access 하는 것이 아닌 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성인 것이다.

이 데이터 지역성은 대표적으로 시간 지역성(Temporal Locality)과 공간 지역성(Spatial Locality)으로 나뉜다.

• 시간 지역성 : 최근에 참조된 주소의 내용은 곧 다음에 다시 참조되는 특성.
• 공간 지역성 : 대부분의 실제 프로그램이 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성

Cache Metrics

캐시의 성능을 측정할 때는 히트 레이턴시(Hit latency)와 미스 레이턴시(Miss latency)가 중요한 요인으로 꼽힌다.

CPU에서 요청한 데이터가 캐시에 존재하는 경우를 캐시 히트(Hit)라고 한다. 히트 레이턴시는 히트가 발생해 캐싱된 데이터를 가져올 때 소요되는 시간을 의미한다. 반면 요청한 데이터가 캐시에 존재하지 않는 경우를 캐시 미스(Miss)라고 하며, 미스 레이턴시는 미스가 발생해 상위 캐시에서 데이터를 가져오거나(L1 캐시에 데이터가 없어서 L2 캐시에서 데이터를 찾는 경우) 메모리에서 데이터를 가져올 때 소요되는 시간을 말한다.

평균 접근 시간(Average access time)은 다음과 같이 구한다:

캐시의 성능을 높이기 위해서는 캐시의 크기를 줄여 히트 레이턴시를 줄이거나, 캐시의 크기를 늘려 미스 비율을 줄이거나, 더 빠른 캐시를 이용해 레이턴시를 줄이는 방법이 있다

Caching line

CPU가 메모리 주소를 사용하여 메모리로 데이터를 받을려고 한다. 하지만 CPU가 쓰는 주소는 가상 메모리 주소로 메모리 입장에서는 외계어다. 따라서 중간에 메모리 관리 장치(MMU)가 가운데에서 번역을 하여 메모리가 알아 먹을 수 있는 물리 주소로 변환을 해준다. 그리고 캐시에 해당 주소에 대한 데이터가 있는지 확인을 하는데 캐시에 데이터를 저장하는 방식에 따라 물리주소를 다르게 해석을 할 수 있다.

그렇기 때문에 캐시에 데이터를 저장할 때 특정 자료구조를 사용하여 묶음으로 저장하게 되는데 이를 캐싱 라인 이라고 한다. 다양한 주소에 있는 데이터를 사용하므로 빈번하게 사용하는 데이터의 주소는 흩어져 있다. 따라서 캐시에 저장하는 데이터에는 데이터의 메모리 주소 등을 기록해 둔 태그를 달아놓을 필요가 있다. 이러한 태그들의 묶음을 캐싱 라인이라고 하고 메모리로부터 가져올 때도 캐싱 라인을 기준으로 가져온다. 종류로는 대표적으로 세 가지 방식이 존재한다.

Direct Mapping

우선 메인 메모리에서 캐시로 데이터를 저장할 때 참조의 지역성 때문에 한번 퍼낼 때 인접한 곳까지 한꺼번에 캐시 메모리에 저장하고 이 때 단위를 블록(Block)라고 한다. 그리고 캐쉬는 메인 메모리의 몇번째 블록인지를 알려주는 태그(Tag)도 함께 저장한다.

메모리 주소 중에 가장뒷부분(붉은색)은 블럭의 크기를 의미한다. 지금 블럭의 크기가 4이므로 뒤의 두자리를 사용하여 블럭의 크기를 표현하였다. 그리고 이 영역은 블럭에 몇 번째에 원하는 데이터가 있는지 보여주는 지표가 되어 준다. 만일 위의 예에서 붉은 영역이 01이라면 블록의 두 번째 내용을 CPU에서 요청한 것이다.

같은 라인에 위치하는 데이터는 파란색 색칠한 영역에 의하여 구별이 가능하다.. 예를 들면 메모리의 첫번째 요소 00000과 다섯번째 주소 00100은 캐시내에 같은 위치에 자리잡고 있어서 구별이 필요로 한데, 앞의 세자리 000과 001로 구별을 할 수 있다.

이와 같은 요소의 활용은 캐시 메모리에 저장된 데이터 중 내가 원하는 것이 있는지 없는지 확인이 가능하다.

1. 캐시의 태그와 주소상의 태그가 동일한지 확인한 후 같으면 붉은 영역을 통해 데이터를 읽는다.
2. 만일 태그가 다르다면 메모리에서 데이터를 가지고 온다.

직접 매핑은 위의 사진처럼 캐시에 저장된 데이터들은 메인 메모리에서와 동일한 배열을 가지도록 매핑하는 방법을 말한다. 이와 같은 방식을 사용하기 때문에 매우 단순하고 탐색이 쉽다는 장점이 있다. 하지만 적중률(Hit ratio)가 낮다는 단점이 있다. 반복문을 사용할 건데 같은 라인의 00000을 불렀다가 그다음엔 00100을 부른다면 캐시에 빈번하게 변경이 발생할수 있기 때문이다.

Associative Mapping

연관 매핑은 직접 매핑의 단점을 보완하기 위해 등장하였다. 캐시에 저장된 데이터들은 메인 메모리의 순서와는 아무런 관련이 없다. 이와 같은 방식을 사용하기 때문에 캐시를 전부 뒤져서 태그가 같은 데이터가 있는지 확인해야한다. 따라서 병렬 검사를 위해 복잡한 회로를 가지고 있는 단점이 있지만 적중률이 높다는 장점이 있다.

Set Associative Mapping

직접 매핑의 단순한 회로와 연관 매핑의 적중률 두 개의 장점만을 취하기 위해서 만들어진 방식이다. 각각의 라인들은 하나의 에 속해 있다. 세트 번호를 통해 영역을 탐색하므로 연관 매핑의 병렬 탐색을 줄일 수 있다그리고 모든 라인에 연관 매핑처럼 무작위로 위치하여 직접매핑의 단점도 보완하였다. 세트 안의 라인 수에 따라 n-way연관 매핑이라고 한다.(위 그림은 2-way 연관 매핑)