Understanding CPU Caching and Performance 04/04

By | 2006/03/30

Temporal and Spatial Locality Revisited: Replacement/Eviction Policies and Block Sizes

Replacement/Eviction policies

캐시는 훌륭한 리플레이스먼트 폴리시(에빅션 폴리시-eviction policy-라고 부른다)로 템포럴 로컬리티로부터 장점을 취할 수 있다. 리플레이스먼트 폴리시는 캐시에 현재 들어 있는 블럭을 페치되는 새로운 블럭으로 바꾼다. 이러기 위해서, 교체될 블럭을 무작위로 고르는 방법이 있고, FIFO(First in, First Out)나 LIFO (Last In, First Out), 혹은 기타 방법이 있다. 하지만 위 폴리시중 어느 것도 최근 사용한 블럭을 곧바로 재사용하진 않는다. 이 알고리즘에서, 캐시 미스 비율을 늘리거나, 불필요한 페치를 통해 가능한 메모리 버스 밴드위쓰를 늘려서 단기적으로 사용한 블럭을 재사용할 수는 있다.

최적의 리플레이스먼트 폴리시는 사용안한지 오래된 블럭을 불러들이거나 LRU(Least Recently Used) 블럭을 사용하는 것이다. 어느 정도 블럭을 사용하지 않았다면, 현재 작업중인 셋이 좀더 빈번하게 사용하는 블럭보다 더 사용할 가능성이 떨어지기 때문이다.

그러나 LRU 알고리즘은 이상적이며, 실제로 구현하기는 어렵다. 어떤 블럭이 LRU인가를 분별하는 건 캐시 디자인에서 매우 어려울 뿐만 아니라, 이러한 검색은 시간을 많이 잡아먹기 때문에 불필요한 대기 현상이 리플레이스먼트를 할 때마다 일어난다. 대부분의 캐시는 가(假)-LRU 알고리즘으로 구현을 하는데, 이 알고리즘은 캐시에 사용하지 않은 채로 남아있는 블럭을 “dirty”로 표시하여 LRU를 측정한다. 새 블럭을 캐시에 페칭하면, 제일 더러운 블럭이 먼저 교체 된다.

전혀 더럽지 않은 블럭이 단지 비좁다는 이유로 교체되는 현상도 종종 일어난다. 필요한 데이터를 가진 블럭이 캐시 크기 문제로 교체되는 현상은 용량 미스(capacity miss)라고 부르며, 이 미스가 캐시 미스의 세 번째이자 마지막 종류이다.

 

Block Sizes

스페이셜 로컬리티에서 필자는 전체 블럭의 저장은 캐시가 스페이셜 로컬리티의 장점을 취하는 방법 중에 하나라고 소개하였다. 이제 우리는 캐시가 내부적으로 어떻게 돌아가는 지 좀더 알게 되었기에, 블럭 크기에 대해 좀더 자세하게 볼 수 있다. 캐시 크기가 커질 수록 블럭 크기도 늘어나기 때문에 스페이셜 로컬리티의 장점을 좀더 용이하게 얻을 수 있으리라 생각할 것이다. 분명히, 블럭당 좀더 많은 바이트를 캐시로 페칭시키면, 다른 블럭에 있다는 이유로 돌아가는 셋을 물리치는 현상을 줄일 수 있다. 하지만 여기에는 사실이되 한계가 있다. 캐시 크기를 유지하면서 블럭 크기를 늘리면, 캐시가 가질 수 있는 블럭 수는 줄어든다. 더 적은 블럭은 더 적은 셋을 의미하며, 더 적은 셋은 충돌 현상, 즉 캐시 미스를 더 많이 일으킬 수 있다. 또한 블럭 수가 적으면 당연히 CPU가 필요로하는 특정 블럭도 찾기 힘들어진다.

이경우 장점으로는 캐시를 좀더 잘 조절할 수 있다. 캐시 블럭이 더 적으면, 고해상도에서 워킹 셋의 한계점까지 검색할 수 있으며, 캐시 블럭이 너무 커지면, 블럭이 소수의 바이트만을 갖기 때문에 낭비 공간이 많아진다. 캐시 오염의 문제로 본다면, 더 커진 캐시 블럭은 그보다 더 적은 캐시 블럭보다 캐시를 비-재사용 데이터로 캐시를 오염시킬 우려가 있다고 말할 수 있다.

다음 그림은 우리가 얘기한, 더 큰 블럭 크기를 갖는 메모리 맵을 보여준다.

다음 그림은 똑같은 맵이지만 더 적은 블럭 크기의 상태이다.

