현대 CPU 캐시가 메모리 지연을 숨기기 위해 어떻게 동작하며, 계층 구조·연관도·프리페치·캐시 일관성(MESI)·멀티스레드에서의 비용 등 구현 세부와 성능 측정 결과를 다룬다.
알고 계셨나요...? LWN.net은 구독자 지원으로 운영되는 매체입니다. 전체 운영을 지속하기 위해 구독자들의 도움에 의존합니다. 구독을 구매하여 LWN을 계속 온라인에 유지할 수 있도록 도와주세요.
[편집자 주: 이 글은 Ulrich Drepper의 “What every programmer should know about memory(모든 프로그래머가 메모리에 대해 알아야 할 것)” 문서의 두 번째 연재입니다. 첫 번째 파트를 읽지 않은 분은 그쪽부터 시작하는 것이 좋을 것입니다. 내용이 정말 훌륭하며, 이번에도 Ulrich가 게재를 허락해 준 것에 감사드립니다.
짧은 부탁 하나: 이처럼 긴 문서에는 오타가 몇 개 남아 있을 수밖에 없습니다. 오타를 발견했고 수정되길 원하신다면 댓글로 달기보다는 lwn@lwn.net으로 메일을 보내 주세요. 그래야 수정 사항을 문서에 반영하고 Ulrich의 원본에도 되돌려 놓을 수 있으며, 다른 독자들이 흥미롭지 않은 댓글을 읽느라 시간을 쓰지 않아도 됩니다.]
오늘날의 CPU는 25년 전과 비교하면 훨씬 더 정교해졌다. 당시에는 CPU 코어의 주파수가 메모리 버스 주파수와 비슷한 수준이었고, 메모리 접근은 레지스터 접근보다 약간 느린 정도였다. 하지만 90년대 초반에 CPU 설계자들이 CPU 코어의 주파수는 크게 올린 반면, 메모리 버스의 주파수와 RAM 칩 성능은 비례해서 증가하지 않으면서 상황이 극적으로 바뀌었다. 이는 이전 절에서 설명했듯이 더 빠른 RAM을 만들 수 없어서가 아니다. 만들 수는 있지만 경제성이 없다. 현 세대 CPU 코어만큼 빠른 RAM은 어떤 DRAM보다도 자릿수로 훨씬 비싸다.
매우 작지만 매우 빠른 RAM을 가진 기계와, 많지만 상대적으로 빠른 RAM을 가진 기계 중 하나를 선택해야 한다면, 작업 집합(working set) 크기가 작은 RAM의 크기를 초과하고 하드디스크 같은 2차 저장장치 접근 비용이 존재하는 한, 후자가 항상 이긴다. 문제는 2차 저장장치(대개 하드디스크)의 속도인데, 스왑된 작업 집합 일부를 보관하기 위해 이를 사용해야 한다. 디스크 접근은 DRAM 접근보다도 자릿수로 느리다.
다행히 ‘전부 아니면 전무’의 선택일 필요는 없다. 컴퓨터는 많은 양의 DRAM과 더불어 소량의 고속 SRAM을 가질 수 있다. 한 가지 구현 방법은 프로세서 주소 공간의 특정 영역을 SRAM으로, 나머지를 DRAM으로 두는 것이다. 그러면 운영체제는 SRAM을 최대한 활용하도록 데이터를 최적으로 배치하는 역할을 맡는다. 기본적으로 이 상황에서 SRAM은 프로세서 레지스터 집합의 확장처럼 동작한다.
이 방식은 가능은 하지만 실용적이지 않다. 이러한 SRAM 기반 메모리의 물리 자원을 프로세스의 가상 주소 공간에 매핑하는 문제(그 자체로도 엄청나게 어렵다)를 제쳐두더라도, 이 방식은 각 프로세스가 소프트웨어로 이 메모리 영역의 할당을 관리해야 한다. 이 메모리 영역의 크기는 프로세서마다 다를 수 있다(즉, 비싼 SRAM 기반 메모리 양이 서로 다름). 프로그램을 이루는 각 모듈이 빠른 메모리의 지분을 주장할 것이고, 그 과정에서 동기화 요구로 인한 추가 비용이 생긴다. 요컨대 빠른 메모리로 얻는 이득은 자원 관리 오버헤드에 의해 완전히 상쇄될 것이다.
그래서 SRAM을 OS나 사용자 통제 하에 두는 대신, 프로세서가 투명하게 사용하고 관리하는 자원으로 만든다. 이 모드에서 SRAM은 가까운 미래에 프로세서가 사용할 가능성이 높은 메인 메모리의 데이터를 임시로 복사해 두는(즉, 캐시하는) 데 쓰인다. 이는 프로그램 코드와 데이터가 시간적/공간적 지역성(temporal/spatial locality)을 갖기 때문이다. 즉, 짧은 시간 동안 동일한 코드나 데이터가 재사용될 가능성이 높다. 코드의 경우 보통 루프가 있으므로 동일한 코드가 반복 실행된다(공간적 지역성에 아주 적합). 데이터 접근도 이상적으로는 작은 영역에 제한된다. 짧은 시간 동안 사용하는 메모리가 서로 가깝지 않더라도, 같은 데이터가 머지않아 다시 사용될 확률이 높다(시간적 지역성). 예를 들어, 루프 안에서 함수 호출이 이루어지고 그 함수가 주소 공간의 다른 곳에 있어도, 메모리상 거리는 멀지만 호출 시점은 가깝다. 데이터의 경우, 한 시점에 사용하는 총 메모리(작업 집합 크기)는 이상적으로 제한되지만 RAM은 ‘랜덤’ 접근 특성 때문에 물리적으로 서로 가까운 곳만 쓰는 게 아닐 수 있다. 지역성이 존재한다는 사실을 이해하는 것이 오늘날 CPU 캐시 개념의 핵심이다.
단순한 계산으로도 캐시의 이론적 효과를 볼 수 있다. 메인 메모리 접근이 200 사이클, 캐시 접근이 15 사이클 걸린다고 하자. 100개의 데이터 원소를 각각 100번 사용하는 코드는 캐시가 없으면 메모리 연산에 2,000,000 사이클을 쓰지만, 모든 데이터가 캐시에 담긴다면 168,500 사이클만 쓴다. 91.5% 개선이다.
캐시에 쓰이는 SRAM의 크기는 메인 메모리보다 훨씬 작다. 필자의 워크스테이션 경험에서 CPU 캐시 크기는 항상 메인 메모리의 1/1000 정도였다(오늘날 예: 4MB 캐시와 4GB 메인 메모리). 이것 자체는 문제가 아니다. 작업 집합 크기(현재 작업 중인 데이터 집합)가 캐시보다 작으면 상관없다. 그러나 메인 메모리가 큰 데에는 이유가 있다. 작업 집합은 캐시보다 클 수밖에 없다. 여러 프로세스를 실행하는 시스템에서는 작업 집합이 모든 개별 프로세스와 커널의 작업 집합 합이므로 더더욱 그렇다.
캐시의 제한된 크기를 다루려면, 어떤 것을 언제 캐시할지 결정하는 좋은 전략들이 필요하다. 작업 집합의 모든 데이터가 ‘정확히’ 동시에 사용되는 것은 아니므로, 캐시 안의 일부 데이터를 다른 데이터로 잠시 교체하는 기법을 쓸 수 있다. 더 나아가 실제로 필요해지기 전에 이를 해둘 수도 있다. 이런 프리페치(prefetching)는 프로그램 실행과 비동기적으로 메인 메모리 접근을 수행함으로써 비용 일부를 제거한다. 이런 기법들을 포함한 여러 기법을 이용해 캐시가 실제보다 더 커 보이도록 만들 수 있다. 이들은 3.3절에서 다룬다. 모든 기법을 활용한 뒤에는 프로그래머가 프로세서를 돕는 일만 남는다. 어떻게 하는지는 6절에서 논의한다.
CPU 캐시 구현의 기술적 세부로 들어가기 전에, 현대 컴퓨터 시스템의 “큰 그림”에서 캐시가 어디에 들어맞는지 조금 더 자세히 보는 것이 도움이 될 수 있다.
그림 3.1: 최소 캐시 구성
그림 3.1은 최소 캐시 구성을 보여준다. 이는 CPU 캐시를 도입한 초기 시스템에서 볼 수 있던 구조에 해당한다. CPU 코어는 더 이상 메인 메모리에 직접 연결되지 않는다. {더 이전 시스템에서는 캐시가 CPU와 메인 메모리처럼 시스템 버스에 붙어 있었다. 이는 진정한 해결책이라기보다 해킹에 가까웠다.} 모든 로드/스토어는 캐시를 통해야 한다. CPU 코어와 캐시 사이의 연결은 특별하고 빠른 연결이다. 단순화된 표현에서는 메인 메모리와 캐시가 시스템 버스에 연결되어 있고, 시스템의 다른 구성 요소들과 통신할 때도 이 버스를 사용할 수 있다. 2.2절에서 시스템 버스를 “FSB”로 소개했는데, 이는 오늘날 쓰이는 이름이다. 이 절에서는 노스브리지를 무시하며, CPU(들)와 메인 메모리 간 통신을 돕기 위해 존재한다고 가정한다.
지난 수십 년 동안 컴퓨터가 폰 노이만 구조를 사용해 왔지만, 경험상 코드용 캐시와 데이터용 캐시를 분리하는 것이 유리하다는 것이 밝혀졌다. 인텔은 1993년부터 코드 캐시와 데이터 캐시를 분리해 왔고 되돌아간 적이 없다. 코드와 데이터에 필요한 메모리 영역은 서로 상당히 독립적이므로, 독립 캐시가 더 잘 작동한다. 최근에는 또 다른 장점도 나타났다. 흔한 프로세서에서 명령 디코딩 단계가 느리기 때문에, 디코딩된 명령을 캐시하면 실행을 빠르게 할 수 있다. 특히 분기 예측 실패나 예측 불가능 분기 때문에 파이프라인이 비어 있을 때 효과가 크다.
캐시 도입 이후 곧 시스템은 더 복잡해졌다. 캐시와 메인 메모리 간 속도 차가 다시 커지면서, 1차 캐시보다 크고 느린 또 다른 캐시 레벨이 추가되었다. 경제성 때문에 1차 캐시 크기만 늘리는 것은 선택지가 아니었다. 오늘날에는 세 단계 캐시를 가진 기계도 일반적으로 사용된다. 이런 프로세서를 가진 시스템은 그림 3.2와 같다. 한 CPU에 코어 수가 늘면서, 앞으로는 캐시 레벨 수가 더 증가할 수도 있다.
그림 3.2: 레벨 3 캐시가 있는 프로세서
그림 3.2는 3단계 캐시를 보여주며, 문서 나머지에서 사용할 명명 규칙을 도입한다. L1d는 레벨 1 데이터 캐시, L1i는 레벨 1 명령 캐시 등이다. 이는 도식이며, 실제로는 코어에서 메인 메모리로 가는 데이터 흐름이 반드시 상위 캐시들을 거칠 필요는 없다. CPU 설계자들은 캐시 인터페이스를 설계할 때 많은 자유가 있다. 프로그래머에게는 이런 설계 선택이 보이지 않는다.
또한 여러 코어를 갖고, 각 코어가 여러 “스레드”를 가질 수 있는 프로세서도 있다. 코어와 스레드의 차이는, 별도의 코어는 (거의 {초기의 멀티코어 프로세서는 2차 캐시도 각각 따로이고 3차 캐시는 없기도 했다.}) 모든 하드웨어 자원을 별도 복사본으로 가진다는 점이다. 코어들은 같은 자원(예: 외부 연결)을 동시에 쓰지 않는 한 완전히 독립적으로 실행할 수 있다. 반면 스레드는 프로세서 자원의 거의 전부를 공유한다. 인텔의 스레드 구현은 스레드별로 레지스터만 분리해 두고, 그마저도 제한적이며 일부 레지스터는 공유한다. 따라서 현대 CPU의 전체 그림은 그림 3.3과 같다.
그림 3.3: 멀티 프로세서, 멀티코어, 멀티스레드
이 그림에서는 프로세서 2개가 있고, 각 프로세서에 코어 2개, 각 코어에 스레드 2개가 있다. 스레드는 레벨 1 캐시를 공유한다. 코어(더 진한 회색 음영)는 개별 레벨 1 캐시를 가진다. CPU의 모든 코어는 상위 레벨 캐시를 공유한다. 두 프로세서(더 옅은 회색의 큰 박스)는 물론 캐시를 전혀 공유하지 않는다. 이는 특히 다중 프로세스/다중 스레드 애플리케이션에서 캐시 효과를 논할 때 중요하다.
캐시 사용의 비용과 절감을 이해하려면 2절에서의 머신 아키텍처 및 RAM 기술에 대한 지식과, 앞 절에서 설명한 캐시 구조를 결합해야 한다.
기본적으로 CPU 코어가 읽거나 쓰는 모든 데이터는 캐시에 저장된다. 캐시할 수 없는 메모리 영역도 있지만 이는 OS 구현자만 신경 쓰면 되며 애플리케이션 프로그래머에게는 보이지 않는다. 또한 프로그래머가 의도적으로 특정 캐시를 우회할 수 있는 명령도 있다. 이는 6절에서 다룬다.
CPU가 데이터 워드를 필요로 하면 먼저 캐시를 탐색한다. 캐시는 메인 메모리 전체를 담을 수 없지만(그렇다면 캐시가 필요 없다), 모든 메모리 주소가 캐시 가능하므로 각 캐시 엔트리는 메인 메모리에서 해당 데이터 워드의 주소로 태그(tag) 된다. 따라서 특정 주소에 대한 읽기/쓰기 요청은 캐시에서 일치하는 태그를 찾는 방식으로 처리된다. 이때 주소는 캐시 구현에 따라 가상 주소일 수도 물리 주소일 수도 있다.
태그는 실제 데이터 외에 추가 공간을 필요로 하므로, 캐시의 단위를 워드로 선택하는 것은 비효율적이다. x86에서 32비트 워드라면 태그 자체가 32비트 이상 필요할 수 있다. 또한 캐시는 공간적 지역성에 기대므로 이를 반영하지 않는 것도 좋지 않다. 인접한 메모리는 함께 사용될 가능성이 크므로 함께 캐시에 로드해야 한다. 2.2.1절에서 배운 것도 떠올리자. RAM 모듈은 새 CAS 또는 RAS 신호 없이 연속된 많은 데이터 워드를 전송할 수 있을 때 훨씬 효율적이다. 따라서 캐시에 저장되는 엔트리는 단일 워드가 아니라 여러 연속 워드를 담은 “라인(line)”이다. 초기 캐시는 32바이트 라인을 썼지만, 오늘날 표준은 64바이트다. 메모리 버스가 64비트 폭이라면 캐시 라인당 8번 전송이 필요하다. DDR은 이 전송 모드를 효율적으로 지원한다.
프로세서가 메모리 내용을 필요로 할 때 전체 캐시 라인이 L1d에 로드된다. 각 캐시 라인의 메모리 주소는 캐시 라인 크기에 따라 주소 값을 마스킹해 계산한다. 64바이트 캐시 라인의 경우 하위 6비트를 0으로 만든다. 버려진 비트는 캐시 라인 내 오프셋으로 쓰인다. 남은 비트는 경우에 따라 캐시에서 라인을 찾는 데 쓰이거나 태그가 된다. 실제로는 주소 값을 세 부분으로 나눈다. 32비트 주소의 예는 다음과 같을 수 있다.
캐시 라인 크기가 2^O 이면 하위 O비트는 캐시 라인 오프셋이다. 다음 S비트는 “캐시 세트(set)”를 선택한다. 왜 단일 슬롯이 아니라 세트가 쓰이는지는 곧 자세히 다룬다. 지금은 2^S 개의 세트가 있다는 것만 이해하면 된다. 그 위의 32-S-O=T 비트가 태그를 이룬다. 이 T비트는 같은 캐시 세트에 캐시되는 모든 별칭(alias) {주소의 S 부분이 같은 모든 캐시 라인은 같은 별칭으로 알려져 있다.} 을 구분하는 값으로 각 캐시 라인에 함께 저장된다. 세트를 지정하는 S비트는 같은 세트에 속한 라인들에 대해 동일하므로 저장할 필요가 없다.
명령이 메모리를 수정할 때도 프로세서는 먼저 캐시 라인을 로드해야 한다. 어떤 명령도 한 번에 캐시 라인 전체를 수정하지 않기 때문이다(예외: 6.1절에서 설명하는 write-combining). 따라서 쓰기 이전의 캐시 라인 내용이 로드돼야 한다. 캐시는 부분 캐시 라인을 담을 수 없다. 쓰인 뒤 아직 메인 메모리에 기록되지 않은 캐시 라인은 “더티(dirty)”라고 한다. 메인 메모리에 기록되면 더티 플래그는 클리어된다.
새 데이터를 캐시에 로드하려면 거의 항상 캐시에 공간을 만들어야 한다. L1d에서의 축출(eviction)은 캐시 라인을 L2로 밀어 넣는다(L2도 같은 캐시 라인 크기를 사용). 그러면 L2에서도 공간을 만들어야 한다. 이는 다시 L3로, 궁극적으로 메인 메모리로 밀어낼 수 있다. 각 단계의 축출은 점점 더 비싸진다. 여기서 설명하는 모델은 현대 AMD와 VIA 프로세서가 선호하는 배타적(exclusive) 캐시 모델이다. 인텔은 포함적(inclusive) 캐시 를 구현한다 {이 일반화는 완전히 정확하지 않다. 일부 캐시는 배타적이고, 일부 포함적 캐시는 배타적 성질도 갖는다.}. 포함적 캐시에서는 L1d의 각 캐시 라인이 L2에도 존재하므로 L1d에서의 축출이 훨씬 빠르다. L2가 충분히 크다면 두 곳에 중복 저장해 메모리를 낭비하는 단점은 작아지고, 축출 시 이득이 된다. 배타적 캐시의 장점은 새 캐시 라인 로딩 시 L1d만 건드리고 L2는 건드리지 않아도 되어 더 빠를 수 있다는 점이다.
CPU는 프로세서 아키텍처에서 정의한 메모리 모델을 바꾸지 않는 한 캐시를 원하는 방식으로 관리할 수 있다. 예를 들어 메모리 버스 활동이 적을 때 더티 캐시 라인을 메인 메모리에 선제적으로 기록해도 완전히 괜찮다. x86 및 x86-64 프로세서들의 다양한 캐시 아키텍처(제조사 간, 같은 제조사 내 모델 간)는 메모리 모델 추상화의 강력함을 보여준다.
대칭형 멀티프로세서(SMP) 시스템에서는 CPU들의 캐시가 서로 독립적으로 동작할 수 없다. 모든 프로세서는 항상 같은 메모리 내용을 봐야 한다. 이 균일한 메모리 관점을 유지하는 것을 “캐시 일관성(cache coherency)”이라고 한다. 프로세서가 자기 캐시와 메인 메모리만 본다면 다른 프로세서의 더티 캐시 라인 내용을 볼 수 없다. 한 프로세서의 캐시에 다른 프로세서가 직접 접근하도록 하는 것은 엄청 비싸고 큰 병목이 된다. 대신, 프로세서들은 다른 프로세서가 특정 캐시 라인을 읽거나 쓰려는 것을 감지한다.
쓰기 접근이 감지되고 해당 캐시 라인의 깨끗한 사본을 로컬 캐시에 갖고 있다면, 그 캐시 라인은 무효(invalid)로 표시된다. 이후 참조에서는 재로딩이 필요하다. 다른 CPU의 읽기 접근은 무효화를 필요로 하지 않으며, 동일 캐시 라인의 깨끗한 사본을 여러 개 보유해도 된다.
더 정교한 캐시 구현에서는 또 다른 경우가 가능하다. 다른 프로세서가 읽거나 쓰려는 캐시 라인이 첫 번째 프로세서의 캐시에서 더티로 표시돼 있다면 다른 조치가 필요하다. 이 경우 메인 메모리는 최신이 아니므로, 요청한 프로세서는 메모리 대신 첫 번째 프로세서로부터 캐시 라인 내용을 받아야 한다. 스누핑(snooping)으로 첫 프로세서는 이 상황을 감지하고 자동으로 요청한 프로세서에게 데이터를 보낸다. 이 동작은 메인 메모리를 우회하지만, 어떤 구현에서는 메모리 컨트롤러가 이 직접 전송을 감지해 업데이트된 캐시 라인 내용을 메인 메모리에 저장하기도 한다. 쓰기 접근이라면 첫 프로세서는 자신의 로컬 캐시 라인 사본을 무효화한다.
시간이 지나며 여러 캐시 일관성 프로토콜이 개발되었다. 가장 중요한 것은 3.3.4절에서 소개할 MESI다. 요약하면 다음 단순한 규칙으로 정리할 수 있다.
이 규칙을 유지할 수 있다면 멀티프로세서 시스템에서도 프로세서들은 캐시를 효율적으로 사용할 수 있다. 필요한 것은 서로의 쓰기 접근을 감시하고 주소를 로컬 캐시의 주소와 비교하는 것뿐이다. 다음 절에서 구현과 특히 비용에 대해 더 자세히 다룬다.
마지막으로, 캐시 히트/미스의 비용에 대한 감을 주기 위해 인텔이 Pentium M에 대해 제시한 수치를 보자.
어디로 사이클 레지스터 <= 1 L1d ~3 L2 ~14 메인 메모리 ~240
이는 CPU 사이클 단위로 측정한 실제 접근 시간이다. 다이 위의 L2 캐시 접근 시간 중 상당 부분(아마도 대부분)은 배선 지연(wire delay) 때문이라는 점이 흥미롭다. 이는 캐시 크기가 커질수록 악화되는 물리적 한계다. 공정 미세화(예: 인텔 라인업에서 Merom의 60nm에서 Penryn의 45nm로 이동)만이 수치를 개선할 수 있다.
표의 수치는 높아 보이지만, 다행히 캐시 로드와 미스가 발생할 때마다 전체 비용을 다 지불해야 하는 것은 아니다. 일부 비용은 숨길 수 있다. 오늘날 프로세서는 서로 다른 길이의 내부 파이프라인을 사용하여 명령을 디코딩하고 실행 준비를 한다. 준비 과정의 일부는 레지스터로 옮길 값을 메모리(또는 캐시)에서 로드하는 것이다. 파이프라인에서 충분히 일찍 메모리 로드를 시작할 수 있다면 다른 연산과 병렬로 진행돼 로드 비용 전체가 숨겨질 수 있다. 이는 L1d에서는 종종 가능하며, 파이프라인이 긴 일부 프로세서에서는 L2에서도 가능하다.
메모리 읽기를 일찍 시작하는 데에는 많은 장애물이 있다. 메모리 접근 자원이 부족한 것처럼 단순한 이유일 수도 있고, 다른 명령의 결과로 최종 주소가 늦게 결정되는 것일 수도 있다. 이런 경우 로드 비용을(완전히) 숨길 수 없다.
쓰기 연산에서는 CPU가 값이 메모리에 안전하게 저장될 때까지 반드시 기다릴 필요는 없다. 뒤따르는 명령들의 실행이 “값이 메모리에 저장된 것과 같은 효과”를 보이기만 한다면 CPU가 지름길을 택해도 막을 것이 없다. 다음 명령을 일찍 실행할 수 있다. 일반 레지스터에 더 이상 존재하지 않는 값을 보관하는 섀도 레지스터의 도움으로, 완료되지 않은 쓰기 연산에 저장될 값을 바꾸는 것도 가능하다.
그림 3.4: 랜덤 쓰기 접근 시간
캐시 동작 효과를 보여주기 위해 그림 3.4를 보자. 이 데이터가 생성된 프로그램은 나중에 다루겠지만, 설정 가능한 양의 메모리를 반복적으로 랜덤 접근하는 프로그램을 단순히 시뮬레이션한 것이다. 각 데이터 항목은 고정 크기이며, 원소 개수는 선택한 작업 집합 크기에 따라 달라진다. Y축은 원소 하나를 처리하는 데 걸리는 평균 CPU 사이클 수이며, Y축 스케일이 로그라는 점에 유의하라. 이런 유형의 모든 다이어그램에서 X축 역시 마찬가지다. 작업 집합 크기는 항상 2의 거듭제곱으로 표시된다.
그래프는 세 개의 뚜렷한 평탄 구간(plateau)을 보여준다. 놀랍지 않다. 해당 프로세서는 L1d와 L2 캐시는 있지만 L3는 없다. 경험이 있다면 L1d가 2^13 바이트 크기이고 L2는 2^20 바이트 크기임을 추론할 수 있다. 작업 집합이 L1d에 모두 들어가면 원소당 연산 사이클 수는 10 미만이다. L1d 크기를 넘으면 L2에서 로드해야 하므로 평균 시간이 약 28로 뛴다. L2도 부족해지면 480 사이클 이상으로 점프한다. 이때는 많은(혹은 대부분) 연산이 메인 메모리에서 데이터를 로드해야 한다. 더 나쁜 점은 데이터가 수정되므로 더티 캐시 라인도 기록돼야 한다는 것이다.
이 그래프는 캐시 사용을 개선하는 코딩 개선을 들여다볼 충분한 동기를 제공한다. 여기서 말하는 개선은 몇 퍼센트 수준이 아니라, 때로는 자릿수 차이의 개선이다. 6절에서는 더 효율적인 코드를 작성하는 기법을 논의한다. 다음 절은 CPU 캐시 설계의 세부로 들어간다. 지식이 있으면 좋지만 문서 나머지에는 필요하지 않으므로 이 절은 건너뛰어도 된다.
캐시 구현자는 거대한 메인 메모리의 각 셀이 잠재적으로 캐시돼야 한다는 문제를 가진다. 프로그램의 작업 집합이 충분히 크면, 많은 메인 메모리 위치가 캐시의 각 자리를 두고 경쟁한다. 앞에서 캐시 대 메인 메모리 크기 비율이 1:1000 정도인 경우가 흔하다고 언급했다.
3.3.1 연관도(Associativity)
각 캐시 라인이 어떤 메모리 위치의 복사본이든 담을 수 있도록 캐시를 구현할 수도 있다. 이를 완전 연관 캐시(fully associative cache) 라고 한다. 캐시 라인에 접근하려면 프로세서 코어가 모든 캐시 라인의 태그를 요청 주소의 태그와 비교해야 한다. 이 경우 태그는 캐시 라인 오프셋이 아닌 주소의 모든 부분으로 구성된다(즉, 3.2절 그림에서 S는 0).
이런 캐시도 구현된 사례가 있지만, 오늘날의 L2 수치를 보면 비현실적임이 드러난다. 4MB 캐시에 64B 캐시 라인이라면 65,536 엔트리가 있다. 적절한 성능을 내려면 캐시 로직이 이 모든 엔트리 중 주어진 태그와 일치하는 것을 몇 사이클 안에 골라내야 한다. 이를 구현하는 노력은 엄청날 것이다.
그림 3.5: 완전 연관 캐시 개략도
각 캐시 라인마다(여기서는 S=0이므로 큰 태그) 비교기가 필요하다. 각 연결 옆의 문자는 비트 폭을 의미한다. 표시가 없다면 1비트 라인이다. 각 비교기는 T비트 폭의 두 값을 비교해야 한다. 그 결과에 따라 적절한 캐시 라인 내용을 선택해 제공한다. 이는 캐시 버킷 수만큼의 O 데이터 라인 묶음을 병합해야 함을 의미한다. 단일 비교기를 구현하는 데 필요한 트랜지스터 수는 매우 많으며, 특히 매우 빠르게 동작해야 하므로 더 그렇다. 반복(iterative) 비교기는 쓸 수 없다. 비교기 수를 줄이는 유일한 방법은 태그를 반복 비교해 비교기 수를 줄이는 것이지만, 이것도 너무 느려서 적합하지 않다.
완전 연관 캐시는 작은 캐시에는 실용적이다(예: 일부 인텔 프로세서의 TLB 캐시는 완전 연관). 하지만 그런 캐시는 정말 작다. 많아야 수십 엔트리 수준이다.
L1i, L1d 및 상위 레벨 캐시에는 다른 접근이 필요하다. 가능한 것은 탐색 범위를 제한하는 것이다. 가장 극단적인 제한에서는 각 태그가 정확히 하나의 캐시 엔트리에만 매핑된다. 계산은 간단하다. 4MB/64B 캐시에서 65,536 엔트리가 있으니, 주소의 6~21비트(16비트)를 사용해 각 엔트리를 직접 지정할 수 있다. 하위 6비트는 캐시 라인 내 인덱스다.
그림 3.6: 직접 매핑 캐시 개략도
이런 직접 매핑 캐시(direct-mapped cache) 는 빠르고 구현이 비교적 쉽다(그림 3.6 참조). 정확히 하나의 비교기, 하나의 멀티플렉서(이 도식에서는 태그와 데이터를 분리해 둘이라 두 개지만 설계상 필수는 아니다), 그리고 유효한 캐시 라인 내용만 선택하는 로직이 필요하다. 비교기는 속도 요구 때문에 복잡하지만 이제는 하나뿐이므로, 빠르게 만드는 데 더 많은 노력을 들일 수 있다. 이 방식의 진짜 복잡성은 멀티플렉서에 있다. 단순 멀티플렉서의 트랜지스터 수는 O(log N)(N은 캐시 라인 수)로 증가한다. 이는 감당할 만하지만 느려질 수 있고, 그 경우 멀티플렉서에 더 많은 트랜지스터를 써서 일부 작업을 병렬화하고 속도를 올릴 수 있다. 총 트랜지스터 수는 캐시 크기가 커져도 완만히 증가하므로 매우 매력적이다. 하지만 단점이 있다. 직접 매핑에 쓰는 비트에 대해 프로그램이 사용하는 주소가 고르게 분포할 때만 잘 동작한다. 그렇지 않으면(대개 그렇다) 일부 캐시 엔트리는 과도하게 사용되어 계속 축출되고, 다른 엔트리는 거의 사용되지 않거나 비어 있게 된다.
그림 3.7: 세트 연관 캐시 개략도
이 문제는 캐시를 세트 연관(set associative) 으로 만들어 해결할 수 있다. 세트 연관 캐시는 완전 연관과 직접 매핑 캐시의 특징을 결합해 두 설계의 약점을 대체로 피한다. 그림 3.7은 세트 연관 캐시 설계를 보여준다. 태그 및 데이터 저장소는 주소로 선택되는 세트로 나뉜다. 이는 직접 매핑 캐시와 유사하다. 하지만 캐시에서 각 세트 값에 대해 하나의 요소만 갖는 대신, 같은 세트 값에 대해 소수의 값을 캐시한다. 세트 멤버들의 태그는 병렬로 비교되는데, 이는 완전 연관 캐시의 동작과 비슷하다.
그 결과, 불운하거나 의도적으로 같은 세트 번호를 가진 주소를 선택해도 쉽게 무너뜨릴 수 없고, 동시에 캐시 크기가 병렬로 구현 가능한 비교기 수에 의해 제한되지 않는 캐시가 된다. 캐시가 커지면(이 그림에서는) 행 수가 아니라 열 수만 늘어난다. 행 수(연관도)는 연관도를 늘릴 때만 증가한다. 오늘날 프로세서는 L2 캐시에 최대 16-way 이상 연관도를 쓰기도 한다. L1 캐시는 보통 8-way로 충분하다.
| L2 캐시 크기 | 연관도 |
|---|---|
| Direct | 2 |
| CL=32 | CL=64 |
| 512k | 27,794,595 |
| 1M | 19,007,315 |
| 2M | 12,230,962 |
| 4M | 7,749,986 |
| 8M | 4,731,904 |
| 16M | 2,620,587 |
표 3.1: 캐시 크기, 연관도, 라인 크기의 영향
4MB/64B 캐시에 8-way 세트 연관을 적용하면 8,192 세트가 남고, 캐시 세트를 주소 지정하는 데 태그의 13비트만 사용된다. 세트 안의 엔트리 중 (있다면) 어느 것이 해당 캐시 라인을 담고 있는지 알아내려면 8개의 태그를 비교해야 한다. 이는 매우 짧은 시간 안에 가능하다. 실험을 통해 이것이 타당함을 확인할 수 있다.
표 3.1은 캐시 크기, 캐시 라인 크기, 연관도 세트 크기를 바꾸면서 한 프로그램(gcc, 리눅스 커널 사람들이 말하길 가장 중요한 벤치마크)의 L2 캐시 미스 수가 어떻게 변하는지 보여준다. 7.2절에서 이 테스트에 필요한 캐시 시뮬레이션 도구를 소개한다.
아직 명확하지 않다면, 이들 값의 관계는 캐시 크기가 다음과 같다는 것이다.
캐시 라인 크기 × 연관도 × 세트 수
주소는 다음을 사용해 캐시에 매핑된다.
O = log2(캐시 라인 크기)
S = log2(세트 수)
이는 3.2절의 그림이 보여주는 방식과 같다.
그림 3.8: 캐시 크기 vs 연관도(CL=32)
그림 3.8은 표의 데이터를 더 이해하기 쉽게 만든 것이다. 캐시 라인 크기를 32바이트로 고정한 데이터를 보여준다. 주어진 캐시 크기에서 연관도를 높이면 캐시 미스를 상당히 줄일 수 있음을 알 수 있다. 8MB 캐시에서 직접 매핑에서 2-way 세트 연관으로 바꾸면 캐시 미스가 거의 44% 줄어든다. 직접 매핑 캐시보다 세트 연관 캐시에서 프로세서는 더 많은 작업 집합을 캐시에 유지할 수 있다.
문헌에서는 연관도를 도입하는 효과가 캐시 크기를 두 배로 늘리는 것과 같다고 가끔 말한다. 이는 4MB에서 8MB 캐시로 갈 때처럼 극단적인 경우에만 그렇다. 하지만 연관도를 더 두 배 늘리는 것까지 항상 그렇지는 않다. 데이터에서 보듯 추가 이득은 훨씬 작다. 그렇다고 효과를 완전히 무시해서는 안 된다. 예제 프로그램의 피크 메모리 사용은 5.6M이다. 따라서 8MB 캐시라면 같은 캐시 세트를 두 번 이상(많이) 사용할 가능성은 낮다. 더 큰 작업 집합에서는 작은 캐시 크기에서 연관도의 이득이 더 큰 것처럼 절감 효과가 커질 수 있다.
일반적으로 단일 스레드 워크로드에서는 캐시 연관도를 8 이상으로 늘려도 효과가 작아 보인다. 하지만 공유 L2를 사용하는 멀티코어 프로세서가 등장하면 상황이 달라진다. 이제 사실상 두 프로그램이 같은 캐시를 두드리므로 실제 연관도는 절반이 된다(쿼드코어면 1/4). 따라서 코어 수가 늘수록 공유 캐시의 연관도도 늘어야 할 것으로 예상할 수 있다. 더 이상 불가능해지면(16-way도 이미 어렵다) 설계자는 공유 L3 이상을 사용해야 하며, L2는 코어 일부가 공유할 수도 있다.
그림 3.8에서 또 볼 수 있는 효과는 캐시 크기 증가가 성능에 어떻게 도움이 되는가이다. 이 데이터는 작업 집합 크기를 알아야 해석할 수 있다. 캐시가 메인 메모리만큼 크다면 작은 캐시보다 당연히 좋은 결과를 낸다. 따라서 일반적으로 측정 가능한 이득을 제공하는 최대 캐시 크기에는 한계가 없다.
위에서 언급했듯 작업 집합의 피크 크기는 5.6M이다. 이것만으로 ‘유익한 캐시 크기의 최대치’를 절대값으로 알 수는 없지만, 대략 추정은 가능하다. 모든 메모리가 연속적이지 않으므로, 16M 캐시와 5.6M 작업 집합을 갖더라도 충돌이 존재한다(직접 매핑 16MB에 비해 2-way 세트 연관 16MB가 이득이 있는 것을 보라). 그래도 같은 워크로드라면 32MB 캐시의 이득은 미미할 것이라고 보는 것이 안전하다. 하지만 작업 집합이 꼭 동일하다고 누가 보장하는가? 워크로드는 시간에 따라 증가하며 캐시 크기도 그래야 한다. 기계를 구매할 때 지불할 용의가 있는 캐시 크기를 선택해야 한다면 작업 집합 크기를 측정하는 것이 가치 있다. 이것이 중요한 이유는 그림 3.10의 그림들에서 볼 수 있다.
그림 3.9: 테스트 메모리 레이아웃
두 종류의 테스트를 수행한다. 첫 번째 테스트에서는 원소를 순차적으로 처리한다. 테스트 프로그램은 포인터 n을 따라가지만, 배열 원소들은 메모리에 놓인 순서대로 순회되도록 연결되어 있다. 그림 3.9의 아래쪽에서 볼 수 있다. 마지막 원소에서 되돌아가는 참조 하나가 있다. 두 번째 테스트(그림 상단)에서는 배열 원소를 랜덤 순서로 순회한다. 두 경우 모두 배열 원소는 원형 단일 연결 리스트(circular single-linked list)를 이룬다.
3.3.2 캐시 효과 측정
모든 그림은 임의 크기의 작업 집합, 읽기/쓰기 접근, 순차/랜덤 접근을 시뮬레이션할 수 있는 프로그램을 측정해 만들었다. 그림 3.4에서 일부 결과를 이미 보았다. 이 프로그램은 작업 집합 크기에 해당하는 배열을 다음 타입의 원소로 만든다.
cstruct l { struct l *n; long int pad[NPAD]; };
모든 엔트리는 n 원소를 사용해 원형 리스트로 연결되며, 순차 또는 랜덤 순서로 연결된다. 다음 엔트리로 진행할 때는 원소가 순차 배치되어 있어도 항상 포인터를 사용한다. pad 원소는 페이로드이며 임의로 크게 만들 수 있다. 어떤 테스트에서는 데이터를 수정하고, 어떤 테스트에서는 읽기만 수행한다.
성능 측정에서는 작업 집합 크기를 말한다. 작업 집합은 struct l 원소 배열로 구성된다. 2^N 바이트의 작업 집합에는
2^N / sizeof(struct l)
개의 원소가 있다. 당연히 sizeof(struct l)는 NPAD 값에 따라 달라진다. 32비트 시스템에서 NPAD=7이면 각 배열 원소 크기는 32바이트이고, 64비트 시스템에서는 64바이트이다.
가장 단순한 경우는 리스트의 모든 엔트리를 단순히 순회하는 것이다. 리스트 원소는 순차적이며 밀집해 배치된다. 처리 순서가 전방이든 후방이든 상관없으며, 프로세서는 양 방향을 동일하게 잘 처리한다. 여기서 측정하는 것(그리고 이후 모든 테스트에서 측정하는 것)은 단일 리스트 원소를 처리하는 데 걸리는 시간이다. 시간 단위는 프로세서 사이클이다. 그림 3.10은 결과를 보여준다. 별도 언급이 없으면 모든 측정은 64비트 모드의 Pentium 4에서 수행되며, 이는 NPAD=0인 구조체 l이 8바이트임을 뜻한다.
그림 3.10: 순차 읽기 접근, NPAD=0
그림 3.11: 여러 크기에 대한 순차 읽기
처음 두 측정은 잡음의 영향을 받는다. 측정 워크로드가 너무 작아서 시스템 나머지의 효과를 걸러낼 수 없다. 값이 모두 4 사이클 수준이라고 안전하게 가정할 수 있다. 이를 감안하면 세 단계가 보인다.
이 단계는 쉽게 설명된다. 이 프로세서는 16kB L1d와 1MB L2를 가진다. 한 레벨에서 다른 레벨로의 전환이 날카롭지 않은 이유는 캐시가 시스템의 다른 부분에서도 사용되며, 프로그램 데이터만을 위해 독점적으로 사용되지 않기 때문이다. 특히 L2 캐시는 통합(unified) 캐시이며 명령에도 사용된다(참고: 인텔은 포함적 캐시를 사용).
예상과 다르게 보일 수 있는 것은 각 작업 집합 크기에서의 실제 시간이다. L1d 히트 시간은 예상대로다. P4에서 L1d 히트 후 로드 시간은 약 4 사이클이다. 그런데 L2 접근은 어떨까? L1d가 데이터를 담기에 부족해지면 원소당 14 사이클 이상이 걸릴 것처럼 보이지만, 결과는 약 9 사이클만 필요하다고 나온다. 이는 프로세서의 고급 로직으로 설명할 수 있다. 연속된 메모리 영역을 사용할 것을 예상하고 프로세서는 다음 캐시 라인을 프리페치 한다. 즉 다음 라인을 실제로 사용할 때는 이미 절반쯤 로드돼 있으므로, 다음 캐시 라인이 로드되기를 기다리는 지연이 L2 접근 시간보다 훨씬 작다.
프리페치 효과는 작업 집합이 L2를 넘어설 때 더 두드러진다. 메인 메모리 접근이 200+사이클이라고 했는데, 효과적인 프리페치가 있어야만 접근 시간을 9 사이클처럼 낮게 유지할 수 있다. 200과 9의 차이에서 보듯 잘 작동한다.
프리페치하는 동안의 프로세서 동작을(적어도 간접적으로) 관찰할 수 있다. 그림 3.11은 같은 작업 집합 크기에서 이번에는 구조체 l 크기를 바꾼 그래프를 보여준다. 즉 리스트 원소 수는 줄고 각 원소는 커진다. 크기가 달라지면 (여전히 연속인) 리스트에서 n 원소 간 간격이 커진다. 그래프의 네 경우에서 간격은 각각 0, 56, 120, 248바이트이다.
맨 아래는 이전 그래프의 선인데, 이번에는 대체로 평평하게 보인다. 다른 경우의 시간이 너무 나빠서 그렇다. 이 그래프에서도 세 단계가 보이고, 작은 작업 집합에서 큰 오차가 보인다(다시 무시하라). L1d만 관련되는 동안에는 선들이 거의 일치한다. 프리페치가 필요 없어서 각 접근이 L1d만 히트하기 때문이다.
L2 캐시 히트에서는 세 개의 새 선이 대체로 서로 일치하지만 더 높은 수준(약 28)에 있다. 이는 L2 접근 시간 수준이다. 즉 L2에서 L1d로의 프리페치는 사실상 비활성화된다. NPAD=7이면 루프 매 반복마다 새 캐시 라인이 필요하고, NPAD=0이면 다음 캐시 라인이 필요해질 때까지 루프가 8번 반복된다. 프리페치 로직은 매 사이클마다 새 캐시 라인을 로드할 수 없다. 따라서 매 반복마다 L2에서 로드하기 위한 스톨이 보인다.
작업 집합이 L2 용량을 넘어설 때는 더 흥미롭다. 이제 네 선이 크게 벌어진다. 원소 크기가 성능 차이에 큰 역할을 한다. 프로세서는 스트라이드 크기를 인식하고 NPAD=15와 31에 대해 불필요한 캐시 라인을 가져오지 말아야 하는데, 원소 크기가 프리페치 윈도보다 작기 때문이다(6.3.1절 참조). 원소 크기가 프리페치를 방해하는 이유는 하드웨어 프리페치의 한계: 페이지 경계를 넘을 수 없기 때문이다. 크기가 늘 때마다 하드웨어 스케줄러의 효율을 50%씩 떨어뜨린다. 만약 하드웨어 프리페처가 페이지 경계를 넘을 수 있고 다음 페이지가 상주하지 않거나 유효하지 않다면, OS가 페이지를 찾아야 하므로 프로그램은 자신이 시작하지도 않은 페이지 폴트를 겪게 된다. 이는 프로세서가 페이지가 없는 것인지 존재하지 않는 것인지 알 수 없고, 후자의 경우 OS는 프로세스를 종료해야 하므로 전혀 받아들일 수 없다. 어쨌든 NPAD=7 이상에서는 리스트 원소당 캐시 라인이 하나 필요하므로 하드웨어 프리페처가 할 일이 없다. 프로세서는 한 워드를 읽고 다음 원소를 로드하기만 하기 때문에 메모리에서 데이터를 로드할 시간이 없다.
느려지는 또 다른 큰 이유는 TLB 캐시 미스다. TLB는 가상 주소를 물리 주소로 변환한 결과를 저장하는 캐시로, 4절에서 더 자세히 설명한다. TLB 캐시는 매우 빨라야 하므로 꽤 작다. 접근되는 페이지 수가 TLB 엔트리 수를 초과하면 가상→물리 변환을 계속 다시 해야 하며, 이는 매우 비싸다. 원소 크기가 커질수록 TLB 조회 비용은 더 적은 원소에만 분산되므로, 리스트 원소당 계산해야 할 TLB 엔트리 수가 증가한다.
TLB 효과를 보기 위해 다른 테스트를 수행할 수 있다. 한 측정에서는 원소를 평소처럼 순차 배치하고 NPAD=7(원소가 캐시 라인 하나를 꽉 채움)을 사용한다. 두 번째 측정에서는 각 리스트 원소를 별도 페이지에 배치한다. 각 페이지의 나머지는 건드리지 않으며 작업 집합 크기 총계에 포함하지 않는다. {다른 테스트에서는 구조체의 사용되지 않는 부분도 원소 크기에 포함시키며, NPAD를 조정해 각 원소가 페이지를 채우게 할 수도 있겠지만, 이 테스트의 요점은 그것이 아니고 프리페치가 어차피 비효율적이므로 큰 차이가 없다.} 결과적으로 첫 측정에서는 각 반복에 새 캐시 라인이 필요하고, 64개 원소마다 새 페이지가 필요하다. 두 번째에서는 각 반복이 새 페이지 위의 새 캐시 라인을 로드한다.
그림 3.12: 순차 읽기에서 TLB 영향
결과는 그림 3.12에 있다. 측정은 그림 3.11과 같은 머신에서 수행했다. 사용 가능한 RAM 제한 때문에 작업 집합은 2^24 바이트로 제한했는데, 원소를 별도 페이지에 두려면 1GB가 필요하기 때문이다. 아래쪽 빨간 곡선은 그림 3.11의 NPAD=7 곡선과 정확히 일치한다. L1d와 L2 크기를 보여주는 뚜렷한 단계가 보인다. 두 번째 곡선은 완전히 다르다. 중요한 특징은 작업 집합이 2^13 바이트에 도달할 때 시작하는 거대한 스파이크다. 이때 TLB 캐시가 넘친다. 원소 크기 64바이트로부터 TLB 캐시 엔트리가 64개임을 계산할 수 있다. 프로그램은 스왑아웃을 막기 위해 메모리를 잠그므로 페이지 폴트는 비용에 영향을 주지 않는다.
물리 주소를 계산해 TLB에 저장하는 데 걸리는 사이클 수가 매우 큼을 알 수 있다. 그림 3.12는 극단적 사례지만, 이제 NPAD가 큰 값에서 느려지는 큰 요인 중 하나가 TLB 효율 감소임을 알 수 있다. 물리 주소는 L2나 메인 메모리에서 캐시 라인을 읽기 전에 계산돼야 하므로, 주소 변환 페널티는 메모리 접근 시간에 더해진다. 이는 NPAD=31에서 원소당 총 비용이 RAM의 이론적 접근 시간보다 더 높은 이유를 부분적으로 설명한다.
그림 3.13: 순차 읽기/쓰기, NPAD=1
리스트 원소를 수정하는 테스트 데이터로 프리페치 구현의 몇 가지 세부를 더 엿볼 수 있다. 그림 3.13은 세 선을 보여준다. 원소 폭은 모두 16바이트다. 첫 선은 익숙한 리스트 순회로 기준선이다. “Inc”로 라벨된 두 번째 선은 현재 원소의 pad[0] 멤버를 증가시킨 뒤 다음으로 간다. 세 번째 “Addnext0”는 다음 원소의 pad[0] 값을 현재 원소의 pad[0]에 더한다.
순진한 가정으로는 “Addnext0”가 더 느릴 것 같다. 다음 원소로 진행하기 전에 다음 원소에서 값을 로드해야 하기 때문이다. 그런데 일부 작업 집합 크기에서는 이 테스트가 “Inc”보다 빠르게 실행되는 것이 놀랍다. 이는 다음 원소에서의 로드가 사실상 강제 프리페치가 되기 때문이다. 프로그램이 다음 원소로 이동할 때 그 원소는 이미 L1d에 들어있다. 그 결과 작업 집합이 L2에 들어가는 동안 “Addnext0”는 단순 “Follow” 테스트만큼 잘 수행된다.
하지만 “Addnext0”는 “Inc”보다 L2를 더 빨리 벗어난다. 메인 메모리에서 더 많은 데이터를 로드해야 한다. 따라서 작업 집합이 2^21 바이트일 때 “Addnext0”는 28 사이클 수준에 도달한다. 28 사이클 수준은 “Follow”가 도달하는 14 사이클 수준의 두 배다. 이것도 쉽게 설명된다. 다른 두 테스트는 메모리를 수정하므로 새 캐시 라인을 위한 공간을 만들기 위해 L2에서 축출할 때 데이터를 그냥 버릴 수 없다. 대신 메모리에 기록해야 한다. 이는 FSB의 사용 가능한 대역폭을 반으로 줄이므로 메인 메모리에서 L2로 데이터를 옮기는 시간이 두 배가 된다.
그림 3.14: 더 큰 L2/L3 캐시의 이점
순차적이고 효율적인 캐시 처리에서 마지막 측면은 캐시 크기다. очевид하지만 짚고 넘어갈 가치가 있다. 그림 3.14는 128바이트 원소(NPAD=15, 64비트 머신)의 Increment 벤치마크 타이밍을 보여준다. 이번에는 세 다른 머신의 측정을 본다. 첫 두 머신은 P4이고 마지막은 Core2 프로세서다. 첫 두 개는 캐시 크기가 다르다. 첫 프로세서는 32k L1d와 1M L2를 가진다. 둘째는 16k L1d, 512k L2, 2M L3를 가진다. Core2는 32k L1d와 4M L2를 가진다.
그래프에서 흥미로운 부분은 Core2가 다른 둘보다 얼마나 잘하는가도 있지만(인상적이긴 하다), 더 중요한 것은 각자의 마지막 레벨 캐시로 작업 집합을 담을 수 없어서 메인 메모리가 크게 관여하는 영역이다.
| 세트 크기 | 순차 | 랜덤 |
|---|---|---|
| L2 Hit | L2 Miss | |
| 2^20 | 88,636 | 843 |
| 2^21 | 88,105 | 1,584 |
| 2^22 | 88,106 | 1,600 |
| 2^23 | 88,104 | 1,614 |
| 2^24 | 88,114 | 1,655 |
| 2^25 | 88,112 | 1,730 |
| 2^26 | 88,112 | 1,906 |
| 2^27 | 88,114 | 2,244 |
| 2^28 | 88,120 | 2,939 |
| 2^29 | 88,137 | 4,318 |
표 3.2: 순차 및 랜덤 워크에서의 L2 히트/미스, NPAD=0
예상대로 마지막 레벨 캐시가 클수록 곡선이 L2 접근 비용에 해당하는 낮은 수준에 더 오래 머문다. 중요한 것은 이것이 제공하는 성능 이점이다. 두 번째 프로세서(조금 더 오래된)는 작업 집합 2^20 바이트에서 첫 번째 프로세서보다 두 배 빠르게 일을 수행할 수 있다. 전적으로 더 큰 마지막 레벨 캐시 크기 덕분이다. 4M L2를 가진 Core2는 더 낫다.
랜덤 워크로드에서는 큰 의미가 없을 수도 있다. 하지만 워크로드를 마지막 레벨 캐시 크기에 맞출 수 있다면 프로그램 성능이 극적으로 향상될 수 있다. 그래서 때로는 더 큰 캐시를 가진 프로세서에 추가 비용을 지불할 가치가 있다.
프로세서는 프리페치로 메인 메모리와 심지어 L2 접근 지연의 대부분을 숨길 수 있음을 보았다. 하지만 이는 메모리 접근이 예측 가능할 때만 잘 된다.
그림 3.15: 순차 vs 랜덤 읽기, NPAD=0
접근이 예측 불가능하거나 랜덤이면 상황이 다르다. 그림 3.15는 순차 접근(그림 3.10과 동일)의 원소당 시간과, 리스트 원소가 작업 집합 내에서 랜덤 분포될 때의 시간을 비교한다. 순서는 랜덤화된 연결 리스트로 정해진다. 프로세서가 데이터를 신뢰성 있게 프리페치할 방법이 없다. 우연히 메모리상 가까운 원소들이 시간상으로도 가깝게 사용될 때만 도움이 된다.
그림 3.15에서 두 가지 중요한 점이 있다. 첫째, 작업 집합이 커질수록 필요한 사이클 수가 매우 크다. 메인 메모리에 200~300 사이클로 접근할 수 있다고 하지만 여기서는 450 사이클 이상에 도달한다. 이런 현상은 이전에도 보았다(그림 3.11과 비교). 자동 프리페치가 오히려 불리하게 작동한다.
둘째, 순차 접근과 달리 곡선이 여러 평탄 구간으로 눕지 않는다. 계속 상승한다. 이를 설명하기 위해 다양한 작업 집합 크기에서 프로그램의 L2 접근을 측정할 수 있다. 결과는 그림 3.16과 표 3.2에 있다.
그림은 작업 집합이 L2보다 커질 때 캐시 미스 비율(L2 miss / L2 access)이 증가하기 시작함을 보여준다. 곡선 형태가 그림 3.15와 유사하다. 빠르게 상승했다가 약간 내려갔다가 다시 오른다. 원소당 사이클 그래프와 강한 상관이 있다. 충분히 큰 작업 집합(과 RAM)이 있다면 랜덤하게 고른 어떤 캐시 라인이 L2에 있거나 로딩 중일 확률을 임의로 작게 만들 수 있으므로 L2 미스율은 결국 100%에 근접한다.
미스율 증가만으로도 비용 일부는 설명된다. 하지만 다른 요인이 있다. 표 3.2의 L2/#Iter 열을 보면 프로그램 반복당 L2 사용 횟수가 증가한다. 각 작업 집합은 이전의 두 배 크기다. 캐시가 없다면 메인 메모리 접근도 두 배가 되기를 기대한다. 캐시와 (거의) 완벽한 예측 가능성이 있으면 순차 접근 데이터처럼 L2 사용이 완만히 증가한다. 이는 작업 집합 증가 때문일 뿐이다.
그림 3.16: L2d 미스 비율
그림 3.17: 페이지 단위 랜덤화, NPAD=7
랜덤 접근에서는 작업 집합이 두 배가 될 때 원소당 시간이 100% 이상 증가한다. 즉 작업 집합은 두 배인데 평균 접근 시간은 그 이상으로 늘어난다. 이는 TLB 미스율 증가 때문이다. 그림 3.17은 NPAD=7에서 랜덤 접근 비용을 보여주되, 랜덤화 방법을 변형했다. 정상적인 경우 전체 리스트를 한 블록으로 랜덤화(라벨 ∞)하지만, 나머지 11개 곡선은 더 작은 블록으로 랜덤화를 수행한다. 라벨 ‘60’은 60페이지(245,760바이트) 묶음마다 개별 랜덤화를 뜻하며, 다음 블록으로 넘어가기 전에 블록 안의 모든 리스트 원소를 순회한다. 이는 한 번에 사용하는 TLB 엔트리 수를 제한하는 효과가 있다.
NPAD=7의 원소 크기는 64바이트로 캐시 라인 크기와 같다. 랜덤 순서 때문에 하드웨어 프리페처가 영향이 나타날 가능성은 낮고, 나타나더라도 몇 원소 수준일 것이다. 즉 L2 미스율은 전체를 한 블록으로 랜덤화한 경우와 크게 다르지 않다. 블록 크기를 늘리면 성능은 점근적으로 한 블록 랜덤화 곡선에 접근한다. 이는 한 블록 랜덤화 케이스의 성능이 TLB 미스에 크게 영향을 받음을 의미한다. TLB 미스를 줄일 수 있으면 성능이 크게 향상된다(후에 최대 38%까지 향상되는 테스트를 볼 것이다).
3.3.3 쓰기 동작
여러 실행 컨텍스트(스레드 또는 프로세스)가 같은 메모리를 사용할 때 캐시 동작을 보기 전에 캐시 구현의 세부 하나를 살펴야 한다. 캐시는 일관적이어야 하며, 이 일관성은 사용자 수준 코드에 완전히 투명해야 한다. 커널 코드는 예외로, 때때로 캐시 플러시가 필요하다.
구체적으로 이는 캐시 라인이 수정되면 그 시점 이후 시스템의 결과가 ‘캐시가 전혀 없고 메인 메모리 위치 자체가 수정된 것’과 같아야 함을 뜻한다. 이는 두 정책으로 구현할 수 있다.
write-through 캐시는 캐시 일관성을 구현하는 가장 단순한 방법이다. 캐시 라인에 쓰면 프로세서는 즉시 메인 메모리에도 그 캐시 라인을 쓴다. 이렇게 하면 메인 메모리와 캐시가 항상 동기화된다. 캐시 라인이 교체될 때 캐시 내용은 그냥 버리면 된다. 단순하지만 빠르지 않다. 예를 들어 로컬 변수를 반복 수정하는 프로그램은 다른 어디에도 쓰이지 않고 수명이 짧을 수 있음에도 FSB에 많은 트래픽을 만든다.
write-back 정책은 더 정교하다. 여기서 프로세서는 수정된 캐시 라인을 즉시 메인 메모리에 쓰지 않는다. 대신 캐시 라인을 더티로 표시한다. 나중에 캐시에서 해당 라인이 떨어질 때 더티 비트가 그때 데이터를 버리지 말고 메모리에 쓰도록 지시한다.
write-back 캐시는 성능이 크게 좋아질 수 있으며, 그래서 괜찮은 프로세서가 있는 시스템의 대부분 메모리는 이 방식으로 캐시된다. 프로세서는 FSB의 여유 대역폭을 활용해 캐시 라인이 반드시 비워지기 전에 내용을 미리 저장할 수도 있다. 그러면 더티 비트를 클리어하고, 캐시에 공간이 필요할 때 해당 캐시 라인을 그냥 버릴 수 있다.
하지만 write-back에는 중요한 문제가 있다. 둘 이상의 프로세서(또는 코어 또는 하이퍼스레드)가 같은 메모리를 접근할 때도 두 프로세서가 항상 같은 메모리 내용을 봐야 한다. 한 프로세서에서 캐시 라인이 더티(즉, 아직 메모리에 기록되지 않음)이고, 두 번째 프로세서가 같은 메모리 위치를 읽으려 한다면 읽기는 메인 메모리에 나갈 수 없다. 대신 첫 번째 프로세서의 캐시 라인 내용이 필요하다. 다음 절에서 이것이 어떻게 구현되는지 보게 된다.
그 전에 두 가지 캐시 정책을 더 언급하자.
이 둘은 실제 RAM이 아닌 주소 공간의 특수 영역에 사용된다. 커널이 주소 범위에 대해 이 정책을 설정하고(x86에서는 MTRR: Memory Type Range Registers 사용), 나머지는 자동으로 처리된다. MTRR은 write-through와 write-back 사이를 선택하는 데도 쓸 수 있다.
write-combining은 주로 그래픽 카드 RAM 같은 장치 RAM에 쓰이는 제한적 캐시 최적화다. 장치로의 전송 비용이 로컬 RAM 접근보다 훨씬 크므로 전송 횟수를 줄이는 것이 더 중요하다. 라인에서 한 워드만 썼다고 캐시 라인 전체를 전송하는 것은 낭비인데, 다음 연산이 다음 워드를 수정할 수 있기 때문이다. 화면에서 수평으로 인접한 픽셀의 메모리도 대개 인접하므로 흔한 상황이다. 이름처럼 write-combining은 여러 쓰기 접근을 결합한 뒤 캐시 라인을 내보낸다. 이상적으로는 캐시 라인의 모든 워드를 하나씩 수정하고 마지막 워드까지 쓴 뒤에 캐시 라인이 장치로 기록된다. 이는 장치 RAM 접근을 크게 빠르게 할 수 있다.
마지막으로 uncacheable 메모리다. 이는 보통 해당 위치가 RAM으로 백업되지 않음을 뜻한다. CPU 밖의 기능을 갖도록 하드코딩된 특수 주소일 수 있다. 일반 하드웨어에서는 PCIe 같은 버스에 붙은 카드/장치로의 접근으로 변환되는 메모리 매핑 주소 범위가 흔하다. 임베디드 보드에서는 LED를 켜고 끌 수 있는 메모리 주소를 가끔 볼 수 있다. 이런 주소를 캐시하는 것은 명백히 나쁜 생각이다. LED는 디버깅/상태 보고에 쓰이며 가능한 한 빨리 보이길 원한다. PCIe 카드의 메모리는 CPU 개입 없이 바뀔 수 있으므로 캐시되면 안 된다.
3.3.4 멀티프로세서 지원
앞 절에서 멀티프로세서에서 생기는 문제를 이미 지적했다. 멀티코어 프로세서도 공유되지 않는 캐시 레벨(최소 L1d)에는 같은 문제가 있다.
한 프로세서가 다른 프로세서의 캐시에 직접 접근하도록 하는 것은 완전히 비실용적이다. 연결이 충분히 빠르지 않기 때문이다. 실용적인 대안은 필요할 때 캐시 내용을 다른 프로세서로 전송하는 것이다. 이는 같은 프로세서 내부에서 공유되지 않는 캐시에도 적용된다.
그렇다면 언제 캐시 라인 전송이 필요할까? 답은 간단하다. 한 프로세서가 다른 프로세서의 캐시에 더티로 있는 캐시 라인을 읽기나 쓰기 위해 필요로 할 때다. 하지만 프로세서는 다른 프로세서의 캐시 라인이 더티인지 어떻게 알까? 단지 다른 프로세서가 캐시 라인을 로드했다고 가정하는 것은(최선의 경우에도) 비최적이다. 보통 메모리 접근의 대부분은 읽기이며, 그 결과 캐시 라인은 더티가 아니다. 캐시 라인에 대한 프로세서 연산은 매우 빈번하므로(이 문서가 존재하는 이유), 각 쓰기마다 변경된 캐시 라인 정보를 브로드캐스트하는 것은 비실용적이다.
시간이 지나며 MESI 캐시 일관성 프로토콜(Modified, Exclusive, Shared, Invalid)이 발전했다. 이름은 MESI 프로토콜에서 캐시 라인이 가질 수 있는 네 상태에서 유래한다.
이 프로토콜은 더 단순하지만 덜 효율적인 버전에서 수년에 걸쳐 발전했다. 이 네 상태를 통해 write-back 캐시를 효율적으로 구현하면서도 여러 프로세서가 읽기 전용 데이터를 동시에 사용할 수 있다.
그림 3.18: MESI 프로토콜 전이
상태 전이는 프로세서가 다른 프로세서의 작업을 ‘듣는’, 즉 스누핑함으로써 큰 노력 없이 이뤄진다. 프로세서가 수행하는 특정 연산은 외부 핀을 통해 공표되어 캐시 처리 동작이 외부에 보인다. 관련 캐시 라인의 주소는 주소 버스에 보인다. 이하 상태 및 전이(그림 3.18) 설명에서는 언제 버스가 관여하는지도 언급한다.
초기에는 모든 캐시 라인이 비어 있으므로 Invalid다. 데이터를 쓰기 위해 캐시에 로드하면 Modified가 된다. 읽기 위해 로드하면, 다른 프로세서도 그 캐시 라인을 갖고 있는지에 따라 새 상태가 달라진다. 그렇다면 Shared, 아니면 Exclusive.
Modified 캐시 라인을 로컬에서 읽거나 쓰면 현재 캐시 내용을 사용하면 되고 상태는 변하지 않는다. 두 번째 프로세서가 이 캐시 라인을 읽으려 하면, 첫 프로세서는 자신의 캐시 내용을 두 번째 프로세서로 보내고 상태를 Shared로 바꿀 수 있다. 두 번째 프로세서로 보낸 데이터는 메모리 컨트롤러도 받아 메모리에 저장한다. 이것이 없으면 캐시 라인을 Shared로 표시할 수 없다. 두 번째 프로세서가 쓰려 한다면, 첫 프로세서는 캐시 라인 내용을 보내고 로컬 상태를 Invalid로 표시한다. 이것이 악명 높은 “소유권 요청(Request For Ownership, RFO)”이다. 마지막 레벨 캐시에서 이 연산(I→M 전이처럼)을 수행하는 것은 비교적 비싸다. write-through 캐시라면 새 캐시 라인 내용을 상위 캐시나 메인 메모리에 기록하는 시간도 더해야 하므로 비용이 더 커진다.
Shared 상태에서 로컬 프로세서가 읽으면 상태 변경이 필요 없고 캐시에서 읽기를 충족한다. 로컬에서 쓰면 캐시 라인을 사용할 수 있지만 상태는 Modified로 바뀐다. 또한 다른 프로세서의 가능한 모든 사본을 Invalid로 표시해야 하므로, 쓰기 연산은 RFO 메시지로 다른 프로세서들에게 공표돼야 한다. 두 번째 프로세서가 읽기 요청을 해도 할 일은 없다. 메인 메모리가 최신 데이터를 가지고 있고 로컬 상태도 이미 Shared다. 두 번째 프로세서가 쓰기(RFO)하면 캐시 라인은 단순히 Invalid로 표시된다. 버스 연산은 필요 없다.
Exclusive 상태는 대부분 Shared와 같지만 중요한 차이가 하나 있다. 로컬 쓰기 연산은 버스에 공표할 필요가 없다. 로컬 캐시 사본이 유일한 사본임이 알려져 있기 때문이다. 이는 큰 이점이 될 수 있으므로, 프로세서는 가능한 한 많은 캐시 라인을 Shared가 아니라 Exclusive 상태로 유지하려 한다. Shared는 그 순간 정보를 알 수 없을 때의 폴백이다. Exclusive 상태는 기능적으로는 없어도 되지만, 성능은 떨어진다. E→M 전이가 S→M보다 훨씬 빠르기 때문이다.
이 전이 설명에서 멀티프로세서 환경에서의 비용이 어디서 생기는지 분명해졌을 것이다. 캐시를 채우는 것만으로도 비싸지만 이제 RFO 메시지도 주의해야 한다. RFO 메시지를 보내야 할 때마다 느려진다.
RFO 메시지가 필요한 상황은 두 가지다.
멀티스레드/멀티프로세스 프로그램에는 항상 어느 정도 동기화가 필요하며, 이는 메모리를 이용해 구현된다. 따라서 일부 RFO 메시지는 정당하다. 그래도 가능한 한 드물게 해야 한다. 하지만 RFO 메시지의 다른 원인도 있다. 6절에서 이런 시나리오를 설명한다. 캐시 일관성 프로토콜 메시지는 시스템의 프로세서들에 배포되어야 한다. 모든 프로세서가 메시지에 응답할 기회를 가졌음이 명확해질 때까지 MESI 전이는 완료될 수 없다. 즉 가능한 가장 긴 응답 시간이 일관성 프로토콜 속도를 결정한다. {이것이 예컨대 오늘날 AMD Opteron 시스템이 3소켓 구성을 갖는 이유 중 하나다. 프로세서가 3개의 하이퍼링크만 갖고 그 중 하나가 사우스브리지 연결에 필요하므로, 각 프로세서는 정확히 한 홉 거리다.} 버스 충돌, NUMA에서의 높은 지연, 트래픽량 모두를 고려하면 불필요한 트래픽을 피해야 하는 이유가 충분하다.
둘 이상의 프로세서가 있으면 또 다른 문제가 있다. 효과는 머신별로 다르지만 원리상 항상 존재한다. FSB는 공유 자원이다. 대부분의 머신에서는 모든 프로세서가 단일 버스를 통해 메모리 컨트롤러에 연결된다(그림 2.1). 단일 프로세서가 버스를 포화시킬 수 있다면(대개 그렇다), 두 개 또는 네 개 프로세서가 같은 버스를 공유하면 각 프로세서에 할당되는 대역폭은 더 줄어든다.
그림 2.2처럼 프로세서별로 메모리 컨트롤러로 가는 버스가 따로 있어도, 메모리 모듈로 가는 버스는 여전히 존재한다. 보통은 하나의 버스이고, 확장 모델에서도 같은 메모리 모듈로의 동시 접근은 대역폭을 제한한다.
AMD 모델처럼 프로세서가 로컬 메모리를 갖는 경우에도 마찬가지다. 모든 프로세서가 로컬 메모리에 빠르게 접근할 수는 있지만, 멀티스레드/멀티프로세스 프로그램은 적어도 때때로 동기화를 위해 같은 메모리 영역을 접근해야 한다.
필요한 동기화를 구현할 수 있는 유한한 대역폭 때문에 동시성은 심각하게 제한된다. 프로그램은 서로 다른 프로세서/코어가 같은 메모리 위치에 접근하는 일을 최소화하도록 주의 깊게 설계되어야 한다. 다음 측정은 이를 비롯한 멀티스레드 코드 관련 캐시 효과를 보여줄 것이다.
서로 다른 프로세서에서 같은 캐시 라인을 동시에 사용하는 문제가 얼마나 심각한지 이해시키기 위해, 이전과 같은 프로그램에 대해 성능 그래프를 더 보자. 이번에는 여러 스레드가 동시에 실행된다. 측정하는 값은 어떤 스레드든 가장 빠른 런타임이다. 즉 모든 스레드가 끝날 때의 전체 완료 시간은 더 길다. 사용한 머신은 프로세서 4개이며 테스트는 최대 4개 스레드를 사용한다. 모든 프로세서는 메모리 컨트롤러로 가는 버스를 하나 공유하며, 메모리 모듈로 가는 버스도 하나뿐이다.
그림 3.19: 순차 읽기 접근, 다중 스레드
그림 3.19는 128바이트 엔트리(NPAD=15, 64비트 머신)의 순차 읽기 전용 접근 성능을 보여준다. 1스레드 곡선은 그림 3.11과 비슷한 형태를 기대할 수 있다. 머신이 다르므로 수치는 다르다.
이 그림에서 중요한 부분은 다중 스레드 실행 시 동작이다. 메모리를 수정하지 않으며 연결 리스트를 걷는 동안 스레드들을 동기화하지도 않는다. RFO 메시지가 필요 없고 모든 캐시 라인을 공유할 수 있음에도, 2스레드에서는 가장 빠른 스레드가 최대 18% 성능 저하, 4스레드에서는 최대 34% 저하가 보인다. 프로세서 간 캐시 라인 이동이 없으므로 이 느려짐은 두 병목(프로세서→메모리 컨트롤러 공유 버스, 메모리 컨트롤러→메모리 모듈 버스) 중 하나 또는 둘에 의해 발생한다. 작업 집합이 이 머신의 L3를 넘어서면 모든 스레드가 새 리스트 원소를 프리페치한다. 2스레드만으로도 사용 가능한 대역폭이 선형 확장(멀티스레드 페널티 없음)에 충분치 않다.
메모리를 수정하면 상황은 더 나빠진다. 그림 3.20은 순차 Increment 테스트 결과다.
그림 3.20: 순차 Increment, 다중 스레드
이 그래프는 Y축이 로그 스케일이다. 겉보기의 작은 차이에 속지 말라. 2스레드에서 약 18% 페널티가 있고, 4스레드에서는 놀랍게도 93% 페널티가 있다. 즉 4스레드에서는 프리페치 트래픽과 write-back 트래픽이 버스를 거의 포화시킨다.
로그 스케일은 L1d 범위의 결과를 보여주기 위해 사용했다. 관찰할 수 있는 것은, 1스레드 이상이 실행되면 L1d가 사실상 무력해진다는 점이다. 단일 스레드 접근 시간은 작업 집합이 L1d에 들어가지 못할 때만 20사이클을 넘는다. 하지만 여러 스레드가 실행되면 가장 작은 작업 집합에서도 즉시 그런 접근 시간이 나타난다.
문제의 한 측면은 여기서 보이지 않는다. 이 특정 테스트 프로그램으로는 측정이 어렵다. 테스트는 메모리를 수정하므로 RFO 메시지를 기대해야 하지만, 1스레드 이상에서 L2 범위에 더 높은 비용이 보이진 않는다. 이를 보려면 프로그램이 큰 메모리를 사용하고 모든 스레드가 같은 메모리를 병렬로 접근해야 하는데, 이를 달성하려면 많은 동기화가 필요하고 그 비용이 실행 시간을 지배하게 된다.
그림 3.21: 랜덤 Addnextlast, 다중 스레드
마지막으로 그림 3.21은 랜덤 접근에서 Addnextlast 테스트의 수치다. 이 그림은 주로 충격적으로 큰 수치를 보여주기 위해 제공한다. 최악의 경우 리스트 원소 하나를 처리하는 데 약 1,500 사이클이 든다. 스레드를 더 늘리는 것이 더욱 의심스럽다. 다중 스레드 효율을 표로 요약할 수 있다.
#스레드 순차 읽기 순차 Inc 랜덤 Add 2 1.69 1.69 1.54 4 2.98 2.07 1.65 표 3.3: 다중 스레드 효율
표는 그림 3.21의 세 그래프에서 가장 큰 작업 집합 크기에 대해, 2개 또는 4개 스레드를 사용했을 때의 가능한 최고 가속 비율을 보여준다. 이론적 한계는 2스레드면 2, 4스레드면 4다. 2스레드의 수치는 나쁘지 않다. 하지만 4스레드에서는 마지막 테스트 수치가 보여주듯, 2스레드를 넘어 확장할 가치가 거의 없다. 추가 이득이 미미하다. 이는 그림 3.21의 데이터를 다르게 표현하면 더 쉽게 보인다.
그림 3.22: 병렬성을 통한 속도 향상
그림 3.22의 곡선은 속도 향상 계수, 즉 단일 스레드 대비 상대 성능을 보여준다. 가장 작은 크기들은 측정이 부정확하므로 무시해야 한다. L2 및 L3 캐시 범위에서는 거의 선형 가속이 달성됨을 볼 수 있다. 거의 2와 4에 도달한다. 하지만 작업 집합을 담기엔 L3가 부족해지자마자 수치는 급락한다. 2스레드와 4스레드의 속도 향상이 동일해질 정도로(표 3.3의 네 번째 열 참조) 붕괴한다. 이것이 동일 메모리 컨트롤러를 쓰는 4CPU를 넘는 소켓의 메인보드를 거의 찾기 힘든 이유 중 하나다. 더 많은 프로세서의 머신은 다르게 만들어져야 한다(5절 참조).
이 수치는 보편적이지 않다. 어떤 경우에는 작업 집합이 마지막 레벨 캐시에 들어가도 선형 가속을 허용하지 않는다. 사실 이것이 일반적이다. 보통 스레드는 이 테스트 프로그램처럼 독립적이지 않다. 반대로 큰 작업 집합에서도 2스레드를 넘어 이득을 볼 수 있는 경우도 있다. 다만 고민이 필요하다. 6절에서 몇 가지 접근을 논의한다.
하이퍼스레드(대칭 멀티스레딩 SMT라고도 함)는 CPU가 구현하며, 개별 스레드가 진정으로 병렬 실행되지 못한다는 점에서 특수한 경우다. 레지스터 집합을 제외한 거의 모든 처리 자원을 공유한다. 개별 코어/CPU는 여전히 병렬로 동작하지만, 각 코어 안의 스레드는 이 제약을 받는다. 이론상 코어당 많은 스레드를 가질 수 있지만, 현재까지 인텔 CPU는 코어당 최대 2스레드다. CPU가 스레드를 시간 다중화(time-multiplex)한다. 하지만 이것만으로는 큰 의미가 없다. 진짜 장점은 현재 실행 중인 하이퍼스레드가 지연될 때 CPU가 다른 하이퍼스레드를 스케줄할 수 있다는 점이다. 대부분의 경우 지연은 메모리 접근 때문이다.
하이퍼스레드 코어에서 두 스레드가 실행될 때, 두 스레드의 합산 런타임이 단일 스레드 코드 런타임보다 낮을 때만 단일 스레드보다 효율적이다. 이는 서로 다른 메모리 접근의 대기 시간을 원래는 순차로 발생할 것을 겹쳐서(overlap) 가능하게 한다. 단순 계산으로 특정 가속을 얻기 위한 최소 캐시 히트율 요구를 구할 수 있다.
프로그램 실행 시간은 하나의 캐시 레벨만 가진 단순 모델로 다음처럼 근사할 수 있다([htimpact] 참조).
T_exe = N[(1-F_mem)T_proc + F_mem(G_hit T_cache + (1-G_hit)T_miss)]
각 변수는 다음을 뜻한다.
N = 명령 수 F_mem = 메모리를 접근하는 명령 비율 G_hit = 캐시 히트하는 로드 비율 T_proc = 명령당 사이클 수 T_cache = 캐시 히트 사이클 수 T_miss = 캐시 미스 사이클 수 T_exe = 프로그램 실행 시간
두 스레드를 쓰는 것이 의미 있으려면, 두 스레드 각각의 실행 시간이 단일 스레드 코드의 절반 이하여야 한다. 양변에서 유일한 변수는 캐시 히트 수다. 식을 풀어 스레드 실행이 50% 이상 느려지지 않도록 하는 최소 캐시 히트율을 구하면 그림 3.23이 된다.
그림 3.23: 가속을 위한 최소 캐시 히트율
X축은 단일 스레드 코드의 캐시 히트율 G_hit이고, Y축은 멀티스레드 코드에서 요구되는 히트율이다. 이 값은 단일 스레드 히트율보다 높을 수 없다. 그렇다면 단일 스레드 코드도 그 개선된 코드를 썼을 것이기 때문이다. 단일 스레드 히트율이 55% 미만이면 어떤 경우든 스레드를 사용해 이득을 볼 수 있다. 캐시 미스로 CPU가 충분히 놀고 있어서 두 번째 하이퍼스레드를 돌릴 여지가 있기 때문이다.
초록 영역이 목표다. 스레드 느려짐이 50% 미만이고 각 스레드 작업이 절반으로 나뉘면 합산 런타임이 단일 스레드 런타임보다 작을 수 있다. 여기의 모델 시스템(P4 하이퍼스레드 수치 사용)에서 단일 스레드 히트율이 60%인 프로그램은 듀얼 스레드에서 최소 10% 히트율이 필요하다. 보통 가능하다. 하지만 단일 스레드 히트율이 95%이면 듀얼 스레드는 최소 80% 히트율이 필요하다. 더 어렵다. 특히 하이퍼스레드의 문제는 각 하이퍼스레드가 사용할 수 있는 유효 캐시 크기(L1d뿐 아니라 실무에서는 L2 등)가 반으로 줄어든다는 점이다. 두 하이퍼스레드는 같은 캐시로 데이터를 로드한다. 두 스레드의 작업 집합이 겹치지 않으면 원래 95%였던 히트율이 반으로 깎여 요구되는 80%에 못 미칠 수 있다.
따라서 하이퍼스레드는 제한된 상황에서만 유용하다. 단일 스레드 코드의 캐시 히트율이 충분히 낮아서, 위 식과 캐시 크기 감소를 고려하더라도 새로운 히트율이 목표를 만족할 때만 의미가 있다. 그리고 실전에서 더 빠른지는 프로세서가 한 스레드의 대기 시간을 다른 스레드의 실행 시간과 충분히 겹칠 수 있는지에 달려 있다. 병렬화 오버헤드도 새로운 총 런타임에 더해야 하며, 이 추가 비용은 종종 무시할 수 없다.
6.3.4절에서는 스레드가 긴밀히 협력하고 공통 캐시를 통한 결합이 오히려 이점이 되는 기법을 볼 것이다. 프로그래머가 시간과 에너지를 들여 코드를 확장하기만 한다면 많은 상황에 적용될 수 있다.
분명히 해야 할 점은 두 하이퍼스레드가 완전히 다른 코드를 실행한다면(즉 OS가 별도 프로세스를 실행하기 위해 스레드를 별도 프로세서처럼 취급한다면) 캐시 크기는 실제로 반으로 줄고 캐시 미스가 크게 증가한다는 것이다. 이런 OS 스케줄링 관행은 캐시가 충분히 크지 않다면 의심스럽다. 머신의 워크로드가 하이퍼스레드에서 이득을 볼 수 있도록 설계된 프로세스로 구성되지 않는다면, BIOS에서 하이퍼스레드를 꺼 두는 것이 최선일 수도 있다. {하이퍼스레드를 켜 두는 또 다른 이유는 디버깅이다. SMT는 병렬 코드의 특정 종류 문제를 찾아내는 데 놀라울 정도로 유용하다.}
3.3.5 기타 세부
지금까지 주소를 태그, 세트 인덱스, 캐시 라인 오프셋의 세 부분으로 구성된다고 말했다. 그런데 실제로 어떤 주소가 사용될까? 오늘날의 관련 프로세서는 모두 프로세스에 가상 주소 공간을 제공하므로 주소는 두 종류가 있다. 가상 주소와 물리 주소.
가상 주소의 문제는 유일하지 않다는 점이다. 하나의 가상 주소는 시간에 따라 다른 물리 주소를 가리킬 수 있다. 다른 프로세스에서 같은 주소는 다른 물리 주소를 가리킬 가능성이 크다. 그렇다면 물리 주소를 쓰는 것이 항상 더 낫지 않을까?
문제는 명령이 가상 주소를 사용하며, 이를 MMU의 도움으로 물리 주소로 변환해야 한다는 점이다. 이는 비트리비얼한 연산이다. 명령 실행 파이프라인에서 물리 주소는 나중 단계에서야 얻어질 수 있다. 따라서 캐시 로직은 메모리 위치가 캐시되어 있는지 매우 빠르게 결정해야 한다. 가상 주소를 쓸 수 있다면 캐시 조회는 파이프라인 더 앞단에서 가능하고, 캐시 히트인 경우 메모리 내용을 즉시 제공할 수 있다. 결과적으로 파이프라인으로 더 많은 메모리 접근 비용을 숨길 수 있다.
프로세서 설계자들은 현재 1레벨 캐시에 가상 주소 태깅을 사용한다. 이런 캐시는 작고 큰 고통 없이 비울 수 있다. 프로세스의 페이지 테이블 트리가 바뀌면 최소한 부분적으로 캐시를 클리어할 필요가 있다. 프로세서가 변경된 가상 주소 범위를 지정하는 명령을 제공한다면 전체 플러시를 피할 수도 있다. L1i와 L1d의 지연이 낮기 때문에(~3 사이클) 가상 주소 사용은 거의 필수다.
L2, L3 등 더 큰 캐시에는 물리 주소 태깅이 필요하다. 이 캐시들은 지연이 더 크고 가상→물리 변환이 그 사이에 끝날 수 있다. 또한 캐시가 크기 때문에(플러시하면 정보 손실이 큼) 메인 메모리 접근 지연으로 리필 시간이 오래 걸리므로, 자주 플러시하는 것은 비용이 크다.
일반적으로 프로그래머가 이 캐시들의 주소 처리 세부를 알아야 할 필요는 없다. 바꿀 수 없고, 성능에 영향을 주는 요인들은 보통 피해야 하거나 높은 비용과 연관된다. 캐시 용량을 넘치는 것은 나쁘고, 대부분의 사용 캐시 라인이 같은 세트에 몰리면 모든 캐시가 일찍 문제를 겪는다. 후자는 가상 주소 캐시에서는 피할 수 있으나 물리 주소 캐시에서는 사용자 수준 프로세스가 피할 수 없다. 기억해 둘 만한 유일한 세부는 가능하면 같은 프로세스에서 동일한 물리 메모리 위치를 두 개 이상의 가상 주소에 매핑하지 말라는 것이다.
프로그래머에게 덜 흥미로운 또 다른 세부는 캐시 교체(replacement) 전략이다. 대부분의 캐시는 LRU(가장 오래 사용되지 않은 것 먼저)를 축출한다. 이는 항상 좋은 기본 전략이다. 하지만 연관도가 커지면(코어가 늘면서 앞으로 더 커질 수 있다) LRU 리스트 유지 비용이 점점 커져 다른 전략이 채택될 수도 있다.
캐시 교체에 대해 프로그래머가 할 수 있는 일은 많지 않다. 물리 주소 태그 캐시라면 가상 주소가 캐시 세트와 어떻게 대응되는지 알아낼 방법이 없다. 모든 논리 페이지의 캐시 라인이 같은 캐시 세트로 매핑되어 캐시의 상당 부분이 놀 수도 있다. 가능하다면 이런 일이 너무 자주 일어나지 않게 하는 것은 OS의 역할이다.
가상화가 등장하면서 더 복잡해졌다. 이제 OS조차 물리 메모리 할당을 제어하지 못한다. VMM(하이퍼바이저)이 물리 메모리 할당을 책임진다.
프로그래머가 할 수 있는 최선은 a) 논리 메모리 페이지를 완전히 사용하고 b) 의미 있는 범위에서 가능한 한 큰 페이지 크기를 사용하여 물리 주소를 최대한 다양화하는 것이다. 큰 페이지 크기는 다른 이점도 있지만, 이는 4절의 다른 주제다.
프로세서가 사용하는 데이터뿐 아니라 실행하는 명령도 캐시된다. 하지만 명령 캐시는 데이터 캐시보다 덜 문제가 된다. 이유는 여러 가지다.
프로그래머가 따라야 할 규칙이 몇 가지 있지만, 대부분은 도구 사용법에 대한 규칙이다. 6절에서 논의한다. 여기서는 명령 캐시의 기술적 세부만 다룬다.
CPU 코어 클록이 크게 올라 캐시(심지어 1레벨 캐시)와 코어 간 속도 차가 커지면서 CPU는 파이프라인화됐다. 즉 명령 실행이 단계로 나뉜다. 먼저 명령을 디코딩하고, 다음으로 인자를 준비하고, 마지막으로 실행한다. 이런 파이프라인은 꽤 길 수 있다(인텔 Netburst 아키텍처는 20단계 초과). 파이프라인이 길면 스톨(명령 흐름이 끊김)이 발생할 때 다시 속도를 내는 데 시간이 오래 걸린다. 스톨은 다음 명령 위치를 올바로 예측하지 못했거나, 다음 명령을 로드하는 데 시간이 너무 오래 걸릴 때(예: 메모리에서 읽어야 할 때) 발생한다.
따라서 CPU 설계자들은 분기 예측에 많은 시간과 칩 면적을 쏟아 파이프라인 스톨을 최대한 줄인다.
CISC 프로세서에서는 디코딩 단계도 시간이 걸린다. x86 및 x86-64는 특히 그렇다. 그래서 최근 프로세서는 L1i에 명령의 원시 바이트열을 캐시하는 대신 디코딩된 명령을 캐시한다. 이 경우 L1i는 “트레이스 캐시(trace cache)”라고 불린다. 트레이스 캐시는 캐시 히트 시 파이프라인의 첫 단계를 건너뛸 수 있게 해 주며, 파이프라인이 스톨했을 때 특히 좋다.
앞서 말했듯 L2 이상 캐시는 코드와 데이터를 함께 담는 통합 캐시다. 여기서는 당연히 코드가 디코딩된 형태가 아니라 바이트열 형태로 캐시된다.
최고 성능을 위해 명령 캐시와 관련된 규칙은 몇 가지뿐이다.
이 규칙은 대개 컴파일러의 코드 생성이 강제한다. 프로그래머가 할 수 있는 몇 가지는 6절에서 다룬다.
3.4.1 자기 수정 코드(Self Modifying Code)
초기의 컴퓨터 시대에는 메모리가 귀했다. 사람들은 프로그램 데이터를 위한 공간을 늘리기 위해 프로그램 크기를 줄이는 데 많은 노력을 들였다. 자주 쓰인 트릭 중 하나는 시간이 지나며 프로그램 자체를 바꾸는 것이었다. 이런 자기 수정 코드(SMC)는 오늘날에도 가끔 발견되는데, 대개 성능 이유나 보안 익스플로잇 때문이다.
SMC는 일반적으로 피해야 한다. 대체로 올바르게 실행되지만, 경계 사례에서 그렇지 않을 수 있고, 올바르게 하지 않으면 성능 문제를 만든다. 명백히 변경되는 코드는 디코딩된 명령을 담는 트레이스 캐시에 유지될 수 없다. 또한 트레이스 캐시를 쓰지 않더라도(코드가 아직 실행되지 않았거나 한동안 실행되지 않았더라도) 프로세서는 문제를 겪을 수 있다. 파이프라인에 이미 들어간 앞으로의 명령이 변경되면, 프로세서는 많은 작업을 버리고 다시 시작해야 한다. 어떤 상황에서는 프로세서 상태 대부분을 버려야 하기도 한다.
마지막으로 프로세서는 단순화와, 99.9999999%의 경우 참이기 때문에 코드 페이지가 불변이라고 가정한다. 그래서 L1i 구현은 MESI가 아니라 단순화된 SI 프로토콜을 쓴다. 즉 수정이 감지되면 많은 비관적 가정을 해야 한다.
가능하면 SMC를 피하는 것을 강력히 권장한다. 메모리는 더 이상 그렇게 희귀한 자원이 아니다. 특정 필요에 따라 한 함수를 수정하는 대신 별도 함수를 작성하는 편이 낫다. 언젠가 SMC 지원이 옵션이 되어, 이런 방식으로 코드를 수정하려는 익스플로잇 코드를 탐지할 수도 있을 것이다. SMC를 꼭 써야 한다면, L1d에 있는 데이터와 L1i에 필요한 데이터 사이 문제를 만들지 않도록 쓰기 연산이 캐시를 우회해야 한다. 이 명령에 대한 추가 정보는 6.1절을 보라.
리눅스에서는 일반 툴체인으로 빌드된 경우 모든 프로그램 코드는 쓰기 보호되므로, SMC가 있는 프로그램은 쉽게 식별된다. 프로그래머는 코드 페이지가 쓰기 가능하도록 링크 시점에 상당한 마법을 부려야 한다. 이런 일이 발생하면 현대 인텔 x86 및 x86-64 프로세서는 자기 수정 코드 사용을 세는 전용 성능 카운터를 제공한다. 이 카운터로, 권한이 완화되어 프로그램이 성공하더라도 SMC 포함 프로그램을 쉽게 알아낼 수 있다.
메모리 접근이 캐시에서 미스하면 비용이 급증함을 이미 보았다. 때로는 피할 수 없고, 실제 비용과 이를 완화할 수 있는 방법을 이해하는 것이 중요하다.
3.5.1 캐시와 메모리 대역폭
프로세서의 능력을 더 잘 이해하기 위해 최적 상황에서 사용 가능한 대역폭을 측정한다. 이 측정은 프로세서 버전 간 편차가 크므로 특히 흥미롭다. 그래서 이 절에는 여러 머신의 데이터가 들어 있다. 성능 측정 프로그램은 x86 및 x86-64의 SSE 명령을 사용해 한 번에 16바이트를 로드/스토어한다. 다른 테스트처럼 작업 집합을 1kB에서 512MB까지 늘리며, 사이클당 몇 바이트를 로드/스토어할 수 있는지 측정한다.
그림 3.24: Pentium 4 대역폭
그림 3.24는 64비트 인텔 Netburst 프로세서에서의 성능이다. 작업 집합이 L1d에 들어가는 동안 프로세서는 사이클당 16바이트를 모두 읽을 수 있다. 즉 로드 명령 하나를 사이클마다 수행한다(movaps는 한 번에 16바이트 이동). 테스트는 읽은 데이터를 사용하지 않고 읽기 명령 자체만 테스트한다. L1d가 부족해지자 성능은 6바이트/사이클 미만으로 극적으로 떨어진다. 2^18 바이트의 단계는 DTLB 캐시가 소진되어 각 새 페이지마다 추가 작업이 필요해져서다. 읽기가 순차이므로 프리페치는 접근을 완벽히 예측하고, FSB는 작업 집합 크기 전 범위에서 약 5.3바이트/사이클로 메모리 내용을 스트리밍할 수 있다. 하지만 프리페치 데이터는 L1d로 전파되지 않는다. 물론 이는 실제 프로그램에서는 절대 달성 불가능한 수치다. 실질적 한계로 생각하라.
읽기 성능보다 더 놀라운 것은 쓰기 및 복사 성능이다. 쓰기 성능은 작업 집합이 작아도 4바이트/사이클을 넘지 못한다. 이는 이 Netburst 프로세서에서 인텔이 L1d에 write-through 모드를 선택했음을 시사하며, 성능이 L2 속도에 의해 제한됨을 뜻한다. 이 때문에 겹치지 않는 두 메모리 영역 간 복사를 수행하는 copy 테스트도 크게 더 나쁘지 않다. 필요한 읽기는 훨씬 빠르며, 쓰기와 일부 겹칠 수 있다. 쓰기/복사 측정에서 가장 주목할 점은 L2도 부족해질 때의 낮은 성능이다. 0.5바이트/사이클로 떨어진다. 이는 쓰기가 읽기보다 10배 느리다는 뜻이며, 프로그램 성능을 위해 쓰기 최적화가 더 중요함을 의미한다.
그림 3.25는 같은 프로세서에서 2스레드를 실행한 결과이며, 각 스레드는 프로세서의 두 하이퍼스레드에 고정(pin)된다.
그림 3.25: 2 하이퍼스레드에서의 P4 대역폭
차이를 보여주기 위해 이전과 같은 스케일로 그래프를 표시했다. 두 동시 스레드를 측정하는 문제로 곡선은 약간 지글거린다. 결과는 예상대로다. 하이퍼스레드는 레지스터를 제외한 모든 자원을 공유하므로 각 스레드는 캐시와 대역폭을 절반만 사용할 수 있다. 대기 시간이 많아 다른 스레드에 실행 시간을 양보할 수 있음에도, 다른 스레드도 메모리를 기다려야 하므로 아무 차이가 없다. 이는 하이퍼스레드를 최악으로 사용하는 사례다.
그림 3.26: Core 2 대역폭
그림 3.24와 3.25에 비해, 인텔 Core 2 프로세서의 결과(그림 3.26과 3.27)는 상당히 다르다. 이것은 2코어이며 L2를 공유하고, L2는 P4 머신보다 4배 크다. 하지만 이는 쓰기/복사 성능 하락이 지연되는 것만 설명한다.
더 큰 차이가 있다. 읽기 성능은 작업 집합 전 범위에서 최적의 16바이트/사이클 주변을 유지한다. 2^20 바이트 이후 읽기 성능이 떨어지는 것은 DTLB가 작업 집합을 담기엔 너무 커져서다. 이런 높은 수치를 달성한다는 것은 프로세서가 데이터를 프리페치해 제때 운반하는 것뿐 아니라, 데이터를 L1d로 프리페치한다는 뜻이기도 하다.
쓰기/복사 성능도 극적으로 다르다. 프로세서는 write-through 정책이 아니다. 쓰인 데이터는 L1d에 저장되며 필요할 때만 축출된다. 이는 16바이트/사이클에 가까운 쓰기 속도를 허용한다. L1d가 부족해지면 성능이 크게 떨어진다. Netburst처럼 쓰기 성능은 읽기보다 유의미하게 낮다. 읽기 성능이 매우 높아서 그 차이는 더 커진다. L2마저 부족해지면 속도 차는 20배로 늘어난다. 하지만 이는 Core 2가 성능이 나쁘다는 뜻이 아니다. 오히려 언제나 Netburst 코어보다 빠르다.
그림 3.27: 2 스레드에서의 Core 2 대역폭
그림 3.27에서는 Core 2의 두 코어에 각각 1스레드씩 실행한다. 두 스레드는 완벽히 동기화되진 않지만 같은 메모리에 접근한다. 읽기 성능 결과는 단일 스레드와 다르지 않다. 멀티스레드 테스트에서 기대되는 약간 더 많은 지글거림이 보인다.
흥미로운 점은 L1d에 들어갈 수 있는 작업 집합 크기에서의 쓰기 및 복사 성능이다. 그림에서 보듯 성능은 마치 데이터를 메인 메모리에서 읽어야 하는 것처럼 동일하다. 두 스레드는 같은 메모리 위치를 두고 경쟁하며, 캐시 라인에 대해 RFO 메시지를 보내야 한다. 문제는 두 코어가 캐시를 공유하더라도 이 요청이 L2 속도로 처리되지 않는다는 점이다. L1d가 부족해지면 수정된 엔트리는 각 코어의 L1d에서 공유 L2로 플러시된다. 그 시점부터 성능은 크게 증가한다. 이제 L1d 미스는 L2로 충족되고, RFO 메시지는 데이터가 아직 플러시되지 않았을 때만 필요하다. 그래서 해당 작업 집합 범위에서 속도가 50% 감소하는 모습을 본다. 점근적 동작은 예상대로다. 두 코어가 같은 FSB를 공유하므로 각 코어는 FSB 대역폭의 절반만 얻어, 큰 작업 집합에서는 각 스레드 성능이 단일 스레드의 절반 정도다.
한 벤더 내 프로세서 버전 간 차이가 크므로 다른 벤더의 프로세서 성능도 살펴볼 가치가 있다. 그림 3.28은 AMD 패밀리 10h Opteron의 성능이다. 이 프로세서는 64kB L1d, 512kB L2, 2MB L3를 가진다. L3는 모든 코어가 공유한다. 결과는 그림 3.28에 있다.
그림 3.28: AMD 패밀리 10h Opteron 대역폭
가장 먼저 눈에 들어오는 것은 L1d가 충분할 때 사이클당 2명령을 처리할 수 있다는 점이다. 읽기 성능은 32바이트/사이클을 넘고, 쓰기도 18.7바이트/사이클로 높다. 하지만 읽기 곡선은 빠르게 평탄해지고 2.3바이트/사이클로 꽤 낮다. 이 테스트의 프로세서는 데이터를 프리페치하지 않거나 적어도 효율적으로 프리페치하지 못한다.
반면 쓰기 곡선은 여러 캐시 크기에 따라 성능이 변한다. 최대 성능은 L1d 전체 크기에서 달성되고, L2에서는 6바이트/사이클, L3에서는 2.8바이트/사이클, L3도 부족하면 0.5바이트/사이클까지 내려간다. L1d 성능은 (오래된) Core 2보다 좋고, L2 접근은 (Core 2가 더 큰 캐시임에도) 비슷하며, L3와 메인 메모리 접근은 더 느리다.
복사 성능은 읽기 또는 쓰기 성능보다 좋을 수 없다. 그래서 초기에는 읽기 성능이 지배하고 나중에는 쓰기 성능이 지배하는 곡선을 본다.
Opteron의 멀티스레드 성능은 그림 3.29에 있다.
그림 3.29: 2 스레드에서의 AMD 10h 대역폭
읽기 성능은 대체로 영향을 받지 않는다. 각 스레드의 L1d와 L2는 이전처럼 동작하고, L3는 여기서도 프리페치가 별로 좋지 않다. 두 스레드는 이 목적에서는 L3에 과도한 부담을 주지 않는다. 이 테스트에서의 큰 문제는 쓰기 성능이다. 스레드들이 공유하는 모든 데이터는 L3를 거쳐야 한다. 이 공유는 비효율적으로 보이며, L3 크기가 전체 작업 집합을 담을 수 있어도 비용이 L3 접근보다 크게 높다. 이 그래프를 그림 3.27과 비교하면 Core 2의 두 스레드는 적절한 작업 집합 범위에서 공유 L2 속도로 동작한다. Opteron은 아주 좁은 작업 집합 범위에서만 이 수준에 도달하며, 그마저도 Core 2의 L2보다 느린 L3 속도에 불과하다.
3.5.2 임계 워드 로드(Critical Word Load)
메인 메모리에서 캐시로의 전송은 캐시 라인보다 작은 블록 단위로 이뤄진다. 오늘날은 한 번에 64 비트 가 전송되고 캐시 라인 크기는 64 또는 128 바이트 이다. 즉 캐시 라인당 8회 또는 16회 전송이 필요하다.
DRAM 칩은 64비트 블록을 버스트 모드로 전송할 수 있다. 이는 추가 명령(및 지연) 없이 캐시 라인을 채울 수 있다. 프로세서가 캐시 라인을 프리페치한다면 아마 이것이 최선의 동작 방식이다.
데이터 또는 명령 캐시 접근이 미스하면(즉 처음 사용하는 데이터라서 강제 미스이거나, 캐시 용량 제한으로 라인이 축출되어 용량 미스가 발생한 경우) 상황이 다르다. 프로그램이 계속 진행하려면 캐시 라인 내부의 특정 워드가 필요할 수 있는데, 그 워드가 캐시 라인의 첫 워드가 아닐 수 있다. 버스트 모드와 DDR 전송을 쓰더라도 개별 64비트 블록은 눈에 띄게 다른 시점에 도착한다. 각 블록은 이전 블록보다 4 CPU 사이클 이상 늦게 도착한다. 프로그램이 계속하기 위해 필요한 워드가 라인의 8번째라면, 첫 워드가 도착한 뒤에도 추가로 30 사이클 이상을 기다려야 한다.
반드시 그럴 필요는 없다. 메모리 컨트롤러는 캐시 라인의 워드를 다른 순서로 요청할 수 있다. 프로세서는 프로그램이 기다리는 워드, 즉 임계 워드(critical word) 가 무엇인지 알려줄 수 있고, 메모리 컨트롤러는 이 워드를 먼저 요청할 수 있다. 그 워드가 도착하면, 캐시 라인의 나머지가 도착해 아직 캐시가 일관된 상태가 아니어도 프로그램은 계속할 수 있다. 이 기법을 Critical Word First & Early Restart라고 한다.
요즘 프로세서는 이 기법을 구현하지만, 불가능한 상황도 있다. 프로세서가 데이터를 프리페치하면 임계 워드를 알 수 없다. 프리페치가 진행 중인 동안 프로세서가 캐시 라인을 요청해야 하면, 순서를 바꿀 수 없어 임계 워드가 도착할 때까지 기다려야 한다.
그림 3.30: 캐시 라인 끝의 임계 워드
이 최적화가 있어도 임계 워드의 캐시 라인 내 위치는 중요하다. 그림 3.30은 순차 및 랜덤 접근에서 Follow 테스트를 보여준다. 포인터를 첫 워드에 두는 경우와 마지막 워드에 두는 경우의 느려짐을 보여준다. 원소 크기는 캐시 라인 크기인 64바이트다. 수치는 꽤 noisy하지만 L2가 작업 집합을 담지 못하기 시작하면 임계 워드가 끝에 있는 경우가 약 0.7% 더 느리다. 순차 접근이 더 영향을 받는 것으로 보이는데, 이는 다음 캐시 라인 프리페치가 진행 중일 때 발생할 수 있는 앞서 언급한 문제와 일치한다.
3.5.3 캐시 배치(Cache Placement)
하이퍼스레드, 코어, 프로세서에 대한 캐시 배치는 프로그래머가 제어할 수 없다. 하지만 프로그래머는 스레드를 어디서 실행할지 결정할 수 있고, 그러면 사용된 CPU에 캐시가 어떻게 연결되는지가 중요해진다.
여기서는 어떤 코어에서 스레드를 실행할지의 세부를 다루지 않는다. 대신 스레드 affinity를 설정할 때 프로그래머가 고려해야 할 아키텍처 세부만 설명한다.
하이퍼스레드는 정의상 레지스터 집합을 제외한 모든 것을 공유한다. 여기에는 L1 캐시도 포함된다.
진짜 재미는 프로세서의 개별 코어에서 시작된다. 각 코어는 최소한 자신의 L1 캐시를 가진다. 그 밖의 공유 방식은 오늘날에도 다양하다.
프로세서 벤더들의 홍보 자료에는 각 모델의 장점이 많이 쓰여 있다. 분리된 L2는 코어들이 처리하는 작업 집합이 겹치지 않을 때 이점이 있다. 이는 단일 스레드 프로그램에 잘 맞는다. 여전히 흔한 현실이므로 나쁘지 않다. 하지만 항상 어느 정도는 겹친다. 캐시에는 공통 런타임 라이브러리의 가장 활발히 쓰이는 부분이 들어가므로, 캐시 공간 일부가 낭비된다.
인텔의 듀얼코어처럼 L1을 제외한 모든 캐시를 완전히 공유하면 큰 이점이 있을 수 있다. 두 코어에서 처리하는 작업 집합이 많이 겹치면 총 사용 가능한 캐시 메모리가 늘어나고 성능 저하 없이 더 큰 작업 집합을 다룰 수 있다. 작업 집합이 겹치지 않으면 인텔의 Advanced Smart Cache 관리가 한 코어가 캐시를 독점하지 않도록 막아야 한다.
하지만 두 코어가 각각 캐시의 절반 정도를 사용한다면 마찰이 생긴다. 캐시는 두 코어의 사용을 계속 저울질해야 하고, 재균형 과정에서의 축출이 나쁜 선택일 수 있다. 문제를 보기 위해 또 다른 테스트 프로그램 결과를 보자.
그림 3.31: 두 프로세스에서의 대역폭
테스트 프로그램은 하나의 프로세스가 SSE로 2MB 메모리 블록을 계속 읽거나 쓰게 한다. 2MB는 이 Core 2 프로세서의 L2 캐시 크기 4MB의 절반이기 때문에 선택했다. 이 프로세스는 한 코어에 고정된다. 두 번째 프로세스는 다른 코어에 고정되며, 가변 크기의 메모리 영역을 읽고 쓴다. 그래프는 읽거나 쓰는 바이트/사이클 수를 보여준다. 네 가지 그래프는 두 프로세스의 읽기/쓰기 조합 각각을 나타낸다. read/write 그래프는 2MB 작업 집합으로 쓰기를 수행하는 백그라운드 프로세스와, 가변 작업 집합으로 읽기를 하는 측정 프로세스의 조합이다.
그래프에서 흥미로운 부분은 2^202^23 바이트 구간이다. 만약 두 코어의 L2 캐시가 완전히 분리되어 있다면 네 테스트 모두 2^212^22 바이트, 즉 L2가 소진될 때 성능이 떨어질 것으로 예상할 수 있다. 하지만 그림 3.31에서는 그렇지 않다. 백그라운드 프로세스가 쓰기를 수행하는 경우가 특히 두드러진다. 성능은 작업 집합이 1MB에 도달하기도 전에 악화되기 시작한다. 두 프로세스는 메모리를 공유하지 않으므로 RFO 메시지를 만들지 않는다. 이는 순수한 캐시 축출 문제다. 스마트 캐시 처리가 문제를 보이며, 코어당 체감 캐시 크기가 사용 가능한 2MB/코어가 아니라 1MB에 더 가깝다. 코어 간 공유 캐시가 앞으로도 유지된다면, 스마트 캐시 알고리즘이 개선되길 바랄 뿐이다.
2개의 L2를 가진 쿼드코어는 상위 캐시가 도입되기 전의 임시방편이었다. 이 설계는 분리 소켓의 듀얼코어 대비 큰 성능 이점이 없다. 두 코어는 외부에서 FSB로 보이는 같은 버스로 통신한다. 특별히 빠른 데이터 교환 경로가 없다.
멀티코어 프로세서 캐시 설계의 미래는 더 많은 계층에 있다. AMD 10h가 시작점이다. 하위 레벨 캐시가 코어 일부만 공유하는 방식이 계속될지는 지켜봐야 한다. 자주 쓰이고 고속인 캐시는 많은 코어 간 공유가 불가능하므로 추가 캐시 레벨이 필요하다. 성능에 영향을 주기 때문이다. 또한 큰 캐시와 높은 연관도가 필요하다. 캐시 크기와 연관도 모두 공유하는 코어 수에 따라 스케일해야 한다. 큰 L3 캐시와 적당한 L2 캐시를 쓰는 것은 합리적 절충이다. L3는 느리지만 이상적으로는 L2만큼 자주 쓰이지 않는다.
프로그래머에게 이런 다양한 설계는 스케줄링 결정의 복잡성을 의미한다. 최선의 성능을 위해 워크로드와 머신 아키텍처 세부를 알아야 한다. 다행히 머신 아키텍처를 알아내는 지원이 있다. 관련 인터페이스는 뒤에서 소개한다.
3.5.4 FSB 영향
FSB는 머신 성능에서 중심적 역할을 한다. 캐시 내용은 메모리로의 연결이 허용하는 만큼만 빠르게 저장/로드될 수 있다. 이를 보여주기 위해 메모리 모듈 속도만 다른 두 머신에서 프로그램을 실행해 보자. 그림 3.32는 64비트 머신에서 NPAD=7로 Addnext0 테스트(다음 원소의 pad[0] 값을 자기 pad[0]에 더함) 결과를 보여준다. 두 머신 모두 인텔 Core 2 프로세서이며, 첫 번째는 667MHz DDR2, 두 번째는 800MHz 모듈(20% 증가)을 쓴다.
그림 3.32: FSB 속도의 영향
수치는 큰 작업 집합에서 FSB가 크게 스트레스 받을 때 실제로 큰 이득이 있음을 보여준다. 이 테스트에서 최대 성능 증가가 18.2%로 측정되었는데, 이론적 최대치에 가깝다. 즉 더 빠른 FSB는 큰 보상을 줄 수 있다. 작업 집합이 캐시에 들어갈 때는 중요하지 않다(이 프로세서는 4MB L2). 하지만 시스템의 작업 집합은 동시에 실행되는 모든 프로세스가 필요로 하는 메모리로 구성된다는 점을 기억해야 한다. 따라서 훨씬 작은 프로그램들로도 4MB 이상의 메모리를 쉽게 초과할 수 있다.
오늘날 인텔 일부 프로세서는 최대 1,333MHz FSB를 지원하며, 이는 추가 60% 증가를 의미한다. 미래에는 더 높은 속도가 나올 것이다. 속도가 중요하고 작업 집합이 크다면, 빠른 RAM과 높은 FSB 속도는 충분히 돈값을 한다. 다만 주의해야 한다. 프로세서가 더 높은 FSB를 지원하더라도 메인보드/노스브리지가 지원하지 않을 수 있다. 사양을 확인하는 것이 중요하다.
파트 3 (가상 메모리)로 계속.
| 이 글의 인덱스 항목 |
|---|
| GuestArticles |
