Understanding CPU Caching and Performance
by Jon "Hannibal" Stokes

처음, 본 사이트를 시작했을 때, 인텔은 첫 번째 셀러론 프로세서를 로우엔드 시장을 겨냥해서 출하했었다. 당시, 펜티엄 II가 갖고 있던 백사이드 캐시를 셀러론은 갖고 있지 않았기 때문에, 반대로 극도의 오버클럭킹도 셀러론에서는 가능하였다. 실제로 오버클럭킹을 주류로 옮긴 주역이 바로 셀러론이라 할만 하며, 본 사이트는 오버클럭킹 가이드를 어떻게, 왜 하는 지에 대한 상세한 기사를 올린 적이 있다. 프랑크 먼로(Frank Monroe)의 셀러론 오버클럭킹 FAQ는 당시 제일 유명한 기사였으며, "셀러론"과 "오버클럭킹"을 야후에서 검색한 이들은 바로 먼로의 FAQ 페이지로 오곤 했다. (심지어는 필자의 여자친구가 말하기를, 필자와 만나기 전에 야후를 통해 본 사이트의 FAQ를 읽은 적이 있었다는 것이다.)

오버클럭킹과 더불어, 셀러론에는 "캐시 없음"의 기능이 특히 주목받았다. 셀러론에서의 퀘이크 벤치마킹은 캐시가 있는 펜티엄 II와 거의 비슷했기 때문에 더더욱 그러했다. 당시 뉴스그룹과 각종 BBS는 이 현상에 대해 논의하였지만 실제로 캐시가 어떤 방식으로 퍼포먼스를 늘리는 데에 대해서 올바르게 이해하는 이들은 거의 없었다. 개인적으로 지금도 마찬가지리라 생각한다. 하지만 현재의 시스템 디자인에서는 캐시가 다시금 중요해졌다. RAMBUS와 DDR, 그 외 차세대 메모리 기술이 나왔음에도 불구하고, CPU 클럭 속도와 퍼포먼스는 메인 메모리 퍼포먼스보다 더더욱 빠르게 증대하였다. 결과적으로 L1과 L2, L3 캐시는 상대적으로 느린 RAM이 전체 시스템 퍼포먼스를 떨어뜨리지 않도록 막는 역할을 맡았다.

본 기사는 CPU 캐시와 퍼포먼스에 대한 일반적인 소개를 내용으로 하며, spatial과 temporal locality와 set associativity와 같은 근본적인 캐시의 개념과, 애플리케이션이 각기 캐시를 이용하는 방법, 메모리 위계 등을 기술한다. 이와 같은 내용에 더불어, 다음 기사에는 인텔 P4와 모토로라 G4e 기반의 시스템에서 실제로 캐시와 메모리 서브시스템이 어떻게 돌아가는 지에 대해 다룰 예정이다. (개인적으로 엑스서브 하드웨어에 대한 논의도 하고 싶다.) 하지만 본 기사는 캐시의 크기가 왜 애플리케이션에 따라서 중요해지는 지, "tag RAM"이 뭘 의미하는 지 모르는 분들을 위한 기사이다.

Caching basics

시스템 디자인에서 캐시의 역할을 이해하기 위해서는 소비자-생산자(혹은 클라이언트-서버) 모델로 CPU와 메모리 서스시스템부터 알아야한다. CPU는 생산자인 하드 디스크와 RAM이 제공하는 정보를 소비한다. 프로세스 기술과 프로세서 디자인의 발전덕택에, CPU는 고도의 효율로 정보의 소비가 가능해졌으며, 문제는 CPU의 클럭 사이클이 버스 클럭 사이클과 메모리보다 더 빠른 비율로 짧아진다는 데에 있다. 따라서, 메인메모리가 요구받은 데이터를 채울 수 있기 전까지 기다림을 의미하는 CPU 클럭 사이클 수치는 늘어나기 때문에, CPU 클럭속도가 늘어나면, 메모리는 CPU로부터 멀어지기만 한다.


Slower CPU


Clock Faster CPU Clock

이렇게 서로 벌어지는 간격은 전체 시스템 퍼포먼스에 영향을 끼친다. CPU를 가구 공장 공방으로, 메인 메모리를 목재 하치장으로 생각해보라. 좀더 큰 트럭으로 모든 나무를 실어 나르더라도, 공방에서 주문을 채우는 시간은 더 길어지기만 할 것이다.

