[CS:APP] 6 : 메모리 계층 구조

지금까지 시스템을 공부하며 컴퓨터 시스템이라는 것은 CPU가 명령어를 실행하고, 메모리 시스템이 CPU를 위해 명령어와 데이터를 저장하는 간단한 모델로 이해했다.

• 이 간단한 모델에서는 메모리 시스템이 바이트의 선형 배열로 구성되어있으며,
• CPU는 각 메모리 위치에 일정한 시간 이내 접근 할 수 있다고 가정한다.

이러한 모델은 어느 정도까지는 효과적이지만, 현대 시스템이 실제 작동하는 방식은 반영하지 않는다.
실제로 메모리 시스템은 여러 저장장치들이 계층적으로 구성된 구조이다.

• 메모리 계층 구조가 작동하는 이유는 잘 작성된 프로그램들이 특정 레벨의 저장 장치를 다음 레벨보다 더 자주 접근하는 경향이 있기 떄문이다.

프로그래머로써 메모리 계층을 이해하는 것이 중요한 이유는, 그것이 성능에 큰 영향을 미치기 때문이다.

프로그램이 필요한 데이터가 레지스터에 저장되어 있다면, 해당 데이터는 명령어 샐힝 중 0 사이클만에 접근 할 수 있다.
캐시에서는 4-75 사이클, 램에는 수백 사이클이다. 디스크에서는 수천만 사이클이 걸린다.

시스템이 데이터를 메모리 계층 상에서 위 아래로 이동시키는 방식을 이해한다면,
프로그램을 작성 할 때 데이터를 더 빠르게 접근 할 수 있도록 메모리 계층 상위에 저장되도록 할 수 있다.

• 이 아이디어는 프로그램의 기본적인 특성인 지역성과 관련이 있다. 지역성이 좋은 프로그램은 동일한 데이터 항목을 반복해서 접근하거나, 인접한 데이터 항목을 접근하는 경향이 있다. 지역성이 좋다면 그렇지 않은 프로그램보다 더 빠르게 실행된다.

 

6.1 Storage Technologies

초기 컴퓨터는 몇 KB 수준의 RAM을 가졌고, 최초의 IBM PC는 하드도 없었다. 1982년 IBM PC-XT의 등장으로 변화 했고, 이 모델은 10MB의 디스크를 탑재하고 있었다..

6.1.1 RAM

Random Access Memory는 두 가지 종류가 있다.

• SRAM은 각 비트를 이진 안정 메모리 셀에 저장한다. 각 셀은 6개의 트랜지스터 회로로 구현된다.
  이 회로는 두 가지 전압 상태 중 하나에 무기한 머무를 수 있는 특성을 가지고 있다.
  다른 상태는 불안정하여, 그 상태에서 회로는 빠르게 안정된 상태 중 하나로 이동하게 된다.
  이런 메모리 셀은 아래 나오는 역방향 진자와 유사하다. 

• SRAM과 DRAM
  • SRAM : 빠르고 비싸다. 캐시 메모리에 이용된다.
  • DRAM : 느리고 저렴하다. 주 메모리 및 그래픽 시스템의 프레임 버퍼에 사용한다.

• SRAM
  • SRAM의 메모리 셀 구성
    • 6개의 트랜지스터로 구현된 이진 안정 메모리 셀이다.
    • 두 가지 전압 상태를 왔다갔다하며 무기한 유지한다.
  • 역방향 진자로 비유되었다 :
    • 진자는 왼쪽 끝이나 오른쪽 끝에서 안정적이다.
    • 수직 상태는 메타 안정 상태로, 작은 충격도 넘어지게 한다.
  • SRAM의 특성
    • 전원이 공급되면 무기한 값을 유지한다.
    • 전기적 잡음에도 안정된 상태로 돌아오게 한다.

• DRAM
  • DRAM 메모리 셀의 구성
    • 비트 저장 : 커패시터에 저장된 전하이다.
    • 셀 구성 : 커패시터 + 단일 접근 트랜지스터로 구성된다.
  • DRAM의 특징
    • 민감성 : 방해에 민감하다. (빛이나 전기적 잡음 같은 것들)
    • 전하 유지 시간이 약 10-100 밀리초이다.
      • 이로 인한 주기적인 갱신이 필요하다.
    • 오류 수정 코드 : 일부 시스템에서 오류 수정 기능을 제공한다.

• 작동 원리에 대한 차이가 있다.
  • SRAM은 전원이 공급되는 한 지속적, 갱신이 필요없고, 방해에도 강하다. 저장 밀도가 낮고 비싸고, 많은 전력을 소모한다.
  • DRAM은 높은 밀도와 경제성 부분에서 장점이 있지만 주기적인 갱신이 필요하고, 더 저렴하지만 방해에 민감하고 전하 손실의 문제를 가진다.

• 전통적인 DRAM
  • DRAM 칩의 셀은 d개의 슈퍼 셀로 나누어진다. 각 슈퍼셀은 w 개의 DRAM 셀로 구성된다.
    따라서 d * w DRAM은 총 dw 비트의 정보를 저장 할 수 있다.
  • 슈퍼셀은 r 행과 c 열로 구성된 직사각형 배열로 조직 되며, rc = d이다.
    • 각 슈퍼셀은 (i, j) 형식의 주소를 가지며, 여기서 i는 행, j는 열이다.
  • DRAM 칩의 데이터 흐름도 조금은 다르다.
    • 핀 : 1비트 신호를 전송한다.
    • 데이터 핀 : 8개의 데이터 핀을 사용해 1바이트를 전송한다.
    • 주소 핀 : 2개의 주소 핀을 이용하여 행 및 열의 주소를 전달한다.
  • 슈퍼셀 읽기 과정
    • RAS : 행 주소 요청이다.
    • CAS : 열 주소 요청이다.
    • 행 버퍼 : 행 데이터를 임시로 저장하는 역할이다.
  • 2차원 배열의 장점과 단점
    • 장점 : 주소 핀 수를 줄일 수 있다.
    • 단점 : 두 단계로 주소를 전송해야 하므로 접근 시간이 증가한다.

• 이 그림은 d = 16 슈퍼셀, w = 8 비트의 슈퍼셀당 크기, r = 4 행, c = 4 열로 구성된 16 * 8 DRAM 칩의 구성을 보여준다. 그 안에서 (2, 1) 주소의 슈퍼셀은 음영 처리된 박스로 표시되어 있다.

• 예를 들어 그림 6.3의 16 * 8 DRAM에서 슈퍼셀 (2, 1)을 읽으려면, 메모리 컨트롤러는 2번 행의 주소를 전송한다. (a)
• 그러면 DRAM은 2번 행의 모든 내용을 내부 행 버퍼에 복사한다. 그 후, 메모리 컨트롤러는 1번 열 주소를 전송한다. (b)
• DRAM은 (2, 1) 슈퍼셀의 8비트를 행 버퍼에서 복사하여 메모리 컨트롤러로 전송한다.
• 메모리 모듈
  • DRAM 칩 : 메모리 모듈에 패키징되어 마더보드 확장 슬롯에 연결된다.
  • DIMM : 240핀 듀얼 인라인 메모리 모듈을 말한다.

• 메모리 모듈 예시를 들어보자.
  • 64MB 저장 시도는 : 8개의 64-Mbit 8M * 8 DRAM 칩으로 구성되어 이뤄진다.
  • 슈퍼셀 : 각 슈퍼셀은 1바이트를 저장한다.
  • 64비트 워드 : 8개의 슈퍼셀로 구성되며, 각 DRAM이 하나의 바이트를 저장한다.

• 메모리 주소 변환 및 데이터 전송
  • 주소 변환 : 메모리 주소 A를 슈퍼셀 주소 (i, j)로 변환한다.
  • DRAM 응답 : 각 DRAM은 (i, j) 슈퍼셀의 8비트 데이터를 출력한다.

• 메모리 모듈 확장
  • 여러 메모리 모듈을 메모리 컨트롤러에 연결하여 메인 메모리를 확장한다.
  • 컨트롤러는 A를 포함하는 모듈을 선택하고 데이터를 전송한다.

 

• 향상된 DRAM | Enhanced DRAMs
  • 기본 DRAM 셀을 기반으로 하지만, 접근 속도를 높이기 위한 최적화를 포함한다.
  1. Fast Page Mode DRAM | FPM DRAM
     • 기본 DRAM은 어떤 행 전체를 내부 버퍼로 복사한 뒤, 필요한 슈퍼셀 하나만 사용하고 나머지는 버린다.
     • FPM DRAM은 같은 행에서 여러 번 데이터를 읽을 때 복사한 버퍼를 계속 활용 할 수 있다.
     • 즉, 첫 번째 접근 이후에는 추가 복사 없이 빠르게 다음 데이터를 가져올 수 있다.
     • 쉽게 말해, 같은 책 페이지에서 여러 줄을 읽는다면, 매번 책을 다시 펴야했던 기존과 달리 여러 번을 읽는다.
  2. Extended Data Out DRAM | EDO DRAM
     • FPM DRAM보다 더 빠르다.
     • 데이터 요청 신호를 뜻하는 CAS 신호 사이의 간격을 더욱 좁혀서 연속 읽기의 속도를 더 높였다.
  3. Synchronouis DRAM | SDRAM
     • 기존 DRAM들은 명령 신호로 데이터를 주고받았는데, SDRAM은 메모리 컨트롤러와 같은 클럭 신호(주기적 신호)에 맞춰 동작한다.
     • 덕분에 데이터를 더 규칙적이고 빠르게 전송 할 수 있게 되었다.
  4. Double Data-Rate SDRAM | DDR SDRAM
     • SDRAM을 개선한 것이다.
     • 클럭 신호의 상승, 하강 둘 다를 이용해서 데이터 전송 속도를 2배로 높였다.
     • 종류는 2비트 프리패치의 DDR, 4비트의 DDR2, 8비트의 DDR3.. 존재한다.
     • 쉽게 말해, 발을 딛을 때와 뗄 때 모두 일을 처리하듯, 한 신호 주기에 두 번 데이터를 처리한다.
  5. Video RAM | VRAM | 여기는 노선이 조금 다르다
     • 그래픽 시스템을 위한 특별한 메모리이다.
     • 내부 버퍼 전체를 한번에 읽은 뒤 순차적으로 출력하게 된다.
     • 화면에 이미지를 그리는 와중에도 다음 이미지를 준비하는 읽기/쓰기가 동시에 가능하다.

 

