IT 엘도라도 로고
IT 엘도라도
황금

[CSAPP] Memory Hierarchy

2020-03-17 21:59

[CSAPP] Memory Hierarchy

1. 메모리 계층 (Memory Hierarchy)

notion image
DRAM은 비트당 가격이 저렴하지만 접근 속도가 매우 느리고, SRAM은 비트당 가격이 비싸지만 접근 속도가 매우 빠르다. 이때 뒤에서 설명할 지역성(Locality)을 잘 활용하면, DRAM과 SRAM을 동시에 사용하여 비트당 가격은 DRAM만큼 저렴하고 접근 속도는 SRAM만큼 빠른 메모리 소자가 있는 듯한 효과를 만들어낼 수 있다. SRAM으로 만들어지는 캐시 메모리가 DRAM에서 자주 참조되는 부분들을 저장하고, CPU는 접근 속도가 더 빠른 SRAM에 먼저 접근함으로써 메모리 참조의 성능을 엄청나게 향상시킬 수 있다. 이와 같이 메모리는 DRAM 하나로만 되어 있지 않고 메모리 참조의 성능을 개선시키기 위한 여러 계층으로 구성되어 있는데, 이를 메모리 계층(Memory Hierarchy)이라고 한다. 메모리 계층의 구조는 위 그림과 같다. 접근 속도가 빠르지만 비싼 메모리 소자는 CPU와 가까운 계층에 위치시키고, 접근 속도는 느리지만 저렴하여 큰 용량으로 만들 수 있는 메모리 소자는 CPU와 먼 계층에 위치시킨다. 그리고 번째 계층의 메모리 소자는 번째 계층의 메모리 소자에서 자주 참조되는 부분들을 저장하도록 한다. 이렇게 하면, CPU는 메모리 참조가 필요할 때마다 자신과 가까운 계층에 존재하는 메모리 소자부터 접근함으로써 메모리 참조를 더욱 효율적으로 수행할 수 있게 된다.
실제로 현대 컴퓨터의 메모리 계층은 대략 다음과 같은 구조로 나타낼 수 있다. 위에서 설명한 것보다 훨씬 더 다양한 계층이 존재한다는 것을 볼 수 있다. 물론 당장 이 그림을 이해하는 것은 불가능에 가깝다. 그러니 그냥 이런 게 있구나 하고 간단히 보고만 넘어가자. 나중에 공부를 마친 뒤 돌아오면 안 보이던 게 보일 것이다.
notion image
 

2. RAM (Random Access Memory)

2-1. DRAM vs SRAM

RAM(Random Access Memory)은 컴퓨터에서 보조 기억 장치로 사용되는 메모리 소자를 의미한다. 기본적으로 각 셀(Cell)은 1비트를 저장하고, 여러 셀이 모여서 하나의 칩(Chip)을 이룬다. 그리고 이러한 칩을 여러 개 쌓아서 최종적으로 RAM을 만들게 된다. 자세한 구조는 아래에서 설명하는 내용을 참고하자.
DRAM(Dynamic RAM)의 경우, 각 셀은 하나의 축전기를 사용하여 1비트를 저장하며, 접근 시에는 하나의 트랜지스터가 사용된다. 따라서 SRAM에 비해서는 비트당 가격이 저렴하다. 그러나 SRAM보다 접근 속도가 느리고, 방사선 등의 외부 방해 요소에 취약하다. DRAM에 저장되는 값은 오래 두면 휘발될 수 있기 때문에 10-100ms 간격으로 계속 Refresh 작업을 수행해줘야 한다. 일반적으로 DRAM은 메인 메모리로서 사용된다.
SRAM(Static RAM)의 경우, 각 셀은 무려 4~6개의 트랜지스터로 이뤄진 회로를 사용하여 1비트를 저장한다. 따라서 DRAM에 비해서는 비트당 가격이 비싸다. 그러나 DRAM보다 접근 속도가 빠르고, 방사선 등의 외부 방해 요소에 크게 영향받지 않는다. SRAM에 저장되는 값은 전력이 계속 공급되는 한 휘발되지 않고 안전하게 유지된다. 일반적으로 SRAM은 캐시 메모리를 만드는 데 사용된다.

