Post

Lecture 11: The Memory Hierarchy

Computer Systems: A Programmer's Perspective (CS:APP)

Posted Updated
By 송기종
views 19 min read

Random-Access Memory

RAM(Random-Access Memory)은 칩 형태로 패키징되어, 여러 개의 칩이 하나의 메모리를 구성한다.

  • RAM이 데이터를 저장하는 기본 단위는 셀(Cell)이며, 각 셀은 1비트를 저장한다.

  • RAM은 셀의 구조에 따라 SRAM(Static RAM)과 DRAM(Dynamic RAM)으로 구분된다.

     Trans. per cellAccess timeCostApplications
    SRAM4 또는 61x100x캐시 메모리
    DRAM110x1x프레임 버퍼, 메인 메모리
    • DRAM은 축전기를 이용하여 데이터를 저장하는데, 축전기는 전압을 가하지 않으면 전하가 누출된다. 이로 인한 데이터 손실을 방지하기 위해, 주기적으로 Memory refresh를 수행해야 한다.
    • SRAM은 오류가 발생할 가능성이 낮아 DRAM보다 훨씬 안정적이다.
    • SRAM과 DRAM은 전원이 차단되면 데이터를 잃어버리는 휘발성 메모리이다.

Nonvolatile Memories

비휘발성 메모리는 전원이 차단된 후에도 데이터를 유지한다.

  • ROM(Read-Only Memory): 칩을 생산할 때 한 번 데이터를 기록하면 수정이 불가능하여, 말 그대로 읽기 전용이다.
  • 플래시 메모리(Flash memory): 블록 단위로 데이터를 지우고 새로 쓸 수 있다. 다만 읽기/쓰기 작업을 수행할 때마다 블록이 열화되기에, 내구성에 한계가 있다.

비휘발성 메모리의 주된 용도는 다음과 같다.

  • 펌웨어(firmware)와 같은 소프트웨어 저장
  • SSD, USB 드라이브 등의 각종 저장 매체

Memory Read/Write Transaction

CPU와 메모리 간 데이터가 움직이는 통로를 버스(Bus)라 한다.

1
2
3
4
5
6
7
8
9

 CPU
+—————————————————+
|       ALU       |
|        ↕        |
|  Register file  |
|        ↕        |
|  Bus interface ←+—→ I/O bridge ←——→ Main memory
+—————————————————+ \               \
                     System bus      Memory bus

메모리에 존재하는 데이터를 CPU로 가져오는 Load 연산 movq A, %rax에 대해 살펴보자.

  1. CPU가 주소 A를 메모리 버스에 놓는다.
  2. 메인 메모리가 메모리 버스에서 A를 감지하고, 주소 A에서 8바이트 워드 x를 가져와 버스에 놓는다.
  3. x가 I/O bridge를 통해 버스 인터페이스로 이동하면, CPU가 x를 읽어 %rax에 복사한다.

CPU에 존재하는 데이터를 메모리에 저장하는 Store 연산 movq %rax, A도 비슷한 과정을 거친다.

  1. CPU가 주소 A를 메모리 버스에 놓는다.
  2. 메인 메모리가 메모리 버스에서 A를 감지하고, 해당하는 데이터가 버스에 도착하기를 기다린다.
  3. CPU가 %rax의 값 y를 버스에 놓는다.
  4. y가 I/O bridge를 통해 메모리 버스로 이동하면, 메인 메모리가 y를 읽어 주소 A에 저장한다.

보다시피 레지스터 파일은 ALU(Arithmetic Logic Unit)와 무척 가까운 반면에, 메모리는 상대적으로 멀리 떨어져 있어 읽기/쓰기 작업을 수행하려면 버스를 거쳐야 한다. 그래서 레지스터 간의 연산이 1 ns 미만 걸린다면, 메모리에 대한 연산은 50~100 ns 소요될 정도로 메모리 연산은 레지스터 연산에 비해 느리다.

Hard Disk Drive

Flat design hard drive illustration Components of a HDD1

  • 플래터(Platter): 자성 물질로 코팅된 원판이다. 자기장을 이용하여 비트를 저장한다.
  • 암(Arm): 플래터 위의 얇은 공기층에 떠 있다. 암의 끝에는 자기장의 변화를 감지하는 헤드(Head)가 있다.