비휘발성 메모리

• DRAM과 SRAM은 전원이 꺼지면 저장된 데이터가 모두 사라진다. 반면, 비휘발성 메모리는 전원이 꺼져도 데이터가 남아있다.
• 전통적으로 비휘발성 메모리는 ROM(Read-Only Memory)라고 불린다.
  • 이름 값을 못하는것이, 요즘은 쓰기도 된다고 한다?

• ROM의 종류  Programmable ROM | PROM
  • 한 번만 데이터를 기록 할 수 있다.
  • 셀마다 퓨즈가 있어서, 기록 할 때 퓨즈를 태우면서 한 번만 저장하게 된다. 이후에는 다시 수정 할 수 없다. 
  • Erasable Programmable ROM | EPROM
    • 저장된 데이터를 자외선을 쬐게 해서 지울 수 있다.
    • 그 다음에 다시 새 데이터를 기록 할 수 있다.
    • 반복 사용 가능하나, 1,000번 정도의 횟수로만 가능하다.
  • Electrically Erasable PROM | EEPROM
    • 전기로 지우고 다시 기록 할 수 있다.
    • 별도의 장치 없이 회로에 연결된 상태에서 바로 수정 할 수 있다.
    • 대략 10만 번 정도 반복 사용이 가능하다.
  • Flash Memory
    • EEPROM 기반으로 만들어졌다.
    • 빠르고, 튼튼하고, 전기도 적게 먹는다.
    • 거의 모든 전자기기 저장장치에 사용한다.
  • ROM과 펌웨어 (Firmware)
    • ROM안에는 펌웨어라고 불리는 프로그램이 저장되어 있다.
    • 컴퓨터가 켜질 때, 제일 먼저 ROM에 저장된 펌웨어가 실행된다. PC의 BIOS는 대표 예제이다.
    • 복잡한 기기들은 전부 펌웨어를 사용하며 시동이 걸린다.
    • 예를 들어, 기계 입장에서 부팅 할 때 해야 할 것들에 대한 내용이 ROM에 저장 되어 있다.

종류	특징
PROM	한 번만 기록 할 수 있다. 한 번 기록하면 수정 할 수 없다.
EPROM	자외선으로 지우고, 그 이후에 새로 쓸 수 있다. | 1,000번
EEPROM	전기로 지우고 다시 쓴다. | 약 10만 번 가능
Flash Memory	EEPROM 개선판.

메인 메모리 접근하기

• CPU와 DRAM 사이에는 전기 신호 통로인 버스가 존재한다.
• 이 버스를 사용하기 위해선 버스 트랜젝션이라는 일련의 과정을 거쳐 데이터를 주고 받게 된다.
  • Read 트랜잭션 수행 시 : DRAM에서 CPU로
  • Write 트랜잭션 수행 시 : CPU에서 DRAM으로

• 버스?
  • 버스는 여러 가닥의 병렬 전선 묶음을 말한다. 버스는 다양한 것을 운반한다.
    • address, data, control signals.
  • 버스 설계에 따라 :
    • 주소와 데이터가 같은 전선을 쓸 수도 있고, 따로 분리해서 쓸 수도 있다.
    • 여러 장치가 하나의 버스를 공유 할 수도 있다.
  • 제어 신호는 트랜잭션을 조정하고 구분한다 :
    • 지금 버스에 흐르는 정보는 주소인가, 데이터인가?
    • 이 작업은 메모리를 대상으로 하나? 아니면 다른 I/O 장치를 대상으로 하나?
    • 작업 종류는 read인가 write인가?

• 시스템 구조 예시를 이 그림을 통해 확인해보자!

• 주요 부품은 CPU 칩, I/O Bridge, DRAM Memory Module이 해당한다.
  • 이들 부품을 연결하는 두 개의 버스가 존재한다 :
    • CPU ↔ I/O Bridge 연결의 System Bus
    • I/O Bridge ↔ DRAM 연결의 Memory Bus
  • I/O Bridge는 :
    • 시스템 버스 신호와 메모리 버스 신호를 양방향에서 교환 할 수 있도록 한다.
    • 이후, I/O 장치들이 공유하는 I/O 버스와도 연결이 이루어진다.

 

메모리 load 과정 | 읽기

• movq A, %rax | 주소 A의 값을 읽어와 %rax 레지스터에 저장하기.

• 3단계의 과정을 거치게 된다.
  1. CPU가 주소 A를 시스템 버스에 올린다.
     • I/O Bridge가 이것을 Memory Bus에 전달한다. (a)
  2. 메모리가 주소를 감지하고 데이터를 메모리 버스에 올린다.
     • I/O Bridge가 이를 다시 시스템 버스로 전달한다. (b)
  3. CPU가 시스템 버스에서 데이터를 읽어와 %rax에 복사한다. (c)

 

메모리 store 과정 | 쓰기

• movq %rax, A | %rax의 레지스터 값을 주소 A에 저장한다.

• 3단계의 과정을 거치게 된다.
  1. CPU가 주소 A를 시스템 버스에 올린다.
     • 메모리가 주소를 감지하고 데이터를 기다린다. (a)
  2. CPU가 시스템 버스에 데이터를 올린다. (b)
  3. 메모리가 시스템 버스에서 데이터를 읽어와 DRAM에 저장한다. (c)

 

6.1.2 Disk Storage

디스크는 보통 대용량 저장 장치를 말한다 : 용량은 수백 ~ 수천 GB이다.
용량이 많지만 아쉽게도 메인 메모리보다 읽기 속도가 훨 씬 느리다.

• 디스크는 읽는데 ms 단위의 시간이 필요하다. 이는 DRAM 보다 10만 배 느리고, SRAM 보다 100만 배 느리다.

디스크 구조

• 플래터 | Platter
  • 디스크는 하나 이상의 플래터로 구성되어 있다. 플래터는 양쪽의 면 모두를 활용한다.
    각 면은 자가 기록 물질로 코딩되어 있다. 플래터는 중심 축(spindle)을 기준으로 초당 수천 번 회전한다.
    • 보통 5,400 ~ 15,000 RPM (Rotate per min)
  • 디스크는 플래터 여러 장을 수직으로 쌓고, 밀봉된 케이스 안에 넣어서 만든다.

 

 

• 플래스 표면의 구성 | 그림의 (a)
  • 각 플래스 면은 여러 개의 트랙으로 구성되어있다. 트랙(track)은 플래터 면 위의 동심원을 말한다. (원을 겹겹이 겹쳐 놓은 것)
  • 각 트랙은 다시 여러 개의 섹터(sector)로 나뉜다. 섹터 하나에는 보통 512바이트 정도의 데이터가 저장된다.
  • 섹터 사이에는 갭(gap)이 존재한다. 갭에는 섹터를 구분하는 포맷 정보가 저장되어 있고, 데이터는 저장되지 않는다.

• 디스크 전체 구조 | 그림의 (b)
  • 디스크는 플래터 여러 장을 수직으로 쌓아 올린 형태임을 확인했다.
  • 모든 플래터를 감사는 밀폐된 패키지 안에 들어있다. 이것은 SSD가 아닌 HDD임에 유의.

• 실린더 | Cylinder
  • 여러 플래터를 가진 디스크에서는 실린더라는 개념이 등장한다.
  • 실린더란, 같은 반지름 상에 있는 모든 플래터의 트랙 모음을 말한다.
  • 플래터가 3장이면 면이 6개 있는 것인데, 각 면의 트랙 번호가 같다면,
    • k번 실린더는 6개의 k번 트랙을 모두 포함하는 집합이다.

디스크 용량

디스크 용량은 디스크에 저장 할 수 있는 최대 비트 수를 말한다. 보통은 Capacity라고 부른다.

• 디스크 용량을 결정하는 기술적 요소는 세 가지가 있다.
  • Recording Density, 기록 밀도
    • 1인치 길이의 트랙 위에 저장 할 수 있는 비트 수를 말한다. (bits/inch)
  • Track Density, 트랙 밀도
    • 플래터 반지금 1인치 길이 안에 저장 할 수 있는 트랙 수를 말한다. (tracks/inch)
  • Areal Density, 면적 밀도
    • 기록 밀도와 트랙 밀도를 곱한 것. (bits/inch^2)
  • 디스크 제조사는 Areal Density를 끊임 없이 높이려고 하고 있으며, 최근에는 2년에 한 번씩 2배로 늘어나는 추세이다.

트랙 구성 변화 : Fixed vs Multiple Zone Recording

• 과거에는 모든 트랙에 같은 수의 섹터를 배치 했다.
  • 기준은 가장 안쪽 트랙에 저장 할 수 있는 섹터 수였다.
  • 바깥쪽 트랙은 더 공간이 있는데도 섹터 간 간격이 너무 커져, 저장 공간이 낭비 되는경우가 있었다.