주: 공방과 하치장 모델로 캐시를 설명한 사람은 필자가 처음이 아니다. 제일 유명한 사례는 Thing King 게임이며, 필자는 이 게임을 페터 반 데어 린덴(Peter van der Linden)의 책에서 처음 보았다.

이 사례에서 문제 해결의 한 가지 방법은, 시내의 좀더 소규모의 공방을 임대하여 최근에 들어온 나무 주문을 저장해두는 것이 있다. 이 공방은 원래 공방의 캐시로 작동하여, 여기에 원래 공방에서 필요로하는 것을 미리 비치해둘 수 있다. 물론, 원래의 공방은 더 크고 더 잘 돌아간다. 좀더 다양한 타입의 나무를 저장할 수 있기 때문에 어떤 주문이던지 간에 처리할 수 있다. 가까운 공방에 없는 나무가 필요할 때에는 원래 공방까지 가서 찾아와야하는데, 이경우는 특수한 주문이기 때문에 상당 시간을 기다려야한다는 단점이 있다. 주문한 사람은 대기실에서 담배나 피면서 오프라나 볼 수 밖에. 오프라를 보는 데 돈을 내야한다면 그 누가 좋아할까?

The Memory Hierarchy

이해가 잘 됐으리라 확신한다. 하지만 우리의 소규모 공방은 캐시 분석의 첫 번째 단계(혹은 레벨 1-L1-캐시)에 불과하다. L1은 CPU에서 매우 빠르게 접근할 수 있기 때문에 CPU가 제일 많이 요구할법한 코드와 데이터를 저장하기에 매우 적당하다. (잠시 후에는, L1이 어떻게 CPU가 원하는 바를 "예측"할 수 있는 지에 대해 알아보겠다.) 빠른 접근 시간을 갖는 L1은 static RAM(SRAM)이라는 제일 고가이면서 제일 빠른 램으로 만들어진다. SRAM 메모리 셀은 네 개에서 여섯 개의 트랜지스터(DRAM은 셀당 하나의 트랜지스터를 갖는다.)를 갖기 때문에 가격이 비싸며, 따라서 L1이 커질 수록 시스템 전체 비용도 대폭 상승한다.

최근에 나온 대부분의 CPU는 프로세서의 나머지 부분, 같은 실리콘 상에 L1을 입힌다. 공방 모델로 설명하자면, 원래 공방과 같은 동네에 작은 공방을 새로 설치하는 것과 마찬가지이다. 즉, CPU와 최대한 접근시켜서 더욱 빠른 속도를 얻는 것이다. 단점도 있다. L1이 프로세서에 좀더 가까워질 수록, 메인 메모리(혹은 지방의 공방)는 프로세어와 그만큼 멀어질 수 밖에 없다. 따라서, L1에 없는 데이터가 필요한 경우,(이와 같은 경우를 캐시 miss라고 부른다.) 메모리로부터 데이터를 얻는 시간은 오래 걸리며, 프로세서가 빠르다면 더더욱 오래걸리게 마련이다. 이경우 공방 모델로 비유하자면, 목재 하치장이 지방이나 다른 마을은 고사하고, 다른 나라에 있는 것이나 마찬가지이다. P4같은 높은 클럭속도를 갖는 프로세서는 오퍼레이션 하나를 완수하기 위해 메인 메모리로부터 데이터를 받을 때, 공방이 해외의 하치장에서 며칠 지난 뒤에 목재를 받는 것이나 마찬가지로 오래걸릴 수 있다.

아래의 표를 보기 바란다. 이 표는 여러가지 타입의 메모리에서 레이턴시와 크기 정보를 보여준다. (수치가 최신은 아니다. 현재의 수치는 좀더 감소하였다.) L1 캐시와 메인 메모리 사이에서의 접근 시간에 대한 거대한 간격에 주목하기 바란다. 1GHz CPU에서 50 나노세컨드는 50번의 클럭 사이클을 낭비한다는 뜻이다.



여기에 대한 해결책은, 좀더 많은 캐시를 다는 방법이 있다. 우선적으로 L1 자체를 늘리는 방법도 생각할 수 있겠지만, 위에서 밝힌 바와 같이 비용 상승을 고려해보면 오히려 L1의 캐시 크기를 제한해야한다. 공방 분석으로 보자면, 도심지에서의 임대비용은 교외보다 매우 비싸기 때문에 생산성을 높이기 위해 도심지에 공방을 따로 임대하는 데에는 한계가 있게 마련이다. 그러므로 공방의 크기를 적절히 해서 모든 비용과 수익이 균형이 맞도록 해야 최적의 비용으로 최대의 아웃풋을 낼 수 있다.

