컴퓨터 시스템 정리 (CSAPP) Chapter 6

Chapter 6 메모리 계층구조 The Memory Hierarchy

메모리 시스템이란?

• 여러가지 용량, 비용, 접근시간을 갖는 저장장치들의 계층구조
• 메모리 시스템의 저장장치들
  • CPU 레지스터: 가장 자주 이용하는 데이터를 보관하는 장소
  • 캐시 메모리: 작고 빠름. CPU 부근에서 비교적 느린 메인메모리에 저장된 데이터, 인스트럭션들에 대한 준비 장소
  • 메인메모리: 크고 느린 디스크들에 저장된 데이터를 위한 준비 장소
  • 디스크: 네트워크로 연결된 다른 컴퓨터들의 디스크에 저장된 데이터를 위한 준비 장소
• 하드웨어 & 소프트웨어의 중요한 근본적인 특성 3가지
  1. 다양한 저장장치 기술들은 각기 다른 접근시간을 가지며, 더 빠른 기술들은 느린 것보다 바이트당 더 많은 비용 + 더 적은 용량에 + 더 많은 파워(heat)를 필요로 함
  2. CPU와 메인메모리 사이의 속도 격차는 더욱 커지고 있음
  3. 잘 작성된 프로그램은 좋은 지역성을 보임
• 메모리 시스템을 이해하면 좋은 지역성을 갖는 프로그램을 만들 수 있다
  • 좋은 지역성을 갖는 프로그램이란, 좀 더 상위 메모리 계층에서 더 많은 데이터에 접근하려고 하는 프로그램
  • 시스템이 어떻게 데이터를 메모리 계층구조에서 위아래로 이동시키는지 안다면? -> 데이터를 계층의 상부에 저장시켜 CPU가 보다 빨리 접근할 수 있도록 프로그램을 작성할 수 있다!

6.1 저장장치 기술

6.1.1 랜덤-접근 메모리 (RAM, Random-Access Memory)

1. RAM의 종류

^[1]

1. 정적 램(SRAM): 동적 램보다 더 빠르고 훨씬 더 비쌈. 캐시 메모리로 사용됨. CPU칩 내부나 외부에 장착(즉 CPU 근처). 수십 메가바이트.
2. 동적 램 (DRAM): 메인메모리와 그래픽 시스템의 프레임 버퍼로도 사용. 수백~수천 메가바이트.

2. 정적 RAM(SRAM)

• 각 비트를 이중안정 메모리 셀(bistable cell)에 저장 + 각 셀은 여섯개의 트랜지스터 회로로 구성
• 이 회로는 두 가지 상태외의 다른 상태는 모두 “불안정” 상태
• 이 “불안정” 상태에서 시작해 다른 안정한 상태로 빠르게 이동
• 이러한 특징으로 SRAM은 자신의 값을 전원이 공급되는 한 무한히 유지함

3. 동적 RAM(DRAM)

• 각 비트를 전하로 capacitor에 저장
• 매우 dense하게 만들 수 있다
• SRAM과 달리 외부 자극에 매우 민감하며, capacitor가 달라지면 다시 회복 X (햇빛에 노출되면 capacitor 전압이 변함)
• 따라서 메모리 시스템은 주기적으로 메모리의 모든 비트를 읽고 다시 쓰는 refresh가 필요하게 됨

추가) DRAM과 SRAM의 특징 요약

1. SRAM은 전원이 공급되는 한 지속적이다. DRAM과 달리 리프레시 필요 X
2. SRAM은 DRAM보다 빨리 접근 가능
3. SRAM은 빛, 전기적 잡음 등에 민감하지 않음
4. SRAM 셀들이 DRAM보다 트랜지스터를 더 많이 사용 -> 더 낮은 밀도, 더 비싸고, 더 전력 소모 큼

4. 일반 DRAM

▲ 16개의 슈퍼셀과 슈퍼셀당 8비트를 갖는 DRAM 칩