• 현대 : Multiple Zone Recording을 사용한다.
  • 실린더를 여러 개의 Recording Zones로 나눠서 과거의 문제를 해결한다.
  • 각 Zone마다 트랙 당 섹터 수가 다를 수 있다.
  • 같은 Zone 안에서는 모든 트랙이 같은 섹터 수를 가진다.
  • 덕분에 바깥쪽 Zone에서는 더 많은 섹터를 저장 할 수 있다.
  • Capacity = (bytes/sector) × (average sectors/track) × (tracks/surface) × (surfaces/platter) × (platters/disk)
    • 예시 계산을 한번 시도해보겠다.
    • 디스크 사양 : 5개의 플래터, 1 섹터는 512Byte, 1면 당 2만 개의 트랙, 트랙당 평균 300개의 섹터
    • Capacity = 512 * 300 * 20,000 * 2 * 5 = 30,720,000,000 Bytes | 30.72 GB

디스크 동작

• 기본 구조
  • 디스크 표면 위에 저장된 비트를 읽고 쓰는 장치는 Read/Write Head이다.
  • Head는 Actuator Arm 끝에 부착되어 있으며, 방사형(radial)으로 이동 할 수 있다.
  • 주요 동작은 :
    • Seek : Arm이 원하는 트랙 위로 헤드를 이동시킨다.
    • Read/Write : 트랙 아래를 지나가는 데이터를 읽거나 변경시킨다.
  • 멀티 플래터 디스크에서는 :
    • 각 플래터 면마다 별도의 Head가 존재한다.
    • 모든 Head는 같은 Cylinder 상의 트랙에 정렬되어 동시에 움직인다.

• Read/Write Head 특징
  • Head는 디스크 표면 위를 약 0.1 마이크로 미터 높이로 떠서 비행한다. 비행 속도는 약 80km/h에 달한다.
  • Head Crash 위험
    • 미세한 먼지도 거대한 장애물처럼 작용 할 수 있어, Head가 충돌하면 치명적인 손상이 발생 할 수 있다.
    • 그래서 밀폐된 공간에 디스크가 보관되는 것이다!

 

• 디스크 접근 과정과 시간 요소 
  • 디스크는 섹터 단위로 데이터를 읽고 쓴다. 섹터 접근 시간은 다음 3가지 요소의 합이다.
  • Seek Time (Tseek)
    • Arm이 원하는 트랙으로 이동하는 데 걸리는 시간을 말한다.
    • 무작위 여러 번 측정 후 평균을 내는데, 보통 3-9 사이의 평균값이 발생한다.
  • Rotational Latency (Trotation)
    • 헤드가 트랙에 도착한 뒤, 디스크가 회전하여 원하는 섹터가 헤드 아래 올 때까지 기다리는 시간을 말한다.
  • Transfter Time (Ttransfer)
    • 섹터 데이터를 읽거나 쓰는 데 걸리는 시간을 말한다. 

논리 디스크 블록

• 실제 디스크는 되게 복잡하다. 여러 플래터.. 면.. 각 면에 막 기록하고..
• 운영체제가 디스크의 복잡성을 몰라도 되도록, 디스크는 단순한 논리 블록 번호 (Logical Block Number) 체계를 제공한다.
• 하드웨어/펌웨어 장치가 논리 블록 번호 ↔ 물리적 위치 매핑을 관리한다.
  • 주요 동작 흐름은 :
    1. OS가 특정 논리 블록을 읽어달라고 요청한다.
    2. 디스크 컨트롤러가 Surface, Track, Sector 3 튜플로 변환된다.
    3. 컨트롤러 하드웨어가 아래와 같은 절차를 수행한다
       • 헤드를 올바른 실린더로 이동시킨다.
       • 디스크 회전을 기다린다.
       • 데이터를 읽어 내부 버퍼에 저장한다.
       • 이후 메인 메모리로 복사한다.

I/O 디바이스 연결

• I/O 버스부터 알아야하는데, 이 버스는 CPU와 메모리, 다양한 I/O 장치를 연결하는 독립형 버스이다.
  • CPU 구조와 무관하게 설계되었으며, 시스템 버스나 메모리 버스보다 느리지만, 다양한 장치에 대한 호환성이 훌륭하다.

• 대표적인 I/O 버스 연결 구조는 여러가지가 있다 : 
  • USB Controller, GPU, Host Bus Adapter

디스크 접근 과정

• 전체 흐름 요약
  • CPU는 Memory-Mapped I/O 방식으로 디스크와 통신한다.
  • 디스크 컨트롤러가 직접 메모리에 데이터 전송 (DMA)를 수행한다.
  • 디스크 읽기 완료 후, Interrupt를 통해 CPU에 알린다.

 

• 단계별 세부 과정 
  1. CPU가 디스크에 읽기를 요청한다 | Memory-Mapped I/O
     • 메모리 공간 중 일부가 I/O 장치를 위한 I/O 포트로 예약된다.
     • 예를 들어 디스크 컨트롤러가 포트 0xA0에 매핑된 경우
     • CPU는 디스크 읽기를 위해 3번 연속 store 명령어를 실행한다.
       1. 첫 store :
          • 디스크에 읽기 시작 명령을 전송한다.
          • 추가 옵션으로, 읽기 완료 후 인터럽트 발생 여부를 설정한다.
       2. 둘 store : 읽고자 하는 논리 블록 번호를 전달한다.
       3. 셋 store : 읽은 데이터를 저장할 메인 메모리 주소를 전달한다.
     • 요청을 보낸 후, CPU는 디스크 작업을 기다리지 않고 다른 일을 계속 수행한다.
  2. 디스크 컨트롤러가 직접 데이터를 전송한다 | DMA, Direct Memory Access
     • 디스크 컨트롤러가 논리 블록 번호를 Surface, Track, Sector 3튜플로 변환한다.
     • 디스크로 부터 데이터를 읽고, CPU의 개입 없이 메모리로 직접 데이터를 전송 할 수 있다.
  
  
  3. 데이터 전송 완료 후 CPU에 알린다 | Interrupt
     • DMA 전송 완료 시, 디스크 컨트롤러가 인터럽트를 CPU에 보낸다.
     • 인터럽트 처리 순서 :
       1. CPU 외부 핀에 신호하여 현재 작업을 중단한다.
       2. 운영체제 커널의 인터럽트 핸들러를 실행하고, I/O 작업 완료 사실을 기록한다.
       3. CPU는 인터럽트 처리 후 원래 작업을 계속 이어서 수행한다.

 

6.1.3 SSD

• SSD는 플래시 메모리를 기반으로 만든 HDD의 대체품으로써 등장했다.
• SSD는 일반 디스크 슬롯에 연결되고, CPU의 논리적 블록 요청을 받아서 처리한다.

• 구성 요소
  • Flash Memory Chip, 실제 데이터를 저장하는 부분이다.
  • Flash Translation Layer (FTL),
    • 디스크 컨트롤러처럼 동작하며, 논리 블록 번호는 물리 메모리 위치로 변환된다.
    • 복잡한 쓰기 관리 및 wear leveling(마모 분산)을 수행한다.

• 플래시 메모리의 구조와 동작 특성
  • 플래시 메모리 구조
    • Block : 여러 개의 Page로 구성되어있다.
    • Page 크기는 : 보통 512byte ~ 4KB
    • Block 크기는 : 16KB ~ 512KB (32 ~ 128 페이지)
  • 데이터 읽기/쓰기 단위
    • 읽기/쓰기 : 페이지 단위
    • 지우기 : 블록 단위
  • 쓰기 제약사항 :
    • 블록 전체를 먼저 지워야만 페이지에 새로 쓰는 것이 가능하다.
    • 지우기는 비트 전체를 1로 초기화 하는것.
    • 어? Lazy Initialize?
  • 마모 Wear Out
    • 블록은 약 100,000회 쓰기 후 수명이 끝난다. 수명이 다한 블록은 더 이상 사용 할 수 없다.

• SSD 성능 특성
  • 읽기는 빠르고, 쓰기는 상대적으로 느리다. (그래도 HDD보다 압도적으로 빠르지?)
    • 이유 1. Block erase 시간이 길다. (약 1ms 필요)
    • 이유 2. 기존 데이터가 존재하는 페이지를 수정 할 때, 해당 블록의 유효 데이터까지 새 블록으로 복사해야 한다 : copy overhead
  • Random Write 성능 저하의 핵심 : 블록 지우기 + 데이터 복사의 비용이 추가된 것이 크다.
  • FTL | Flash Translation Layer의 역할
    • Erase 비용을 분산 (amortize), 내부 복사를 최소화 (minimize) 하는데 의의가 있다.

 

6.1.4 Storage Technology Trends

• 속도가 빠를수록 가격이 높다.

• SSD는 DRAM과 디스크의 중간 성능/가격 위치에 포진해 있다.

• 시간에 따른 저장 기술의 발전 추이를 가볍게 보자.

• SRAM
  • 성능은 약 100배 향상되었고 가격은 약 100배가 하락했다. 성능과 가격이 비슷한 비율로 발전하고 있다.

• DRAM
  • 액세스 타임 기준으로 성능이 약 10배 향상 되었고, 가격은 44,000배 하락했다.
  • 밀도는 급격히 증가하였지만 속도는 상대적으로 정체인 상태이다.

• HDD
  • 성능은 약 25배 향상되었고 가격은 약 3,000,000배가 감소했다. 그러나 속도 개선이 더딘 상태.

• CPU
  • 사이클 타임만 보면, 단일 코어 기준 500배, 멀티코어 반영시 2,000배 향샹의 기록이 있다.

 

• 저장 장치들의 액세스 타임과 CPU 사이클 타임을 같은 축에서 본 반로그 그래프를 보자.
• SRAM은 CPU 성능과 유사한 속도로 발전했고, DRAM/HDD는 성능 격차가 점점 커지고 있다.

성능 격차는 시대가 가면서 본질이 변화하게 되었는데,