L1을 늘리는 것보다 더 나은 해결책은 L1처럼 행동하면서 바로 옆 동네에 좀더 저렴하고 커다란 공방을 임대하는 방법이 있다. P4와 G4e와 같은 프로세서가 바로 이 방법을 써서, 메인 메모리와 L1 캐시 사이에 L2 캐시를 갖고 있다. L2 캐시는 보통 L1이 가진 모든 데이터에 별도의 데이터를 포함한다. 따라서 보통, L1 캐시가 L2 캐시의 부분집합이라고도 한다. L2는 L1에 플러스 알파가 더 있기 때문이다. 아래 그림에서 CPU가 현재 돌리고 있는 프로세스의 코드와 데이터는 붉은 셀로 나타나 있다. 푸른 셀은 현재 활성중인 프로세스와는 관련이 없다. (이 그림은, 로컬리티를 알게되면 좀더 잘 이해할 수 있다.)



하드 디스크에서 파일을 페이징하는 것으로 시작하여 CPU의 모든 레지스터로 들어가는 과정을 캐시 계층(cache hierarchy)이라고 한다. CPU까지 위로 올라갈 수록 캐시는 점점 작아지고 빨라지며 구현에 대한 비용도 더 올라간다. 반대로 캐시 계층에서 아래로 내려갈 수록 좀더 커지고 저렴해지지만 더 느려진다. 계층에서 각기 갖고 있는 데이터는 보통 미러화 되기 때문에, L1 캐시에 있는 데이터는 L2와 메인 메모리까지 계속 복사하여 파일을 페이징한다. 따라서 계층의 각 레벨은 하위 레벨의 부분집합이다. 어떻게 서로 복사본을 유지하는 지에 대해서는 다음에 논의하도록 한다.

위에서부터 보면, 각 레벨을 시스템의 각기 다른 부분이 통제하는 걸 알 수 있다. 데이터는 각기 다른 영역에 따라서 올라가고 내려가지만, 본 기사에서는 계층의 상위 레벨만 다루도록 한다. 또한 본 기사가 제시하는 수치는 최신 수치가 아니다. 이 수치는 필자가 에네시(Hennessy)와 패터슨(Patterson)의 책에서 발췌한(후반부의 참고 자료를 보기 바란다.) 부분이며, P4와 G4e 기반의 시스템의 좀더 구체적인 수치는 다음 기사에서 다룰 예정이다.

Locality

Example: A Byte's Brief Journey Through the Memory Hierarchy

예에서, CPU는 LOAD 인스트럭션으로 메모리 서브시스템에게 데이터를 레지스터로 읽어들이도록 시킨다. (이경우, 단일 바이트이다.) 첫 번째로, 이 리퀘스트는 L1 캐시에서 나와서 리퀘스트에 필요한 데이터가 있는 지를 확인한다. L1 캐시가 필요한 데이터를 갖고 있지 않다면, 리퀘스트를 처리할 수 없기-바로 이 상황이 위에서 얘기한 캐시 미스이다-때문이며, 만약 데이터를 갖고 있는 경우, L2 캐시로 내려온다. L2 캐시가 필요한 바이트를 갖고 있지 않다면 이 리퀘스트는 메인 메모리로 기나긴 여정을 시작한다. 메인 메모리가 데이터를 갖고 있지 않다면 실로 중대한 문제이다. 이럴 경우에는 하드 디스크에서 페이징을 해야하기 때문이며, CPU 시간을 매우 많이 잡아먹게 된다.

필요한 바이트가 메인 메모리에 있다고 가정해보자. 그럴 경우, 메인 메모리에서 복사한 바이트는 캐시 라인을 통해 L2로, L1으로 간다. CPU가 똑같은 바이트를 다시 리퀘스트할 경우 L1에 이미 있는 똑같은 바이트를 재사용하게 되며, 이 경우는 캐시 힛(hit)이라고 부른다.

