[Computer Architecture] Classifying Caches

우리가 알고있는 Cache의 구조는 다음과 같다.

다들 알겠지만 프로세서와 Memory사이의 데이터는 항상 Cache를 거치게 되어 있다. 물론 이건 Architecture에 따라 다른 내용이긴 하다. 내가 연구실에서 다루고 있는 Single-chip Cloud Computer 에 포함되어 있는 Processor는 프로세서와 Memory사이의 데이터 이동시 Cache를 거치지 않는 경우도 있다. 하여간 프로세서가 Memory에서 주소를 넘겨주면 Main memory는 그 주소에 있는 데이터를 반환해준다. 여기서 Cache는 그 데이터가 지나가서 저장되는 역할을 한다. 비유를 하자면 데이터를 먹물이라고 비유할 때 Cache에 묻으면 그 색이 남는다. 물론 시간이 지나면 그 색이 희미해지는 식으로 이해하면 좋겠다. 

 그런데 단순히 Cache가 그냥 아무 의미없이 데이터의 임시저장공간이라고 생각하면 Cache의 의미가 없어지는 것이다. 당연히 Processor 입장에서는 자기가 자주쓰는 Data를 Cache에 넣어놓고 빼서 쓰는게 Performance 측면에서 좋을 것이다. 소위 말하면 데이터를 쓰는데도 Policy가 있다는 것이다. 자 그럼 일단 Cache와 Process간의 데이터 과정을 잠깐 보자.

다른 포스트에서 언급한 적이 있는데 기본적으로 Cache는 각 영역마다 address Tag라는 것이 붙어 있다. 그래서 만약 Processor가 cache로부터 데이터를 불러오도록 요구했을때는 이 Tag를 이용해서 원하는 데이터가 있는지를 확인하는 과정을 거친다. 당연히 있으면 땡큐인거고 문제는 없을때 발생한다.  그러면 Cache는 Processor한테 데이터가 없다고 알려주는 게 아니라 Main Memory까지 넘어가서 그 주소에 있는 데이터를 가져온다. 물론 이 Main Memory에도 없으면 그 요청한 데이터는 유효하지 않으므로 보통 Segmentation Fault같은 오류를 호출한다. 그런데 사실 이런 Cache miss는 I/O입장에서는 overhead로 작용하게 된다. 당연히 매번 이 영역을 접근하게 되면 항상 Cache에서 Main memory로 요청할 것이기 때문이다. 이 때문에 한번 Miss가 발생한 부분은 비워주는 작업을 거치게 된다. 이 작업을 흔히 Cache Invalidate라고 한다.  말그대로 Cache에 들어있는 내용을 무효화 시킨다는 것이다. 이와 비슷한 개념으로 Cache Flush라는게 있는데 단어뜻에 들어있는 것처럼 비워준다는 것이다. 그러면 어떤 사람은 invalidate와 flush의 차이가 뭐냐고 물어볼 수 있다. 이때의 대답은 데이터 유효성이다. invalidate는 말 그대로 안에 있는 data를 invalidate시킨다는 의미이고, flush는 안에 있는 data는 invalidate 시키고 그 data를 processor에 전달하는 것이다. 그러니 결국 데이터는 계속 살아서 전달이 된다는 것이다. 아무튼 그런 차이가 있다. 

 그래서 앞에서 말한것처럼 policy를 어떤 걸로 가지고 있느냐에 따라서 Cache를 다르게 구별할 수 있다. 그런데 이 분류에도 여러가지 가닥이 있다. 첫번째로는 Data가 들어왔을때 Cache에 어떤식으로 배치할 것인가에 따라서 구별할 수 있겠다. 아마 이부분은 이전 포스트에서 Direct mapped Cache와 Set Associative Cache라는 이름으로 다뤘었던 것 같다. 둘의 차이는 한 cache line에 데이터를 얼마나 가지고 있느냐는 것이다. 궁금한 사람은 그글을 참고해보면 좋을 것 같다.

2013/03/22 - [About School/About Architecture] - [Study] Memory Hierarchy (1)

2013/03/22 - [About School/About Architecture] - [Study] Memory Hierarchy (2) - Direct Mapped Cache

2013/03/22 - [About School/About Architecture] - [Study] Memory Hierarchy (3) - Cache Write Policy

