CS

메모리 계층 구조

메모리 계층 구조의 동기

• CPU와 메인 메모리 사이의 속도 차이가 매우 크기 때문에, 여러 단계의 저장 장치를 계층적으로 배치하여 전체 시스템의 비용과 성능을 균형있게 맞춤
• 상위 계층은 빠르지만 용량이 작고 비싸며, 하위 계층은 느리지만 용량이 크고 저렴함.

계층 구조의 핵심 원리

• 지역성: 대부분의 프로그램은 메모리 접근 패턴에 시간적/공간적 지역성을 보이기 때문에, 자주/가까이 접근하는 데이터는 빠른 계층에 저장해두면 전체 성능이 크게 향상된다.
• 캐싱: 상위 계층이 하위 계층의 데이터를 일부 복사해두고, 필요할 때 빠르게 접근하도록 함.

1) 저장장치 기술

1-1) 랜덤 접근 메모리(RAM)

SRAM(static ram)

• 각 비트를 6개의 트랜지스터로 구현한 휘발성 메모리
• 빠르고, 전력 소모가 크고, 비싸고, 집적도*가 낮음
• CPU 캐시(레지스터, L1/L2/L3 캐시)에 사용됨

* 집적도: 반도체나 전자 회로에 소자를 밀어넣은 정도

DRAM(dynamic ram)

• 각 비트를 커패시터와 트랜지스터 1개로 저장하는 휘발성 메모리
• 느리지만(접근 시간이 길고), 저렴하고, 집적도가 높아 대용량 구현에 적합
• 메인 메모리, 그래픽 프레임 버퍼 등에 사용됨

비휘발성 메모리

• ROM: 전원이 꺼져도 데이터 보존, 주로 펌웨어 저장

1-2) 디스크 저장장치

• 디스크 저장장치의 개념

  • 디스크는 대용량의 비휘발성 저장장치로 데이터를 영구적으로 저장함.
  • CPU, 메인 메모리와 비교해 접근 속도가 매우 느리지만, 가격이 저렴하고 용량이 큼

• 디스크의 구조

  • 여러 개의 원형 플래터로 구성되며, 각 플래터는 자기 물질로 코팅됨
  • 플래터는 중심축을 기준으로 회전하며, 각 플래터의 양면에는 데이터를 읽고 쓰는 헤드가 있음.
  • 플래터는 동심원의 트랙으로 나뉘고, 각 트랙은 다시 여러 개의 섹터로 분할됨.
  • 동일 위치의 트랙들이 수직으로 쌓인 구조를 실린더라고 함.

• 데이터 접근 방식

  • 디스크에서 특정 데이터를 읽으려면, 원하는 트랙으로 헤드를 이동시키고 플래터가 회전하여 해당 섹터가 헤드 아래에 올 떄까지 기다림
  • 데이터 전송은 한 번에 여러 섹터로 이루어짐.

• 디스크 성능 요소

  • 탐색 시간: 헤드가 원하는 트랙으로 이동하는 데 걸리는 시간
  • 회전 지연: 플래터가 회전하여 원하는 섹터가 헤드 아래에 올 때까지 기다리는 시간
  • 전송 속도: 데이터를 실제로 읽거나 쓰는 속도

• 디스크의 장점과 한계

  • 장점: 대용량, 저렴한 비용, 비휘발성
  • 한계: 느린 접근 속도, 기계적 부품의 내구성 문제

• 논리적 디스크 블록

  • 운영체제와 응용 프로그램이 디스크의 데이터를 접근할 때 사용하는 추상화된 블록 단위
  • 실제 디스크는 복잡한 물리 구조를 갖지만 동일 크기의 논리 블록들의 연속으로 제공함.
  • 동작 방식
    • 디스크 내부의 디스크 컨트롤러가 논리 블록 번호와 실제 물리적 위치를 매핑함
    • 운영체제는 논리 블록 번호만 지정하면, 디스크 컨트롤러가 이를 물리적 위치로 변환해 해당 데이터를 읽거나 씀.