• 과거의 성능 격차는 지연(latency) 차이가 주된 내용이었다.
• 멀티코어가 주된 현재로써는 처리량 차이로 전환이 되었고, 이것은 여러 코어가 동시에 메모리/디스크에 접근하기 때문이다.
• 현대 컴퓨터는 이런 성능 격차를 극복하기 위해 SRAM 기반 캐시 계층을 적극적으로 활용하고 있다.

6.2 Locality

지역성은 프로그램이 최근 참조된 데이터나 그 근처의 데이터를 다시 참조하는 경향을 말한다. 이는, 대부분 잘 작성된 프로그램에서 관찰 될 수 있다.

• 지역성은 하드웨어, 운영체제, 프로그램 설계에 큰 영향을 미친다. 지역성이 좋을수록 프로그램은 더 빠르게 동작한다.

지역성은 두 가지의 유형이 있다 :

Temporal Locality, 시간적 지역성 | Spatial Locality, 공간적 지역성..

시스템에서의 지역성 활용 사례를 같이 보자.

• 하드웨어 (CPU - 메모리 계층)
  • 캐시 메모리
    • 최근 접근한 데이터 명령어/블록을 보관한다.
    • 지역성을 이용해 메인 메모리 접근을 줄여 속도를 향상시키는데 기여한다.

• 운영체제 (메모리 관리 및 파일 시스템)
  • 가상 메모리 (Virtual Memory)
    • 메인 메모리를 디스크의 캐시로 사용한다.
    • 최근 접근된 주소 공간을 메모리에 유지시킴으로써 구현된다.
  • 디스크 캐시
    • 최근 사용된 디스크 블록을 메인 메모리에 유지하여 I/O를 최소화하는데 기여한다.

• 사용자 수준의 애플리케이션
  • 웹 브라우저 : 최근 방문한 웹 문서를 로컬 디스크에 캐싱한다. 이것은 시간적 지역성과 관련이 깊다.
  • 웹 서버
    • 인기 있는 문서를 프론트엔드 캐시에 보관하여 빠르게 응답한다. 서버 부하 없이 요청 처리가 가능하다.

 

6.2.1 Locality of References to Program Data

• 이 함수를 같이 보자.
  • sum은 루프마다 1번씩 참조하며, 자주 재사용된다는 점에서 Temporal Locality가 있다고 할 수 있다.
  • v[i]는 배열 요소를 순차적으로 접근하니, Spatial Locality가 있다고 할 수 있다.
  • 각 언급되지 않은건 없다고 간주 할 수 있다. (즉 sum은 Spatial Locality가 없다)

• 어쨌든 결론을 내면, 이 함수는 각 변수에 대해 적어도 한 형태의 지역성을 가지고 있으니 전체적으로 괜찮은 지역성을 가진다고 할 수 있다.

 

Spatial Locality에는 패턴이 있다. 이것을 Stride 패턴이라고 한다 :

• Stride-1 패턴
  • 요소를 연속적으로 한 칸씩 접근하는 경우이다.
  • v[0], v[1], v[2] ..
  • 제일 훌륭한 공간적 지역성에 속한다.

• Stride-k 패턴 [Figure 6.18, 6.19]
  • k 칸씩 건너 뛰며 접근하는 경우가 해당한다.
  • Stride 값이 커질 수록 Spatial Locality가 감소하게 된다.
  • C 언어는 row-major order | 행 우선 메모리 배치를 채택하고 있다.
  • 이 언어의 배치 상태를 존중한 코드로, 이 함수는 행 기준으로 순차적 접근이 이루어진다.
  • stride-1 패턴으로 → 매우 훌륭한 Spatial Locality라고 할 수 있다.
  • 이번엔 row-major order와 반대되는 column-wise 접근을 보자.
  • 열 기준으로 접근을 하게 되는데, 메모리 상에서는 stride-N 식의 접근이 일어난다.
  • 이런 경우엔 Spatial Locality가 정말 나쁜 편에 속한다.

 

우린 작은 코드 변경으로도 메모리 접근에 큰 차이가 있을 수 있음을 이 내용에서 얻었다.
Stride-1 접근이 성능 최적화에 유리함을 기억 해두자.

 

6.2.2 Locality of Instruction Fetches

메모리를 아우르며 보는 루프문 뿐만 아니라 명령어 접근에도 지역성은 적용된다.

• 프로그램 명령어도 메모리에 저장되며, CPU가 실행을 위해 읽어들인다.
  • 따라서 instruction fetch 패턴도 locality 분석 대상이다.

• 루프 구조의 명령어는 지역성이 좋다.
  • sumvec 함수의 for 루프를 아까 보았다.
    • 루프 내부의 명령어들은 메모리 내부에 연속적으로 저장된다. → Spatial Locality를 만족한다
    • 루프는 여러 번 반복 실행된다 → Temporal Locality를 만족한다.

코드와 데이터의 차이점은, 코드는 거의 수정이 이루어지지 않는다는 것이다.

• 즉, 코드에 대해서는 읽기 전용 캐시 최적화를 수행 할 수 있다.
• 이는 CPU 및 메모리 설계에서 Instruction Cache를 별도로 두는 주요 이유 중 하나이기도 하다.

 

6.2.3 Summary of Locality

프로그램을 읽을 때 어떤 데이터나 명령어가 얼마나 자주, 얼마나 가깝게 접근되는지를 빠르게 감지하는 능력은 중요하다!

 

6.3 The Memory Hierarchy

저장 기술의 특징

• 속도 차이 : 저장 장치들은 접근 속도가 매우 다르다.
• 빠를수록 가격이 비싸고, 느릴수록 저렴하다.
• CPU와 메모리 속도 차이도 시간이 지날수록 격차가 벌어지고 있다.

컴퓨터 소프트웨어의 특징

• 잘 작성된 프로그램은 보통 시간적/공간적 지역성을 보인다.
  • 최근에 접근한 데이터또는 주변 데이터를 다시 참조하는 경향이 있다.

하드웨어와 소프트웨어의 조화

• 저장 기술과 소프트웨어의 특성이 서로를 보완한다.
  • 빠르고 비싼 메모리는 빈번히 접근되는 데이터를 저장함으로써 성능 최적화를 달성 할 수 있다.

메모리 계층 구조 | Memory Hierachy

• 메모리를 속도, 비용, 용량 특성에 따라 여러 계층으로 나누어 구성하였다.
• 위로 갈수록 빠르나 비싸고 작아진다. 아래로 갈수록 느리나 싸고 커진다.

 

6.3.1 Caching in the Memory Hierarchy

캐시에 대해 논해보자.

• 캐시는 작은 고속 저장장치인데, 더 크고 느린 저장 장치에서 데이터 객체를 임시로 보관하는 중간 단계 저장소이다.
• Caching은 이 캐시를 사용하는 과정을 의미한다.

메모리 계층과 캐시 역할

• 각 계층 k는 그 아래 계층 k+1을 위한 캐시 역할을 한다.

• 구조 예시
  • 로컬 디스크 → 네트워크 서버 데이터 캐시
  • 메인 메모리 → 로컬 디스크 데이터 캐시
  • 캐시 메모리 → 메인 메모리 데이터 캐시
  • 레지스터 → 캐시 메모리 데이터 캐시

캐시와 블록

• 블록
  • 계층 k+1 저장소는 연속된 블록 단위로 분할된다.
  • 각 블록은 고유한 주소 또는 이름을 가진다.

• 블록 특징
  • 일반적으로 고정 크기, 가끔 가변 크기도 있다.
• 데이터 이동 단위 : 항상 블록 단위로 데이터를 이동시킨다. 

계층 간 블록 크기 차이

• 계층 쌍마다 블록 크기가 다르다.
  • L0 ↔ L1 : 워드 크기의 블록을 전송한다.
  • L1 ↔ L2, L2 ↔ L3, L3 ↔ L4 : 수십 바이트 블록을 전송한다.
  • L4 ↔ L5 : 수백 수천 바이트의 블록을 전송한다.
• 하위 계층일수록 접근 시간이 길다. 그래서 한 번에 더 많은 데이터를 전송해 오버헤드를 줄이는데 목적이 있다.

Cache 동작 : 히트, 미스, 미스의 종류

• Cache Hit
  • 프로그램이 필요한 데이터 객체 d를 먼저 레벨 k에서 찾는다.
  • d가 레벨 k에 존재하면, Cache Hit가 발생!
  • → 빠른 레벨 k에서 직접 읽을 수 있으니 향상된 성능을 이룰 수 있다.

• Cache Miss
  • 데이터 d가 레벨 k에 없으면 Cache Miss가 발생한다.
  • → 레벨 k+1에서 블록 전체를 가져와야 한다.
  • 만약 캐시가 가득 찼다면, 기존 블록 하나를 퇴출 해야 한다.

• Eviction | 교체
  • 캐시가 가득 찬 경우, 기존 블록을 대체해야한다.
  • 제거된 블록을 victim block이라고 부른다.
  • 교체 정책에 따라 어떤 블록을 버릴지 결정해야 한다 :
    • Random : 무작위로 하나 선택한다.
    • LRU (Least Recently Used) : 가장 오래 전에 사용된 블록을 제거한다.

• Cache Miss의 종류

• Placement Policy | 배치 정책
  • 어떤 블록을 캐시 어디에 둘지 결정하는 규칙이다.
  • 일반적인 방법은 두 가지가 있는데,
    • Fully Associative | 자유 배치 : 아무 위치나 저장 가능하다. (고성능 시스템에서 드물게 사용한다)
    • Restricted Placement | 제한 배치 : 특정 위치에만 저장이 가능하다.
      • (i mod N) 규칙 → 블록 i는 캐시의 (i mod N) 위치에 저장한다.
  • 예시를 한번 보자. 앞에서 봤던 그림 6.22
    • 캐시 크기는 4블록, 블록 0 4 8 12는 모두 캐시 블록 0에 매핑되었다.

