메모리 계층 구조
컴퓨터 시스템에서 저장 장치는 가격, 용량, 속도 측면에서 다양한 특성을 가진 여러 계층으로 구성되어 있다.
CPU가 느린 저장 장치와 직접적으로 자주 통신하게 된다면 성능이 크게 저하되기 때문에 메모리를 계층적으로 나누어 속도와 비용의 균형을 맞춘다.
| 계층 | 저장장치 | 특징 |
|---|---|---|
| L0 | Registers (레지스터) | 가장 빠르며 CPU 내부에 위치 |
| L1 | L1 Cache (SRAM) | 매우 빠르나 용량이 작고 비용이 높음 |
| L2 | L2 Cache (SRAM) | L1보다 느리지만 용량이 크고 여전히 빠름 |
| L3 | L3 Cache (SRAM) | 멀티코어 공유 캐시, 대용량 중속도 |
| L4 | Main Memory (DRAM) | 일반적인 RAM, 용량 큼, 상대적으로 느림 |
| L5 | Local Secondary Storage (e.g., SSD/HDD) | 비휘발성 저장장치, 대용량, 느림 |
| L6 | Remote Secondary Storage (e.g., Web servers, Cloud storage) | 네트워크 기반, 매우 느림, 매우 큼 |
속도: L0 > L1 > ... > L5 > L6
용량: L0 < L1 < ... < L5 < L6
비용: L0 > L1 > ... > L5 > L6
캐시 - Cache
캐시는 CPU가 더 느린 저장장치에 접근하지 않고도 최근 사용했거나 앞으로 사용할 가능성이 높은 데이터를 임시로 저장하는 작고 빠른 SRAM-based 메모리이다.
구성요소
- Cache Block
메인 메모리에서 가져온 연속적인 데이터 조각 - cache line
하나의 캐시 entry 블록 + 메타데이터(tag, valid bit 등) - cache set
캐시 인덱싱을 통해 접근되는 line들의 집합
캐시 구조
cache +---------------------------------------+ | | line | line | ... | line | | <- set0 | | line | line | ... | line | | <- set1 | | line | line | ... | line | | . | | line | line | ... | line | | . | ... | . | | line | line | ... | line | | . +---------------------------------------+ line +---------------------------------+ | |v| |tag| | Block (Data bytes)| | +---------------------------------+ v(valid bit) : 해당 line이 유효한 데이터를 지녔는지 나타냄 tag(tag bit) : 메모리 주소의 일부. 메모리 블록 식별용 Block : 실제 저장된 데이터
CPU가 메인 메모리 또는 그 이하 저장장치에 직접 접근하는 것은 너무 느리기 때문에 캐시에 미리 그 값을 올려놓는 과정이 필요하다.
캐시의 동작을 일반화하면 다음과 같다.
+----------------+
| 4 | 9 | 10 | 3 | ← 캐시 (Cache)
+----------------+
↑
(블록 단위로 복제된 데이터)
+----------------+
| . | . | .. | . |
| . | . | .. | . |
| . | . | .. | . | ← 메인 메모리
| . | . | 10 | . |
| . | . | .. | . |
+----------------+CPU가 찾는 블록이 캐시에 있는 경우를 Cache Hit이라고 하고 없는 경우를 Cache Miss라고 한다.
만약 Miss가 발생했다면 캐시는 placement policy에 따라 데이터가 캐시의 어디에 배치될 지 결정하고, replacement policy에 따라 캐시 내부의 어떤 블록을 제거할지 결정한다.
Miss에는 세 종류가 있다.
-
Cold(compulsory) miss
캐시가 비어있거나 처음 접근하는 블록일 때 발생하는 miss. -
Capacity miss
캐시 전체 용량이 부족해서 발생하는 miss. -
Conflict miss
캐시 공간은 충분하나 특정 블록이 같은 캐시 인덱스에 매핑되어 서로 충돌할 때 발생하는 miss.
캐시에서 데이터 읽기 절차
- Set 선택 : 주소의 인덱스 부분을 이용해 접근할 set 결정
- Tag 비교 : 해당 set 내의 모든 line에서 tag 비교
- 유효성 확인 : tag가 일치하고 valid bit가 1이면
Hit- 데이터 추출 : block offset을 사용해 필요한 데이터에 접근
읽기 예시
1. Direct-Mapped Cache
하나의 set에 하나의 line이 위치하는 방식.
데이터 주소가 다음과 같을 때
+-----------------------+
| t bits | 0...01 | 100 |
+-----------------------+
└ tag └ address └ offset이 주소를 기준으로 캐시 line과의 비교는 이렇게 이루어진다.
+-----------------------------+
| |v| |tag| |0|1|2|3|4|5|6|7| |
+-----------------------------+
| | |
1 + matched 데이터 위치(offset 4)
만약 tag가 맞지 않다면 현재 line을 버리고 새로 로드한다.
Directed Mapping 방식은 각 블록이 캐시의 한 위치에만 저장되기 때문에 여러 메모리 블록이 동일한 캐시 위치로 매핑된다면 캐시 블록 교체가 자주 일어나 miss 발생이 증가한다.
2. E-way Set Associative Cache
하나의 set에 E개의 line이 위치한다.
예를 들어 2-way Set Associative Cache는 하나의 set에 2개의 line이 위치하는 것이다.
접근 방법은 set에 있는 모든 line에 대해 Direct-Mapped Cache 때와 동일하게 검사를 한 후 miss가 날 경우 line들 중 하나를 제거하고 새로 로드한다.
쓰기(Write)는?
캐시에 올라온 데이터들은 복사본이 상당히 많다. 그렇다면 쓰고 나서 저장할 때 어떻게 해야할까?
Write-Hit
-
Write-through 방식
쓸 때 캐시와 메인 메모리에 매번 함께 업데이트를 한다. -
Write-back 방식
캐시에만 업데이트하다가 해당 line이 교체되어 캐시에서 내려갈 때 메인메모리에 업데이트 한다.
이 방식의 경우 dirty bit가 필요하다.+---------------------------------+ | |v| |d| |tag| |0|1|2|3|4|5|6|7| | +---------------------------------+ └ memory와 다른지 판별
Write-Miss
- Write-allocate 방식
캐시에 로드하고, 캐시의 line을 업데이트한다. - No-write-allocate 방식
캐시에 로드하지 않고 메모리에 직접 쓴다.
일반적인 조합
- Write-through + No-write-allocate
단순하고 구현 쉬움, 일관성 유지 쉬움, 느림 - Write-back + Write-allocate
일반적으로 성능이 좋고 캐시 효율 높음 (가장 많이 사용됨)
캐시 성능 측정
Miss Rate
Miss 발생률 (1 - hit rate)
보통 L1에서 3~10% 정도
Hit Time
Hit 발생 시 line에서 프로세서로 데이터가 전달되는데 걸리는 시간 (캐시에서 데이터 찾는 시간까지 포함)
보통 L1에서 4 clock-cycles
Miss Penalty
Miss 발생 시 요구되는 추가 시간
보통 메인 메모리에 접근하는데 50~200 cycles
점점 증가하는 추세임
캐시 친화적인 코드 작성
-
자주 발생하는 경우를 빠르게 처리하도록 작성
핵심 함수의 루프(특히 inner loop)에 집중 -
내부 루프에서 miss를 최소화 하여 작성
Temporal Locality와 Spatial Locality 고려
<참고자료>
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
안성용, "시스템소프트웨어", 부산대학교