컴퓨터 설계자들은 보통 캐시 미스를 가져오는 상황에 따라 세 가지 종류를 구분해 두었다. 앞으로 본 기사의 적절한 부분에 이 세 가지 분류를 넣을 예정이지만 우선은 첫 번째 경우만 이야기하겠다. Compulsory miss는 필요한 데이터가 케시에 없어서 프로그램 실행할 때 페이징해야하는 경우의 캐시 미스를 의미한다. 데이터 프리페칭같은 트릭을 사용할 수 없어서 피할 수가 없기 때문에 '강제 미스'라고 이름지은 것이다. 캐시화된 모든 데이터는 어느 순간에 첫 번째로 캐시로 옮겨져야하며, 그렇지 못할 경우는 보통 컴펄서리 미스가 생긴다.

나머지 두 가지 미스는 CPU가 리퀘스트한 데이터가 캐시에 존재하지만 몇 가지 이유 때문에 사용할 수 없는 경우(eviction)에 생겨난다. 에빅션에 대해서는 다음에 다루기로 한다.

How different applications use the cache

캐시가 돌아가는 방식에 대한 매우 기본적이며 단순한 원칙이 있다. 바로 두 가지 종류의 locality of reference이다. 하나는 spatial locality이고, 다른 하나는 tamporal locality이다. 스페이셜 로컬리티는 CPU가 어느 시각에 메모리로부터 한 아이템을 원할 경우, 이웃들도 원한다는 것이며, 템포럴 로컬리티는 메모리의 아이템이 한 번 접근하면, 가까운 장래에 다시 한 번 접근할 경우를 일컫는다. 스페이셜과 템포랄은 코드와 데이터 스트림에 따라서, 즉 애플리케이션의 종류에 따라 나뉘어진다.

Spatial locality

로컬리티 오브 리퍼런스의 개념은 그다지 자세한 설명이 없어도 이해하기 어렵지 않지만, 자세히 알아보도록 하자. 스페이셜 로컬리티는 이해하기 쉬운 편에 속한다. 우리들 대부분은 MP3 플레이어나 DVD 플레이어, 혹은 거대한 데이터를 다루는 비슷한 종류의 미디어 애플리케이션을 사용한다. MP3 파일을 고려해보자. MP3 파일은 시작부터 끝까지 프로세서가 소비하는 데이터 블럭으로 이뤄져있다. 만약 CPU가 Winamp를 돌린다면, 5분 짜리 MP3 파일을 1:23의 비율로 리퀘스트할 때, 다음 리퀘스트는 1:24, 1:25로 할 것임을 추측할 수 있다. DVD도 마찬가지이며, 사진이나 오토캐드 드로잉, 퀘이크 레벨도 마찬가지이다. 이러한 애플리케이션들은 CPU를 차례로 지나가는 연속적인 데이터 어레이에서 돌아간다.



위 그림에서 붉은 부분은 메모리 어레이에 있는 데이터에 관계가 있으며, 꽤 좋은 스페이셜 로컬리티를 갖췄음을 나타낸다. 붉은 부분들이 서로 가까이 모여있기 때문이다. 스페이셜 로컬리티가 제대로 갖춰지지 않은 애플리케이션에서의 붉은 부분은 관련없는 푸른색 부분 사이에서 마구잡이로 분포한다.

Temporal Locality

워드 프로세서와 같은 업무용 애플리케이션은 보통 스페이셜 로컬리티를 상당히 갖춘다. 생각해보라. 한 워드 프로세서에서 예닐곱 개의 문서를 한꺼번에 열어서 동시에 작업해나가는 이들은 거의 없다. 대부분은 한 두개의 관련성 있는 파일을 열어서 작업한다. 따라서 스페이셜 로컬리티는 관련있는 데이터가 메모리상에서 같이 모임에 다를 바가 없다. 서로 관련있는 데이터이기 때문에 CPU에서도 같이 프로세싱한다.

스페이셜 로컬리티는 또한 데이터는 물론 코드에도 적용된다. 대부분의 잘 작성된 코드들은 점프와 브랜치를 되도록이면 피하기 때문에 프로세서는 커다란 블럭을 터치안하고 실행시킬 수 있다. 게임이나 시뮬레이션, 미디어 프로세싱 애플리케이션은 상당히 커다란 데이터셋에서 지속적으로 작동하는 적은 규모의 코드를 다루기 때문에, 상당한 수준의 스페이셜 로컬리티를 코드에 갖추고 있다.

