Understanding CPU Caching and Performance 03/04

By | 2006/03/30

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)

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

Leave a Reply