• DRAM은 그림처럼 이차원 배열로 구성됨 (칩의 주소핀 수를 줄이기 위해 그렇게 디자인했다고 함, 하지만 주소를 두 단계 보내줘야 해서 접근 시간은 증가한다고…)
• 각각의 DRAM 칩은 메모리 컨트롤러에 연결되며, 슈퍼셀이 전송할 수 있는 비트(여기서는 8비트)가 두 사이를 왔다갔다 할 수 있음
  • RAS(row access strobe) 요청: 슈퍼셀의 행 주소 요청
  • CAS(column access strobe) 요청: 슈퍼셀의 열 주소 요청
  • 메모리 컨트톨러가 DRAM의 슈퍼셀 행 주소 i, 열 주소 j를 보내면 DRAM이 슈퍼셀 (i, j)의 값을 보내주는 방식

5. 메모리 모듈

• 각 슈퍼셀들은 1바이트의 메인 메모리를 저장
• 메인 메모리 바이트 주소 A에 있는 각 64비트 워드는 해당 슈퍼셀 주소로 (i, j)를 갖는 8개의 슈퍼셀로 나타냄
• 메모리 주소 A에서 64비트 워드를 가져오려면?
  1. 메모리 컨트롤러가 A를 슈퍼셀 주소 (i, j)로 변환
  2. 이걸 메모리 모듈로 보냄
  3. 메모리 모듈이 i, j를 각 DRAM에 보냄
  4. 각 DRAM이 자신의 (i, j) 슈퍼셀의 8비트 내용을 출력
  5. 메모리 모듈이 이 출력을 모아서 64비트 워드로 구성 -> 메모리 컨트롤러로 전송

6. Enhanced DRAM

1. fast page mode DRAM (FPM DRAM)
2. extended data out DRAM (EDO DRAM)
3. synchronous DRAM (SDRAM)
4. Double Data-Rate Synchronous DRAM (DDR SDRAM)
5. Video RAM (VRAM)

7. 비휘발성 메모리

• 휘발성과 비휘발성 메모리?: 전원이 꺼져도 정보를 유지하는가 그렇지 못한가에 따라 구분
• 비휘발성 메모리는 Read-only memory (ROM)\이라고도 함
• 비휘발성 메모리의 종류
  1. Programmable ROM (PROM): 단 한번 프로그램 될 수 있음
  2. Erasable programmable ROM (EPROM): 빛을 쬐면 EPROM 셀이 0으로 초기화됨
     1. Electrically erasable PROM (EEPROM): PCB에서 직접 재프로그램 될 수 있음
     2. 플래시 메모리: EEPROM에 기반을 둔 비휘발성 메모리의 일종. 다양한 전자기기에서 빠르고 안정적임.
• 펌웨어: ROM 디바이스에 저장된 프로그램들

8. 메인메모리 접근하기

• 버스 트랜잭션: CPU와 메모리 간의 전송이 일어나는 일련의 단계들.
  • 읽기 트랜잭션: 데이터를 메인메모리에서 CPU로 이동 (e.g. movq A,%rax)
    1. CPU는 주소 A를 시스템 버스에 보낸다
    2. I/O 브릿지가 신호를 메모리 버스를 따라 보낸다
    3. 메인메모리는 메모리 버스에서 주소 신호를 감지하고, 메모리 버스로부터 주소를 읽는다
    4. DRAM에서 데이터 워드를 선입한다
    5. 데이터를 메모리 버스에 쓴다
    6. I/O 브릿지는 메모리 버스 신호를 시스템 버스 신호로 변환하여 시스템 버스로 넘겨준다
    7. CPU는 시스템 버스에서 데이터를 감지 + 버스에서 데이터를 읽고 %rax에 복사
  • 쓰기 트랜잭션: 데이터를 CPU에서 메인메모리로 이동 (e.g. movq %rax,A)
    1. CPU는 주소를 시스템 버스에 보낸다
    2. 메모리는 메모리 버스에서 주소를 읽고 데이터 도착하기를 기다린다
    3. CPU가 %rax에 있는 데이터를 시스템 버스에 복사한다
    4. 메인메모리는 데이터를 메모리 버스에서 읽고 비트들을 DRAM에 저장