그런데 업무용 애플리케이션에서는 다소 섞여 있다. 워드 프로세서를 사용한다고 가정해보자. 문서를 만들 때 대부분은 여러가지 다른 포맷 버튼을 누르고 여러가지 다른 메뉴 옵션을 사용한다. 예를 들어서, 한 단어를 이탤릭 체로 작성한 다음에 패러그래프의 스페이싱을 바꾸고 파일을 저장하는 과정은 연속적이다. 이런 과정은 MS Word와 같은 거대한 애플리케이션에서 각기 다른 코드가 처리한다. 즉, 파일->저장 메뉴가 서체를 이탤릭으로 바꾸는 코드와 같은 부분에 있지 않다는 말이다. 따라서 워드 프로세서는 CPU가 올바른 코드를 수행하기 위해 메모리 이곳 저곳을 헤매게 한다. 하지만 각 개별 액션(즉, 파일 저장이나 서체 스타일 등)은 거대한 애플리케이션 안의 하위 프로그램들처럼, 보통 꽤 커다란 스페이셜 로컬라이징 된 데이터에서 같이 일어난다. 그러므로 파일->저장 액션이 이탤릭 체 옵션과 코드가 별다른 장소에 있다고 하더라도, 두 코드 모두 나름의 권리를 지난 작은 프로그램들처럼 좋은 스페이셜 로컬리티를 나타낸다.

즉, 캐시 디자이너들은 업무용 애플리케이션용으로 커다란 캐시를 이용하여 자주 사용하는 코드를 모아들어야한다. 캐시가 너무 작다면, 그만큼 수행하는 액션들에 따라 CPU가 메모리 상을 왔다갔다 해야한다. 캐시가 충분히 크다면, 모든 하부-프로그램들도 맞을테고, 교환해야할 경우도 줄어든다. 바로 캐시가 없는 셀러론에서 업무용 프로그램들의 퍼포먼스가 매우 떨어지는 이유이다.

Cache lines or "blocks"

캐시는 두 가지 방법으로 스페이셜 로컬리티의 장점을 취한다. 첫 번째로, CPU가 메모리 서브시스템으로부터 특정 데이터를 요구할 때, 이 데이터는 L1 캐시로 로딩된다. 리퀘스트된 실제 데이터는 the critical word로 불리우고 데이터에 딸려온 나머지는 캐시 라인, 혹은 캐시 블럭이라 불린다. 따라서 크리티컬 워드 뿐만이 아닌 캐시 블럭도 같이 팻칭해서 캐시로 불러들이면, CPU는 나머지 바이트로 다음 프로세스를 처리할 준비를 한다. 캐시가 스페이셜 로컬리티로부터 얻는 다른 방법은 프리펫칭(prefetching)이라 불리는 트릭인데, 다음에 다루기로 한다.

Temporal locality

간단한 포토샵 필터로 이미지를 음화시킨다고 해보자. 시작점에서 각 픽셀을 변화시키는 코드들이 연속적으로 끝점까지 돌아간다. 이 코드는 각 픽셀에 연속적으로 실행되는 작은 루프에 불과하기 때문에, 재사용하는 코드의 사례랄 수 있다. 게임이나 미디어 애플리케이션, 시뮬레이션 등은 수많은 "작은 루프"를 사용하여 코드에서 훌륭한 템포럴 로컬리티를 갖고 있다.

하지만, 이런 종류의 애플리케이션들이 데이터에 대해서는 그리 템포럴 로컬리티를 잘 지키지 못함을 지적해야한다. MP3의 사례로 돌아가서, 음악 파일은 보통 연속적으로 동작하되, 어떤 부분도 반복 재생하진 않는다. 이경우, CPU에 일시적으로 중단 없이 지나가기만 하기 때문에, 캐시에 이 파일을 저장하는 건 낭비이다. 다시 사용하지 않기 때문에 실제로 재사용하는 캐시 를 위해 저장하지 말아야함에도 불구하고, 절실하지 않은 데이터를 캐시에 저장하는 행위를 "캐시 오염(pollute the cash)"라고 한다. 미디어 애플리케이션과 게임과 같은 종류의 애플리케이션들은 거대한 캐시 오염자이기도 하지만, 셀러론이 캐시가 없기 때문에 큰 영향을 받진 않았다. 매우 빠른 속도로 CPU를 통해 데이터를 스트리밍하기 때문에, 이들 애플리케이션들은 데이터가 캐시되는 지 관심을 기울일 이유가 없다. 이 데이터는 다시 필요하지 않기 때문에, 접근 가능하지 않은 캐시라는 사실은 그리 중요하지 않다.