플래터가 시계 반대 방향으로 회전하고, 암이 앞뒤로 움직이며 헤드가 데이터를 읽고 쓴다. 이렇듯 읽기/쓰기 작업이 물리적으로 이루어지다 보니 아무래도 느릴 수밖에 없다.

Cylinder Head Sector Disk geometry2

플래터는 위쪽과 아래쪽의 두 표면을 사용할 수 있다. 각 표면은 트랙(Track)이라고 불리는 동심원으로 구성되어 있고, 트랙은 데이터가 기록되는 단위인 섹터(Sector)로 구성되어 있다. 플래터들은 스핀들(Spindle)을 축으로 하여 겹쳐지며, 서로 다른 표면에 있는 동일 트랙들의 집합을 실린더(Cylinder)라 한다.

DiskStructure Recording zones3

처음엔 각 트랙에 동일한 수의 섹터가 있었기에, 플래터 바깥쪽으로 갈수록 섹터 간 간격이 넓어져 공간이 낭비되었다. 이러한 문제를 해결하기 위해, 플래터를 여러 개의 레코딩 존(Recording zone)으로 나누어 바깥쪽 존의 트랙에는 더 많은 섹터를 할당하였다.

Disk Capacity

디스크의 용량은 면밀도(Areal density)에 비례한다.

  • 기록 밀도(Recording density): 단위 면적당 저장할 수 있는 데이터의 양
  • 트랙 밀도(Track density): 반지름 방향의 단위 길이당 트랙의 수
\[\mathrm{\rho_{areal} = \rho_{recording} \times \rho_{track}}\]

구체적인 용량은 다음과 같이 구할 수 있다.

\[\mathrm{capacity = \frac{byte}{sector} \times \frac{sector}{track} \times \frac{track}{surface} \times \frac{surface}{platter} \times \frac{platter}{disk}}\]

Disk Access Time

디스크 접근 시간(Disk access time)은 3가지 요소에 의해 결정된다.

\[\begin{align*} \mathrm{T_{access} = T_{avg. \ seek} + T_{avg. \ rotation} + T_{avg. \ transfer}} \end{align*}\]
  • Seek time: 헤드가 목표 실린더로 이동하는 데 걸리는 시간
  • Rotational latency: 헤드가 목표 섹터에 도달할 때까지 디스크가 회전하는 데 걸리는 시간
  • Data transfer time: 헤드가 목표 섹터에서 데이터를 읽는 데 걸리는 시간
\[\begin{align*} \mathrm{T_{avg. \ rotation}} &= \mathrm{\frac{1}{2} \times \frac{1}{rpm} \times \frac{60 \ s}{1 \ min}} \\[6pt] \mathrm{T_{avg. \ transfer}} &= \mathrm{\frac{1}{rpm} \times \frac{track}{sector} \times \frac{60 \ s}{1 \ min}} \end{align*}\]

$\mathrm{T_{avg. \ transfer}}$는 상대적으로 매우 짧기 때문에, $\mathrm{T_{access}}$는 사실상 $\mathrm{T_{avg. \ seek}}$와 $\mathrm{T_{avg. \ rotation}}$에 좌우된다.

TypeAccess time (512-byte block)
SRAM약 250 ns
DRAM약 4,000 ns
HDD약 10 ms

디스크 접근 시간은 SRAM보다 40,000배, DRAM보다 2,500배 정도 느리다.

Logical Blocks

현대의 디스크 컨트롤러는 디스크를 논리 블록(Logical block)의 시퀀스로 나타내어, CPU는 트랙 및 섹터와 같은 물리적 구조에 대해 신경 쓰지 않고 논리 블록 단위로 데이터에 액세스한다. 각 논리 블록의 크기는 섹터의 배수이며, 0부터 시작하여 순차적으로 번호가 할당된다. 디스크 컨트롤러는 논리 블록과 실제 섹터 간의 매핑 정보를 내부적으로 관리한다.