2013/03/23 - [About School/About Architecture] - [Study] Memory Hierarchy (4) - Sequence of Cache Write

 또다른 분류방법으로는 Cache에 쓸모없는 데이터를 비우려고 할때 어떤 방법으로 비울지에 대한 정책이다. 다르게는 Replacement policy라고 표현할 수 있겠다. 가장 쉽게 생각해볼 수 있는 방법은 Cache의 장점을 잘 살려서 가장 많이 쓰는 데이터만 가지고 있게끔 하는 것이다. 이 방법을 LRU(Least Recently Use) 방식이라고 하는데 이 경우는 당연히 매번 Cache내에 들어있는 state를 확인해야 한다는 점이 있다. 물론 LRU라고 막연하게 적게 쓰는 데이터를 없애는 것이 아닌 Segmented LRU라던가 Pseudo LRU 같은 조금더 개선된 방식의 정책도 존재한다. 

 그러면 당연히 덜쓴 걸 없애는게 아닌 자주쓰는 걸 없애는 방식은 LFU(Least Frequently used) 방식도 있을 법하다. 물론 생각해보면 말이 안되긴 한데 자료를 찾다보면 LRU와 결합해서 policy를 만든 논문들이 몇가지 있는 듯 하다. 이 밖에도 먼저 들어온 것을 없애는 FIFO 방식도 존재하고, 이 FIFO와 LRU를 결합한 NMRU(Not Most Recently Used) 방식도 있다. 그런데 찾다보면 Policy 방식중에 Random Replacement Policy 방식이라는게 있다. 진짜 말그대로 랜덤하게 cache에 있는 데이터를 날리는 방식인데, 생각해보면 Cache의 특성을 무시한 policy라고 볼 수 있는데 사실 실험적인 결과를 가지고 보면 이런 random replacement 방식도 LRU와 비슷한 결과를 나타낸다고 한다. 짐작이 되는 것은 어차피 Cache 자체가 Main Memory에 비해서는 Size가 무척 작기 때문에 오히려 이런 대체방식도 효과적이라고 볼수 있을 듯 하다. 아무튼 이 방식은 ARM Processor에서 적용되는 방식이라고 한다.

 다른 분류방법으로 들 수 있는 것이 바로 Cache에 어떻게 쓸거냐 하는 것이다.(write Policy)

앞에서 잠깐 소개했던 것처럼 Cache에 Data를 쓰는 조건은 딱 두가지가 Cache에 원하는 Data가 있을 경우와 없어서 해당 영역을 invalidate시킬때의 경우다, 흔히 Cache Hit가 났을때는 두가지 방법으로 나눠서 Cache에 Data를 쓸 수 있다. 첫번째는 Cache가 hit됬을때 Cache에도 데이터를 쓰고 Main Memory 상에도 쓰게끔 하는 방식인 Write Through 방식이다. 당연히 Cache에 있는 것을 Main Memory에도 쓰기 때문에 앞에서 나온 그림을 따라가자면 Cache와 Main Memory 사이의 통로도 Write하는데 쓰이는 것이다. 그러면 지난 포스트에서도 언급했던 Bottleneck 현상도 발생할 수 있겠다. 하지만 그냥 단순히 Processor는 그냥 Write한다는 신호만 전달하면 되기 때문에 설계하기가 간단하다는 이점이 있다. 이와는 다르게 Cache에만 쓰게 하고, 특정 조건에 의해서 Data가 나왔을 때만 Main Memory에 써지는 Write Back 방식도 있다. processor가 Main memory로부터 읽어오는 Data중에는 당연히 자주 쓰는 데이터이기 때문에 확실한 것도 있지만 계속 Write와 replacement가 일어나면서 Data 자체가 지저분해지는 경우가 발생할 수 있다. 그런데 앞에서 언급한 Write Through 방식을 쓰게 되면 이 지저분한 데이터 역시 Main Memory에 써지기 때문에 역시 낭비라고 할 수 있겠다. WriteBack 방식을 쓰면 이런걸 막을 수 있다. 물론 이로 인해서 구조가 복잡해지는 단점도 있다.

  앞에서 Cache Hit에 따른 분류를 했으니까 이제는 Miss가 발생했을때 Cache와 Memory에 어떻게 쓰겠냐에 따른 분류를 해봐야 한다. 언급한 바와 같이 Miss가 발생했을 경우는 만약 현재 작업하는 instruction이 store라면 Memory에 써야 한다. 그런데 Hit 때와 마찬가지로 역시 Data 중에 올바른 데이터도 있을 수 있고, 혹은 지저분한 데이터도 있을 수 있다. 이 경우는 꼭 Memory에 데이터를 쓸 필요가 없게 된다. 그래서 중간에 block을 하나 두고 거르는 작업을 거치게 된다. 이 block이 있냐 없냐에 따라서 Write Policy가 다르게 되는데 보통 block이 있는 경우를 Write Allocate라고 하고, 반대의 경우를 No Write Allocate 라고 한다. 

 당연히 Cache Hit과 Miss는 항상 Cache 내부에서 발생하는 현상이므로 위에서 언급한 policy는 하나로 묶여서 처리된다. 그래서 가장 흔한 조합이 

- Write Through + No Write Allocate

- Write Back + Write Allocate

의 조합이다. 왜 이렇게 묶이게 되었는지는 앞에서 한 설명과 연관지어보면 쉽게 이해할 수 있을 듯 하다. 차이는 단지 중간에 뭔가가 막냐, 아니면 그냥 Write만 하게 놔두냐는 것이다.

자 제목에서 언급한 것처럼 Cache를 구분하는데 있어서 몇가지 방법들이 있으며 대충 요약해보면 다음과 같이 구별할 있다.

- Cache Placement

- Direct mapped Cache

- Set Associative Cache

- Full Associative Cache

- Cache Identification Policy

- Direct mapped Cache

- 2 way set associative cache

- 4 way set associative cache

....

- Cache Replacement Policy

- Least Recently Used

- Most Recently Used

- FIFO Type

- Random 

- Not Most Recently used

- Write Policy

- Cache Hit

- Write Through

- Write Back

- Cache Miss

- Write Allocate

- No Write Allocate

그냥 이정도가 될거 같다.

Reference:

- Coursera Computer Architecture :https://www.coursera.org/course/comparch

- Cache Algorithm : http://en.wikipedia.org/wiki/Cache_algorithms