• Working Set | 작업 집합
  • 프로그램 실행 중 특정 단계에서 자주 접근하는 데이터 집합이다.
  • 워킹 셋 크기가 캐시보다 크면 Capacity Miss가 발생한다.

• 캐시 관리
  • Memory Hierarchy에서 Cache 관리의 필요성
    • 각 계층은 바로 아래 계층의 데이터를 캐싱한다.
    • 따라서 각 레벨마다 다음을 담당하는 관리 로직이 필요하다.
      • 캐시를 블록 단위로 분할한다.
      • 블록을 상하위 레벨 간에 이동한다.
      • 히트와 미스를 감지한다.
      • 미스 발생 시 적절한 조치를 수행한다.
  • 캐시 관리 주체 : 하드웨어, 소프트웨어, 또는 둘 다
  • 프로그램 입장에서의 캐시
    • 대부분의 캐시는 자동으로 작동하기에, 프로그래머는 명시적으로 조작, 관여 할 필요가 없다.

6.3.2 Summary of Memory Hierarchy Concepts

메모리 계층 구조는 저장장치 성능 대비 비용 차이와 프로그램의 지역성 특성을 활용하여 전체 시스템 성능을 최적화 하는 구조이다.

6.4 Cache Memories

초기의 메모리 계층은 3단계였다 : CPU 레지스터, 주 기억 장치 RAM, 디스크 저장소.

• 단순하지만 CPU의 메인 메모리 간 속도 차이가 점점 심화됨에 따라 변화가 필요해졌다.

다양한 시도 중 의미가 있었던 캐시 메모리는 현대까지도 채택되고 있다.

• L1 캐시, CPU 레지스터와 메인 메모리 사이에 위치한다.
  • SRAM 기반으로 만들어졌으며, 약 4 클럭 사이클의 접근 속도이다.
  • 가장 빠른 접근이 필요한 데이터를 위한 최상위 캐시이다.

• L2 캐시, L1 캐시와 메인 메모리 사이에 위치한다.
  • 접근 속도는 약 10 클럭 사이클이다. L1 보다 큰 용량이나, L1 보다 느리다.
  • L1에서 누락된 데이터를 보조적으로 저장해주는 역할을 수행한다.

• L3 캐시, L2 캐시와 메인 메모리 사이에 위치한다.
  • 접근 속도는 약 50 클럭 사이클이다. 멀티코어 CPU 간의 공유 캐시로도 사용된다.

 

6.4.1 Generic Cache Memory Organization

일반적인 캐시 메모리 구조

• 기본 개념 및 용어를 정의하겠다.

• 주소 비트 수는 m → 메모리 주소 공간의 총 크기는 M = 2^m 이다. (유일한 주소 개수)