디스크의 일부는 예비 실린더로 미리 할당되어 있어, 어떤 실린더의 섹터에 문제가 발생하면 디스크 컨트롤러는 해당 섹터의 데이터를 예비 실린더로 복사한 뒤 작업을 진행한다. 이로 인해, 실제로 사용 가능한 디스크 용량은 물리적인 실린더 수를 기준으로 계산한 최대 용량보다 작다.

Reading a Disk Sector

1
2
3
4
5
6
7
8
9
10
11
12
13
14

 CPU
+—————————————————+
|       ALU       |
|        ↕        |
|  Register file  |  System bus      Memory bus
|        ↕        | /               /
|  Bus interface ←+—→ I/O bridge ←——→ Main memory
+—————————————————+        ↑
←—————+—————————————+——————+———————+————————————→
      ↓             ↓              ↓       ㄴ I/O bus
     USB         Graphics         Disk
  controller      adapter      controller
  ↑       ↑         ↓              ↕
Mouse  Keyboard   Monitor         Disk

디스크 읽기 작업의 수행 과정을 살펴보자.

  1. CPU가 디스크 컨트롤러에게 읽기 명령을 전달한다. 이 명령에는 읽어 올 데이터의 논리 블록 번호와 해당 데이터를 저장할 메모리 주소가 포함된다. CPU는 이 정보를 디스크 컨트롤러와 연결된 포트에 쓴다.
  2. 디스크 컨트롤러는 CPU가 요청한 논리 블록에 해당하는 섹터를 읽는다. 그런 다음, 버스의 제어권을 가져와서 CPU의 개입 없이 직접 데이터를 I/O bus와 I/O bridge를 통해 메인 메모리로 복사한다. 이를 직접 메모리 접근(Direct Memory Access, DMA)이라 한다.
  3. 데이터 전송이 완료되면, 디스크 컨트롤러는 CPU 칩의 특정 핀 값을 0에서 1로 변경(assert)하여 CPU에게 데이터 전송이 완료되었음을 알린다. 이를 인터럽트(Interrupt)라 한다.
  4. CPU는 인터럽트를 받으면 현재 수행 중인 작업을 중단하고, 대기 중이던 프로그램을 실행하여 전송된 데이터를 처리한다.

이러한 인터럽트 메커니즘이 CPU와 디스크 컨트롤러 간의 비동기 통신을 가능하게 하여, CPU는 데이터 전송이 완료되기를 기다리지 않고 다른 작업을 수행할 수 있다.

Solid-State Drive

SSD(Solid-State Drive)는 플래시 메모리와 펌웨어로 구성된다. HDD와 같은 인터페이스를 사용하므로, CPU는 두 저장 장치를 동일한 방식으로 제어할 수 있다.

  • FTL(Flash Translation Layer)은 SSD 내부의 펌웨어로, HDD의 디스크 컨트롤러와 유사한 역할을 수행한다.
  • 플래시 메모리는 페이지(Page) 단위로 데이터를 읽고 쓴다. 페이지의 크기는 일반적으로 0.5~4 KB이다.
  • 여러 개의 페이지가 모여 블록(Block)을 형성한다. 페이지에 새로운 데이터를 쓰기 위해서는, 먼저 해당 페이지가 속한 블록 전체를 삭제해야 한다.

플래시 메모리의 블록은 CPU가 다루는 논리 블록과 별개이다.

 ReadWrite
Sequential550 MB/s470 MB/s
Random365 MB/s303 MB/s
  • HDD의 읽기 속도가 보통 40~50 MB/s임을 감안하면, SSD가 10배 정도 빠른 셈이다.
  • 물리적으로 움직이는 부품이 없기 때문에 HDD보다 빠르고, 전력 소모가 적으며, 충격과 진동에 강하다.
  • 데이터를 기록하거나 삭제할 때 플래시 메모리가 마모된다는 단점이 있지만, 수명 연장을 위해 다양한 기술을 사용하기 때문에 일반적인 환경에서는 거의 문제가 되지 않는다.
  • HDD에 비해 성능이 좋은 만큼, 가격이 비싸다.


Locality of Reference