캐시가 템포럴 로컬리티로 장점을 취하는 주요 방법은 이시점에서 명확해진다. 캐시는 현재 CPU가 작업하는 코드와 데이터를 저장할 장소를 제공한다. "작업"은 CPU가 한 번 코드와 데이터를 사용하되, 재사용할 빈도가 있는 경우를 의미한다. 관련 코드 블럭과(이나) 데이터는 해당 태스크의 퍼포먼스를 다소 증가시키는데 기여한다.

다른 방법으로는, 리플레이스먼트를 현명하게 하는 방법이 있는데, 여기에 대해서는 다음 섹션에서 자세히 다룬다.

Associativity

Locality: Conclusions

한가지 재확인해야할 점이, 템포럴 로컬리티가 스페이셜 로컬리티이기도 하지만 그 반대는 아니다. 즉, 재사용한 데이터는 언제나 관련(따라서 메모리 상의 스페이셜 로컬리티 영역에 모아진다)지어지지만, 관련 데이터를 언제나 재사용하진 않는다. 열려진 텍스트 파일은 메모리의 로컬라이징 영역을 점유하는 재사용 가능한 데이터의 사례이며, MP3 파일은 같은 영역에 있되, 재사용하지 않는 데이터의 사례이다.

한 가지 더 지적한다면, 코드에 대한 메모리 접근 패턴과 데이터에 대한 메모리 접근 패턴은 같은 애플리케이션 내에서도 매우 다를 때가 많다. 이를테면, 미디어 애플리케이션은 코드에 대해서는 훌륭한 템포럴 로컬리티를 갖추고 있지만 데이터에 대해서는 그렇지 못하다. 이때문에 L1 캐시를 코드 영역과 데이터 영역으로 나누는 디자이너들이 많다. 코드용 캐시는 인스트럭션 캐시, 혹은 i-캐시라 불리며, 데이터 캐시는 d-캐시라고 불린다. 이러한 구분은 캐시의 양과 시스템에서 돌리는 애플리케이션 종류, 그 외 여러가지 요소에 따라 상당한 퍼포먼스 증대를 가져온다.

Cache organization: block frames and blocks

앞서 언급했듯이, 캐시는 블럭(혹은 "라인")으로 데이터를 펫칭하여 각 블럭은 "블럭 프레임"이라 불리우는 특별한 슬롯에 들어간다. 이 블럭이 캐시의 기본 유닛을 구성한다. RAM도 캐시의 블럭만큼 같은 크기의 블럭으로 구성되며, 캐시 디자이너들은 어떤 RAM 블럭을 캐시의 블럭 프레임에 저장할 것인 지를 몇 가지의 스킴을 통해 고를 수 있다. 이 스킴을 캐시 리플레이스먼트(replacement) 폴리시라 부른다. 메모리 블럭을 캐시의 어느 곳에 저장할 지를 정하기 때문이다.

따라서 램 블럭은 캐시로 패치되서, 블럭 프레임에 저장된다.

CPU가 특정 램 블럭에서 한 바이트를 요구할 때, 매우 빠르게 새 가지를 결정한다. 1. 필요한 블럭이 실제로 캐시에 있는지 없는 지를 알아본다. (즉, 캐시 히트인지 캐시 미스인지를 알아본다.) 2. 캐시 안의 블럭 위치(캐시 히트인 경우) 3. 블럭 내에서 바람직한 바이트의 위치(이경우도 캐시 히트의 경우다.) 특별한 메모리, 태그(tag)가 캐시 안의 각 블럭 프레임에서 캐시에 요구하는 것이 바로 위 세 가지이다. 태그 필드는 CPU가 이 세 질문에 모두 답하도록 허용하지만, 여러 가지 요소에 따라 답변의 속도는 달라진다.

태그는 "태그 램"이라 불리우는 장소에 저장된다. 이 메모리는 매우 빠른 SRAM으로 구성되어있는데, 알맞는 블럭의 위치를 찾는데 시간이 다소 걸리기 때문이다. 캐시가 더 커질 수록 블럭 수도 더 많아지며, 블럭 수 자체가 커지기 때문에, 더 많은 태그 램이 생기지만 올바른 블럭을 찾는데 그만큼 시간이 더 걸리게 마련이다. 따라서 태그 램은 캐시에 불필요한 지체 현상을 가져다줄 수 있다. 결과적으로 태그 램에는 제일 빠른 램을 사용해야할 뿐만이 아니라, 블럭 프레임에 RAM을 매핑하는데 태그를 현명하게 사용해야한다. 다음 섹션에서 그러한 매핑의 일반적인 세 가지 옵션을 소개하고 각 옵션의 장단점을 논하겠다.

