[Study] Memory Hierarchy (1)

Computer Memory의 일반적인 역할은 Data를 담아두고 있으면서 CPU가 순차적으로 접근해서 그안에 들어있는 Instruction을 읽어오게끔 하는 것이다. 그러면 다음의 과정을 생각해보자.

Processor와 Memory은 각각의 모듈이기 때문에 서로간의 신호를 주고 받기 위해서는 Bus라는 통로를 거치게 된다. 만약 우리가 이 안에 있는 정보를 확인하고 싶으면  I/O를 통해서 관찰할 수 있는 것이다. 그런데 이런 것들이 공통의 bus를 사용하기 때문에 당연히 한계가 있을 것이다. 가령 예를 들어서 한꺼번에 Data가 이 Bus를 통해서 전달이 되면 Bottle neck 과 같은 성능을 저하시킬 수 있는 요소도 존재할 것이다. 그러면 컴퓨터 구조를 설계하는데 있어서 추구해야 될 목적 중에는 어떻게 하면 bus를 거쳐지 않고 Memory의 Data를 Access할 수 있게 하냐는 것이고 그로 인해서 나오게 된것이다. 바로 Cache 이다. 

Memory 속에서 자주 쓰는 내용을 일부만 Processor 근처에 놔서 Bus를 거치지 않고 Data를 읽어오자는 것이다. 이렇게 하면 Memory와 CPU간의 신호 교환에 이용되었던 Memory Bandwidth를 I/O에도 조금더 사용할 수 있기 때문에 성능 향상이라는 궁극적인 결과를 가져오게 된다.

Cache Memory를 다루게 되면 덩달아 나오는 개념이 Locality라는 것이다. 현대 컴퓨터의 구조상 컴퓨터의 동작은 커다란 super Loop 내에서 신호가 오면 처리되는 식으로 설계되어 있다. 그중 시간이나 공간에 중점적으로 처리하느냐에 따라 두가지로 구분을 둘 수 있다. 

 첫번째는 시간에 따른 Locality인 Temporal Locality이다. 간단히 이야기하면 가장 최근에 읽어온 Data는 다시 읽어올 때도 빠르게 Access할 수 있다는 것이다. 바로 앞에서 언급했던 것처럼 컴퓨터의 동작은 Super Loop 내에서 수행되는데 이 Loop내에도 반복적으로 카운팅이 되는 것도 있을 것이고, 혹은 subroutine 같은 것이 돌 수 있을 것이다. 분명 같은 메모리영역에 할당되어 있는 상태라면 그 곳을 집중적으로 Access를 할 것이고, 이런 걸 Cache로 할당한다면 다른 부분을 할당한 것보다도 성능 향상을 크게 느낄 수 있을 것이다. Temporal 이란 용어 내에도 담겨 있다시피 Memory가 반복적으로 접근하는 영역은 임시로 공간을 두어 처리하는 접근 방식인 것이다.

 두번째는 공간에 따른 Locality인 Spatial Locality인데 한번 참고한 영역은 다음에 참고할 때도 빠르게 Access할 수 있다는 것이다. 이렇게 하면 Temporal과 Spatial이 무슨 차이를 나타내느냐는 의문을 가질 수 있는데 설정한 기준이 시간이냐 공간이냐가 다른 것이다. 그래서 Temporal 자체는 시간을 고려한 저장방식이 되는 것이고, Spatial은 데이터가 저장된 장소를 고려한 저장방식이 된 것이다. 가까운 예로는 일반적인 Sequential Execution을 들 수 있다. 

 결론적으로 위에서 소개한 Locality를 뭉뚱그려서 표현하면 CPU가 Memory로부터 Data를 가져오는데 있어서 가장 최근에, 가장 접근하기 가까운 영역에 Data를 저장해놓으면 Access하기도 편해지는 개념인 것이고.궁극적인 목적은 하나의 Virtual Memory를 만들어서 이런 것들을 실현시키기 위해 Cache라는 개념을 추가시킨 것이다.

