10. 메모리 계층 (Memory Hierarchy)

최근 수년간 메모리(DRAM)의 속도는 프로세서의 속도 증가에 비해 많이 증가하지 않았다.
이로인해, 프로세서와 메모리 사이의 속도 차이는 점차 커지고 있다.

이러한 문제를 해결하고자 컴퓨터 구조에서는 메모리의 계층을 분리하여 가장 빠른 메모리인 레지스터를 프로세서 데이터 패스 안에 넣고, 레지스터에 비해 느린 메모리에서 레지스터로 미리 데이터를 보내놓는 방식으로 속도 차이로 인한 문제를 완화시키고 있다.

레지스터와 시스템 메모리 사이에는 L1 캐시, L2 캐시 L3 캐시와 같은 메모리가 추가로 들어가서 이러한 역할을 수행한다.

	레지스터	L1캐시	L2캐시	L3캐시	메모리 (DRAM)
속도	빠름	↔			느림
크기(용량)	작음				큼
비용	비쌈				쌈

메모리 계층의 관리

메모리 계층의 관리는 다음과 같은 주체에 의해 이루어진다.

• 레지스터 ↔ 메모리 : 컴파일러, 프로그래머 (어셈블리 등 일부 언어)
• 캐시 ↔ 메모리 : 하드웨어
• 메모리 ↔ 디스크 : 하드웨어와 운영체제 (가상 메모리), 프로그래머 (파일 관리)

메모리 기술

• Static RAM (SRAM) : 레지스터 다음으로 가장 빠르고 가장 비쌈
• Dynamic RAM (DRAM) : 빠르고 비쌈
• Magnetic Disk : 느리고 쌈
• 이상적인 메모리는 SRAM의 속도를 가지면서도 disk와 같은 저장용량 대비 가격비를 갖는 메모리

이전 시대의 메모리(CD 등)들은 Sequential Access 방법을 사용했다. 메모리 상의 어떤 위치에 존재하는 데이터에 접근하려면, 마치 비디오 테이프를 앞으로 감듯 해당 위치까지의 모든 영역을 거쳐 접근해야 했고, 이 때문에 속도가 느렸다.

반면 Random Access 방법을 채용한 메모리인 DRAM, SRAM 등은 이런 문제가 해결되었다. 이런 메모리들을 RAM^{Random Access Memory}이라고 부른다.

DRAM과 SRAM

• DRAM
  • 보통 1개의 트랜지스터를 사용한다.
  • 이 때문에 밀집도가 높아 많은 데이터를 저장할 수 있고, 저전력이며, 저렴하다.
  • 그러나 느리다.
  • 트랜지스터가 하나기 때문에 주기적으로 refresh 해주지 않으면 전하가 점점 약해져 데이터가 사라진다. (Dynamic)
• SRAM
  • 보통 6개의 트랜지스터를 사용한다.
  • 밀집도가 낮아 전력을 많이 소모하고, 비싸지만 빠르다.
  • 6개의 트랜지스터로 데이터가 유지되어, 전력을 끊기 전까지 데이터가 유지된다. (Static)

현대의 컴퓨터는 주로 주기억장치로 DRAM을 활용하고, 캐시 메모리로 SRAM을 사용한다.

지역성^Locality

프로그램은 메모리의 작은 특정 영역에 반복적으로 접근한다. (반복문, 자주 쓰이는 프로그램 함수 등)
여기서 지역성이 발생하는데, 캐시 메모리의 원리는 이에 기반한다.

• 시간적 지역성^{Temporal Locality}
  • 최근 access된 item들은 조만간 다시 access되는 경향이 있음
  • 반복문, 귀납 변수 등
• 공간적 지역성^{Spatial Locality}
  • 최근에 access된 item들 근처에 것들이 조만간 다시 access되는 경향이 있음
  • 순차적 명령어 실행, 배열 데이터 등

지역성과 캐시

메모리 계층 구조의 원리는 지역성과 밀접한 관련이 있다. Disk에 저장된 정보 중, 최근에 access된 item과(시간적 지역성) 그 주변의 item들(공간적 지역성)을 disk로부터 smaller DRAM memory로 copy해 놓는다.

더욱 최근에 access된 (인접) item들은 DRAM으로부터 smaller SRAM memory로 copy해 놓는다.

메모리 계층 레벨

만약 Access된 데이터가 상위 계층 메모리에 존재하면 Hit라고 한다. 즉, 사용될 것으로 예상되어 캐시해 둔 메모리가 실제로 사용된 것이다.

하지만 Access할 데이터가 하위 계층 메모리에 존재하면, 즉, 예측하지 못한 데이터가 요구된다면 이는 Miss라고 표현하고, 이를 상위 계층 메모리를 거쳐 프로세서까지 전달하는데 걸리는 시간을 Miss Penalty라고 한다.

DRAM의 구조

메모리 접근에 Miss가 발생하여, DRAM에서 데이터를 불러올 때, DRAM의 데이터를 모두 탐색하면 너무 오랜 시간이 걸린다. 때문에 병렬처리를 위한 Memory Bank 구조가 되었다.

DRAM 구조

