Memory hierarchy

데이터를 모두 하드디스크에서 처리한다면 어떨까?

적은 가격에 많은 공간을 사용할 수 있겠지만, 속도가 매우 느릴 것이다.

반대로 모두 캐시에서 처리한다면?

매우 빠르겠지만, 비싸고 적은 공간만 사용할 수 있을 것이다.

 

그렇기에 메모리는 계층구조를 이루어 데이터가 이동하며 저장 및 사용되는데, 이때 사용되는 용어가 캐싱이다.

캐시메모리 - DRAM - Disk의 계층 구조에서 장치간 동작 속도의 차이가 큰데, 이 속도차이를 극복하기 위해

디스크부터 캐시로 데이터를 미리 로드하는 행위를 캐싱이라 하는데, 캐싱이 가능한 이유는 메모리의 Locality 특성 때문이다.

Locality란, 같은 메모리 영역을 자주 접근하려는 경향, 그리고 접근한 메모리 근처의 메모리영역을 접근하려는 영향을 의미한다.

즉, 캐싱을 할 때 근처의 메모리 영역을 캐싱하면 hit확률이 올라가고 성능 향상으로 이어지는 것이다.

 

DRAM에서 데이터를 읽어올 때는 row buffer를 이용해서 여러개의 word를 읽어온다.

DRAM같은 경우에는 한 줄을 통째로 읽어오는 것인데, Locality 특성 덕분에 한 줄을 읽고난 뒤에

다른 데이터를 읽어올 때 row buffer에서 이전에 읽어온 여러개의 word중에 데이터가 있을 확률이 높다.

 

기본적인 계층 구조의 개념과 특징을 알아봤으니, 이제 각 단계에서의 동작과 성능을 평가해보자.

 

Disk

이번엔 메모리 계층구조에서 CPU에서 가장 먼 계층, 디스크에 대해 알아보자.

위에서 잠깐 언급했 듯 DRAM에서는 데이터를 읽어올 때 한 Row를 통째로 읽어오는데, Disk는 한 sector을 통째로 읽어온다.

각 섹터에는 Sector ID, Data(512 or 4096 bytes), Error Correcting Code와 같은 데이터가 저장된다.

섹터에 접근하기 위해서는 침처럼 생긴 디스크 헤더가 해당 위치로 이동하며, 실린더가 해당 위치로 돌아가야 한다.

 

이런 디스크에서 데이터를 읽어오는데는 얼마나 시간이 걸리기에 느리다고 표현하는 것일까?

한 번 예시와 함께 계산해보자.

섹터 크기: 512B
실린더 회전속도: 15,000 rpm
헤더 seek time: 4ms
데이터 읽는 속도: 100MB/s
Controller overhead: 0.2ms

 

- 평균 읽기 시간

4 + 2 + 0.005 + 0.2 = 6.2ms

* 헤드 이동시간 = 4ms

* 실린더가 반 바퀴 회전하는데 걸리는 시간 = 1/2 / (15,000/60) = 0.002s = 2ms

(1/초당 회전수 = 1바퀴 회전에 걸리는 시간)

* 데이터 전송 시간 = 512 / 100MB/s = 0.00000512s = 0.00512ms

* 컨트롤러 딜레이 = 0.2ms

 

여기서 알 수 있는 사실은 헤드 이동시간에서 소요되는 시간이 매우 큰 비중을 차지하는 것이다.

그렇기에 디스크에서 데이터를 읽을 때는 linear search가 더 효율적인 것이다.

 

Cache Memory

이번엔 메모리 계층구조에서 CPU에 가장 가까운 계층, 캐시메모리에 대해 알아보자.

메모리에서 읽은 데이터를 임시 보관하는 장소가 캐시메모리인데,

공간이 큰 메모리의 주소를 작은 공간의 캐시 주소로 변환하는 과정이 필요하다.

Direct Mapped Cache는 메모리 주소를 캐시 블럭 수로 모듈러 연산을 통해 얻어낸다.

(캐시 크기가 2^n개 일 때는 메모리의 하위 n비트를 가져와 캐시 주소를 얻을 수 있다)

 

예시를 들어보자.

1번에서 하위 3비트로 캐시 메모리의 인덱스를 알아내서 찾아간다.

이 때, 해당 위치에 데이터가 없었기에(정확히는 Valid가 No이었기에) 데이터를 넣고, miss 처리한다.

2번도 마찬가지.

3번은 찾아갔더니 데이터가 있었기에 그 데이터를 바로 사용하고 hit 처리한다.

 

이 때, 사용하지 않은 상위 비트를 tag로서 왜 저장하는걸까?

작은 도메인으로 주소를 압축하는 과정에서 collision 현상이 발생할 수 있기에

이를 구분하기 위해 tag를 사용한다.

 

위 과정을 회로 형태로 그려보면 다음과 같다.