이 그림을 보면 그런게 적용되어 있음을 알 수 있다. 얼핏 보면 이게 무슨 그림인가 할 수 있지만 gcc를 실행시켰을 때 Memory Location에 따른 Processing Time을 표현한 그래프이다. 점 하나가 해당 시간에 접근한 영역이 되는데 당연히 빽빽하게 밀집된 지점이 자주 Memory Access된 지점이 될 것이다. 잘 보면 process time이 흘러감에도 특정 Location에서는 Access가 잘 이뤄지는 특징을 발견할 수 있을 것이고, 또 한편으로는 같은 시간대에서 보면 그 주변 영역에 대해서도 Memory Access가 일어나는 것을 볼 수 있다. 또는 process time이 증가하면서 Access가 일어나는 Location 역시 이동하는 특성도 볼 수 있다. 앞에서 배운 관점으로 보자면 전자의 특성은 Temporal Locality를 나타낸 예이고, 후자는 Spatial Locality 를 나타낸 예라고 생각하면 될 듯 하다.

 이제 Cache를 만들면 확실히 Memory에서 Data를 Access하는 것보다 빠르다는 것을 알 수 있다. 하지만 한 가지 큰 문제가 있다. 바로 Cache에 있는 Data가 원래의 CPU가 읽어온 Data와 동일하냐는 것이다. 원래 Instruction을 만든 사람의 의도는 분명 원래 저장된 Memory에서는 확실하게 보장될 것이다. 하지만 이 Memory에 있던 것이 Cache에 옮겨지면서 과연 100% 동일한 Data가 옮겨지느냐 알 수 없는 것이다. 그래서 이런 것을 Hit 과 Miss라는 개념으로 설명한다.

위의 예로 보자면 과연 노란색으로 칠해진 Data가 Cache에 있을 때와 Memory에 있을 때 같은 걸 나타내는지가 궁금한 것이다. 그래서 그걸 확인해보고 맞으면 Hit, 틀리면 Miss가 나게끔 처리가 된다. 조금더 정확히 표현하자면 I/O가 Memory에서 찾은 Data를 Cache에서도 찾으려고 했을 때 있으면 Hit이라고 한다. 물론 이것도 확률적으로 Hit rate이라고 표현할 수도 있고, Hit이 되는데 걸리는 시간을 따로 Hit time이라고 표현할 수 도 있다. 물론 이런게 시스템의 성능을 평가하는 요소로 고려될 수 있다. 

 반면 Memory에서 발견한 Data가 Cache에서는 찾지 못했을 때는 Miss가 발생한다. 이 때 Process는 자기가 처리하고 있던 동작에 Stall을 건 후에 다시 instruction을 수행하는 과정을 거치게 된다. 당연히 이때는 찾는데 걸린 시간과 해당 데이터를 대체하는 데 걸린 시간이 필요할 것이고, 이 시간을 보통 miss penalty로 표현하곤 한다. 그래서 지금까지 나온 정의들을 적절히 조합하면 Memory에 Access하는데 걸린 평균 시간을 계산할 수 있게 되고 이 것도 역시 performance의 평가 척도가 된다. 책에 나온 수식은 다음과 같다.

Average Memory Access Time (AMAT) = (Hit Rate * Hit Time) + (Miss rate * Miss Penalty) 

(The hit rate (or the miss rate if you prefer) does not characterize the memory hierarchy alone; it depends both upon the memory organization and the program being run on the machine.)

= miss rate * (hit time + miss penalty) + (1 - miss rate) * hit time 

= hit time + miss rate * miss penalty

아무튼 miss로 인한 성능 저하가 나타나긴 하지만 Cache를 달면서 얻을 수 있는 큰 장점은 바로 CPU와 Memory간에 발생하던 Bandwidth 할당이 줄어든다는 것이다. 이는 곧 I/O에 할당되는 System Bus의 Bandwidth 를 넓힐 수 있기 때문에 당연히 한번에 처리할 수 있는 Data 량이 많아질 수 있다는 것이다. 또한 기존에 정의되어 있는 Instruction Set 기반의 구조를 바꿀 필요없이 모듈하나만 설치해서 얻을 수 있는 게 많다는 것이다. 

- 추가 내용 (2013. 10. 19)

: 이전에 작성했던 내용중에 오류가 있어서 수정한다. Cache에 대한 신뢰성 문제는 hit이냐 miss냐에 대한 문제가 아니다. 간혹 cache에는 사용자가 의도하지 않은 정보가 저장되는 경우가 있다. 이때 만약 사용자가 메모리에 Data를 읽거나 쓰게끔 한다고 가정해보자. 그러면 그 Data는 십중팔구 Cache를 거치게 될 것이고 만약 Cache를 읽어오는 과정에서 이전에 의도하지 않은 정보가 겹치면 최종적으로 CPU가 읽는 데이터 역시 신뢰할 수 없는 데이터가 될 것이다. 그래서 Cache를 저장하는 영역내에 따로 Valid bit과 Dirty Bit을 두어 지금 가지고 있는 데이터가 신뢰할 수 있는 건지 아닌지를 확인할 수 있는 과정이 포함되어 있다. 당연히 신뢰할 수 없는 데이터라면 Cache내에 들어있는 데이터를 싹 비워주는 과정을 해야 될텐데 이 과정을 Cache Clean과 Cache Flush가 수행한다.