DRAM은 수많은 열로 이루어진 데이터 뱅크로 볼 수 있다. DRAM의 데이터에 접근할 때, 32비트 주소 중 우선 상위 주소인 행 주소만을 받아온다.

행 주소를 기반으로 DRAM의 모든 해당 행의 데이터를 bus로 옮긴다. 이제, 열 주소를 이용하여 그 중 정확한 데이터를 찾는다. 행 주소로부터 데이터를 bus로 불러오는 시간이 오래걸리는 편인데, 행 주소와 열 주소 요청의 간격이 짧다면 좋은 RAM이다.

행 주소가 4인 메모리에서 값을 불러오는 것보다, 행 주소가 1인 메모리에서 값을 4개 가져와, 속도가 빠른 Bus에서 맞는 값을 받아왔는지 판별하는 것이 빠르다. 즉, 데이터 뱅크가 늘어날수록 메모리 성능이 향상되는데, 이를 대역폭이라 한다.

최근에는 요구되는 행 주소가 같다면 행 주소를 이용한 데이터 다운을 생략하는 버스트 모드가 적용되는데, 이런 방식을 Double Data Rate, DDR이라고 한다. 이런 과정을 2배로 개선한 QDR(DDR 2)도 존재하는데 현재는 DDR 4가 널리 통용되고 있다.

메모리 Bank

프로세서에서 메모리로 데이터를 요청할 때, 주소를 전달하는 과정에서 1 Cycle이 소요된다. 이후, 크기 1의 DRAM Access 시마다 15 Cycle이 소요되고, 찾아낸 데이터를 프로세서로 보내는데 1 Cycle이 소요된다.

이때, Bank 방식의 메모리와 시퀀스 메모리를 비교해보자.

길이 4의 시퀀스 메모리 접근을 생각해보자.

$$P = 1 + 4\times 15 + 1 = 62$$

길이 4를 모두 탐색하는 데 많은 시간이 소요된다. 반면 Bank 방식은 길이 1인 DRAM 4개를 동시 탐색한다.

$$P = 1 + 15 + 4\times 1 = 20$$

비록 bus로 데이터를 4번 보내야 하지만, bus야 실행속도가 1 사이클밖에 안되니 시퀀스 메모리보다 훨씬 빠르다.

캐시 주소 문제

캐시에서는 두 가지 문제가 발생하는데, 우리가 찾는 데이터가 캐시에 있는지를 확인해야 하고, 이 데이터가 있다면 어떻게 찾을지가 문제이다.

직접 매핑이 하나의 방법이다. 원래 데이터의 메모리 주소를 캐시 메모리의 용량으로 모듈로 연산하여 캐시 상에서의 주소를 정할 수 있다. (메모리 주소 % 캐시 용량)

이를 이용하여, 접근하고자 하는 메모리의 하위 비트들을 이용해 캐시 상에서 해당 데이터의 위치를 알 수 있다.

한번에 꼭 1바이트씩 다룰 것 없이 블럭 크기를 키워서 여러 데이터들을 다룰 수 있는데, 이렇게 되면 공간적 지역성이 확보되어 Miss가 적어지지만, Miss Penalty는 증가한다.

또 다른 방법은 Set Associative다. 직접 매핑에서 어떤 캐시 주소 000에 들어가야 하는 두 데이터 $A,B$가 번갈아 호출되는 상황을 고려해보자. 두 데이터는 반복적으로 호출됨에도 계속 miss가 난다.

이를 막기 위해, Set Associative는 두개의 블럭을 한 캐시에 넣을 수 있다. 이런식으로 확장되어 캐시에 얼마든지 데이터가 들어가는 Fully Associative도 있지만, 이는 너무 Idle한 상황이므로 다루지 않겠다.

예시

데이터의 주소가 $11101$이고, 캐시 크기가 $8 (000 ~ 111)$이면, 해당 데이터의 캐시에서의 주소는 $101$이다.

캐시 Associativity

캐시 주소 (entry)로 들어온 데이터는 Tag와 Data로 구성되어 저장되는데, Tag는 Cache에 들어오는 과정에서 사용하지 않은 주소의 나머지 부분이다. (예를들어 위 예시에서, 11)

One-way set associative, 즉 직접 매핑에서는 한 entry에 한 쌍의 데이터만을 저장하지만, Two-way나 Four-way에서는 각각 2, 4개의 쌍을저장한다.

실험적으로, Associative를 1-way에서 2-way로 늘릴 때 성능이 크게 향상되며, 이후에는 비슷하다. 이 때문에 주로 2-way나 4-way 가 사용된다.

자세히 보기

데이터 주소는 32비트로 구성된다. 이 중, 최하위 2비트는 어차피 데이터가 1바이트 단위로 처리되므로 중요하지 않다.

다음 하위비트 8비트는 데이터의 Index로, Cache entry를 결정하는데 사용된다. 캐시의 어느 엔트리에 값이 저장될지 결정하고 나면, 나머지 22비트인 index를 활용해 우리가 찾는 데이터를 엔트리 속에서 찾는다.

캐시 대체