Fully associative, n-way, and direct-mapped caches

램 블럭을 캐시 블럭 프레임에 따라 매핑하는 제일 단순한 스킴은 "fully associative" 매핑이라고 부른다. 이 스킴으로, 어떠한 램 블럭도 가능한 블럭 프레임에 저장할 수 있다.



이 스킴의 문제는, 만약 캐시로부터 특정 블럭을 회수할 경우, 블럭이 어떠한 프레임에도 있을 수 있기 때문에 전체 캐시의 모든 블럭 프레임을 뒤져야한다. 더 큰 캐시는 그만큼 블럭 프레임도 많기 때문에 페치에 상당한 지체 현상이 발생할 수 있으며, 캐시가 클 경우, 각 페치때마다 더 많은 블럭 태그와 블럭 프레임을 뒤져야하므로 지체는 더더욱 커진다.

두 번째로는 "다이렉트 매핑"을 이용하는 방법이 있다. 다이렉트-매핑한 캐시에서 각 블럭 프레임은 주 메모리의 특정한 블럭 서브셋만 캐시화할 수 있다.



위의 그림에서, 각 붉은 블럭(블럭 0, 8, 16)은 붉은 블럭 프레임(프레임 0)에서만 캐시화되었다. 블럭 1, 9, 17도 비슷하게, 프레임 1에만 캐시화 되었고, 블럭 2, 10, 18은 프레임 2에만 캐시화 되어있다. 이러한 패턴으로, 각 프레임은 메인 메모리의 각 여덞 블럭만 캐시화한다. 결과적으로 한 블럭의 잠재적인 로케이션 숫자를 좁힐 수 있기 때문에 페칭해야할 태그 숫자도 비약적으로 줄어든다. 따라서, CPU가 블럭 0, 8, 16에서 바이트를 원하는 경우, 프레임 0만 체크하면 된다. 모든 프레임을 뒤지는 편보다 훨씬 효율적이고 더 빠르다.

하지만 이 스킴에도 단점은 있다. 만약 0~3과 8~11의 블럭이 "working set"으로 8-block을 형성해서, CPU가 캐시로 불러들어서 전체를 돌리려 한다고 가정해보자. 캐시는 여덟 개의 블럭의 크기를 갖지만, 다이렉트-매핑됐기 때문에 여덟 개 중에서 한 번에 네 개의 블럭만 저장할 수 있다. 블럭 0에서 블럭8이 같은 프레임에 들어갔고, 블럭 1~9, 2~10, 2~11도 마찬가지라면, 결과적으로 CPU는 한 번에 네 블럭만을 불러들이므로, 교체해야하며, 여덟 블럭 때문에 시간이 지체된다. 그러는 동안 캐시의 절반은 전혀 사용하지도 않는 채로 말이다! 따라서, 다이렉트-매핑 캐시가 fully associative 캐시보다 언제나 빠르지만, 특정 상황에서는 비효율적일 수 있다.

위에 묘사한 상황, 즉 CPU가 다중 블럭을 저장하길 원하지만 모두 같은 프레임 안에 있기 때문에 그럴 수 없는 경우를 충돌(collision)이라고 부른다. 앞서의 사례에서, 블럭 0과 8은 충돌하였다. 두 블럭 모두 프레임 0 안에 들어가길 원하지만 그럴 수 없기 때문이다. 이러한 충돌에서 생기는 미스를 충돌 미스(conflict miss)라고 부르며, 필자가 앞서 언급한 세 가지 종류의 캐시 미스 중에 두 번째에 해당된다.

충돌로 생겨나는 캐시 공간 낭비를 줄이기 위해 다이렉트-매핑 캐시는 메인 메모리 블럭을 캐시 프레임의 서브셋에 따라 제한시킬 수 있다. 아래의 그림을 보기 바란다.



이 그림에서, 붉은 블럭은 붉은 프레임 셋(셋 0) 안에서 어디든 갈 수 있고 노랑 블럭은 노랑 프레임 셋(셋 1) 안 어디로든 갈 수 있다. 이렇게 생각할 수 있다. fully associative 캐시를 둘로 잘라서, 메인 메모리 블럭을 절반씩 제한한 것이다. 이렇게 함으로써 다이렉트 매핑 캐시에서 충돌 현상을 상당히 줄일 수 있다. 이경우 패치할 때, 캐시 절반에 있는, 단일한 네-블럭 셋을 뒤지기만 하면 된다.