2-2. DRAM의 구조와 인터페이스

notion image
위 그림은 DRAM의 전반적인 구조를 나타낸다. 128바이트 크기의 DRAM을 가정하고 있다. 위 그림을 기준으로 DRAM의 데이터를 참조하는 과정을 이해해 보자. 먼저, CPU가 접근하고자 하는 메모리의 물리 주소를 메모리 컨트롤러에 입력하면, 메모리 컨트롤러는 하위 3비트를 제외한 나머지 비트를 (Row, Col)로 변환한다. 이는 각 DRAM 칩에서 어떤 행과 어떤 열에 위치한 슈퍼 셀을 고를 것인지를 나타내는 것이다. 그렇게 변환한 후에는 우선 Row 정보를 바탕으로 각 DRAM 칩에서 행을 하나씩 골라 해당 칩의 내부 행 버퍼로 가져온다. 그리고 Col 정보를 바탕으로 각 내부 행 버퍼에서 알맞은 슈퍼 셀을 고른 뒤, 그렇게 칩의 총개수만큼 선택된 슈퍼 셀들을 메모리 컨트롤러로 가져온다. 그러면 메모리 컨트롤러에는 8바이트 크기의 데이터가 들어오게 된다. 그러면 이제 마지막으로 CPU가 입력한 메모리 주소의 하위 3비트 정보를 바탕으로 몇 번째 바이트부터 읽을 것인지 결정하고, 그곳에서부터 몇 바이트를 읽어야 하는지를 나타내는 제어 신호의 정보를 바탕으로 몇 바이트만큼 읽을지 결정한다. 그렇게 결정된 범위의 데이터를 이제 CPU로 전달해주면 메모리 참조는 끝이 난다.
여기서 유추할 수 있는 사실이 하나 있다. 만약 모든 데이터가 메모리상에 정렬 원칙(Alignment Principle)에 따라 배치되어 있다면, 적은 횟수의 참조만으로도 메모리의 데이터를 효율적으로 가져올 수 있다는 것이다. 만약 정렬 원칙을 따르지 않고 데이터가 메모리상에 존재한다면 8바이트 데이터를 읽을 때에도 두 번의 참조가 필요할 수도 있다. (메모리 컨트롤러로 가져오는 데이터의 단위를 블록이라고 칭한다고 가정할 때) 한 데이터가 두 블록에 걸쳐 있을 수도 있기 때문이다. 이는 상당히 비효율적이다.

2-3. DRAM의 발전

위에서 설명한 기본적인 DRAM의 내부 구조와 참조 동작 방식은 초창기와도 크게 다르지 않을 만큼 유지되어 왔다. 그러나 인터페이스의 로직이나 입출력 작업의 속도는 날이 갈수록 발전되었다. 예를 들어 SDRAM(Synchronous DRAM)은 Row 주소를 재활용 가능하도록 개선하였고, 기존의 비동기적 제어 대신에 클락 신호를 사용한 동기적 입출력을 수행함으로써 클락의 Rising-edge 때 값을 읽거나 쓸 수 있도록 하였다. 또한 DDR SDRAM(Double Data Rate Synchronous DRAM)은 클락의 Rising-edge 때뿐만 아니라 Falling-edge 때도 값을 읽거나 쓸 수 있도록 하여 입출력 수행 속도를 배로 향상시켰다.

2-4. 비휘발성 메모리

