cache line bouncing에 관하여 Mar 10, 2008

시스템에 관련된 서적이나 기사들을 보면 cache에 관해서 많은 용어들이 나온다.
cache thrashing, cache line bouncing, cache snooping, cache invalidation 등등.


명확한 용어를 사용하지 않는다면 듣는 사람이나 말하는 사람 모두 피곤하기 마련이다.
먼저, 가장 흔히 사용하는 용어는 cache line bouncing 이다.
Cache는 일반적으로 공간 지역성을 최대한 활용하기 위하여 cache line size만큼 한번에 메모리의 데이터를 cache line에 올려 놓게 된다. 현재 Intel의 core2duo와 같은 경우는 이 크기가 64 Byte에 해당한다. 

예를 들어 메모리의 0xC0120800의 한 바이트를 read하였다고 할지라도, cache line size가 64바이트라면 0xc0120800부터 0xc0120840까지 의 데이터를 읽어들이는 셈이된다. SMP환경에서 여러 CPU들이 해당 주소를 읽게 되면 각 CPU이 local cache 안에  같은 메모리 주소의 데이터를 캐시안에 공유하고 있게 된다. 
이때, 여러 CPU중 한 CPU가  0xc0120800~0xc0120840의 범위 중 한 바이트라도 변경하게 되면 MESI 프로토콜에 의해 다른 CPU들의 cache line은 invalid되게 된다. 그러므로 다른 CPU들이 그 주소 범위 내의 한 바이트를 읽으려거든 cache miss가 발생하며 memory로부터 다시 읽어와야만 한다.  이러한 것들이 하드웨어적으로 보장이 되며 우리는 Cache Coherency라고 한다.
Cache line bouncing이란 위의 설명과 같이 한 여러 CPU들의 local cache안에 공유되는 메모리 주소를 한 CPU가 변경하여 다른 CPU들의 Local cache도 update해야만 하는 상황을 일컫는다.  일부 사람들은  false sharing이 cache line bouncing이라고 얘기를 하곤 하는데, 그건 아니다.  False sharing은 cache line bouncing을 발생시키는 행동 중의 하나일 뿐이다.  false sharing을 설명하는 글들은 많이 있으니 굳이 설명하지 않는다. 단지 한가지 덧붙인다면 linux kernel의 hot path에서 사용되는 자료구조들은 false sharing을 막기 위해 최대한 자료 구조의 데이터와 그 데이터를 보호하는 Lock은 다른 cache line에 놓이도록 한다.  Cache line bouncing을 제일 많이 일으키는 부분이바로 contention이 심한 데이터에 대한 lock이다.  spin_lock의 test_and_set op는 해당 op를 발생시킨 CPU의 cache안에 해당 주소를 포함하는 cache line을 modify하고 그리고 다른 프로세서들은 자신의 cache안에 있는 데이터 중 방금 수정된 메모리 주소와 관련된 cache line을 소유하고 있는지 감시하게 되는 데.. 이것이 cache snooping이다.  cache snooping을 통해서 다른 CPU의 local cache들이 invalid 모드로 바뀌는 것이다. 
일반적으로, cache line bouncing이 굉장히 많이 발생하는 것을 cache thrashing이라고 한다. cache trashing은 SMP,CMP와 같은 멀티 프로세서 구조에서 심각하게 성능을 저하할 수 있으며 그 주범인 spin_lock들을 막기 위해 linux kernel은 RCU와 같은 lock free 알고리즘을 사용하여 점차 변화하고 있다.