위 그림의 캐시를 "four-way associative"라고 부른다. 네 개의 프레임에 각기 "셋"으로 캐시를 나누기 때문이다. 위의 캐시는 여덟 개의 프레임만을 갖기에, 두 가지 셋만 갖출 수 있다. 더 큰 캐시는 더 많은 셋을 갖춰서 충돌 가능성을 더욱 줄일 수 있다. 더구나 모든 셋이 정확히 네 개의 블럭으로 이뤄졌기 때문에 캐시의 크기에 상관 없이 주어진 블럭을 찾기 위해 네 프레임씩만 뒤지면 된다. 즉, 캐시가 커지고 셋의 숫자가 늘 수록 좀더 효율적으로 태그를 검색할 수 있다는 의미이다. 세 개의 셋으로 이뤄진 캐시라면 캐시의 1/3만 뒤지면 된다. 네 개의 셋이면 1/4이다. 100 개라면 1/100이기 때문에 캐시 크기가 늘 수록 효율성은 비약적으로 늘어난다.



또한, 캐시 안의 셋 수를 늘리면서 메인 메모리를 유지하면, 충돌 가능성을 더욱 줄일 수 있다. 위 그림에서 셋 0 안의 공간을 다투는 붉은 메모리 블럭이 더 줄었음을 알 수 있다.

Eviction Policies

캐시 크기를 유지한 채로 캐시 안의 셋 수를 늘리는 다른 방법으로는 각 셋마다 블럭 수를 줄이는 방법이 있다. 아래의 그림을 보면 two-way set associative 캐시를 나타낸다.



더 잘 이해하기 위해서, 투 웨이와 포 웨이를 다이렉트-매핑 상태에서 비교해보도록 하자. 비교에 있어서, 캐시와 메모리 크기는 일정하다고 가정한다. 연관성 수준이 늘면, 특정 블럭을 위치시키는 데 이용하는 태그도 늘기 때문에, associativity 증가는 캐시 지체 현상의 발생도 의미함을 염두에 두기 바란다.

Two-way vs. direct-mapped

투-웨이 캐시에서, 잠재적인 충돌 가능성은 다이렉트-매핑에 대비해 줄어들지만, 태그 수는 그 두 배이다. 캐시와 메인 메모리에 따라서, 투 웨이는 캐시의 전체적인 지체 현상을 유발할 수 있으며, 그만큼 충돌 가능성은 줄어든다 할 수 있다.

Two-way vs. four-way

투-웨이 캐시의 대기 현상이 포-웨이보다 낮지만, 잠재적인 충돌은 투 웨이가 포 웨이보다 높다. 앞서의 비교에서, 투 웨이 associative 캐시를 포 웨이와 비교하는 것은 충돌 비율을 줄이는 데 어느 정도 지체가 늘어나는 가를 재는 것이다.

Associativity: Conclusions

일반적으로, 현재의 기술 수준에서(즉, 태그 RAM의 속도) 대부분의 캐시에 associativity 수준은 에잇-웨이보다 같거나 낮은 편이 좋다. 에잇 웨이보다 더 많아지면 캐시의 지체 현상이 충돌 현상을 줄이는 것 이상으로 늘어나기 때문이다. 또한 투 웨이보다 적으면, 지체 현상을 줄이는 것 이상으로 충돌이 많이 발생하기 때문에 역시 가치가 없다. 물론 다이렉트 매핑은 적용하지 않은 상태이다.

associativity에 대한 결론을 내기 전에, 좀더 알아야할 정보가 있다. 우선, 이미 이해했겠지만, 다이렉트-매핑 캐시는 단순히 one-way associative 캐시이며, 완전한 associative 캐시는 n-way associative 캐시이며, n은 캐시 전체 블럭 수와 같다.

두 번째로, 컴퓨팅에서 메모리의 잔여 블럭은 n-way associative 캐시에 저장된다. 에네시와 패터슨의 책 377 페이지를 보면, 캐시 리플레이스먼트는 다음과 같다.

(Block address) MOD (Number of sets in cache)

위의 사례에 대입해보기 바란다. 지루한 연습일 수 있지만 이 단순한 함수로 앞서의 블럭을 세 보면, 정말로 잘 이해할 수 있을 것이다. 또한 재미나기도 하다.

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://casaubon.tv