큰 블럭 크기에 대한 또다른 문제로는 밴드위쓰와 관련이 있다. 더 커진 블럭 크기는 각 LOAD마다 더 많은 데이터를 페칭함을 의미하며, 특히 미스 비율이 높을 때 메모리 버스의 광대역을 모두 차지할 우려가 있다. 따라서 시스템은 커다란 캐시 블럭을 사용할 경우 광대역을 잘 통제해야하며, 그렇지 않으면 버스 트래픽이 늘어나서 메모리로부터 캐시 블럭으로 페칭하는 시간은 늘어날 것이다.

 

Write Policies: Write through vs. Write back

지금까지 본 기사는 메모리 트래픽의 한 가지 종류, LOAD, 혹은 리퀘스트만을 다뤘다. 리퀘스트는 메모리 트래픽의 대부분을 점유하기 때문에 이것만 다뤘는데, 나머지의 트래픽으로는 STORE가 있다. 스토어는 단순한 단일 프로세서일 때 더 다루기 쉽다. 본 장에서는 L1 캐시만 있는 단일 프로세서 시스템에서 스토어를 어떻게 다루는 지 알아보겠다. 캐시와 프로세서가 더 많아질 경우에는 지금보다 훨씬 복잡해진다.

회수한 데이터를 CPU가 변경하면, CPU는 데이터를 저장시키거나, 메인 메모리로 되돌려서 나머지 시스템이 최신 상태를 유지할 수 있도록 해야한다. 메모리에 작성하는 데에는 두 가지 방법이 있다. 첫 번째 방법으로는 변경한 데이터를 최신 변경에 맞춰서 모조리 즉각 업데이트하는 방법이 있다. 이렇게 하면 L1로 쓰여진 변경 데이터와 메인 메모리는 항상 최신을 유지할 수 있다. 이 방법은 write through라고 불리운다. 모든 계층 수준에 변경 데이터를 작성하기 때문이다.

이 방법은 다중 프로세서나 I/O 위주의 시스템 디자인에 적합하다. 다중 클라이언트가 한 번에 메모리로부터 읽어서 필요한 업데이트를 모두 한꺼번에 하기 때문이다. 그러나 쓰기를 할 때마다 다중 업데이트를 벌이는 방법은 메모리 트래픽을 심하게 유발시킨다. 이 방법은 각 STORE마다 시스템은 변경 데이터를 모두 업데이트하므로, 큰 데이터를 변경했을 경우, 좀더 중요한 LOAD 트래픽에 사용해야할 메모리 밴드위쓰를 점유해버릴 수 있다.

메모리 트래픽을 덜 유발시킬 수 있는 다른 방법으로는 write back이 있다. 여기서는, 캐시 블럭이 제일 높은 레벨에서 나온만큼 제일 낮은 레벨에 업데이트를 하기 때문에, L1의 업데이트된 데이터는 L1에서 나오기 전까지 메인 메모리에서 업데이트되지 않는다.

 

Conclusions

캐시에 대해서 할 수 있는 말은 매우 많으며 본 기사는 기본적인 개념만을 다루었다. 다음 기사에서는 P4와 G4e의 캐시와 메모리 시스템을 좀더 자세하 다루며, 여기에는 본 기사에서 다룬 것들 뿐만 아니라, 실제로 어떤 결과가 나오는 지에 대한 논의와 함께, 데이터 프리펫칭(data prefetching)이나 캐시 일치(cache coherency)와 같은 고급 개념도 다루도록 한다.

 

Bibliography

* David A. Patterson and John L. Hennessy, Computer Architecture: A Quantitative Approach. Second Edition. Morgan Kaufmann Publishers, Inc.: San Francisco, 1996.

* Dennis C. Lee, Patrick J. Crowley, Jean-Loup Baer, Thomas E. Anderson, and Brian N. Bershad, “Execution Characteristics of Desktop Applications on Windows NT.” 1998. http://citeseer.nj.nec.com/lee98execution.html

* Institute for System-Level Integration, “Chapter 5: The Memory Hierarchy.”

* Manish J. Bhatt, “Locality of Reference.” Proceedings of the 4th Pattern Languages of Programming Conference. 1997. http://st-www.cs.uiuc.edu/users/hanmer/PLoP-97/

* James R. Goodman, “Using Cache Memory to Reduce Processor-Memory Traffic.” 25 Years ISCA: Retrospectives and Reprints 1998: 255-262

* Luiz Andre Barroso, Kourosh Gharachorloo, and Edouard Bugnion, “Memory System Characterization of Commercial Workloads.” Proceedings of the 25th International Symposium on Computer Architecture. June 1998.

 

원문이 있는 곳 : http://arstechnica.com/paedia/c/caching/caching-1.html

번역판이 있는 곳 : http://www.appleforum.com/archive/index.php/t-6423.html

Leave a Reply