Locality

  • 시간 지역성(Temporal locality): 최근에 참조된 메모리 위치는 가까운 미래에 다시 참조될 가능성이 높다.
  • 공간 지역성(Spatial locality): 최근에 참조된 메모리 위치 부근은 가까운 미래에 참조될 가능성이 높다.

Locality Example

1
2
3

int sum = 0;
for (int i = 0; i < a_len; i++)
    sum += a[i];
  • 일정한 간격(n)으로 인덱스를 증가시키면서 배열의 요소를 참조하는 방식을 stride-n 참조 패턴이라 한다. 이는 공간 지역성에 해당한다.
  • 루프 안에서 sum을 참조하는 것은 시간 지역성에 해당한다.

좋은 지역성은 곧 좋은 성능으로 이어진다.4 따라서 코드를 보고 지역성을 파악하는 능력을 기르고, 지역성에 대한 이해를 바탕으로 메모리 참조 패턴을 최적화해야 한다.


Caching in the Memory Hierarchy

Memory Hierarchy

메모리 계층 구조(Memory hierarchy)는 컴퓨터 시스템의 성능과 비용 간의 균형을 맞추기 위해 사용되는 개념이다.

Cache Hierarchy Updated Simple diagram of the memory hierarchy5

  • 각 계층의 메모리는 하위 계층을 위한 캐시(Cache) 역할을 한다.
  • 지역성의 원리로 인해 상위 계층의 데이터가 더 자주 사용된다.

따라서 속도가 빠르지만 비싸서 용량이 작은 메모리를 위쪽에, 느리지만 저렴하여 용량이 큰 메모리를 아래쪽에 둠으로써 전체적으로 빠르면서 용량도 큰 저장소처럼 사용할 수 있다.

General Cache Concepts

상위 계층에서는 메모리와 캐시 간 블록 단위로 데이터를 주고받는다. 이때 원하는 블록이 캐시에 존재하는 경우를 캐시 적중(Cache hit), 하위 계층에서 블록을 가져와야 하는 경우를 캐시 미스(Cache miss)라 한다.

캐시 미스가 발생하는 경우를 3가지로 나눌 수 있다.

  • Cold(Compulsory) miss: 요청한 블록에 처음 접근할 때 발생하는 미스이다. 해당 블록이 캐시에 없으므로 메인 메모리에서 가져와야 한다. 프로그램 시작 시 모든 데이터가 메인 메모리에만 존재하기 때문에, 이러한 미스가 발생한다.

  • Capacity miss: 프로그램 실행 중 반복적으로 접근하는 블록들의 집합을 작업 집합(Working set)이라 하는데, 작업 집합의 크기가 캐시의 용량을 초과할 때 발생하는 미스이다.

  • Conflict miss: 서로 다른 블록이 캐시의 동일한 위치에 매핑되어 충돌할 때 발생하는 미스이다.

Examples of Caching in the Memory Hierarchy

TypeWhatWhereLatency (cycles)Manager
Registers4/8 byte wordsCPU core0Compiler
TLBAddress translationsOn-Chip TLB0Hardware MMU
L1 cache64 byte blocksOn-Chip L14Hardware
L2 cache64 byte blocksOn-Chip L210Hardware
Virtual memory4 KB pagesMain memory100Hardware + OS
Buffer cacheParts of filesMain memory100OS
Disk cacheDisk sectorsDisk controller100,000Disk firmware
Network buffer cacheParts of filesLocal disk10,000,000NFS client
Browser cacheWeb pagesLocal disk10,000,000Web browser
Web cacheWeb pagesRemote server disks1,000,000,000Web proxy server


References

Footnote

  1. “Flat design hard drive illustration.” Freepik. [Online]. ↩︎

  2. “Cylinder Head Sector.” Wikimedia Commons. [Online]. ↩︎

  3. “DiskStructure.” Wikimedia Commons. [Online]. ↩︎

  4. “Lecture 01: Course Overview.” 고볼. [Online]. ↩︎

  5. Kbbuch. “Cache Hierarchy Updated.” Wikimedia Commons. [Online]. ↩︎

Computer Science, Computer Systems
csapp
이 글은 저작자의 CC BY-SA 4.0 라이선스를 따릅니다.