6.1.2 디스크 저장장치

1. 디스크의 구조

• 한 개 이상의 원판(platter)\ 들로 구성
• 각 원판은 양면의 표면(surface)\로 이루어지며, 이 surface는 자성을 띠는 기억 물질로 코팅 됨
• 원판의 중심부에는 회전하는 축(spindle)\이 있으며, 원판을 일정한 회전율로 돌려줌 (대략 분당 5400~15000번)
• 각 surface는 트랙(track)\이라고 하는 여러개의 동심원으로 이뤄짐
• 각 track은 섹터들의 집합으로 구성되며, 각 섹터는 섹터 위에 자성 물질로 인코딩된 동일한 수의 데이터 비트(일반적으로 512바이트)를 가짐
• 섹터들은 아무 데이터도 기록되지 않은 갭(gap)\으로 분리되어 있음
• 실린더 k: 트랙 k들을 합친 것

2. 디스크 용량

• 디스크의 최대 용량: 하나의 디스크에 기록될 수 있는 최대 비트수
• 다음과 같은 기술 요소들에 의해 결정
  1. 기록밀도(bits/in): 트랙 1인치당 집어넣을 수 있는 비트 수
  2. 트랙밀도(tracks/in): 원판 중심에서 반지름 1인치 길이에 넣을 수 있는 트랙의 수
  3. 면적밀도(bits/in²): 기록밀도 * 트랙밀도

3. 디스크의 동작

• 구동 팔의 끝에 연결된 읽기/쓰기 헤드를 이용해 자성 표면에 저장된 비트를 읽거나 씀
• 구동 팔의 동작
  • 마치 지구 주위를 지상 2.5cm 높이로 날아가는 것과 같다 -> 매우 작은 먼지가 있어도 헤드는 충돌함 -> 디스크를 밀폐 용기에 넣어서 밀봉하는 이유
• 섹터 읽기
  • 디스크는 데이터를 섹터 크기의 블록으로 읽고 기록
  • 섹터 접근 시간(탐색시간과 회전지연시간이 큰 영향)
    1. 탐색시간: 팔을 이동하기 위해 소요되는 시간
    2. 회전지연시간: 헤드가 타깃 섹터의 첫번째 비트에 도달할 때까지의 시간
    3. 전송시간: 타깃 섹터의 첫번째 비트에 도달했을 때, 섹터의 내용을 전송하는 시간

4. 논리적 디스크 블록

• 디스크의 이러한 복잡한 구조를 추상화한 것==(메인 메모리 - 가상 메모리 관계와 유사)==
• 디스크 패키지 안의 디스크 컨트롤러라는 장치가 실제 "물리적 디스크 섹터"와, 섹터 크기의 "논리블록의 배열"간의 매핑을 갖고 있음
• (surface, track, sector) 쌍으로 테이블을 참조하여 실제 섹터로 이동할 수 있게끔 함

5. 입출력장치 연결하기

• 다양한 입출력장치들(그래픽 카드, 모니터, 마우스, 키보드, 디스크 등)은 입출력 버스로 CPU와 메인 메모리에 연결
• CPU 특화된 메모리 버스, 시스템 버스와 달리, I/O 버스는 이들보다 조금 느리지만 여러 회사들의 광범위한 I/O 디바이스를 연결함

6. 디스크 접근하기

1. CPU는 명령어(“디스크 읽기를 해라”), 읽어야 할 논리블록 번호, 디스크 섹터의 내용이 저장 될 목적지 메인메모리 주소를 디스크와 관련된 메모리 매핑된 주소에 써줌으로써, 디스크 읽기를 시작
   • 메모리 매핑 I/O: 주소 공간에 있는 한 개의 주소 블록이 각각의 I/O 디바이스들과 통신하기 위해 예약되어 있는 것. 이 각각의 주소는 I/O 포트라고 함. 각각의 I/O 디바이스는 버스에 연결될 때, 한 개 이상의 포트와 매핑됨
     