• 디스크 접근 단계

  • CPU/운영체제가 논리 블록 번호와 명령을 디스크 컨트롤러에 전달
  • 디스크 컨트롤러가 논리 블록 번호를 물리 위치로 변환
  • 디스크 기계적 동작
  • DMA를 통한 데이터 전송
    • DMA: 디스크 컨트롤러가 CPU의 개입없이 데이터를 메인 메모리로 직접 전송
  • 작업 완료 후 인터럽트로 CPU에 알림
    

1-3) Solid State Disks(SSD)

플레시 메모리에 기반한 저장장치로, 기존의 기계적 회전 디스크 대신 반도체 소자를 사용함.

• 구조

  • 여러 개의 플래시 메모리 칩이 있음
  • 플래시 변환 계층을 통해 논리 블록 요청을 실제 플래시 메모리의 물리적 위치로 변환함.

• 동작 방식

  • 여러 페이지가 모여 블록을 이룬다.
  • 한 페이지는 오직 한 번만 쓸 수 있고, 덮어쓰려면 블록 전체를 먼저 지워야 함
  • 한 블록은 약 10만 번 정도 쓰고 지울 수 있으며 이를 블록 마모라고 함
  • FTL이 블록 사용을 고르게 분산시켜 SSD 수명을 늘리는 웨어 레벨링을 함

• 장점

  • 기계적 부품이 없어 내구성이 높고 충격에 강하다.
  • 전력 소모가 적고 빠른 데이터 접근이 가능하다.

• 단점

  • 플래시 블록의 마모로 인해 수명이 제한적이다.
  • 용량 대비 가격이 하드디스크보다 비싸다.

2) 지역성

프로그램 메모리에 접근할 떄, 특정 데이터 코드에 대한 접근이 시간적으로나 공간적으로 몰려 있는 경향으로 이러한 특성 덕분에 캐시 및 계층적 메모리 시스템이 효과적으로 동작함.

• 시간적 지역성: 최근에 접근한 데이터나 명령어는 가까운 미래에 다시 접근될 가능성이 높다.
• 공간적 지역성: 한 번 접근한 데이터의 "주변" 데이터도 곧 접근될 가능성이 높다.

예시

• 반복문에서 배열을 순서대로 순회하면, 같은 캐시 블록에 속한 데이터가 반복적으로 사용되어 캐시 히트율*이 높아진다.

• 함수 호출 시, 스택 프레임 내의 지역 변수들이 연속적으로 할당되어 공간적 지역성이 높아진다.

  * 캐시 히트율: CPU가 요청한 데이터가 캐시에 있을 확률
  * 캐시 미스율: CPU가 요청한 데이터가 캐시에 없을 확률

2-1) 프로그램 데이터 참조의 지역성

int sumvec(int *v, int N) {
    int i, sum = 0;
    for (i = 0; i < N; i++)
        sum += v[i];
    return sum;
}

• 지역성 분석
  • sum 변수: 반복문마다 계속해서 접근(읽고, 쓰고)하므로 시간적 지역성(Temporal Locality)이 매우 높다.
  • v 배열: 각 원소를 순차적으로 한 번씩만 읽으므로, 공간적 지역성(Spatial Locality)이 매우 높다.
    • 메모리상에 연속적으로 저장된 원소들을 차례대로 접근하기 때문.
    • 하지만 각 원소는 한 번만 접근하므로 시간적 지역성은 낮다.
• 결론
  • 이 함수는 “sum” 변수에 대해 시간적 지역성이, “v” 배열에 대해 공간적 지역성이 뛰어나므로, 전체적으로 좋은 지역성(good locality)을 가진다.
  • 이런 패턴은 캐시 메모리 효율을 높이고, 프로그램 실행 속도를 빠르게 만든다.

with AI