특정 캐시의 값을 대체하는 조건이다. 직접 매핑의 경우 한 cache entry에 값을 하나밖에 가지지 못하므로 선택의 여지가 없다. 대체할 값이 생기면 대체해야 한다.

Set Associative에서는 Non-valid entry가 있으면 이를 사용하고, 아니면 현재 저장된 값 중 삭제할 값을 선정하는데, 가장 오랫동안 사용되지 않은 것을 선택한다.

캐시 Miss

Miss가 발생하면 아래와 같은 절차를 따른다.

• CPU 파이프라인이 Stall
• 필요한 블럭을 메모리 하위 계층에서 가져온다.
• Cache Miss Instruction을 실행한다. (IF를 재개한다.)

Write-Through / Write-Back

프로세서와 캐시가 데이터를 주고 받으며, 당연하게도 캐시에 저장된 데이터는 변화하게 된다. 이 변화된 데이터는 당연히 메모리에 반영되어야 하는데, 이 반영의 시기를 결정하는 방법이 두 가지 있다.

Write-Through는 프로세서에서 접근된 캐시의 데이터를 바로 메모리에 업데이트한다.
Write-Back은 캐시의 데이터가 dirty할 때, 즉 변경되었을 때만 메모리에 반영한다. (이를 위해 블록마다 dirty bit을 둔다.)

일반적으로 성능이 좋은 Write-Back을 쓴다.

캐시 퍼포먼스 비교해보기

Instructon 캐시의 miss율이 2%, Data 캐시의 miss율이 4%이고, miss penalty가 100 사이클, Base CPI (Miss 0일 때)가 2이고, Load&Store 명령어가 36%의 비중을 가질 때, 명령어당 miss cycle은 아래와 같다.

• I-cache: $0.02 \times 100 = 2$
• D-cache: $0.36 \times 0.04 \times 100 = 1.44$

실제 CPI는 $2 + (2 + 1.44) = 5.44$가 된다. (일반 명령어 miss 시 지연 2, load&store 명령 지연시 2 + 1.44 지연)

즉, miss가 없을 때의 프로세서는 $5.44 / 2 = 2.72$배 성능이 좋다.

평균 메모리 접근 시간

Average Memory Access Time = Hit time + Miss Rate $\times$ Miss Penalty

1ns의 클럭을 갖는 CPU에서, hit time이 1 사이클, miss penalty가 20 사이클이고 I-cache miss rate가 5%라면 AMAT은 아래와 같다.

$$\text{AMAT} = 1+ 0.05\times 20 = 2\text{ns}$$

예제: 다계층 캐시

CPU의 CPI가 1이고, Clock Rate는 4GHz이다.
miss율은 2%이며, 메인 메모리 접근 시간은 100ns이다.

primary cache(L1)에서 miss penalty = 100ns/0.25ns = 400 사이클이고, Effective CPI는 1 + 0.02 $\times$ 400 = 9이다. 무려 실제 CPI의 9배이다.

L2 캐시의 접근 시간이 5ns이고 메인 메모리까지 전체 miss율이 0.5%라고 하자.

L1 캐시에서 바로 메인 메모리에 접근하지 않으므로 L1 캐시의 miss penalty가 5ns/0.25ns = 20 사이클로 감소한다.
덕분에 CPI는 $1 + 0.02 \times 20 + 0.005 \times 400 = 3.4$가 된다. 이는 L1 캐시만 있을 때에 비해 2.6배 향상된 결과이다.

다계층 캐시의 고려사항

L1 캐시는 hit time을 최소화 하는 것이 중요하다. (hit이 많이 발생한다는 전재)
L2 캐시는 Main Memory Access를 최소화하기 위하여 miss rate를 최소화 하는 것이 중요하고, hit rate는 전체적인 영향을 크게 주지 않는다.

이로 인해 L1 캐시는 크기가 작고, 블럭 사이즈도 L2에 비해 작아지는 결과가 생겼다.

가상 메모리

메인 메모리가 부족할 경우, 보조 기억장치를 일종의 캐시로 사용하는 기법이다. CPU 하드웨어와 운영체제가 함께 관리하게 되는데, 프로그램들은 주 기억장치 메모리를 공유하고, private virtual address space를 갖는다.

CPU와 OS는 이 virtual address를 physical address로 변환한다.
가상 메모리에서 블록은 page라 하고, miss는 page fault라고 표현한다.

이때, 가상 메모리 중 disk에 있는 데이터를 프로그램이 실제로 활용하고자 하면 DRAM으로 Fetch 해줘야 하는데, 이는 OS가 담당한다. 

한편 virtual address의 변환에는 Translation Look-aside Buffer(TLB)라는 CPU내부의 하드웨어가 이용된다. 이 캐시는 page table 만을 캐시하는 전용 버퍼이다. page table이 지역성이 아주 높기 때문에, 버퍼가 아주 유용하다.

Miss의 종류들

• Compulsory Miss (Cold Start): 컴퓨터 부팅 직후, 캐시가 모두 빈 상태에서의 필연적인 miss
• Capacity Miss: 캐시 용량이 모자라 발생하는 miss
• Conflict Miss: 충돌로 인해 발생하는 miss