[Study] Memory Hierarchy (4) - Sequence of Cache Write

지난 포스트에서 Write Policy를 다뤄봤다. 그럼 강의에 언급된 예제를 다시 되짚어보고자 한다.

이렇게 생긴 Cache block이 있다. 이와중에 Memory로부터 다음과 같이 연속된 Memory Sequence를 읽어오려고 한다. Cache는 과연 어떻게 쓰여질까?

0, 4, 8188, 0, 16384, 0

일단 첫번째 0을 읽어오게 되면 Cache의 0번 index 값을 검색하게 된다. 이 후에 Tag가 맞는지를 확인해야 되는데 Cache에는 아무처리가 되어 있지 않으므로 당연히 Cache Miss가 발생하게 된다. 그럼 이전 포스트에서 언급했던 내용처럼 Write Policy에 따라서 Memory로부터 받아온 Data를 해당 Cache block에 채워넣게 된다. 

4를 읽어왔을 때도 마찬가지일 것이다. 역시 Valid bit이 0이므로 이 Cache에 들어있는 Data는 쓸모가 없고 Miss가 발생한다. 당연히 Memory Data가 Cache Data로 써진후에 Valid bit이 1로 바뀐 상태에서 마무리짓게 된다. 

다음은 8188인데 이걸 32bit binary code로 바꿔보면 위와 같이 나온다. 그중에서 index는 1111111111이므로 1023번째 block에서 검색이 이뤄지게 된다. 역시 valid bit이 0이므로 Miss가 나면서 데이터가 써지게 된다. 이제 문제는 다시 0번째 index를 검색할 때이다.

분명 앞에서 첫번째 instruction을 수행하면 0에 fetch가 일어났었다. 그러고 난 후에 다시 0을 읽어온 케이스니까 Tag나 index가 동일할 것이다. 여기에 valid bit도 1이기에 이 상태에서는 Cache hit이 나타날 것이다. 그러면 CPU가 Cache를 읽어올 때 이 0번째 index에 들어있는 값은 Memory에 있는 것과 동일하게 처리하겠다는 것이다. 그래서 정상적으로 동작한다.

이번에는 16384인데, 코드를 바꿔보면 0번째 index를 가리키는 것을 확인할 수 있다. 하지만 기존의 0번째 index가 가진 tag와 이번에 새로 읽어온 tag를 비교해보면 조금 다른 것을 확인할 수 있다. 당연히 tag가 다르기 때문에 Cache miss가 발생하고 이에 따라서 Memory의 Data를 다시 최신의 것으로 Update되는 과정이 수행될 것이다.

역시 다시 0을 읽어와도 똑같다. Cache miss가 발생하고 다시 tag가 0에 대한 것으로 정의될 것이다.

그런데 잘 보면 위의 예시에선 딱 3군데 Cache block만 다루고 있는 것을 확인할 수 있다. Cache Table이 1024개 있는데 그 중에 3개만 Write되고 또 그 중 0번째 index에서만 3번의 overwrite이 발생했다. 이렇게 하면 이전의 정보가 필요한 경우에는 상황에 따라서 Access할 수 없는 경우가 발생할 수 있는 것이다. 

 사실 이건 Direct mapped Cache이기 때문에 발생하는 문제이다. 이전 포스트에서도 다뤘지만 Direct mapped Cache는 한개의  Cache block에 여러개의 Memory block이 공유되어 있는 형태로 구성되고 있다. 하지만 한개의 Cache가 그 여러개를 표현하는 만큼, 1:1 mapping이 아닌 이상 표현하지 못하는 것도 발생할 수 있는 것이다. 

 일차적으로는 Cache block의 size를 크게 하면 해결할 수 있다.

위의 그림은 Data의 size를 512bit으로 처리한 경우다. 동작자체는 똑같지만 Miss가 났을 경우에는 Overwrite이 되는 것이 아니라 축적되는 것이다. 그래서 해당 Memory Data를 읽어오려면 해당 Address의 Offset과 index만 알게되면 찾을 수 있는 것이다. 

 결론적으로 block의 size를 크게 하면 overwrite로 인한 손실이 없어질 것이란게 위의 예시였다. 하지만 실제로 실험을 해보면 조금 다른 결과가 나온다.

지난 포스트에서 컴퓨터의 performance를 측정할 수 있는 척도로 Miss rate, 즉 Cache로부터 읽어올 때 그 데이터가 Memory에도 있을 확률이 Hit rate이고, 이 값을 1에서 뺀 결과가 miss rate라고 소개했었다. 당연히 Miss가 일어날 경우에는 CPU가 해당 instruction에 대한  stall을 걸기 때문에 전체적인 operation이 느려진다. 앞에서 소개한 것처럼 Block size를 크게 하면 어느기점에서부턴가 이 Miss rate가 증가하는 현상이 발생한다. 

 사실 Size를 늘인다는 의미 자체는 Temporal Locality의 이점을 줄여서 Spatial Locality의 장점을 취하자는 것이었다. 그런게 Cache 크기가 증가하면서 Spatial Locality의 효과가 줄어들면서 Temporal Locality로 잃는 이점이 더 커지는 것이다.간단히 생각하면 이렇게 된다. Cache의 사이즈가 작으면 그만큼 전체에서 해당 데이터를 찾아내는 빈도수가 적겠지만, 그게 커지면서 해당 데이터를 찾기위해 접근하는 빈도가 더 커지고, 이로써 전체적으로 miss도 더 발생하게 되는 것이다. 이걸 강의에서는 Block size가 커지면서 Optimal한 Cache size도 같이 커지기 때문이라고 설명하고 있다.

다른 방법은 cache의 구조를 기존 방식에서 조금 바꾸자는 것이다.가령 이런식으로 고려해보자.

0번째 index가 많이 쓰여지니까 0번째 index의 Cache Block size를 키우는 것이다. 이러면 앞에서 overwrite되면서 사라졌던 정보들도 계속해서 가지고 있을 수 있다. 그런데 사실 이런 건 구현하기가 힘들다. 지금 우리는 위와 과정을 수행해본 후에 0번째 index에 overwrite이 많이 된다는 것을 알고 있었기 때문에 구현이 가능한 것이다. Memory로부터 어떤 Data를 읽어올지 모르는 이상 사실 구현이 복잡할 것이다. 위와 같은 방식을 하나의 Cache Block이 전체 Memory Data와 연관이 있다고 해서 Fully- Associative Cache라고 한다. 사실 위와 같이 구현하려면 index 자체가 의미가 없어지기 때문에 전체 Instruction Set Architecture도 바뀌어야 한다는 결론이 나온다. 이게 아주 이론적인 내용이고, 그럼 한 Cache에 여러개의 Data를 담을 수 있도록 임시 공간을 두는 건 어떨까 하는게 다음의 제시 방향이다.

이렇게 하면 이전 포스트에서도 계속 언급된 direct mapped 방식과 바로 앞에 나온 fully associative 방식의 절충이 될 수 있다. 적절히 overwrite되면서 일정 이상의 Data를 지속적으로 가지고 있게 된다. 이런 방식을 n-way Associative Cache방식이라고 한다. 여기서 n이 나타내는 것은 tag와 Data를 어느정도 동시에 가질 수 있느냐를 표현한 것이고, 이것에 따르면 위의 이미지는 2-way associative Cache라고 볼 수 있다. 이런 맥락에서 보면 direct mapped cache도 일종의 1-way associative cache라고 표현할 수 있을 것이다.

 아무튼 이런식으로 Associativity를 변화시키면 hit rate를 올릴 수 있는 대략적인 결과를 얻을 수 있다.