Bryant, R. E., & O’Hallaron, D. R. (2023). Computer systems: A programmer’s perspective (3rd ed.). Pearson.

좀 지루해져서 넣어봤다.

2-2) 인스트럭션 선입의 지역성

• 명령어 접근의 지역성
  프로그램이 실행될 때, CPU는 메모리에서 명령어(코드)를 읽어온다. 이때 명령어 접근 역시 데이터 접근과 마찬가지로 지역성(locality) 특성을 가진다.
• 시간적 지역성(Temporal Locality)
  • 최근에 실행된 명령어는 가까운 미래에 다시 실행될 가능성이 높다.
  • 예: 짧은 루프(loop) 안의 명령어들은 반복적으로 실행되므로, 해당 명령어들이 캐시에 남아 있으면 성능이 크게 향상된다.
• 공간적 지역성(Spatial Locality)
  • 한 번 실행된 명령어의 “주변” 명령어들도 곧 실행될 가능성이 높다.
  • 예: 프로그램이 순차적으로 실행될 때(즉, 함수나 루프의 본문을 따라 직선적으로 실행될 때), 연속된 메모리 공간에 저장된 명령어들이 차례로 접근된다.

3) 메모리 계층 구조

• CPU와 메모리 사이의 성능 격차는 점점 더 커짐
• 하드웨어의 물리적 특성과 소프트웨어의 지역성 특성이 서로 보완적으로 작용함.
• 이를 바탕으로, 현대 컴퓨터 시스템은 여러 단계의 저장장치를 계층(hierarchy)으로 구성함.
• 상위 계층은 빠르고(레지스터, 캐시), 하위 계층은 느리지만 크고 저렴함(메인 메모리, 디스크, 네트워크 스토리지 등).
• 각 계층은 바로 아래 계층의 데이터를 캐싱하여, 자주 사용되는 데이터에 빠르게 접근할 수 있게 함.

3-1) 메모리 계층구조에서의 캐시

상위 계층k는 하위 계층(k+1)의 데이터를 캐싱함. k+1에서 저장장치는 블록이라고 하는 연속된 데이터 객체 블록으로 나뉨. k에서는 더 작은 집합의 블록들로 나뉨.

데이터는 레벨 k와 k+1 사이에서 블록 크기의 전송 유닛 단위로 복사됨.

• 블록 크기는 계층구조의 인접한 모든 쌍들 사이에서 고정되어 있음
  ex) L1, L2 간에는 항상 64B의 블록 크기만 사용함.
• 다른 레벨 쌍들은 서로 다른 블록 크기를 가짐
  ex) L1, L2 간에는 64B, L2, L3 간에는 128B으로 블록 크기가 다름.
  

캐시 적중

프로그램이 필요로 하는 데이터 객체 d가 현재 계층 k의 캐시에 이미 저장되어 있는 상황
프로그램은 d를 바로 캐시에서 읽어올 수 있으며, 하위 계층에서 읽는 것보다 빠름.

• 동작 과정
  • 프로그램이 데이터 d를 요청하면, 가장 먼저 현재 계층 k의 캐시에서 d를 찾음
  • 만약 d가 캐시에 존재하면 해당 데이터를 반환

캐시 미스

프로그램이 필요한 데이터를 캐시에서 찾지 못하는 상황, 현재 레벨 k의 캐시에 d가 없다면 캐시 미스가 발생함. 캐시는 하위 계층에서 d가 포함된 블록을 가져와 저장하고, 필요하다면 기존 블록을 덮어씀.

• 처리 과정
  • CPU가 데이터 d를 요청
  • 레벨 k 캐시에 d가 없으면, 하위 계층(k+1)에서 d가 포함된 블록을 읽어옴
  • 레벨 k 캐시에 블록을 저장
  • 프로그램은 d를 레벨 k 캐시에서 읽음

캐시 미스의 종류

캐시 미스는 발생 원인에 따라 세 가지로 분류가 가능함.