2. 디스크 컨트롤러는 논리블록 번호를 섹터 주소로 번역하여, 해당 디스크 섹터를 읽어내고, 메인메모리로 DMA 전송을 수행함 (※ DMA 전송: CPU를 거치지 않고 메인메모리로 바로 읽기/복사하는 것)
   • 이때 CPU가 개입하지 않는 DMA 전송을 함으로써, CPU는 그동안 다른 작업을 수행할 수 있음 (디스크 읽기는 시간이 많이 걸리므로 이걸 CPU가 기다리고 있으면 엄청난 낭비임!)
     
3. DMA 전송이 완료되고, 디스크 섹터의 내용이 메인메모리에 잘 저장되면, 디스크 컨트롤러는 CPU에게 I/O 작업이 끝났다고 인터럽트로 알려줌
   • CPU는 하던 일을 멈추고 OS 모드로 돌아옴 → I/O 작업이 끝났다고 기록 → CPU가 하던 일로 다시 컨트롤 전환

6.1.3 Solid State Disks (SSD)

• 플래시 메모리를 사용하는 저장장치 기술로, 기존의 회전하는 디스크(= HDD)의 대체품으로 많이 쓰임
• SSD의 구성
  1. 플래시 메모리 칩: HDD의 드라이브같은 역할
  2. 플래시 번역 계층: HDD의 디스크 컨트롤러 같은 역할. 하드웨어/펌웨어 기기. 논리블록 접근을 메모리 칩 접근으로 번역해줌
• SSD의 특성
  1. 읽어오기 작업이 쓰기 작업보다 빠르다 (아래 서술할 특징들 때문)
  2. 플래시 메모리는 일련의 B 블록으로 구성, 각각의 블록은 p개의 페이지로 구성됨
     • 페이지 크기: 512바이트 ~ 4KB
     • 블록 구성: 32~128페이지
     • 총 블록 크기: 16KB ~ 512KB
  3. 데이터는 페이지 단위로 읽고 쓰게 됨
  4. 한 개의 페이지는 자신이 속한 블록이 지워져야(블록의 모든 비트가 1로 세팅되는 것), 쓰기 작업이 가능해짐 → 쓰기 작업을 하기 위해 블록을 지우는 시간이 소요될 수 있음
  5. 한 개의 블록은 대략 10만번의 반복적인 쓰기 작업 후 낡아짐 → 더 이상 그 블록을 사용할 수 없게 됨
  6. 만약 지워지지 않은(즉, 모두 1이 아닌) 페이지를 수정해야 한다면, 같은 블록 내의 모든 페이지의 내용을 다른 새로운 블록(1로 세팅되어 있는)으로 먼저 복사해야 함 → 역시 읽기 작업보다 시간이 더 걸림
• SSD의 장점 및 단점
  • 장점: 반도체 메모리로 만들어졌으므로 움직이는 부품이 없음 → HDD보다 접근 시간이 빠르고, 더 적은 전력을 소모하고, 더 견고함
  • 단점:
    1. 반복적인 쓰기 작업으로 인한 플래시 블록 노후화 but 플래시 번역 계층이 이를 막기 위한 노화 평준화 로직을 사용하며, 실제로 노화로 SSD가 죽을 때까지 수년이 소요된다고 함
    2. HDD보다 약 30배 더 비싸면서, 저장 용량은 더 적음 → 최근에는 간격이 많이 줄어들고 있음

6.1.4 저장장치 기술 동향

1. 여러 가지 저장장치 기술은 가격, 성능간의 trade-off를 갖게 됨; 빠른 장치는 느린 장치보다 항상 더 비싸다!
2. 여러 가지 저장장치 기술의 가격과 성능 특성은 매우 빠르고 다양하게 바뀌고 있다(하지만 접근 시간을 줄이는 것보다 집적도를 올리는(= 비용을 줄이는) 것이 훨씬 쉽다)
3. DRAM과 디스크 성능은 CPU 성능에 뒤처져서 쫓아가고 있다 → 이런 프로세서-메모리 차이를 극복하기 위해 SRAM 기반 캐시를 많이 사용함 ☞ 지역성의 원리 활용