32bit 시스템에서는 32bit의 주소를 갖는데,

일단 메모리는 word(2^2 bytes)단위로 인덱싱하기 때문에 하위 2비트를 무시한 하위 10비트를 캐시 메모리의 index삼는다.

(캐시 메모리 크기가 2^10이기 때문)

그리고 나머지 상위 비트를 tag로 삼는다.

그리고나서 메모리 접근이 요구될 때, index 포지션의 valid가 y고, tag가 일치한다면 hit이기 때문에

캐시 메모리에서 바로 데이터를 보내준다.

 

위의 캐시 메모리는 1word/block의 크기를 가졌는데, 만약 블럭의 크기가 커진다면?

1word(4bytes) -> 4word(16bytes)/block
캐시 메모리 blocks: 64 blocks

 

이 경우에는 블럭 사이즈가 2^4bytes이므로 메모리 주소의 하위 4비트를 무시해야 한다.

 

블럭 사이즈를 16word/block까지 화끈하게 키운다면?

하위 6비트를 무시해야 할 것이다. 하지만, 16word 크기의 공간에 16개의 word를 각각 채워서 캐싱한다면,

6비트를 무시하는 방법 대신 2비트만 무시하고 나머지 4개 비트로 각 word를 구분하는 역할로 사용할 수 있다.

아래의 그림으로 이해하자.

 

무식하게 블럭 사이즈만 키운다면 캐시 메모리 블럭 개수가 적어져 hit rate가 떨어지지만,

바로 위처럼 큰 블럭 사이즈를 여러개의 word를 담도록 구성한다면 hit rate를 올릴 수 있다.

 

Cache Performance

- Memory stall cycles

Memory stall cycles
= (Memory accesses / Program) * Miss rate * Miss penalty
= (Instructions / Program) * (Misses / Instruction) * Miss penalty
(= 메모리 엑세스 비율 * Miss 비율 * Miss 페널티)

 

예시를 살펴보자.

I-cache miss rate = 2% (Instruction cache)
D-cache miss rate = 4% (Data cache)
Miss penalty = 100 cycles
Base CPI = 2
Load & Store instruction ratio = 36%

 

* Miss cycles per instruction

I-cache: 0.02 * 100 = 2

D-cache: 0.04 * 100 * 0.36 = 1.44

Actual CPI: 2 + 2 + 1.44 = 5.44

 

 

- Average access time

Average access time
= Hit time * Miss rate * Miss penalty

 

예시를 살펴보자.

CPU clock: 1ns
hit time = 1 cycle
miss penalty = 20 cycles
I-cache miss rate = 5%

 

Average memory access time = 1 + 0.05 * 20 = 2ns

 

즉, miss rate를 줄여야 성능 향상에 도움이 된다.

 

Associative caches

위에서 Cache Memory에서 Direct Mapped Cache를 알아봤었다.

(특정 메모리는 특정위치의 캐시에만 매핑됨)

하지만, 이 방법은 특정 메모리가 여러 캐시 위치에 매핑되는 방법이다.

일반적으로 associative가 증가할수록 miss rate가 낮아지지만,

캐시의 탐색 비용이 증가하기 때문에 무한히 효율이 올라가진 않는다.

따라서 적정한 선을 타협해야 할 것이다.

 

각 캐시의 예시를 살펴보며 이해해보자.

0, 8, 0, 6, 8 block address 순서로 접근한다

 

- 1-way (direct mapped)

 

- 2-way

즉, 캐시 데이터 업데이트 정책에 따라 miss rate가 달라질 수 있는데, 크게 2개의 정책이 있다.

• Least-recently used(LRU)
  오랜 시간동안 사용되지 않는 을 교체하는 방법
• Random
  랜덤으로 교체하는 방법

 

- 4-way (fully)

 

Multilevel Caches

캐시를 하나만 두는 것이 아닌, L1, L2 캐시와 같이 여러개의 캐시를 둬서 성능 향상을 꾀하는 방법이다.

성능이 왜 향상되는지 예시를 보며 살펴보자.

CPU base CPI = 1
Clock rate = 4GHz
L1 Miss rate/instruction = 2%
L1 & L2 Miss rate/instruction = 0.5%
L2-cache access time = 5ns
Main memory access time = 100ns

 

* only L1-cache

Miss penalty = 100ns/(1/4GHz) = 100ns/0.25ns = 400 cycles

Effective CPI = 1 + 0.02 * 400 = 9

 

* L1, L2 cache

L1 miss penalty = 5ns/0.25ns = 20 cycles

L2 miss penalty = 100ns/0.25ns = 400 cycles

Effective CPI = 1 + 0.02 * 20 + 0.005 * 400 = 3.4

 

여기서도 알 수 있는 사실은 miss rate만 줄어도 성능이 크게 향상된다는 점이다.