1. 필수 미스
   • 캐시가 비어 있거나, 해당 데이터 블록을 처음 접근할 때 발생하는 미스
2. 충돌 미스
   • 캐시의 용량은 충분하지만, 여러 데이터 블록이 동일한 캐시 세트에 매핑되어 서로를 덮어쓰는 경우에 발생하는 미스
   • 주로 direct-mapped 캐시나 낮은 연관도를 가진 캐시에서 잘 발생함.
   • 두 개 이상의 자주 접근하는 데이터가 같은 캐시 세트에 할당되어 번갈아 접근할 때마다 서로를 밀어내는 현상(스래싱, thrashing)이 생김
3. 용량 미스
   • 프로그램의 작업 집합이 캐시 전체 용량을 초과할 때 발생하는 미스
   • 캐시가 충분히 크지 않아 자주 사용하는 데이터도 캐시에서 내보내지고 불러와야 하는 상황

캐시 관리

캐시 공간을 블록 단위로 나누고, 블록을 언제/어디에 저장할지, 어떤 블록을 교체할지, 적중/미스 발생 시 어떻게 처리할지, 블록의 일관성을 어떻게 유지할 지를 결정하는 논리와 매커니즘

4) 캐시 메모리

CPU와 메인 메모리(주기억장치) 사이의 성능 격차가 점점 커지며, 이 간극을 메우기 위해 캐시 메모리를 도입함.

4-1) 기본 캐시 메모리 구조

• 캐시의 구성 요소

  • 캐시는 S개의 세트로 이루어진 배열 구조 (S = 2^s)
  • 각 세트는 E개의 라인을 가짐
  • 각 라인은 데이터 블록(block, B bytes, B=2^b), 유효 비트(valid bit), 태그(tag, t bits, t = m - (s + b))를 포함함
  • 전체 캐시 용량 C = S E E (오버헤드 제외)

• 주소 비트의 분할
  m비트의 메모리 주소는 다음 세 부분으로 나뉨.

  • 태그(tag, t비트): 어떤 메모리 블록인지 구분
  • 세트 인덱스(set index, s비트): 해당 데이터가 들어갈 세트 결정
  • 블록 오프셋(block offset, b비트): 블록 내에서의 위치

• 데이터 접근 과정

  • 세트 선택: 주소의 set index 비트를 사용해 S개의 세트 중 하나를 선택함.
  • 라인 매칭: 선택된 세트의 E개의 라인 중, valid bit가 1이고 tag가 주소의 tag와 일치하는 라인이 있는지 확인
  • 단어 추출: 일치하는 라인이 있으면(block hit), block offset 비트로 블록 내에서 원하는 데이터 추출

4-2) 직접매핑 캐시

직접매핑 캐시에서 집합 선택

직접매핑 캐시에서 라인 매칭

직접매핑에서 워드 선택

직접매핑 캐시에서 미스 발생 시 라인 교체

직접매핑 캐시의 동작

직접매핑 캐시에서 충돌 미스

4-3) 집합결합성 캐시

집합결합성 캐시에서 집합의 선택

집합결합성 캐시에서 라인 매칭과 워드 선택

집합결합성 캐시에서 미스 발생 시 라인의 교체

4-4) 완전결합성 캐시

완전결합성 캐시에서 집합의 선택

완전결합성 캐시에서 라인의 매칭과 워드 선택

4-5) 쓰기 관련 이슈

4-6) 실제 캐시 계층구조의 해부

4-7) 캐시 매개변수의 성능에 대한 효과

캐시 크기의 영향

블록 크기의 영향

결합도의 영향

쓰기 전략의 영향

5) 캐시 친화적 코드 작성하기

6) 프로그램 성능에 대한 캐시의 영향

6-1) 메모리 마운틴

6-2) 공간 지역성을 높이기 위한 루프 재배치

6-3) 지역성 활용하기

<수정중>