6.2 지역성

• 지역성의 원리
  • 잘 작성한 컴퓨터 프로그램은 좋은 지역성을 보임
  • 즉, 최근에 참조했던 데이터의 "근처에 있는 데이터"를 참조하거나(= 공간 지역성), "최근에 자신을 참조했던 데이터"를 참조(= 시간 지역성)하려는 경향을 가짐
  • 하드웨어와 소프트웨어 시스템의 성능과 설계에 엄청난 영향을 주는 지속적인 개념
• 지역성의 형태
  1. 시간 지역성: 한번 참조된 메모리 위치는 가까운 미래에 다시 여러번 참조될 가능성이 높음
  2. 공간 지역성: 만일 어떤 메모리 위치가 일단 참조되면, 이 프로그램은 가까운 미래에 근처의 메모리 위치를 참조할 가능성이 높음
• 왜 프로그래머가 지역성을 알아야 하는가?
  • 일반적으로 좋은 지역성을 갖는 프로그램이 나쁜 지역성을 갖는 프로그램보다 더 빨리 돌아감
  • 따라서, 하드웨어, 운영체제, 응용프로그램까지 모든 단계에서 지역성을 활용하도록 설계 됨
• 캐시 메모리
  • 가장 최근에 참조한 인스트럭션과 데이터 아이템의 블록을 저장하는 작고 빠른 메모리
  • 캐시 메모리의 사용
    • 하드웨어 수준: 메인메모리를 빠르게 돌릴 수 있게 함
    • 운영체제 수준: 시스템이 메인메모리를 가장 최근에 참조한 가상주소공간 블록에 대한 캐시로 사용함. 메인메모리를 가장 최근에 사용한 디스크 파일 시스템 상의 디스크 블록을 캐시하기 위해 사용.
    • 응용프로그램 수준: 웹 브라우저는 디스크 상의 가장 최근 참조한 문서를 캐싱하여 시간 지역성을 활용. 웹 서버는 최근에 요청한 문서를 최전방 캐시에 저장함으로써, 서버가 신경쓰지 않아도 이러한 문서에 대한 요청을 만족시킬 수 있음

6.2.1 프로그램 데이터 참조의 지역성

• stride-k 참조 패턴
  • 연속적인 매 k번째 원소를 방문하는 것을 말함
  • 중요한 공간 지역성의 원인
  • 일반적으로 stride(보폭)이 증가하면(즉 k가 커질수록) 공간 지역성이 떨어짐
    
• 위 코드는 좋은 지역성을 가진다:
  1. 데이터 참조 측면에서
     1. 공간 지역성: 연속적으로 위치한 배열 원소를 순차적으로 참조함 → stride-1 참조 패턴(순차 참조 패턴)
     2. 시간 지역성: 똑같은 sum 변수를 순회마다 매번 참조함
  2. 명령 참조 측면에서
     1. 공간 지역성: 시퀀스로 이루어진 명령을 참조함
     2. 시간 지역성: 루프를 통해 반복적으로 같은 명령을 참조함
        
• 위 코드는 나쁜 공간 지역성을 가진다:
  • 이차원 배열이 행 방향으로 순차적으로 저장되어 있는 것을 참조하지 않고, 열 방향으로 매 N번째 원소를 방문함 → stride-N 참조 패턴

6.2.2 인스트럭션 선입(fetch)의 지역성

• 프로그램 인스트럭션은 메모리에 저장되며, CPU가 그것을 읽어야한다!
• 인스트럭션이 순차적인 메모리 순서로 실행되면, 좋은 공간 지역성을 가짐
• 루프 본체가 여러번 실행되면 좋은 시간 지역성도 갖게 됨

6.2.3 지역성 요약