앞서 설명한 DRAM은 휘발성 메모리에 속한다. 전력 공급이 중단되면 저장하고 있던 정보를 모두 잃기 때문이다. 반면 비휘발성 메모리도 존재한다. 이는 전력 공급이 중단되어도 저장하고 있는 정보를 그대로 유지한다. 비휘발성 메모리의 대표적인 사례를 몇 가지 알아보자.
첫째는 ROM(Read-only Memory)이다. 기본적으로 제조 단계에서 모든 정보를 저장하며, 이후 내용 수정이 불가능하다. 둘째는 PROM(Programmable ROM)으로, 사용자의 입맛대로 최초에 한 번은 프로그래밍(원하는 정보를 저장)할 수 있는 ROM을 의미한다. 셋째는 EPROM(Erasable PROM)으로, 자외선이나 X-Ray 등으로 정보를 지울 수 있는 PROM을 의미한다. 넷째는 EEPROM(Electrically Erasable PROM)으로, 전기적 특성을 이용하여 정보를 지울 수 있는 PROM을 의미한다. 마지막은 EEPROM과 유사한 특성을 가진 플래시 메모리(Flash Memory)이다.
비휘발성 메모리는 여러 분야에서 활용된다. 기본적인 펌웨어 프로그램들(EX. 바이오스)이 ROM에 주로 저장되며, 무엇보다 하드 디스크를 대신하는 주기억 장치로 떠오르고 있는 SSD가 플래시 메모리 기반의 저장 장치이다. 스마트폰, MP3 플레이어, 태블릿, 노트북 등의 단말기에서 사용되는 저장 장치를 만드는 데 핵심적인 역할을 수행하고 있다.

2-5. CPU와 메모리의 통신 구조 (인터페이스)

notion image
버스(Bus)란 간단히 말해서 주소, 데이터, 컨트롤 신호 등을 운반하는 도선을 의미한다. 버스를 통해서는 한 번에 해당 CPU의 워드 사이즈만큼의 데이터를 교환할 수 있다. 예를 들어 64비트 CPU의 버스는 64개의 도선이 하나의 버스를 이룬다. 물론 버스는 데이터의 교환을 위한 수단이기 때문에, 여러 장치가 공유하여 사용할 수 있다. 위 그림을 기준으로 메모리의 값을 읽을 때와 메모리에 값을 쓸 때의 동작 방식을 간단히 알아보자.
먼저 메모리의 값을 읽을 때이다. 예를 들어 movq A, %eax 명령어를 실행한다고 해보자. 먼저, CPU가 메모리 주소 A를 시스템 버스에 올려서 메모리 버스로 전달한다. 그러면 메인 메모리가 메모리 버스에서 A를 읽고 그 주소에 위치한 값 X를 로드하여 다시 메모리 버스에 올린다. 이제 CPU가 다시 버스에서 X를 읽어서 %eax에 복사하면 명령어 실행이 마무리된다.
다음으로 메모리에 값을 쓸 때이다. 예를 들어 movq %eax, A 명령어를 실행한다고 해보자. 먼저, CPU가 값을 쓸 메모리 주소 A를 시스템 버스에 올려서 메모리 버스로 전달한다. 그러면 메인 메모리는 메모리 버스에서 A를 읽고 CPU가 쓸 값을 줄 때까지 기다린다. 그러다가 CPU가 쓸 값 Y를 버스에 올리면, 메인 메모리는 버스에서 Y를 읽어서 A가 가리키는 공간에 저장함으로써 명령어 실행을 마무리한다.
 

3. 하드 디스크 (Hard Disk)

3-1. 하드 디스크 구조

notion image
notion image

3-2. 용량 계산

