▼ Why ?
알고리즘 문제를 풀다가 ' Arrays.sort() ' 와 ' Collection.sort() ' 의 차이에 대해 찾아보게 되었고, 그 과정에서 배열(Arrays)가 "참조의 지역성"이라는 것이 적용된다는 사실에 대해 알게 되어 추가적으로 정리를 했었다. 그래도, 이 참조 지역성과 캐시(cache) 메모리라는 것에 대해선 따로 정리해두는 것이 좋을 것 같아 좀 더 공부하고 정리해보려고 한다.
▼ 캐시 메모리 (Cache Memory)
Cache Memory ?
- 속도가 빠른 장치(CPU)와 느린 장치(RAM) 간의 속도차에 따른 병목 현상을 줄이기 위한 범용성 메모리이다.
➜ CPU(주기억장치)와 RAM(메인 메모리) 사이에 위치한다.
➜ CPU에 버금갈 정도의 속도를 갖고 있다.
- 캐시 메모리는 메인 메모리에서 자주 사용하는 프로그램과 데이터를 저장해두어 속도를 빠르게 한다.
➜ 이때, CPU가 어떤 데이터를 원하는지 어느 정도 예측을 해야 하는데, 캐시 메모리에 CPU가 이후에 참조할 정보가 어느 정도 들어있는지에 따라서 캐시 메모리의 성능이 결정된다.
➜ 이를 위해 캐시의 지역성(Locality), 즉 참조의 지역성(Locality of Reference)을 이용하는 것이다 !
▼ 참조의 지역성 (Locality of Reference)
참조의 지역성 ?
- 데이터에 대한 접근이 시간적 혹은 공간적으로 가깝게 발생하는 것.
➜ 즉, 캐시의 적중률(Hit-rate)을 극대화하여 캐시가 효율적으로 동작하기 위해 사용되는 성질이다 ! - 지역성의 전제조건 ➜ 프로그램은 모든 코드나 데이터를 균등하게 접근하지 않는다.
- 참조의 지역성은 크게 두 가지로 나눌 수 있다.
- 공간 지역성 (Spatial Locality)
: 최근에 사용했던 데이터와 인접한 데이터가 참조될 가능성이 높은 특성.
➜ 대표적인 예가 순차적으로 접근하는 자료구조를 가진 배열(Arrays)인 것이다. - 시간 지역성 (Temporal Locality)
: 최근에 사용했던 데이터가 재참조될 가능성이 높은 특성.
➜ 대표적인 예가 특정 구간을 반복해서 접근하는 for문, while문과 같은 반복문이다.
- 공간 지역성 (Spatial Locality)
▼ 캐싱 라인 (Caching Line)
Caching Line ?
- 캐시 메모리는 메인 메모리에 비해 크기가 매우 작아 1:1 매칭이 불가능하여, CPU에서 원하는 데이터가 캐시 내의 어느 곳에 저장되어 있는지 쉽게 찾을 수 있는 구조가 필요하다.
➜ 이때 필요한 것이 캐싱 라인 (Caching Line) ! - 캐싱 라인
: 캐시에 특정 자료구조를 사용하여 저장한 묶음. - 캐싱 라인을 매핑하는 방법은 3가지 정도 있다.
- Direct Mapping
: 메인 메모리를 일정한 크기의 블록으로 나누어 각각의 블록을 캐시의 정해진 위치에 매핑하는 방식.
➜ 가장 간단하고 쉬운 만큼 적중률이 낮아질 수 있다.
➜ 동일한 캐시 메모리에 할당된 여러 데이터를 사용할 때 충돌이 발생할 수 있다. - Full Associative Mapping
: 캐시 메모리의 빈 공간에 마음대로 주소를 저장하는 방식.
➜ 그만큼 저장하는 것은 간단하다.
➜ 원하는 데이터를 찾을 때는 모든 태그를 병렬적으로 검사해야 해서 복잡하고 비용이 높다. - Set Associate Mapping (주로 사용)
: Direct + Full Associative
➜ 빈 공간에 마음대로 주소를 저장하되, 미리 정해둔 특정 행에만 저장하는 방식.
➜ 검색 속도 : Full Associative < Set Associate < Direct
➜ 저장 속도 : Direct < Set Associate < Full Associative
- Direct Mapping
▼ 캐시 미스 (Cache Miss)
Cache Miss ?
- CPU가 참조하려는 데이터가 캐시 메모리에 없을 때 발생한다.
- Cache Miss의 종류
- Compulsory Miss
: 특정 데이터에 처음 접근할 때 발생한다. - Capacity Miss
: 말 그대로, 캐시 메모리 공간(capacity)가 부족해서 발생한다. - Conflict Miss
: 캐시 메모리에서 데이터 A와 B를 저장해야 하는데, A와 B가 모두 같은 캐시 메모리 주소에 할당되어 있어서 발생한다.
( Direct Mapped Cache에서 많이 발생한다. )
- Compulsory Miss
