Understanding CPU Caching and Performance 02/04

By | 2006/03/30

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가 한 번 코드와 데이터를 사용하되, 재사용할 빈도가 있는 경우를 의미한다. 관련 코드 블럭과(이나) 데이터는 해당 태스크의 퍼포먼스를 다소 증가시키는데 기여한다.

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

Leave a Reply