• 캐시는 총 S = 2^s개의 캐시 세트로 구성되며, 각 세트는 E개의 캐시 라인을 가진다.
  • 한 캐시 라인의 구성은 데이터 블록 (B = 2^b 바이트) | 유효 비트 | 태그 비트 t = m - (b + s
  • 캐시 크기 공식에서, 전체 캐시 용량 C (바이트)는 다음과 같이 정의 된다 : C = S * E * B
  • 하나의 메모리 주소 Address는 다음 세 가지로 분할이 이루어진다 :
    • 예를 들어 m = 32, s = 6, b = 5이면
      • t = 32 - (6 + 5) = 21
      • 주소 구조는 | Tag (21) | Set Index (6) | Block Offset (5) |

• 주소를 기반으로 한 데이터 접근 과정
  • Set Index 계산
    • 주소의 중간 s 비트를 이용해 어떤 세트에 접근 할 지를 결정한다.
  • Tag 비교
    • 세트 내의 각 라인과 tag 값과 주소의 tag 비트를 비교한다.
    • 일치하면서 Valid Bit가 1인 경우 → Cache Hit!
  • Block Offset 사용
    • 해당 블록에서 정확한 바이트/워드를 읽는다.

기호	의미
m	전체 주소 비트 수
C	캐시의 총 데이터 용량 (bytes)
B	하나의 블록 크기 (bytes)
E	한 세트 내의 라인 개수
S	세트 수 (= 2^s)
t	태그 비트 수 (= m - s - b)
s	세트 인덱스 비트 수 (= log2(S))
b	블록 오프셋 비트 수 (= log2(B))

 

6.4.2 Direct-Mapped Caches

캐시 유형 분류 기준은 세트랑 라인 수인 E를 기준으로 한다.

E 값	캐시 유형	설명
E = 1	직접 사상 캐시 (Direct-Mapped Cache)	세트당 하나의 라인만 존재 → 구현이 간단하고 빠름
E > 1	집합 연관 캐시 (Set-Associative Cache)	세트당 여러 라인 허용 → 충돌 감소
E = 전체 라인 수	완전 연관 캐시 (Fully Associative Cache)	모든 블록이 모든 위치에 올 수 있음 (성능은 좋으나 구현 복잡)

 

• Direct-Mapped Cache : 작동 과정

• 직접 사상 캐시는 구현과 이해가 쉬워서 기본 개념 설명에 주로 사용된다.
  • 캐시 접근 시 동작 순서는 3단계로 나뉜다.
    • 세트 선택 | Set Selection
      • 주소의 중간 비트 s(Set Index)를 이용하여 캐시 세트를 결정한다.
      • set_index = A[s:s+b]
    • 라인 일치 검사 | Line Matching
      • 해당 세트에 저장된 유일한 라인의 유효 비트를 확인한다.
      • 그리고 저장돤 태그(tag)와 주소의 태그가 일치하는지 확인한다.
    • 워드 추출 | Word Extraction
      • b 비트 (Block offset)을 이용해 블록 내 해당 워드를 읽어 반환한다.

 

• 캐시 미스 처리

• 캐시 미스 발생 시
  1. 메인 메모리에서 해당 블록을 가져온다.
  2. 선택된 세트의 라인을 새로운 블록으로 교체한다.
  3. 필요한 워드만 CPU에 반환한다.

• 예시 요약

• CPU가 어떤 워드 w를 읽는 명령을 실행 할 때
  • L1 캐시에 w가 있다면 → Cache Hit
  • 없다면 → Cache Miss, 메인 메모리에서 블록 요청 후 저장 → w를 반환한다.

 

Direct-Mapped Cache : 접근 및 동작 과정 요약

• Set Selection | 세트 선택
  • 주소에서 s 비트(중간 비트)를 추출하여 세트 인덱스를 구한다.
  • 이 세트 인덱스는 캐시 세트 배열에 대한 인덱스 역할을 한다.
  • 예시로, 세트 인덱스가 0001(2진수) 이면 → 1번을 선택한다.

• Line Matching | 라인 일치 검사
  • 선택한 세트 i에 단 하나의 캐시 라인이 존재한다.
  • 유효 비트가 1로 설정되어 있어야하고, 주소의 Tag 값이 캐시 라인에 저장된 Tag 값과 일치해야 한다.
  • 둘 다 만족하는 경우에 Cache Hit, 둘 중 하나라도 실패하면 Cache Miss가 뜬다.
  • 직접 사상 캐시는 세트랑 1개 라인이기 때문에, 검사 속도가 빠르고 단순하다.

• Word Selection | 워드 추출
  • 히트 발생 시, 블록 안에서 원하는 워드를 찾아내야 한다.
  • Block Offest (b 비트)를 이용해 블록 내 바이트 배열에서 위치를 결정한다.
  • 예시로, Block Offest 100(2진수)는 블록의 4번째 바이트에서 워드가 시작된다.

• Line Replacement on Miss | 라인 교체
  • 캐시 미스 발생 시 :
    • 메인 메모리로부터 요청된 블록을 가져온다.
    • 선택된 세트의 유일한 캐시 라인을 새 블록으로 교체한다.
    • 교체 후, 다시 Word Selection 절차를 통해 필요한 워드를 CPU에 제공한다.
    • 교체 정책 : 직접 사상 캐시는 항상 기존 라인을 덮어쓰도록 한다.

• 작동 예시 : Direct-Mapped Cache
  • 주어진 캐시 구성
    • (S, E, B, m) = (4, 1, 2, 4)
      • S = 4 (세트 수는 4, 세트 인덱스는 2비트)
      • E = 1 (세트 당 라인 수는 1, Direct Mapped 이니까)
      • B = 2 (블록 당 바이트 수는 2, 블록 오프셋은 1비트)
      • m = 4 (주소 비트 수는 4비트)
    • 추가 가정
      • 메모리 워드는 1 바이트 크기이다.
      • 전체 메모리 주소 공간은 2^4, 16개의 주소이다.
  • 주소비트 분할 구조
    • 주소 A(4비트) = [Tag 1비트 | Set Index 2비트 | Block Offest 1비트]
  • 메모리 블록 구성 및 매핑 관게 

    주소	Tag	Set Index	Block Offset	포함된 블록	매핑되는 세트
    0	0	00	0	Block 0	Set 0
    1	0	00	1	Block 0	Set 0
    2	0	01	0	Block 1	Set 1
    3	0	01	1	Block 1	Set 1
    4	1	00	0	Block 2	Set 0
    5	1	00	1	Block 2	Set 0
    6	1	01	0	Block 3	Set 1
    7	1	01	1	Block 3	Set 1
    8	0	10	0	Block 4	Set 2
    9	0	10	1	Block 4	Set 2
    10	0	11	0	Block 5	Set 3
    11	0	11	1	Block 5	Set 3
    12	1	10	0	Block 6	Set 2
    13	1	10	1	Block 6	Set 2
    14	1	11	0	Block 7	Set 3
    15	1	11	1	Block 7	Set 3

  • 관찰 할 수 있는 특징
    • Tag + Set Index 조합이 메모리 블록을 고유 식별한다.
      • 예를 들어 주소 0 (Tag 1, Set 0)과 주소 4 (Tag 1, Set 0)은 서로 다른 블록이다.
      • 동일 세트에 매핑되는 블록들이 존재한다.
        • 예를 들어 블록 0과 블록 2 모두 Set 0으로 매핑된다.
        • 세트가 4개인데 블록은 8개? → 반드시 충돌이 발생한다.
      • Tag가 충돌을 구분하는 역할을 한다.
        • 같은 세트로 오는 블록들을 Tag 값을 보고 구분한다.
  
  
  • Address 0 읽기 시도
    • 주소 0 = 0000 → Tag 0, Set Index 0, Block offset 0.
    • 해당 세트는 Valid = 0 → Miss (Cold Miss)
    • Block 0 (주소 0, 1)을 세트 0에 로드 한다.

  Set Valid Tag block[0] block[1]
  0    1     0   m[0]     m[1]
  1    0
  2    0
  3    0

  
  
  • Address 1 읽기 기도
    • 주소 1 = 0001 → Tag 0, Set 0, Offset 1
    • Set 0 valid 1, Tag = 1 → Hit
    • m[1]을 반환한다.

  Set Valid Tag block[0] block[1]
  0    1     0   m[0]     m[1]
  1    0
  2    0
  3    0

  
  
  • Address 13 읽기 시도
    • 주소 13 = 1101 → Tag 1, Set 2, Offset 1
    • Set 2 valid = 0 → Miss (Cold Miss)
    • Block 6 (주소 12, 13)를 로드한다.

  Set Valid Tag block[0] block[1]
  0    1     0   m[0]     m[1]
  1    0
  2    1     1   m[12]    m[13]
  3    0
  

• Address 8 읽기 시도
  • 주소 8 = 1000 → Tag 1, Set 0, Offset 0
  • Set 0 Valid =1, Tag ≠ 1 (현재 Tag = 0) → Miss (conflict miss)
  • Block 4 (주소 8, 9) 로드, 기존 Block 0 제거

Set Valid Tag block[0] block[1]
0    1     1   m[8]     m[9]
1    0
2    1     1   m[12]    m[13]
3    0

• Address 0 읽기 시도
  • 주소 0 = 0000 → Tag 0, Set 0, Offset 0
  • Set 0 valid = 1, Tag ≠ 0 (현재 Tag = 1) → Miss (conflict miss)
  • Block 0 (주소 0, 1) 로드 → 이전에 불러온 Block 4는 제거된다.

Set Valid Tag block[0] block[1]
0    1     0   m[0]     m[1]
1    0
2    1     1   m[12]    m[13]
3    0

 

• Conflict Misses 예제
  • 실제 프로그램에서도 자주 일어나고 성능 저하에 대한 오류를 잦게 가지고 있다. 예시 코드와 함께 살펴 보자.

float dotprod(float x[8], float y[8]) {
    float sum = 0.0;
    int i;
    for (i = 0; i < 8; i++)
        sum += x[i] * y[i];
    return sum;
}

• 가정
  • float은 4바이트, x[0] - x[7] 은 주소 0 ~ 31까지, y[0] ~ y[7]은 주소 32 ~ 63까지.
  • Block size는 4개의 float를 담을 수 있는 16바이트, Cache는 2 sets (Set 0, Set 1)
  • Cache line 하나 당 하나의 Block (direct-mapped)
  • 주소의 Set Index 결정 : (주소 / block size) % number of sets = (주소 / 16) % 2

• 동작 시나리오
  • 루프가 x[i] → y[i] 순으로 접근한다. 첫 번째 루프 i = 0 기준을 보면,
    • Access x[0] : 주소 0 → Set 0
      • Set 0이 비어있으니 Miss이고, Block(x[0] - x[3])까지 적재한다.
    • Access y[0]: 주소 32 → Set 0
      • Set 0은 이미 사용 중이다. Tag도 달라서 → Conflict Miss 발생
      • Block(y[0] - y[3])으로 교체
    • Access x[1]: 주소 4 → Set 0
      • Set 0 (y block 있음), Tag 다름 → Conflict Miss 발생
      • 다시 Block(x[0] ~ x[3])을 적재한다.
    • 이런 식으로 매 접근 때마다 Conflict Miss가 발생한다.

• Direct-Mapped Cache는 특정 패턴의 데이터에 취약하다.
• 특히 배열 크기가 2의 거듭제곱이면, 서로 다른 배열이 같은 Set에 매핑 될 확률이 높아진다.

 

• 해결 방법 : Padding을 통한 주소 어긋나기를 고의적으로 발생시키기
  • 기존에는 x[0] ~ x[3]와 y[0] ~ y[3] 모두 Set 0에 매핑 되었었다.
  • 이로 인해 두 배열이 번갈아가며 동일 Set을 덮어쓰곤 했다. (Thrashing 발생)
  • 프로그램은 공간 지역성은 좋을지 몰라도 Set 충돌 때문에 캐시 성능이 저하되었다.

• 그래서 실제 코드에 어떻게 반영하면 해결을 도모 할 수 있냐하면.. 
• // Before: float x[8]; float y[8]; // y starts at address 32 // After: float x[12]; // padding: 4 floats = 16 bytes = 1 block float y[8]; // y starts at address 48 (instead of 32)

• 의도적으로 padding을 넣어 x와 y의 시작 주소를 어긋나게 한다.
• 그렇게 하면 x[i]와 y[i]가 다른 set에 매핑된다. → Conflict Miss를 제거하는데 기여한다.

 

수정된 주소는 이와 같이 매핑 된다 :

Element	Address	Set index	Element	Address	Set index
x[0]	0	0	y[0]	48	1
x[1]	4	0	y[1]	52	1
x[2]	8	0	y[2]	56	1
x[3]	12	0	y[3]	60	1
x[4]	16	1	y[4]	64	0
x[5]	20	1	y[5]	68	0
x[6]	24	1	y[6]	72	0
x[7]	28	1	y[7]	76	0

• 이제 x[i]와 y[i]는 짝수 i에서는 서로 다른 set, 홀수 i에서도 다른 set에 매핑이 이루어진다. → Thrashing이 더 발생하지 않는다.

 

6.4.3 Set Associative Caches

Set-Associative Cache라는 것이 존재한다. 이것이 등장한 계기부터 보자.

• Direct-Mapped Cache 에서는 각 set에 오직 하나의 line만 존재한다. (E = 1)
• 이로 인해 Conflict Miss 발생하고, 서로 다른 블록들이 같은 set에 매핑되며 교체가 반복되는 thrashing 이 일어났다.
• 해결책은 Set-Associative Cache가 제시 되었으며, 즉 각 set이 여러 line을 가지는 형태를 말한다. (E > 1)
•  구조
  • E 개의 line이 하나의 set에 포함된다.
  • 1 < E < C/B 인 경우를 E-way Set-Associative Cache 라고 한다.
  • 예를 들어, E = 2라면 2-way set-associative cache라고 부른다. 이 경우의 각 set에 line 은 2개이다.
  • 단, Tag, Set Index, Block Offset 분할 방식은 Direct-Mapped 와 동일하다.

• Set Selection : 동일하다.
  • 주소의 Set Index bits를 통해 어느 set인지 선택한다.
  • 이 과정은 Direct-Mapped Cache와 완전히 동일하다.

• Line Matching : 다르다. 

• 직접 비교해야 할 대상이 1개에서 E개로 늘어났다.
  • 각 set의 E개 line 모두에 대해 유효 비트가 1이고 tag가 일치하는지 비교해야 한다.
  • 이 과정을 Associative Search 라고 하는데, 연관 검색으로 번역하면 적합하다.
  • 이 구조는 Associative Memory 와도 유사하다.

구분	설명
일반 메모리	주소를 기반으로 값 검색
Associative Memory	키(tag)를 기반으로 값 검색
Cache의 Set	tag + valid로 검색, block 반환

• Hit 여부 판별
  • Hit : 한 줄 이라도 (valid == 1 && tag match) 인 line이 있다면 → 해당 block의 offset 위치에서 데이터를 반환한다.
  • Miss : 아무 line도 조건 만족하지 못하면 → Replacement 정책에 따라 한 line을 evict 후 새로운 block을 삽입한다.

• 교체 정책
  • Cache Miss 발생 시
    • CPU가 요청한 데이터가 해당 set의 어떤 line에도 존재하지 않으면 → miss
    • 이 경우, memory에서 block을 불러와야 한다.이후, 그 block을 해당 set의 한 line에 저장해야 한다.
  
  
  • 교체 대상 선정 기준
    • 빈 line이 있다면? valid bit = 0 → 바로 그곳에 삽입을 진행한다.
    • 모든 line이 유효하다면? → 기존의 한 line을 골라서 교체해야 한다. (eviction)
  
  
  • 대표적인 교체 정책 | Replacement Policies

    정책 이름	설명	장점	단점
    Random	무작위로 한 line 선택	구현이 매우 간단	locality 고려 안 함
    LFU (Least Frequently Used)	과거 사용 횟수가 가장 적은 line 교체	자주 사용된 데이터 보존	카운팅 하드웨어 필요
    LRU (Least Recently Used)	가장 오래 전에 사용된 line 교체	시간적 지역성에 적합	시간 추적 필요, 복잡

 

• 고급 정책의 필요성
  • CPU에서 가까운 Cache인 L1은 속도 우선시가 되어야하다보니 간단한 정책 위주로 사용한다.
  • CPU에서 상대적으로 먼 L2, L3는 miss penalty가 크다. 가능한 miss 나지 않기 위해 정교한 정책(LRU) 등을 사용한다.

 

6.4.4 Fully Associative Caches

이어서 완전 연관 캐시 (Fully Associative Caches)도 등장했다.

• Fully Associative Cache는 단 하나의 set만 존재한다.
  • 즉, E = C / B 캐시 전체에 포함된 block 수 = 한 set에 있는 block 수

• 모든 캐시 line이 하나의 set에 속한다.

• 이 도식을 같이 보자. 모든 라인이 단 한 개의 set에 존재하는 것을 확인 할 수 있다.

• Set Selection
  • 선택할 set이 한 개 뿐 → set 선택 과정 자체가 없다.
  • 주소에 set index 비트가 없다.
    • 주소는 [Tag | Block Offset] 밖에 없다. 별 의미가..

• Line Matching & Word Selection
  • 작동 방식은 set-associative cache와 동일하다.
    • 즉, set 내 모든 line에서 tag + valid bit를 검사하여 일치 여부를 확인한다.
    • 일치하면 block offset으로 데이터를 추출한다.
  • Fully Associative이므로, 모든 line이 비교 대상이 된다. 도식적으로는 아래 그림과 유사하다 :

• 구현 상의 어려움
  • 모든 line을 병렬로 비교해야 하니 하드웨어 비용이 매우 크다.
  • 앞의 이유로, 크고 빠른 Fully Associative Cache를 만들기는 어렵다.

• 실제 사용 사례
  • Fully Associative Cache는 보통 작은 용량의 캐시에 적합하다.
  • 대표적인 예시가 : 페이지 테이블 항목 캐싱에 메모리로써 사용되는 TLB | Translation Lookaside Buffer

 

6.4.5 Issues with Writes

• Cache Writes : 기본 동작과 전략
• 캐시에서의 읽기와 쓰기를 다룰 때
  • 읽기는 간단하다.
    • 원하는 데이터 Word 가 캐시에 있는지 검사한다. 이 검사의 결과는 Hit 여부로 나타낸다.
    • Hit라면 Word 를 반환하고, Miss라면 Word 를 포함한 block을 하위 메모리 계층에서 불러와 저장 후, Word 를 반환한다.
  • 쓰기는 복잡하다. → 특히, 쓰기 hit와 쓰기 miss 상황을 다르게 처리한다.
  • Write 시도에 Hit인경우
    • 캐시 블록의 Word 를 업데이트 한 이후, 하위 메모리 계층에 대해 다음 두 가지 전략 중 선택한다.

  전략	설명	장단점
  Write-Through	w를 즉시 다음 계층에 반영	간단하지만, 모든 쓰기마다 버스 트래픽 발생
  Write-Back	w를 즉시 반영하지 않고, 캐시 블록이 축출될 때 반영	버스 트래픽 절감 (공간/시간 지역성 활용), 그러나 추가 복잡성 필요(Dirty bit 관리 필요)

  • Write 시도에 Miss인경우

    전략	설명	특징
    Write-Allocate	블록을 하위 메모리 계층에서 로드하여 캐시에 저장, 이후 쓰기 반영	쓰기 지역성 활용 가능(하지만 miss마다 block 이동 발생)
    No-Write-Allocate	캐시를 건너뛰고, 하위 메모리 계층에 직접 쓰기	캐시 미이용 (특히 write-through와 같이 사용)

  • 일반적인 조합은
    • Write-through → No-write-allocate
    • Write-Back → Write-allocate

 

• 최적화 관점에서의 조언
  • 캐시 쓰기 최적화는 매우 미묘하고 복잡한 문제이다.
  • 시스템마다 상세 구현이 다르고, 때로는 공개되지 않거나 특허로 보호되고 있다.

프로그래머 관점에서는 다음을 전제로 개발하는 것이 현실적이다 :

• Write-back, Write-allocate 캐시를 가정하라.
• 왜냐? 하위 계층일수록 Write-back을 선호한다. 전송 비용이 크기 때문이다.
  • 그래도 약간의 희소식은, 기술 발전으로 Write-back 복잡성 부담이 감소하는 추세이다.

• Write-back, Write-allocate는 읽기 방식과 대칭적이다.
  • 공간/시간 지역성에 집중하여 프로그램을 설계 할 수 있다.

• 특정 캐시 정책을 맞추기보다 일반적 지역성 최적화가 유리하다.

 

6.4.6 Anatomy of a Real Cache Hierarchy

캐시는 꼭 데이터만 저장하는 것이 아니다.
기본적으로 캐시는 프로그램 데이터를 저장하는 용도로 알려져 있지만, 명령어 또한 저장 할 수 있다.

캐시 종류	설명
i-cache (instruction cache)	명령어만 저장
d-cache (data cache)	데이터만 저장
Unified cache (통합 캐시)	명령어 + 데이터 모두 저장

왜 그럼 i-cache, d-cache를 분리 할까?

• 현대 프로세서는 이 두 부분을 분리하는데, 그 이유는 여러 가지가 있다 :

이유	설명
동시 접근 가능	명령어와 데이터를 동시에 읽을 수 있음 (병렬 처리)
i-cache는 보통 읽기 전용	쓰기 불필요 → 구조가 단순해짐
서로 다른 최적화 가능	명령어와 데이터는 접근 패턴이 다르므로 block size, associativity, capacity 등을 다르게 설계 가능
충돌 회피	명령어 접근이 데이터 접근과 캐시 충돌(conflict miss)을 일으키지 않음

6.4.7 Performance Impact of Cache Parameters

Cache Performance Metrics and Design Trade-Offs | 캐시의 성능 측정의 지표

용어	설명
Miss rate	전체 메모리 참조 중 캐시 미스가 발생한 비율. 계산식: #misses / #references
Hit rate	전체 참조 중 캐시 히트가 발생한 비율. 계산식: 1 - miss rate
Hit time	캐시에서 데이터를 읽어오는 데 걸리는 시간. set 선택, line 탐색, word 선택 시간 포함. 보통 L1 캐시에서 수 클럭(cycles) 정도
Miss penalty	캐시 미스로 인해 추가적으로 발생하는 지연 시간. - L1 → L2: 약 10 cycles - L1 → L3: 약 50 cycles - L1 → main memory: 약 200 cycles

• Cache Size의 영향
  • 큰 캐시는 hit rate를 향상시키지만, 대용량 메모리는 빠르게 동작하지는 못한다.
  • 결과적으로, 캐시 크기가 커질 수록 hit time도 증가할 여지도 있다.
  • 이런 이유로 보통 L1 < L2 < L3 순서로 캐시 크기를 키운다.

 

• Block Size의 영향
  • 큰 블록은 공간 지역성을 활용해 hit rate를 높일 수 있다.
  • 그러나 같은 캐시 용량일 때, 블록 크기가 커지면 캐시 line 수가 줄어들어 시간 지역성이 높은 프로그램엔 불리하다.
  • 블록이 클수록 miss penalty도 커진다. → 전송 시간이 증가한다.
  • 현대 시스템은 타협적으로 64비트 블록을 사용한다.

 

• Associativity의 영향
  • Associativity (E값, 즉 각 set의 line 수)가 클 수록 Conflict miss 방지에 유리하다.
  • 하지만.. 더 많은 tag 비트, LRU 상태 저장비트, 복잡한 제어 회로가 필요하다.
    • 결과적으로 hit time, miss penalty 모두 증가 할 수 있다.
  • 일반적으로..
    • L1 캐시는 hit time을 더 중요시 여기니 낮은 associativity를 가진다.
    • L3 캐시는 miss penalty가 크므로 높은 associativity를 가진다.
  • 위 그림에서 L3 unified cache의 Assoc. 값은 16이 있는게 그 예제.

• 쓰기 전략에 대한 영향

전략	장점	단점
Write-through	구현이 간단. 쓰기 버퍼와 병렬 동작 가능. read miss 시 추가 write 없음.	모든 write마다 memory 접근 → bus traffic 증가
Write-back	memory 접근 감소 → I/O 대역폭 확보. 전송 횟수 줄여 성능 향상.	dirty bit 관리, 복잡도 증가 필요

• 하위 계층일수록 transfer timed이 크기 때문에, write-back 방식을 선호한다.

 

6.5 Writing Cache-Friendly Code

여기서는 지역성의 개념을 정교화하고 캐시 친화적 프로그래밍 작성에 대해 다룬다.

• 좋은 지역성은 낮은 Miss Rate가 된다.
• 낮은 Miss Rate는 빠른 실행 속도를 가능하게 한다.
• 따라서, 캐시 친화적인 cache-friendly 코드 작성이 중요하다.
• 캐시 친화적 코드 작성 전략
  • Make the common case go fast
    • 대부분의 실행 시간은 핵심 함수, 특히 그 안의 루프에서 소비된다.
    • 즉, 핵심 루프에 집중하고 나머지는 무시해도 된다.
  • Minimize cache misses in inner loops
    • load와 store 횟수가 같다면, miss rate가 낮은 루프가 더 빠르다.
    • miss가 최소화 되면 성능이 향상된다.

 

• 캐시 친화적인 코드를 하나씩 보자.
  • 1차원 배열을 탐색하는 sumvec() 함수

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

  • 이것은 왜 캐시 친화적일까?
    • Temporal Locality : i, sum은 지역 변수로 레지스터에 캐시됨으로써 실현되었다.
    • Spatial Locality : v[i]는 stride-1 접근 → 한 블록 불러오면 다음 3개까지 적중 가능하는 것에서 실현되었다.
  • 접근 패턴

  v[0] [miss], v[1]~v[3] [hit]
  v[4] [miss], v[5]~v[7] [hit]
  → 4번에 1번 miss, 나머지 hit

  • 2차원 배열에 행 순회를 먼저 하는 sumarrayrows() 함수

  int sumarrayrows(int a[M][N]) {
      int i, j, sum = 0;
      for (i = 0; i < M; i++)
          for (j = 0; j < N; j++)
              sum += a[i][j];
      return sum;
  }

  • 이것은 왜 캐시 친화적일까?
    • C언어는 row-major order → a[i][j]는 strider-1 식 접근.
    • 각 row는 연속된 메모리에 존재한다. Spatial Locality가 최적화 될 수 있다.
  • [얘는 안좋은 케이스임] 2차원 배열에 열 순회를 먼저하는 sumarraycols() 함수

  int sumarraycols(int a[M][N]) {
      int i, j, sum = 0;
      for (j = 0; j < N; j++)
          for (i = 0; i < M; i++)
              sum += a[i][j];
      return sum;
  }

  • 이것은 왜 캐시 비친화적일까?
    • a[i][j]는 stride-N 접근이다. N은 열 수
    • 즉, 행 단위가 아닌 열 단위 접근이다. → 각 접근이 다른 블록을 참조한다.
    • 캐시에 데이터가 없으니 모든 접근이 miss가 일어난다.
    • 실제로 같은 데이터임에도 sumarrayrows()가 25배 더 빨랐다.

 

6.6 실습하기 : The Impact of Caches on Program Perfomance

6.6.1 The Memory Mountain

이번에는 Memory Mountain 개념을 중심으로 캐시의 성능이 프로그램의 지역성에 따라 어떻게 달라지는지를 보자.
실제 테스트를 진행 할 코드는 이렇다.

long data[MAXELEMS];

int test(int elems, int stride) {
    long i, sx2 = stride*2, sx3 = stride*3, sx4 = stride*4;
    long acc0 = 0, acc1 = 0, acc2 = 0, acc3 = 0;
    long length = elems;
    long limit = length - sx4;

    for (i = 0; i < limit; i += sx4) {
        acc0 += data[i];
        acc1 += data[i+stride];
        acc2 += data[i+sx2];
        acc3 += data[i+sx3];
    }

    for (; i < length; i++) {
        acc0 += data[i];
    }
    
    return ((acc0 + acc1) + (acc2 + acc3));
}

double run(int size, int stride, double Mhz) {
    double cycles;
    int elems = size / sizeof(double);
    
    test(elems, stride);
    cycles = fcyc2(test, elems, stride, 0);
    
    return (size / stride) / (cycles / Mhz);
}

그리고 우린 이렇게 생긴 산을 보게 된다.

• Read Throughput | 읽기 처리량
  • 프로그램이 일정 시간 동안 메모리로부터 읽어 들인 데이터 양을 말한다. (n/s, 단위는 MB/s)이다.
  • 특정 메모리 접근 패턴의 성능 특성을 정량적으로 평가하는 지표이다.

• Test 및 Run 함수의 역할
  • test : 지정된 stride 간격으로 배열 요소를 순차 접근하며 읽는 코드이다. 언롤링 기법을 활용해 병렬성을 높인다.
  • run : test 를 감싸고 성능 측정을 담당한다. CPU cycle을 기준으로 처리량을 계산한다.

• Memory Mountain 개념
  • X축은 Working set의 크기, Temporal Locality와 관련이 있다.
  • Y축은 Stride 크기, Spatial Locality와 관련이 있다.
  • Z축은 Read throughput. 처리량

• 각 시스템은 고유한 Memory Mountain을 가지며, 이 산의 형태는 캐시 구조 및 계층 별 성능 차이를 반영한다.

 

• Temporal Locality | 시간 지역성
  • 작은 Working set size로 부여하면, 자주 쓰는 데이터가 작은 공간에 몰려 있으므로 캐시 재사용률이 높다. → L1, L2 캐시에 처리가 가능하다.
  • L1/L2/L3 캐시에 맞는 크기에서 throughput이 급등한다 → 이 그림을 참고하라

 

• Spatial Locality | 공간 지역성
  • 작은 stride로의 연속된 데이터 접근 → 한 캐시 블록에서 여러 요소를 처리 할 수 있게한다.
  • stride 증가 시 throughput이 급락한다 → 이 그림을 참고하라

• Prefetching 효과
  • stride-1 일때는 L1/L2 용량을 넘더라도 throughput이 일정하게 높게 유지되는 경향이 있다 → 하드웨어 프리패처가 연속 접근을 감지하여 사전 로딩을 수행한다.

• 그 외의 관찰된 기록
  • L2, L3 경계에서 throughput이 오히려 일시적으로 낮아지는 dip 현상이 발생했다.
    • 아마 다른 코드/데이터 라인과의 충돌 가능성이 있다.
    • 정확한 분석은 캐시 시뮬레이션이 필요하다 → Figure 6.42의 캐시 경계 근처를 참고하기

 

6.6.2 Rearranging Loops to Increase Spatial Locality

행렬 곱셈같은걸 보면 같은 루프를 참 많이도 반복한다. 근데 루프 구조를 어떻게 하냐에 따라 성능차가 많이 날 수 있다는 것을 우리는 알고 있다. 핵심은 루프 순서에 따라 메모리 접근 패턴이 달라지고, 그로 인해 캐시 미스 및 처리 성능에 큰 영향을 준다는 점이다.

• 문제 가정
  • 두 개의 n * n 행렬 A, B를 곱해 C = AB를 계산한다.
  • 각 C[i][j]는 A의 i번째 행과 B의 j번째 열의 내적이다.
  • O(n^3)의 연산량, 동일한 덧셈/곱셈 횟수.

루프 순서를 보고 6가지의 바리에이션으로 만들 수 있다 :

• 세 개의 중첩 루프 인덱스, i, j, k
•  그러면
  • [i j k], [j i k] | → 클래스 AB
  • [j k j], [k i j] | → 클래스 BC
  • [j k i], [k j i] | → 클래스 AC

• 모두 기능적으로 동일하지만, 메모리 접근 방식이 다르다.
• 루프 내 메모리 접근 패턴 분석을 보자.

• 분석 조건
  • 각 행렬은 double 형의 n * n 배열. 즉 1 아이템은 8 바이트이다.
  • 캐시 블록 크기는 32 바이트로 4개의 double을 넣을 수 있다.
  • n이 커서 한 행이 L1 캐시에 들어갈 수 없다.
  • 지역 변수는 레지스터에 저장된다.

• 루프 클래스별 특징

클래스	루프 순서	inner loop 접근	miss 수 (iteration당)	비고
AB	ijk, jik	A: stride-1B: stride-n	A: 0.25, B: 1.0 → 총 1.25	B column scan으로 locality 낮음
AC	jki, kji	A, C 모두 stride-n	A, C: 1.0씩 → 총 2.0	최악의 spatial locality
BC	ikj, kij	B, C 모두 stride-1	B: 0.25, C: 0.25 → 총 0.5	가장 우수한 locality

 

• 성능 비교 실험 | 낮은게 좋음
  • 기준은 루프 당 CPU 사이클 수 vs n (배열 크기)
  • 결과 요약
    • 최고 성능 버전이 최저 성능보다 40배나 빠르다.
    • 동일한 miss 수를 가지는 버전끼리는 거의 같은 성능을 보인다.
    • miss 수가 성능을 결정짓는 주된 요인이다.
      • 접근 수가 많더라도 miss 수가 적으면 성능이 더 좋게 나왔다. (BC > AB)
    • BC 클래스(ikj, kij)가 가장 우수한 결과로 나왔다.
      • stride-1 접근, 효과적인 prefetching 덕분에 크기 변화와 무관하게 일정한 기록이 나왔다.

 

이 실제 실험을 볼 때 와닿아야 할 내용은 :

• 동일한 연산을 수행하는 코드라도 루프 순서에 따라 성능 차이가 많이 난다.
• 캐시 미스 수가 중요한 성능 예측 지표이다.
• Stride-1 접근을 활용하면, 하드웨어 프리패처가 효과적으로 작동하고, 고정된 높은 성능을 사용 할 수 있다.

• 고성능 코드를 위해서는 메모리 접근 패턴을 캐시 친화적으로 설계해야 한다!

 

6.6.3 Exploiting Locality in Your Programs

핵심 개념 요약

• 메모리 계층 구조
  • 상위 : 작고 빠른 저장장치 (레지스터, 캐시)
  • 하위 : 크고 느린 저장장치 (DRAM, 디스크)
  • 이 구조로 인해 메모리 접근 속도는 단일한 숫자가 아닌 가변적 성능 곡선으로 표현된다.

• Memory Mountain
  • 메모리 접근 시간은 프로그램의 지역성에 따라 큰 차이를 보인다.
  • 좋은 지역성은 : 대부분의 데이터를 빠른 캐시에서 읽으며 빠르다.
  • 나쁜 지역성은 : 대부분의 데이터를 느린 메모리에서 읽어 느리다.

 

성능 최적화를 위한 실용적 가이드

• 내부 루프에 집중하라.
  • 대부분의 계산과 메모리 접근은 내부 루프에서 발생한다.
  • 성능 병목이 생기기 쉬운 구간이니, 여기를 최적화해야 제일 효과적이다.

• 공간적 지역성을 극대화한다.
  • 데이터를 메모리에 저장된 순서대로, stride-1로 접근.
  • 배열을 A[0], A[1] .. 식으로 연속적으로 읽기.
  • 캐시 블록이 여러 데이터를 포함하므로, 순차 접근 시 캐시 효율이 높아진다.

• 시간적 지역성을 극대화한다.
  • 한 번 메모리에서 읽어온 데이터를 반복해서 사용한다.
  • 읽어온 값을 루프 내에서 여러 번 쓰거나, 반복 연산에 활용한다.
  • 이미 캐시에 올라온 데이터를 재활용함으로써 느린 DRAM 접근을 줄인다.