용량(Capacity)은 하드 디스크가 저장할 수 있는 최대 비트 수를 의미하며, 일반적으로 GB 혹은 GiB 단위로 표현한다. 1GB는 바이트를 의미하고, 1GiB는 바이트를 의미한다. 하드 디스크의 용량을 결정짓는 대표적인 요인으로는 대략 세 가지가 있다. 첫 번째는 Recording Density로, 한 트랙의 1인치 세그먼트에 들어가는 비트의 수를 의미한다. 두 번째는 Track Density로, 1인치 길이의 세그먼트에 들어가는 트랙의 수를 의미한다. 마지막은 Areal Density로, 1제곱인치 면적에 들어가는 비트의 수를 의미한다. 이는 Recording Density와 Track Density를 곱해서 얻을 수 있다.
참고로 하드 디스크는 몇 개의 Recording Zone으로 나눠져 있고, 각 Recording Zone에는 고정된 개수의 섹터들이 존재한다. 위 그림을 기준으로, 노란색 영역과 하늘색 영역이 각기 다른 Recording Zone을 의미한다. 동일한 Recording Zone에서는 트랙당 섹터의 개수도 동일한 반면, Recording Zone이 다르면 트랙당 섹터의 개수도 다르다는 것을 관찰할 수 있다. Recording Zone의 트랙당 섹터의 개수는 가장 안쪽에 위치한 트랙에 의해 결정지어진다. 이렇듯 Recording Zone에 따라 트랙당 섹터의 개수가 다르기 때문에, 하드 디스크의 용량을 계산할 때는 트랙당 평균 섹터의 개수를 먼저 계산하여 이를 사용하게 된다. 하드 디스크의 용량을 계산하는 방법은 다음과 같다.
⇒ Capacity = (# bytes/sector) x (평균 # sectors/track) x (# tracks/surface) x (# surfaces/platter) x (# platters/disk)

3-3. 접근

notion image
하드 디스크의 데이터에 접근하는 과정은 이러하다. 먼저, 해당 데이터를 포함하는 섹터가 위치한 트랙을 찾는다. 이를 위해 암(Arm)은 끝 부분에 붙어 있는 헤드(Head)가 해당 데이터를 포함하는 트랙의 위에 놓일 때까지 위 그림과 같이 회전한다. 이렇게 트랙을 찾는 데까지 걸리는 시간을 Seek Time이라고 한다. 트랙을 찾고 나면, 이제 해당 데이터를 포함하는 섹터를 찾아야 한다. 이를 위해 플래터는 고정된 속도로 위 그림과 같이 반시계 방향으로 회전한다. 이렇게 해당 데이터를 포함하는 섹터의 첫 번째 비트를 찾는 데까지 걸리는 시간을 Rotional Latency라고 한다. 이제 찾은 섹터 내에 존재하는 데이터를 읽기만 하면 된다. 이때 걸리는 시간을 Transfer Time이라고 한다. 하드 디스크 접근 과정을 그림으로 요약하면 다음과 같다.
notion image
위에서 설명한 내용을 바탕으로, 간단한 예시를 통해 하드 디스크 접근 시간을 계산해보도록 하자. 플래터의 회전 속도가 7,200 RPM이고, 평균 Seek Time은 9ms이며, 트랙당 평균 섹터의 개수는 400개인 하드 디스크를 가정해보자. 그러면 평균 Rotational Latency와 Transfer Time은 다음과 같이 계산할 수 있다. 그리고 그 둘과 Seek Time을 더하면 최종적인 접근 시간을 알아낼 수 있다.
⇒ 평균 Rotational Latency = (1/2) x (60 secs / 7200 RPM) x (1000 ms/sec) = 4ms
⇒ 평균 Transfer Time = (60 secs / 7200 RPM) x (1/400 secs/track) x (1000 ms/sec) = 0.02ms
⇒ 평균 Access Time = 9ms + 4ms + 0.02ms = 13.02ms
여기서 주목할 것은 두 가지이다. 첫 번째, 접근 시간은 Seek Time과 Rotational Latency의 영향력이 지배적이다. 따라서 이 둘을 줄일 수 있다면 접근 시간도 상당히 많이 감소할 것이다. 두 번째, 이미 알려진 사실과 같이 하드 디스크의 접근 속도는 SRAM이나 DRAM에 비해 눈에 띄게 느리다는 것이다. 하드 디스크는 SRAM보다 대략 40,000배 느리며, DRAM보다는 2,500배 느리다.

3-4. CPU와 하드 디스크의 통신 구조 (인터페이스)

지금까지 하드 디스크의 구조와 접근 원리를 살펴보았는데, 하드 디스크를 사용하는 입장에서 이런 것들까지 다 알고 있기란 쉽지 않다. 그래서 섹터 단위의 데이터들의 집합을 개의 논리적 블록들로 모델링하여 추상화하게 된다. 그리고 논리적 블록과 실제(물리적) 섹터들 사이의 맵핑은 디스크 컨트롤러라 불리는 하드웨어/펌웨어 장치에 의해서 유지된다. 즉, 외부에서 특정 데이터의 참조를 위한 논리적 블록을 요청하면 이를 (Surface, Track, Sector) 정보로 변환하여 하드 디스크에 전달함으로써 요청된 데이터를 포함하는 섹터를 반환하도록 하는 것이다. 이는 앞서 살펴보았던 메모리 컨트롤러의 역할과 유사하다. 메모리 컨트롤러도 메모리의 복잡한 내부 구조를 감추고 외부에서는 단순히 메모리 주소만을 가지고도 원하는 데이터를 참조할 수 있도록 추상화해주기 때문이다.
다음 그림은 앞에서 살펴본 메모리 인터페이스를 포함하여, 하드 디스크를 비롯한 외부 입출력 장치들과의 인터페이스를 보여주고 있다. 메모리와 외부 입출력 장치들은 I/O 브릿지를 경유지로 삼아서 CPU와 통신하며, I/O 버스에는 여러 개의 입출력 장치들을 장착할 수 있는 슬롯들이 마련되어 있다. 참고로 x86 CPU는 메모리와 통신하기 위한 명령어로서 mov, pop, push 등을 갖추고 있고, 외부 입출력 장치들과 통신하기 위한 명령어는 별도로 갖추고 있다. 즉, 외부 입출력 장치에 접근할 때는 아래 그림에서 볼 수 있듯이 메모리에 접근할 때와는 다른 버스를 사용하게 된다. 이는 메모리 주소 공간의 일부를 입출력 장치들에게 부여하는 방식과는 또 다른 방식에 해당한다.
notion image
위 그림을 기준으로 CPU가 하드 디스크의 데이터를 참조하는 과정을 살펴보자. 먼저, 외부 입출력 장치와의 통신을 위해 별도로 마련되어 있는 명령어를 CPU가 실행한다. 해당 명령어에는 접근하고자 하는 입출력 장치의 인터페이스 포트(주소), 참조하고자 하는 데이터의 논리적 블록 정보, 데이터를 로드하여 위치시킬 메모리 주소, 로드할 데이터의 크기 등의 정보들이 담겨 있다. 그러면 디스크 컨트롤러는 요청된 데이터를 포함하는 섹터를 읽은 후, DMA(Direct Memory Access) 컨트롤러를 통해서 메인 메모리에 그 데이터를 로드하게 된다. 이 과정에 CPU는 개입하지 않기 때문에 시스템 버스는 Free 한 상태가 된다. 이제 DMA가 데이터를 성공적으로 메모리에 로드하고 나면, CPU에게 인터럽트를 걸어서 해당 작업이 완료되었음을 알리게 된다.
notion image
notion image
notion image
 

4. SSD (Solid State Disks)

4-1. SSD 구조 및 특징

notion image
SSD(Solid State Disk)는 플래시 메모리 기반의 주기억 장치로, 하드 디스크와 마찬가지로 논리적 디스크 블록 단위에 기초한 인터페이스를 갖추고 있다. 바깥층에는 Flash Translation Layer가 위치하고, 안쪽에는 플래시 메모리가 위치한다. 플래시 메모리 내 데이터는 블록 단위로 나눠지며, 각 블록 내 데이터는 다시 페이지 단위로 나눠진다. 보통 블록은 32개~128개의 페이지를 가지고 있으며, 한 페이지는 대략 512B~4KB의 크기를 가진다. SSD를 대상으로 한 읽기/쓰기 작업은 페이지 단위로 이뤄지며, 특히 쓰기 작업의 경우 한 페이지를 수정하기 위해서는 해당 페이지가 속한 블록 내 모든 페이지를 지워야 한다. 또한 특정 횟수(EX. 10만 번) 이상의 쓰기 작업이 이뤄진 블록은 수명이 다하여 더 이상 사용할 수 없게 된다.

4-2. 성능 평가

notion image
위 그림에서 볼 수 있듯이, 일반적인 메모리 소자와 유사하게 읽기/쓰기 작업의 경우 Random Access보다는 Sequential Access가 좋은 성능을 보인다. 특히, 쓰기 작업의 경우 SSD의 특성상 Random Access는 성능이 많이 떨어진다. 한 블록을 지우는 작업이 적지 않은 시간을 필요로 하는데, 한 페이지를 수정하려면 그 페이지가 속한 블록의 다른 페이지들을 전부 삭제해야 하기 때문이다. 지금은 그래도 괜찮은 편이지만, 초창기 SSD는 이러한 이유 때문에 읽기 작업과 쓰기 작업의 성능 격차가 상당히 컸다.
하드 디스크와는 달리 물리적인 움직임을 필요로 하는 부분이 없기 때문에, 처리 속도가 더 빠르고 전력 소모가 적으며 무엇보다 외부의 충격에 대해 더욱 안전하다. 하지만 앞서 언급했듯, 유한한 횟수의 쓰기 작업을 하고 나면 해당 블록의 수명이 다 하는 문제가 있다. 이러한 문제는 Flash Translation Layer에 특별한 로직을 추가함으로써 어느 정도 완화가 가능하다. 실제 사례로, 인텔이 출시한 SSD 730은 그러한 로직을 추가함으로써 닳기 전까지 무려 128PB만큼의 데이터를 쓸 수 있도록 하였다. 최근 SSD는 MP3 플레이어, 스마트폰, 노트북 등에 주기억 장치로서 많이 사용되고 있으며, 데스크탑과 서버에도 사용되는 사례가 계속해서 증가하는 추세이다. 점점 더 많은 부분에서 하드 디스크를 대체하고 있다.
 

5. 지역성 (Locality)

5-1. CPU와 메모리 기술의 격차

notion image
위 그림에서 볼 수 있듯이, CPU와 DRAM의 속도 차이는 점점 벌어지고 있다. CPU의 속도는 눈에 띄게 빨라지고 있지만, DRAM의 속도는 상대적으로 천천히 빨라지고 있기 때문이다. 본 글의 서론에서 언급한 메모리 계층(Memory Hierarchy)은 이러한 문제를 해결하기 위해 등장했다. 속도가 빠른 CPU와 속도가 느린 DRAM 사이에 SRAM이라는 중간 계층을 두어서 CPU와 DRAM의 속도 격차를 줄여보자는 것이다. 그러나 단순히 중간 계층에 SRAM을 둔다고 해서 그 속도 격차가 줄어드는 건 아니다. 여기에는 특별한 아이디어가 하나 필요하다. 바로 지역성(Locality)이라는 것이다.

5-2. 지역성의 개념

지역성(Locality)이란, 프로그램이 시간적 혹은 공간적으로 가까운 데이터/명령어를 다시 참조할 가능성이 높은 현상을 가리키는 말이다. 지역성은 두 가지로 나뉜다. 첫 번째는 시간적 지역성(Temporal Locality)으로, 어떤 데이터를 참조하면 가까운 미래에 그 데이터를 다시 참조할 확률이 높다는 것을 가리킨다. 두 번째는 공간적 지역성(Spatial Locality)으로, 어떤 데이터를 참조하면 가까운 미래에 그 주변의 데이터를 참조할 확률이 높다는 것을 가리킨다.
다음과 같은 간단한 C 언어 코드를 예시로 시간적 지역성과 공간적 지역성을 살펴보도록 하자. 먼저, 변수 isum은 매 루프마다 계속해서 참조가 되고 있기 때문에 시간적 지역성을 만족한다. 다음으로, 배열 a의 각 요소는 루프에 따라 순서대로 참조가 이뤄지기 때문에 공간적 지역성을 만족한다. 실제로 이와 같이 지역성을 만족하는 코드는 상당히 많기 때문에, 이러한 지역성을 적절히 잘 활용하면 엄청난 성능의 향상을 기대할 수 있다.
notion image

5-3. 메모리 계층에서의 활용 (캐시 메모리)

지금까지 이야기한 내용을 종합해 보자. CPU와 DRAM의 속도 차이는 점점 더 증가하고 있기 때문에, 이에 대한 해결 방법이 필요하다. DRAM보다 훨씬 빠른 SRAM이 존재하긴 하지만, SRAM으로 DRAM을 완전히 대체하기에는 SRAM의 비트당 가격이 너무 비쌌다. 이때, 많은 프로그램들의 코드들을 살펴본 결과 지역성(Locality)이라는 패턴이 존재한다는 것을 알게 되었다. 이러한 아이디어를 바탕으로 새로 고안된 SRAM 기반의 메모리가 바로 캐시 메모리(Cache Memory)이다. 캐시 메모리는 CPU와 DRAM 사이에 위치하여 메모리 참조의 성능을 혁신적으로 향상시켰으며, CPU와 DRAM만 존재하는 단순한 메모리 구조를 혁파하고 오늘날과 같은 메모리 계층(Memory Hierarchy)을 확립하였다.
notion image
그렇다면 캐시 메모리는 지역성을 어떻게 활용하여 메모리 참조의 성능을 향상시켰을까? 크게 시간적 지역성과 공간적 지역성의 관점에서 분석하면 이렇다. 캐시 메모리는 DRAM에서 자주 참조되는 부분을 가져와서 저장하게 되는데, 이때 참조한 데이터만 캐시 메모리로 가져오는 것이 아니라 블록 단위로 그 주변의 데이터까지 한 번에 캐시 메모리로 가져옴으로써 공간적 지역성을 활용한다. 또한, 그렇게 가져온 블록들을 최근에 참조된 순서대로 저장하고 캐시 메모리가 꽉 차는 경우에는 가장 과거에 참조된 블록을 빼내는 방식을 취함으로써 시간적 지역성을 활용한다. 이어지는 설명에서 캐시 메모리의 동작 원리를 간단하게 살펴보도록 하고, 더 자세한 내용은 추후 포스팅을 참고하길 바란다.
 

6. 캐시 메모리 (Cache Memory)

6-1. 개념

넓은 의미에서의 캐시(Cache)란, 크고 느린 저장 장치가 가지고 있는 데이터들 중 접근 빈도가 높은 데이터들 일부를 저장하고 있는 작고 빠른 저장 장치를 의미한다. 가장 대표적인 게 DRAM의 캐시로 사용되는 캐시 메모리(Cache Memory)이다. 참고로, 캐시 메모리가 DRAM의 캐시에 해당한다면, DRAM은 하드 디스크의 캐시에 해당한다. 이는 뒤에서 가상 메모리(Virtual Memory)를 다룰 때 설명하도록 하겠다.
캐시 메모리는 DRAM과 SRAM으로 이뤄지는 메모리 기술에 두 종류의 지역성을 결합시킨 산물이라고 할 수 있다. 캐시 메모리의 핵심 아이디어는 메모리 기술에 대한 가상화(Virtualization)이다. 즉, 가격은 DRAM만큼 저렴하지만 접근 속도는 SRAM만큼 빠른 메모리 장치를 사용하는 듯한 착각을 만들어 내는 것이다. 그러면 캐시 메모리의 동작 원리에 대해 간단히 짚고 넘어가 보자.

6-2. 기본 동작 원리

notion image
위 그림은 캐시 메모리의 기본적인 동작 원리를 나타낸다. DRAM의 데이터들을 일정한 크기의 블록(Blcok)들로 구분하며, 캐시 메모리는 DRAM에서 자주 참조되는 블록들 일부를 저장한다. 그리고 CPU는 메모리 참조가 필요할 시 캐시 메모리를 먼저 확인한다. 이때, 찾으려는 데이터가 캐시 메모리에 존재하면 캐시 히트(Hit), 존재하지 않으면 캐시 미스(Miss)라고 한다. 다음 두 개의 그림은 각각 캐시 히트와 캐시 미스가 발생하는 경우를 나타낸다.
notion image
캐시 미스가 발생하는 경우에는 고려할 점이 두 가지 있다. 첫 번째는 Placement Policy로, DRAM에서 새로 가져온 블록을 어느 위치에 저장해야 하는지 결정하는 것을 말한다. 두 번째는 Replacement Policy로, 캐시 메모리가 이미 꽉 차있는 경우 어떤 블록을 내쫓아야 하는지 결정하는 것을 말한다. 둘은 다른 것이니 혼동하지 말자. 전자는 캐시 메모리가 꽉 차있지 않은 경우, 후자는 꽉 차있는 경우를 가정한다. 참고로 Replacement Policy의 대표적인 예시는 가장 과거에 참조되었던 블록을 내쫓는 것이다. 시간적 지역성을 활용하기 위함이다.

6-3. 캐시 미스의 종류

캐시 미스가 발생할 수 있는 경우는 다음과 같이 크게 세 경우이다.

6-3-1. Cold(Compulsory) Miss

이는 해당 블록에 처음 접근할 때 발생하는 캐시 미스이다. 처음 접근하는 경우라면 해당 블록이 캐시 메모리에 없을 수밖에 없기 때문에, 이는 불가피하게 최소 한 번은 발생할 수밖에 없다.

6-3-2. Conflict Miss

이를 이해하기 위해서는 먼저 충돌이라는 것이 무슨 현상인지 알아야 한다. 일반적으로  단계에 위치하는 각 블록들은  단계의 특정 자리에만 들어갈 수 있도록 되어 있다. 예를 들어, 위 예시에서는 DRAM의 번째 블록이 캐시 메모리의 번째 블록 자리에만 들어갈 수 있다. 이는 캐시 메모리가 꽉 차있지 않은 상황에도 똑같이 적용된다. 즉, 공간이 남아도 정해진 자신의 자리로 들어간다는 것이다. 참고로, 캐시 메모리에서는 각각의 자리를 Set이라고 한다. 따라서 위 예시는 4개의 Set으로 이루어진 캐시 메모리를 나타낸다. Set은 위 예시와 같이 한 블록만 들어갈 수 있는 크기일 수도 있고, 여러 개의 블록이 들어갈 수 있는 크기일 수도 있다. 중요한 것은 Set의 크기가 유한하다는 것이다. 따라서 동일한 Set에 맵핑되는 블록들이 반복적으로 참조되면 어느 순간 Set이 꽉 차서 해당 Set에 들어가 있는 특정 블록을 내쫓아야 하는 상황이 발생한다. 이 현상을 충돌(Conflict)이라고 한다. 그리고 충돌로 인해 발생하는 캐시 미스가 바로 Conflict Miss이다. 예를 들어, 위 예시에서 0번째 블록과 8번째 블록이 반복적으로 참조되면 계속해서 캐시 미스만 발생할 것이다.
💡
각 블록이 들어갈 수 있는 자리가 정해져 있는 이유
메모리 참조가 필요해지면 CPU는 캐시 메모리부터 확인한다. 이때 CPU는 찾고자 하는 데이터가 캐시 메모리에 있는지 어떻게 확인할까? 만약 DRAM의 각 블록이 캐시 메모리의 어디든 들어갈 수 있도록 되어 있다면, CPU는 캐시 메모리의 데이터 전부를 일일이 뒤지는 수밖에 없을 것이다. 그러나 DRAM의 각 블록은 자신이 캐시 될 수 있는 위치가 정해져 있기 때문에, CPU는 그 위치만 확인해서 해당 데이터의 캐시 유무를 판단할 수 있다. 조금 더 구체적으로 설명하자면, DRAM의 각 블록들은 자신의 메모리 주소를 기준으로 자신이 캐시 될 수 있는 Set이 정해진다. 따라서 CPU는 특정 데이터의 캐시 유무를 판단해야 할 때 메모리 주소를 기준으로 해당 데이터가 캐시 될 수 있는 Set을 찾아가서 탐색을 시도하면 된다. 이는 빠른 시간 내에 탐색할 수 있는 해싱(Hashing) 알고리즘을 적용한 것으로, 각 Set의 크기는 유한하기 때문에 탐색의 시간 복잡도는 이 된다.

6-3-3. Capacity Miss

단순히 캐시 메모리의 용량이 적기 때문에 발생하는 미스를 의미한다. 뒤에서 알아볼 용어를 사용한다면, Working Set(Set of active cache blocks)의 크기가 캐시 메모리의 용량보다 큰 경우에 발생하는 미스이다. 예를 들어, 순차적으로 접근하는 배열의 전체 크기가 캐시 메모리의 크기보다 크다면 필연적으로 캐시 미스가 발생할 것이다.
말풍선
댓글 0
좋아요 4
    아직 작성된 댓글이 없어요.
사용자