• 동일한 변수들을 반복적으로 참조하는 프로그램은 좋은 시간 지역성을 가짐
• Stride-k 참조 패턴을 갖는 프로그램에 대해서 stride가 적으면 적을수록 공간 지역성도 좋아짐. Stride-1 참조 패턴을 갖는 프로그램들은 좋은 공간 지역성을 가짐. 메모리를 큰 stride로 뛰어다니는 프로그램들은 나쁜 공간 지역성을 가짐.
• 루프는 인스트럭션 선입 대해 좋은 시간 및 공간 지역성을 가짐. 루프 본체가 작을수록 루프 반복실행의 수는 더 커지고 지역성도 더 좋음

6.3 메모리 계층구조

6.3.1 메모리 계층구조에서의 캐시

• 캐시란?
  • 보다 크고 느린 디바이스에 저장된 데이터 객체를 위한 준비영역으로 사용하는 작고 빠른 저장장치
  • 캐시를 사용하는 과정을 캐싱이라고 부름
• 각 메모리 계층의 저장장치는 아래 레벨에 있는 저장장치에 대한 캐시 공간이다
  • e.g. 로컬 디스크는 네트워크를 통해 원격 디스크로부터 가져온 파일들(e.g. 웹 페이지)에 대한 캐시
    
• ▲ Memory와 Cache의 블록
  • Memory는 여러 개의 블록으로 나뉘어져 있음
  • 각 블록은 고유한 주소나 이름을 가짐
  • 대부분 고정크기이지만, 가변크기(e.g. 웹 서버에 저장된 원격 HTML 파일들)일 수도 있음
  • Cache는 Memory의 블록과 같은 크기의 블록을 가지나, 더 적은 개수를 가짐 (= Memory의 블록들의 부분 집합의 복사본)
  • 데이터는 항상 블록 크기 단위로 복사 됨. 낮은 계층의 디바이스일수록 긴 접근 시간을 가지므로 더 큰 블록을 사용하는 추세
    • e.g. L1-L0 전송은 워드 단위. L2-L1(L3-L2, L4-L3도 마찬가지)의 전송은 일반적으로 수십 바이트 블록

캐시 적중_{Cache Hits}

• Memory로부터 특정 데이터 객체가 필요하다면, 먼저 Cache에 저장된 블록들 중에서 해당 데이터를 찾음 → 만약 해당 데이터가 Cache에 저장되어 있으면 캐시 적중
• 좋은 시간 지역성을 갖는 프로그램은 Cache에서 해당 데이터를 읽어낼 것

캐시 미스_{Cache Misses}

• 만약 해당 데이터가 Cache에 저장되어 있지 않으면 캐시 미스 → Memory에서 해당 데이터 객체가 포함된 블록을 복사해옴. 만약 Cache가 꽉 찼다면 기존 블록에 덮어 씀
• 블록 교체(블록 축출)
  • Cache가 꽉 차서 기존 블록에 데이터를 덮어 씌우는 것
  • 이때, 축출되는 블록을 희생 블록이라고 부름
  • 어떤 블록을 교체할지는 캐시의 교체 정책에 따름 (e.g. 랜덤 교체 정책, LRU 교체 정책(least recently used))

캐시 미스의 종류

1. cold miss
   1. 캐시가 비어있을 때 발생
2. conflict miss
3. capacity miss
   1. 활성화된 캐시 블록들의 집합(working set)이 캐시보다 큰 경우 발생

6.3.2 메모리 계층구조 개념 요약

6.4 캐시 메모리

6.4.1 기본 캐시 메모리 구조

6.4.2 직접매핑 캐시

6.4.3 집합결합성 캐시

6.4.4 완전결합성 캐시

6.4.5 쓰기와 관련된 이슈

6.4.6 실제 캐시 계층구조의 해부

6.4.7 캐시 매개변수의 성능에 대한 효과

6.5 캐시 친화적 코드 작성하기

6.6 종합: 프로그램 성능에 대한 캐시의 영향

6.6.1 메모리 마운틴

6.6.2 공간 지역성을 높이기 위한 루프 재배치

6.6.3 여러분의 프로그램에서 지역성 활용하기

6.7 요약

---

1. https://duniakagyan.com/sram-vs-dram/ ↩︎