CPU 캐시의 역할과 구조, 계층과 연관도, 일관성 프로토콜(MESI), 프리페치·TLB·대역폭 이슈, 하이퍼스레딩과 멀티코어에서의 성능 영향 및 측정까지, 현대 시스템에서 캐시를 이해하고 효율적으로 사용하는 방법을 다룬다.
우리는 마케팅을 못합니다 인정합니다. 마케팅은 우리의 강점이 아닙니다. 우리의 강점은 리눅스 세계에서 무슨 일이 일어나는지 개발자, 관리자, 자유소프트웨어 지지자들이 의존하는 유형의 글을 쓰는 것입니다. 우리가 이 일을 계속할 수 있도록, 그리고 마케팅을 잘 하게 될 필요가 없도록, 오늘 바로 구독해 주세요: https://lwn.net/Promo/nsn-bad/subscribe
[편집자 주: 이것은 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 용량을 넘어서고 보조 저장장치(예: 하드디스크) 접근 비용이 존재하는 현실에서는 두 번째 선택지가 항상 승리합니다. 문제는 보조 저장장치, 보통 하드디스크의 속도인데, 스왑된 작업 집합 일부를 담아야만 합니다. 이런 디스크 접근은 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 메모리). 이것 자체는 문제가 아닙니다. 작업 집합(현재 처리 중인 데이터 집합)이 캐시 크기보다 작으면 상관없습니다. 하지만 컴퓨터가 큰 주메모리를 갖는 데는 이유가 있습니다. 작업 집합은 캐시보다 클 가능성이 큽니다. 특히 여러 프로세스를 동시에 실행하는 시스템에서는 작업 집합 크기가 개별 프로세스와 커널 크기의 합이 되기 쉽습니다.
제한된 캐시 크기를 다루려면, 언제 무엇을 캐시할지 결정하는 좋은 전략이 필요합니다. 작업 집합의 모든 데이터가 정확히 같은 시점에 사용되는 것은 아니므로, 캐시의 일부 데이터를 다른 데이터로 일시적으로 대체할 수 있습니다. 그리고 아예 데이터가 필요해지기 전에 이 작업을 할 수도 있습니다. 이런 프리페치는 프로그램 실행과 비동기적으로 일어나므로 주메모리 접근 비용의 일부를 제거할 수 있습니다. 이 모든 기법 등으로 캐시를 실제보다 크게 보이게 만들 수 있습니다. 이 내용은 3.3절에서 논의합니다. 이런 모든 기법을 활용한 뒤에는 프로그래머가 프로세서를 도와야 합니다. 그 방법은 6장에서 설명합니다.
CPU 캐시 구현의 기술적 세부로 들어가기 전에, 일부 독자에게는 캐시가 현대 컴퓨터 시스템의 “큰 그림” 속에서 어떻게 자리 잡는지 좀 더 자세히 보는 것이 도움이 될 수 있습니다.
그림 3.1: 최소 캐시 구성
그림 3.1은 최소 캐시 구성을 보여줍니다. 이는 CPU 캐시를 처음 도입한 초기 시스템의 아키텍처에 해당합니다. CPU 코어는 더 이상 주메모리에 직접 연결되지 않습니다. {그보다 더 초기 시스템에서는 캐시가 CPU와 주메모리처럼 시스템 버스에 그냥 붙어 있었습니다. 이건 제대로 된 해결책이라기보다 편법에 가까웠습니다.} 모든 load/store는 캐시를 통과해야 합니다. CPU 코어와 캐시 사이의 연결은 특별한 고속 연결입니다. 단순화된 표현에서, 주메모리와 캐시는 시스템 버스에 연결되고, 이 버스는 시스템의 다른 구성요소와의 통신에도 쓰입니다. 우리는 시스템 버스를 오늘날 사용하는 이름인 “FSB”로 소개했습니다(2.2절 참조). 이 절에서는 노스브리지는 무시합니다. CPU(들)와 주메모리의 통신을 돕기 위해 존재한다고 가정합니다.
수십 년 동안 컴퓨터는 폰 노이만(von Neumann) 아키텍처를 사용해 왔지만, 코드와 데이터를 위한 캐시를 분리하는 것이 유리하다는 것이 경험적으로 밝혀졌습니다. 인텔은 1993년부터 코드/데이터 캐시를 분리해 왔고, 되돌아보지 않았습니다. 코드와 데이터에 필요한 메모리 영역은 서로 거의 독립적이어서, 독립 캐시가 더 잘 작동합니다. 최근에는 또 다른 장점이 부각되었습니다. 가장 흔한 프로세서에서 명령어 디코딩 단계는 느립니다. 디코딩된 명령어를 캐시에 저장하면, 특히 분기 예측 실패나 예측 불가능한 분기로 파이프라인이 비었을 때 실행을 가속할 수 있습니다.
캐시 도입 직후 시스템은 더 복잡해졌습니다. 캐시와 주메모리의 속도 차이가 다시 커져서, 더 크고 느린 2차 캐시를 추가했습니다. 1차 캐시의 크기만 키우는 것은 경제적으로 불가능했습니다. 오늘날에는 심지어 3차 캐시까지 갖춘 머신이 흔합니다. 이런 프로세서를 장착한 시스템은 그림 3.2와 같습니다. 단일 CPU 내 코어 수가 증가함에 따라 캐시 계층 수는 앞으로 더 늘어날 수 있습니다.
그림 3.2: 3차 캐시가 있는 프로세서
그림 3.2는 3계층 캐시를 보여주며, 이후 문서에서 사용할 명명법을 소개합니다. L1d는 1차 데이터 캐시, L1i는 1차 명령 캐시 등입니다. 이것은 개략도이며, 실제 데이터 흐름이 코어에서 주메모리로 갈 때 반드시 상위 캐시를 모두 거칠 필요는 없습니다. CPU 설계자들은 캐시 인터페이스 설계에 많은 자유를 가집니다. 프로그래머에게는 이런 설계 선택이 보이지 않습니다.
또한, 오늘날 프로세서는 여러 코어를 가질 수 있고 각 코어는 여러 “스레드”를 가질 수 있습니다. 코어와 스레드의 차이는, 별도의 코어는 (거의 {초기 멀티코어 프로세서는 2차 캐시도 분리되고 3차 캐시는 없었습니다.}) 모든 하드웨어 자원의 별도 사본을 갖는 반면, 스레드는 거의 모든 자원을 공유한다는 점입니다. 인텔의 스레드 구현은 스레드마다 분리된 레지스터만을 갖는데, 그마저도 제한적이며 일부 레지스터는 공유합니다. 현대 CPU의 전체 그림은 그림 3.3과 같습니다.
그림 3.3: 다중 프로세서, 다중 코어, 다중 스레드
이 그림에서 우리는 두 개의 프로세서를 보며, 각 프로세서에는 두 개의 코어가 있고, 각 코어에는 두 개의 스레드가 있습니다. 스레드는 1차 캐시를 공유합니다. 코어(더 짙은 회색으로 음영 처리됨)는 각각 독립적인 1차 캐시를 갖습니다. CPU의 모든 코어는 상위 캐시를 공유합니다. 두 프로세서(더 옅은 회색의 두 큰 상자)는 물론 캐시를 공유하지 않습니다. 이는 특히 멀티프로세스·멀티스레드 애플리케이션의 캐시 효과를 논의할 때 중요합니다.
캐시 사용의 비용과 이득을 이해하려면, 2장에서의 머신 아키텍처와 RAM 기술에 대한 지식을 앞 절의 캐시 구조와 결합해야 합니다.
기본적으로 CPU 코어가 읽거나 쓰는 모든 데이터는 캐시에 저장됩니다. 캐시할 수 없는 메모리 영역도 있지만, 이는 OS 구현자만 신경 쓰면 되는 것이고 응용 프로그래머에게는 보이지 않습니다. 특정 캐시를 고의로 우회(bypass)할 수 있는 명령도 있습니다. 이는 6장에서 다룹니다.
CPU가 한 데이터 워드를 필요로 하면 캐시를 먼저 탐색합니다. 물론 캐시는 전체 주메모리의 내용을 담을 수 없습니다(그랬다면 캐시가 필요 없겠죠). 하지만 모든 메모리 주소는 캐시 가능하므로, 각 캐시 엔트리는 주메모리의 데이터 워드 주소를 태그(tag)로 붙입니다. 이렇게 하면 특정 주소로의 읽기/쓰기 요청이 태그 일치로 캐시를 찾을 수 있습니다. 여기서 주소는 캐시 구현에 따라 가상 주소일 수도 있고 물리 주소일 수도 있습니다.
태그는 실제 메모리 데이터 외에 추가 공간을 필요로 하므로, 캐시의 최소 단위를 워드로 하는 것은 비효율적입니다. x86에서 32비트 워드 하나를 캐시에 담을 때 태그가 32비트 이상 필요할 수 있습니다. 게다가 캐시는 공간 지역성을 전제로 하므로, 이를 고려하지 않는 것도 좋지 않습니다. 이웃한 메모리는 함께 사용될 가능성이 높으므로 함께 캐시에 로드하는 게 좋습니다. 2.2.1절에서 배운 것처럼, RAM 모듈은 새로운 CAS나 RAS 신호 없이 연속된 많은 워드를 전송할 때 훨씬 효율적입니다. 그래서 캐시에 저장되는 항목은 단일 워드가 아니라, 여러 연속 워드로 이루어진 “라인”입니다. 초기 캐시는 캐시 라인이 32바이트였고, 현재 표준은 64바이트입니다. 메모리 버스 폭이 64비트라면 캐시 라인당 8번 전송이 필요합니다. DDR은 이 전송 모드를 효율적으로 지원합니다.
프로세서가 메모리 내용을 필요로 하면 전체 캐시 라인이 L1d로 로드됩니다. 각 캐시 라인의 메모리 주소는 캐시 라인 크기에 따라 주소 값을 마스킹하여 계산합니다. 64바이트 캐시 라인이라면 하위 6비트를 0으로 만듭니다. 버린 비트는 캐시 라인의 오프셋으로 쓰입니다. 남은 비트는 어떤 경우에는 캐시의 위치와 태그로 사용됩니다. 실제로 주소 값은 세 부분으로 나뉩니다. 32비트 주소의 경우 대략 다음과 같습니다:
캐시 라인 크기가 2^O이면 하위 O 비트가 캐시 라인 내 오프셋에 쓰입니다. 그 다음 S 비트는 “캐시 세트(cache 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의 캐시가 서로 독립적으로 작동할 수 없습니다. 모든 프로세서는 언제나 동일한 메모리 내용을 봐야 합니다. 이 일관된 메모리 관점의 유지가 “캐시 일관성(coherency)”입니다. 만약 프로세서가 자기 캐시와 주메모리만 본다면, 다른 프로세서의 더티 캐시 라인 내용은 볼 수 없습니다. 한 프로세서의 캐시에 다른 프로세서가 직접 접근하도록 제공하는 것은 엄청나게 비싸고 큰 병목이 됩니다. 대신, 프로세서는 다른 프로세서가 특정 캐시 라인을 읽거나 쓰려고 할 때 이를 감지(snoop)합니다.
만약 쓰기 접근이 감지되고, 로컬 프로세서가 그 캐시 라인의 클린(clean) 사본을 갖고 있다면, 그 캐시 라인은 무효(invalid)로 표시됩니다. 이후 참조는 다시 로드가 필요합니다. 다른 CPU의 읽기 접근은 무효화를 요구하지 않습니다. 여러 클린 사본은 동시에 존재해도 괜찮습니다.
더 정교한 캐시 구현은 또 다른 가능성을 허용합니다. 다른 프로세서가 읽거나 쓰려는 캐시 라인이, 첫 번째 프로세서의 캐시에서 현재 더티로 표시되어 있다면, 다른 조치가 필요합니다. 이 경우 주메모리는 최신 상태가 아니므로, 요청한 프로세서는 첫 번째 프로세서의 캐시 라인 내용을 받아야 합니다. 스누핑을 통해 첫 번째 프로세서는 이 상황을 알아차리고 자동으로 요청 프로세서에 데이터를 보냅니다. 이 동작은 주메모리를 우회하지만, 어떤 구현에서는 메모리 컨트롤러가 이 직접 전송을 감지해 갱신된 캐시 라인 내용을 주메모리에 저장해야 합니다. 접근이 쓰기라면 첫 번째 프로세서는 로컬 캐시 라인 사본을 무효화합니다.
시간이 지나며 여러 캐시 일관성 프로토콜이 개발되었습니다. 가장 중요한 것은 MESI이며, 3.3.4절에서 소개합니다. 요점을 몇 가지 규칙으로 요약하면 다음과 같습니다:
이 규칙이 유지된다면, 프로세서는 멀티프로세서 시스템에서도 캐시를 효율적으로 사용할 수 있습니다. 필요한 것은 서로의 쓰기 접근을 모니터링하고 그 주소를 로컬 캐시의 주소와 비교하는 것입니다. 다음 절에서는 구현 세부와 특히 비용에 대해 더 자세히 다룹니다.
마지막으로, 캐시 히트와 미스의 비용에 대한 감을 드려야 합니다. 인텔이 펜티엄 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의 거듭제곱으로 표시합니다.
그래프에는 세 개의 뚜렷한 계단이 보입니다. 놀랄 일은 아닙니다. 해당 프로세서에는 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) 캐시”라고 합니다. 캐시 라인에 접근하려면 프로세서 코어는 모든 캐시 라인의 태그를 요청된 주소의 태그와 비교해야 합니다. 태그는 캐시 라인 오프셋이 아닌 주소의 전체 부분으로 구성됩니다(즉, 3.2절의 그림에서 S가 0임을 의미).
이런 캐시도 있긴 하지만, 오늘날 사용되는 L2 크기를 보면 비현실적임을 알 수 있습니다. 4MB 캐시에 64B 캐시 라인이면 65,536개의 엔트리가 있습니다. 적절한 성능을 내려면 캐시 로직은 단 몇 사이클 안에 주어진 태그와 일치하는 엔트리를 이 모든 엔트리에서 찾아내야 합니다. 이를 구현하는 수고는 막대합니다.
그림 3.5: 완전 연관 캐시 개략
각 캐시 라인마다 큰 태그(주: S=0)를 비교하는 비교기(comparator)가 필요합니다. 각 연결 옆의 문자 표기는 비트 폭을 나타냅니다. 표기가 없으면 1비트 선입니다. 각 비교기는 두 개의 T비트 값을 비교해야 합니다. 그런 다음 결과에 따라 적절한 캐시 라인 내용을 선택해 제공합니다. 이를 위해 캐시 버킷 수만큼의 O비트 데이터 선을 병합해야 합니다. 단일 비교기를 구현하는 데 필요한 트랜지스터 수는 큽니다. 특히 매우 빨라야 해서, 반복 비교기는 쓸 수 없습니다. 비교기 수를 줄이려면 태그를 반복적으로 비교해야 하는데, 속도가 너무 느려져 적절하지 않습니다.
완전 연관 캐시는 작은 캐시에서는 실용적입니다(예: 일부 인텔 프로세서의 TLB 캐시는 완전 연관). 하지만 그 캐시는 매우 작습니다. 많아야 수십 엔트리 수준입니다.
L1i, L1d, 상위 캐시에는 다른 접근이 필요합니다. 탐색을 제한할 수 있습니다. 가장 극단의 제한은 각 태그가 정확히 하나의 캐시 엔트리에 매핑되는 것입니다. 계산은 간단합니다. 4MB/64B 캐시로 65,536 엔트리를 직접 주소화하려면 주소의 비트 6~21(16비트)을 사용합니다. 하위 6비트는 캐시 라인 내 인덱스입니다.
그림 3.6: 직접 사상 캐시 개략
이런 “직접 사상(direct-mapped) 캐시”는 그림 3.6에서 보듯 빠르고 구현이 비교적 쉽습니다. 정확히 하나의 비교기, 하나의 멀티플렉서(이 도표에서는 태그와 데이터를 분리해 두 개로 보이지만 설계의 본질적 요구는 아닙니다), 그리고 유효한 캐시 라인 내용만 선택하는 약간의 로직이 필요합니다. 비교기는 속도 요구로 복잡하지만 하나만 있으면 되므로 더 빠르게 만드는 데 자원을 쓸 수 있습니다. 진짜 복잡도는 멀티플렉서에 있습니다. 단순한 멀티플렉서의 트랜지스터 수는 캐시 라인 수 N에 대해 O(log N)로 증가합니다. 이는 감당 가능하지만 느려질 수 있습니다. 이 경우 멀티플렉서에 더 많은 트랜지스터를 투입해 일부 작업을 병렬화하고 속도를 높일 수 있습니다. 전체 트랜지스터 수는 캐시 크기가 커져도 천천히 증가하므로 매력적인 해결책입니다. 그러나 단점이 있습니다. 프로그램이 사용하는 주소가 직접 사상에 쓰이는 비트에 대해 고르게 분포할 때만 잘 작동합니다. 그렇지 않은 경우가 보통이며, 일부 캐시 엔트리는 과도하게 사용되어 반복적으로 퇴출되고, 다른 엔트리는 거의 사용되지 않거나 비어 있게 됩니다.
그림 3.7: 세트 연관 캐시 개략
이 문제는 캐시를 “세트 연관(set associative)”으로 만들어 해결할 수 있습니다. 세트 연관 캐시는 완전 연관과 직접 사상 캐시의 장점을 결합해 단점 대부분을 피합니다. 그림 3.7은 세트 연관 캐시의 설계를 보여줍니다. 태그와 데이터 저장소는 주소로 선택되는 세트로 나뉘며, 이는 직접 사상과 유사합니다. 하지만 각 세트 값마다 캐시에는 하나가 아니라 소수의 값이 저장됩니다. 세트의 모든 멤버 태그를 병렬로 비교하며, 이는 완전 연관 캐시의 동작과 유사합니다.
결과는, 불운하거나 의도적으로 같은 세트 번호를 갖는 주소를 선택해도 쉽게 무력화되지 않고, 동시에 캐시 크기가 병렬로 구현 가능한 비교기 수에 의해 제한되지 않는 캐시입니다. 캐시가 커져도(이 그림에서) 열(column) 수만 증가하고, 행(row) 수는 증가하지 않습니다. 행 수는 캐시의 연관도를 증가시킬 때만 늘어납니다. 오늘날 프로세서는 L2 캐시 이상에서 최대 16웨이 연관도를 사용합니다. L1 캐시는 보통 8웨이로 충분합니다.
| 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웨이 세트 연관을 가정하면, 캐시는 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웨이 세트 연관으로 가면 캐시 미스가 거의 44% 줄어듭니다. 세트 연관 캐시는 직접 사상 캐시보다 더 많은 작업 집합을 캐시에 유지할 수 있게 합니다.
문헌에서는 연관도를 도입하면 캐시 크기를 두 배로 늘린 것과 같은 효과가 있다고 읽을 수도 있습니다. 4MB에서 8MB로의 점프에서 보듯, 극단적 경우에 이는 사실입니다. 하지만 연관도를 계속 두 배로 늘린다고 항상 그런 것은 아닙니다. 데이터에서 보듯, 연속적인 이득은 훨씬 작습니다. 그렇다고 효과를 완전히 무시해서는 안 됩니다. 예제 프로그램의 최대 메모리 사용량은 5.6MB입니다. 따라서 8MB 캐시에서는 동일 세트를 두 번보다 더 많이 사용하는 경우가 많지 않을 것입니다. 작업 집합이 더 크다면, 작은 캐시 크기에서 보듯 연관도의 이점이 더 커질 수 있습니다.
일반적으로, 단일 스레드 작업에서는 캐시 연관도를 8 이상으로 올려도 효과가 크지 않은 듯합니다. 그러나 공유 L2를 사용하는 멀티코어 프로세서가 도입되면서 상황이 바뀝니다. 사실상 두 프로그램이 같은 캐시를 두드리게 되어, 실질적으로 연관도가 반으로 줄어듭니다(쿼드코어는 1/4). 따라서 코어 수가 늘어남에 따라 공유 캐시의 연관도도 증가할 것으로 예상할 수 있습니다. 연관도를 더 늘리기 어려워질 때(16웨이 세트 연관도도 이미 어렵습니다) 프로세서 설계자는 공유 L3 캐시를 도입해야 하고, L2는 일부 코어 집합이 공유하는 형태로 갈 수 있습니다.
그림 3.8에서 또 하나 살펴볼 수 있는 효과는 캐시 크기 증가가 성능을 어떻게 돕는가입니다. 이 데이터는 작업 집합 크기를 모르면 해석할 수 없습니다. 주메모리만큼 큰 캐시는 당연히 더 좋은 결과를 주므로, 일반적으로 측정 가능한 이득의 최대 캐시 크기에 제한은 없습니다.
앞서 언급했듯, 작업 집합의 최대 크기는 5.6MB입니다. 이는 이득이 있는 캐시 최대 크기에 대한 절대 수치를 주지는 않지만, 추정에는 도움이 됩니다. 문제는 사용된 메모리가 모두 연속적이지 않다는 점입니다. 따라서 16MB 캐시에 5.6MB 작업 집합이라도 충돌이 있습니다(직접 사상 16MB보다 2웨이 연관 16MB가 더 나은 점을 보세요). 그러나 동일 작업에서 32MB 캐시의 이득은 미미할 것이라는 베팅은 안전합니다. 물론 작업 집합이 늘지 않는다는 보장은 없습니다. 워크로드는 시간이 지나면 커지고, 캐시 크기도 그래야 합니다. 머신을 구매할 때, 비용을 지불할 캐시 크기를 선택해야 한다면, 작업 집합 크기를 측정할 가치가 있습니다. 왜 중요한지는 그림 3.10의 도표들을 보면 알 수 있습니다.
그림 3.9: 테스트 메모리 배치
두 가지 유형의 테스트를 실행합니다. 첫 번째 테스트에서는 요소를 순차적으로 처리합니다. 테스트 프로그램은 n 포인터를 따라가지만, 배열 요소는 메모리에서 발견되는 순서대로 순회하도록 연결되어 있습니다. 이는 그림 아래쪽에 보입니다. 마지막 요소에서 하나의 역참조가 있습니다. 두 번째 테스트(그림 위쪽)에서는 배열 요소를 무작위 순서로 순회합니다. 두 경우 모두 배열 요소는 단일 연결 리스트의 원형을 이룹니다.
3.3.2 캐시 효과의 측정
모든 도표는, 임의 크기의 작업 집합, 읽기/쓰기 접근, 순차/랜덤 접근을 시뮬레이션할 수 있는 프로그램으로 측정됩니다. 이미 그림 3.4에서 일부 결과를 봤습니다. 프로그램은 다음 타입의 요소로 구성된 작업 집합 크기만큼의 배열을 만듭니다:
struct 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비트 모드의 펜티엄 4 머신에서 이루어졌고, 이는 NPAD=0의 struct l이 8바이트 크기임을 뜻합니다.
그림 3.10: 순차 읽기 접근, NPAD=0
그림 3.11: 여러 크기에서의 순차 읽기
처음 두 개의 측정치는 잡음으로 오염되어 있습니다. 측정한 워크로드가 너무 작아서 시스템의 다른 효과를 걸러내기 어렵습니다. 값이 모두 4사이클 수준이라고 안전하게 가정할 수 있습니다. 이를 염두에 두고 세 가지 뚜렷한 수준을 볼 수 있습니다:
이 단계는 쉽게 설명됩니다. 프로세서에는 16kB L1d와 1MB L2가 있습니다. 한 수준에서 다른 수준으로의 전이가 날카롭지 않은 것은, 캐시가 시스템의 다른 부분에서도 사용되어, 프로그램 데이터에만 독점적으로 사용되지 않기 때문입니다. 특히 L2 캐시는 통합(unified) 캐시로, 명령어에도 사용됩니다(참고: 인텔은 포괄적(inclusive) 캐시를 사용합니다).
아마 예상 밖인 것은 다양한 작업 집합 크기에서의 실제 시간입니다. L1d 히트에 대한 시간은 예상과 같습니다. P4에서 L1d 히트 후 로드 시간은 약 4사이클입니다. 그렇다면 L2 접근은 어떨까요? L1d가 데이터를 담기에 충분하지 않게 되면, L2 접근 시간이 14사이클 이상이므로 요소당 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 용량을 넘어서면 더 흥미로워집니다. 네 선이 크게 갈라집니다. 요소 크기의 차이가 성능 차이에 큰 역할을 합니다. 프로세서는 스트라이드 크기를 인식해, 프리페치 윈도(6.3.1절 참조)보다 요소 크기가 작은 NPAD=15와 31에서는 불필요한 캐시 라인을 가져오지 않아야 합니다. 요소 크기가 프리페치 노력에 장해가 되는 곳은, 하드웨어 프리페쳐의 한계—페이지 경계를 넘을 수 없다는 점—때문입니다. 요소 크기를 늘릴 때마다 하드웨어 프리페쳐의 효과는 절반씩 줄어듭니다. 만약 하드웨어 프리페쳐가 페이지 경계를 넘을 수 있고, 다음 페이지가 상주하지 않거나 유효하지 않다면, OS가 페이지를 찾아 개입해야 합니다. 즉 프로그램이 직접 일으키지 않은 페이지 폴트를 경험하게 됩니다. 이는 완전히 용납할 수 없습니다. 프로세서는 페이지가 존재하지 않는 것인지 단지 상주하지 않는 것인지 알 수 없기 때문입니다. 후자의 경우 OS는 프로세스를 중단해야 합니다. 어쨌든 NPAD=7 이상에서는 리스트 요소마다 하나의 캐시 라인이 필요하므로 하드웨어 프리페쳐가 할 수 있는 일이 많지 않습니다. 프로세서는 메모리에서 데이터 하나를 읽고 다음 요소를 로드하는 일만 하기 때문에, 데이터를 로드할 시간이 없습니다.
또 다른 큰 이유는 TLB 캐시 미스입니다. TLB 캐시는 가상 주소를 물리 주소로 변환한 결과를 저장하는 캐시이며, 자세한 내용은 4장에서 설명합니다. TLB 캐시는 매우 빨라야 하므로 크기가 작습니다. 반복적으로 접근되는 페이지가 TLB 캐시 엔트리보다 많으면, 가상→물리 주소 변환을 계속 반복해야 하고 이는 매우 비쌉니다. 요소 크기가 커지면 TLB 조회 비용이 요소에 분산되는 정도가 줄어듭니다. 즉 요소 하나당 계산해야 하는 TLB 엔트리 수가 증가합니다.
TLB 효과를 관찰하려면 다른 테스트를 실행할 수 있습니다. 한 측정에서는 요소를 평소처럼 순차로 배치합니다. 요소는 캐시 라인 하나를 채우도록 NPAD=7을 사용합니다. 두 번째 측정에서는 리스트 요소를 페이지마다 하나씩 배치합니다. 각 페이지의 나머지는 건드리지 않으며, 총 작업 집합 크기에 포함하지 않습니다. {맞습니다, 이는 약간 일관성이 없을 수 있습니다. 다른 테스트에서는 struct의 사용되지 않은 부분도 요소 크기에 포함했고, 페이지 크기로 요소를 정의할 수도 있습니다. 그러면 작업 집합 크기가 매우 달라질 것입니다. 그러나 이 테스트의 요점은 그게 아니며, 어차피 프리페치가 비효과적이므로 큰 차이는 없습니다.} 결과적으로 첫 번째 측정에서는 리스트 반복마다 새 캐시 라인이 필요하고, 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”는 다음(next) 요소의 pad[0] 값을 현재 요소의 pad[0]에 더합니다.
순진한 가정은 “Addnext0”가 더 느리다는 것입니다. 다음 요소로 넘어가기 전에 그 요소의 값을 하나 더 읽어야 하니까요. 하지만 놀랍게도 몇몇 작업 집합 크기에서는 이 테스트가 실제로 “Inc”보다 빠릅니다. 설명은 간단합니다. 다음 요소에서의 로드는 사실상 강제 프리페치입니다. 프로그램이 다음 요소로 진행할 때, 그 요소는 이미 L1d 캐시에 있음이 보장됩니다. 그 결과 작업 집합이 L2 캐시에 들어가는 한 “Addnext0”는 단순 “Follow” 테스트와 동일한 성능을 보입니다.
하지만 “Addnext0”는 “Inc”보다 L2를 더 빨리 벗어납니다. 더 많은 데이터를 주메모리에서 로드해야 하기 때문입니다. 그래서 “Addnext0”는 작업 집합 2^21 바이트에서 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 | #Iter |
| 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 미스 / L2 접근)이 상승하기 시작함을 보여줍니다. 그림 3.15와 유사한 형태입니다. 빠르게 오르고, 약간 내려갔다가, 다시 오릅니다. 요소당 사이클 그래프와 강한 상관관계가 있습니다. L2 미스율은 결국 100%에 근접할 때까지 증가할 것입니다. 충분히 큰 작업 집합과 RAM을 주면, 무작위로 선택한 캐시 라인이 L2에 있거나 로드 중일 확률을 임의로 낮출 수 있습니다.
증가하는 캐시 미스율 자체가 비용의 일부를 설명합니다. 하지만 또 다른 요인이 있습니다. 표 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 정책은 더 정교합니다. 여기서 프로세서는 수정된 캐시 라인을 즉시 주메모리에 쓰지 않습니다. 대신 캐시 라인이 더티로만 표시됩니다. 미래 어느 시점에서 캐시 라인이 캐시에서 떨어질(eviction) 때, 더티 비트에 의해 내용을 버리는 대신 그때 데이터를 써야 함을 지시합니다.
write-back 캐시는 훨씬 더 좋은 성능을 보일 가능성이 크며, 그래서 쓸만한 프로세서가 있는 시스템의 대부분 메모리는 이 방식으로 캐시됩니다. 프로세서는 FSB가 한가할 때를 이용해, 라인이 비워지기 전에 캐시 라인 내용을 저장해 둘 수 있습니다. 이렇게 더티 비트를 지우면, 캐시가 필요할 때 라인을 그냥 버릴 수 있습니다.
하지만 write-back 구현에는 중요한 문제가 있습니다. 두 개 이상의 프로세서(코어, 하이퍼스레드 포함)가 있고 동일 메모리에 접근할 때도, 두 프로세서가 언제나 동일 메모리 내용을 보게 해야 합니다. 한 프로세서의 캐시 라인이 더티인 상태(아직 주메모리에 씌지 않음)에서, 두 번째 프로세서가 같은 메모리를 읽으려 하면, 단순히 주메모리를 읽어서는 안 됩니다. 대신 첫 번째 프로세서의 캐시 라인 내용이 필요합니다. 다음 절에서 현재 이것이 어떻게 구현되는지 봅니다.
그 전에 더 두 가지 캐시 정책을 언급합니다:
두 정책 모두 실제 RAM이 아닌 주소 공간의 특수 영역에 사용됩니다. 커널은 x86 프로세서의 경우 MTRR(Memory Type Range Registers)을 사용해 이 주소 범위의 정책을 설정하며 나머지는 자동으로 동작합니다. MTRR은 write-through와 write-back 정책 선택에도 사용됩니다.
write-combining은 주로 그래픽 카드 같은 디바이스의 RAM에 사용되는 제한적 캐시 최적화입니다. 디바이스로의 전송 비용이 로컬 RAM 접근보다 훨씬 크므로, 전송 횟수를 줄이는 것이 더 중요합니다. 라인 내 한 워드가 쓰였다고 전체 캐시 라인을 전송하는 것은, 다음 연산이 바로 다음 워드를 수정한다면 낭비입니다. 이는 흔한 상황입니다. 화면에서 수평으로 이웃한 픽셀의 메모리는 대부분 이웃합니다. 이름에서 알 수 있듯, write-combining은 캐시 라인을 쓰기 전 여러 쓰기를 묶어(combine) 처리합니다. 이상적인 경우, 캐시 라인 전체를 워드 단위로 모두 수정한 뒤 마지막 워드가 쓰인 후에야, 캐시 라인을 디바이스로 씁니다. 이는 디바이스 RAM 접근을 크게 가속할 수 있습니다.
마지막으로, uncacheable 메모리가 있습니다. 보통 이는 메모리 위치가 RAM로 백업되지 않았다는 뜻입니다. CPU 외부에서 어떤 기능을 수행하도록 하드코딩된 특수 주소일 수 있습니다. 범용 하드웨어에서는, PCIe 등 버스에 붙은 카드/디바이스에 대한 접근으로 번역되는 메모리 매핑 주소 범위가 가장 흔한 경우입니다. 임베디드 보드에서는 LED를 켜고 끄는 데 사용할 수 있는 메모리 주소를 찾기도 합니다. 이런 주소를 캐시하는 것은 분명히 나쁜 생각입니다. 이 LED는 디버깅이나 상태 표시용으로, 가능한 빨리 보이기를 원합니다. PCIe 카드의 메모리는 CPU의 개입 없이도 바뀔 수 있으므로, 캐시하면 안 됩니다.
3.3.4 멀티프로세서 지원
앞 절에서 이미 여러 프로세서가 등장할 때의 문제를 지적했습니다. 공유되지 않는 캐시 수준(최소 L1d)에 대해서는 멀티코어에서도 같은 문제가 있습니다.
프로세서 간 캐시에 직접 접근을 제공하는 것은 완전히 비실용적입니다. 연결 속도가 턱없이 느립니다. 실용적 대안은, 필요할 때 캐시 내용을 다른 프로세서로 전송하는 것입니다. 이는 동일 프로세서 내에서 공유되지 않는 캐시에도 적용됩니다.
그렇다면 캐시 라인 전송은 언제 일어나야 할까요? 답은 간단합니다. 한 프로세서가, 다른 프로세서의 캐시에서 더티인 캐시 라인을 읽거나 쓰려 할 때입니다. 하지만 한 프로세서가 다른 프로세서의 캐시에서 캐시 라인이 더티인지 어떻게 알 수 있을까요? 단지 다른 프로세서가 그 캐시 라인을 로드했다고 가정하는 것은 최적이 아닙니다. 보통 메모리 접근의 대다수는 읽기이며, 이로 인한 캐시 라인은 더티가 아닙니다. 캐시 라인에 대한 프로세서의 작업은 빈번합니다(그래서 이 글이 있는 거죠). 매 쓰기 접근마다 변경된 캐시 라인 정보를 브로드캐스트하는 것은 비실용적입니다.
여러 해에 걸쳐 발전한 것이 MESI 캐시 일관성 프로토콜(Modified, Exclusive, Shared, Invalid)입니다. 프로토콜 이름은 MESI를 사용할 때 캐시 라인이 가질 수 있는 네 가지 상태에서 왔습니다:
이 프로토콜은 더 단순하지만 덜 효율적인 버전에서 발전해 왔습니다. 이 네 가지 상태로 write-back 캐시를 효율적으로 구현하면서도 서로 다른 프로세서에서 읽기 전용 데이터의 동시 사용을 지원할 수 있습니다.
그림 3.18: MESI 프로토콜 전이
상태 변화는, 프로세서가 서로의 작업을 청취(snoop)함으로써 큰 비용 없이 달성됩니다. 프로세서가 수행하는 특정 동작은 외부 핀을 통해 공표되어, 캐시 처리가 외부에 보이게 됩니다. 해당 캐시 라인의 주소는 주소 버스에 보입니다. 다음 설명(그림 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 상태로 유지하려 합니다. 후자는 그 순간 정보를 알 수 없을 때의 폴백입니다. Exclusive 상태는 아예 빼도 기능적 문제는 없습니다. 다만 성능이 나빠집니다. E→M 전이는 S→M 전이보다 훨씬 빠르기 때문입니다.
이 상태 전이 설명에서, 멀티프로세서 특유의 비용이 어디서 나오는지 명확할 것입니다. 캐시를 채우는 것도 여전히 비싸지만, 이제 RFO 메시지를 경계해야 합니다. 이런 메시지를 보내야 하면 느려집니다.
RFO 메시지가 필요한 경우는 두 가지입니다:
멀티스레드/멀티프로세스 프로그램에는 항상 약간의 동기화가 필요하며, 동기화는 메모리를 사용해 구현됩니다. 그래서 몇몇 RFO 메시지는 정당합니다. 그래도 최대한 드물게 유지해야 합니다. RFO의 다른 원천도 있습니다. 6장에서 이런 시나리오를 설명합니다. 캐시 일관성 프로토콜 메시지는 시스템의 프로세서들 사이에 분배되어야 하며, MESI 전이는 시스템의 모든 프로세서가 메시지에 응답할 기회를 가질 때까지 일어날 수 없습니다. 즉, 응답이 가장 오래 걸릴 가능성이, 일관성 프로토콜의 속도를 결정합니다. {그래서 요즘은 예를 들어 AMD Opteron의 3소켓 시스템을 보게 됩니다. 각 프로세서는 세 개의 하이퍼링크만 있고 하나는 사우스브리지 연결에 쓰여, 서로 정확히 한 홉 거리입니다.} 버스 충돌이 가능하고, NUMA 시스템에서는 지연이 높으며, 순수 트래픽 양도 속도를 늦출 수 있습니다. 모두 불필요한 트래픽을 피해야 할 좋은 이유입니다.
프로세서가 둘 이상일 때 생기는 다른 문제도 있습니다. 효과는 매우 머신 특이적이지만, 원칙적으로 항상 존재합니다. FSB는 공유 자원입니다. 대부분의 머신에서 모든 프로세서는 하나의 버스를 통해 메모리 컨트롤러에 연결됩니다(그림 2.1). 단일 프로세서가 버스를 포화시킬 수 있다면(보통 그렇습니다), 동일 버스를 공유하는 두/네 프로세서는 각 프로세서에 더 적은 대역폭을 제공합니다.
그림 2.2처럼 각 프로세서가 메모리 컨트롤러로 가는 버스를 따로 갖더라도, 메모리 모듈로 가는 버스가 남습니다. 보통 하나의 버스이며, 그림 2.2의 확장 모델에서도 같은 메모리 모듈에 대한 동시 접근은 대역폭을 제한합니다.
각 프로세서가 로컬 메모리를 가질 수 있는 AMD 모델에서도 마찬가지입니다. 네, 모든 프로세서는 로컬 메모리에 동시에 빠르게 접근할 수 있습니다. 하지만 멀티스레드/멀티프로세스 프로그램은—때때로라도—동기화를 위해 동일 메모리 영역에 접근해야 합니다.
동시성은 필요한 동기화를 구현하는 데 제공되는 유한한 대역폭에 의해 심각히 제한됩니다. 서로 다른 프로세서/코어에서 동일 메모리 위치에 대한 접근을 최소화하도록 프로그램을 신중히 설계해야 합니다. 다음 측정은 이를 보여주고, 멀티스레드 코드와 관련된 다른 캐시 효과도 보여줄 것입니다.
서로 다른 프로세서에서 같은 캐시 라인을 동시에 사용하는 문제가 얼마나 심각한지 이해하도록, 앞에서 사용한 같은 프로그램에 대한 더 많은 성능 그래프를 봅니다. 이번에는 둘 이상의 스레드가 동시에 실행됩니다. 측정한 것은 스레드 중 가장 빠른 실행 시간입니다. 즉 모든 스레드가 끝나 전체 실행이 완료되는 데 걸리는 시간은 더 큽니다. 머신은 프로세서 4개를 갖고 있으며, 최대 4개 스레드를 사용합니다. 모든 프로세서는 메모리 컨트롤러로 가는 하나의 버스를 공유하며, 메모리 모듈로 가는 버스도 하나뿐입니다.
그림 3.19: 순차 읽기 접근, 다중 스레드
그림 3.19는 128바이트 엔트리(NPAD=15, 64비트 머신)에 대한 순차 읽기 전용 접근의 성능을 보여줍니다. 한 스레드의 곡선은 그림 3.11과 유사할 것으로 기대할 수 있습니다. 다른 머신에서의 측정이므로 실제 수치는 다릅니다.
이 그림에서 중요한 부분은 멀티스레드 실행 시의 동작입니다. 링크드 리스트를 순회할 때 스레드를 동기화하지 않았고, 메모리를 수정하지도 않음을 주목하세요. RFO 메시지는 필요 없고, 모든 캐시 라인은 공유될 수 있습니다. 그럼에도 불구하고 두 스레드를 사용하면 가장 빠른 스레드가 최대 18% 느려지고, 네 스레드를 사용하면 최대 34% 느려집니다. 캐시 라인을 프로세서 간에 운반하지 않았으므로, 이 느려짐은 오로지 두 병목 중 하나 또는 둘 모두 때문입니다. 프로세서→메모리 컨트롤러 사이의 공유 버스, 그리고 메모리 컨트롤러→메모리 모듈 사이의 버스입니다. 이 머신에서 작업 집합 크기가 L3 캐시보다 커지는 즉시, 세 스레드 모두가 새로운 리스트 요소를 프리페치할 것입니다. 두 스레드만으로도 사용 가능한 대역폭이 선형 확장을 유지하기엔 부족합니다(즉 멀티스레드 페널티가 생깁니다).
메모리를 수정하면 상황은 더 나빠집니다. 그림 3.20은 순차 Increment 테스트의 결과를 보여줍니다.
그림 3.20: 순차 Increment, 다중 스레드
이 그래프는 Y축에 로그 스케일을 사용합니다. 그래서 차이가 작아 보일 수 있지만, 두 스레드에서는 약 18%, 네 스레드에서는 무려 93%의 페널티가 있습니다. 이는 네 스레드가 사용될 때 프리페치 트래픽과 write-back 트래픽이 버스를 거의 포화시킨다는 뜻입니다.
L1d 범위의 결과를 보여주기 위해 로그 스케일을 사용했습니다. 두 개 이상의 스레드가 실행되는 순간, L1d가 사실상 비효과적이 됨을 볼 수 있습니다. 단일 스레드 접근 시간은 L1d가 작업 집합을 담기에 충분하지 않을 때에야 20사이클을 초과합니다. 하지만 멀티스레드에서는, 작업 집합이 가장 작은 경우에도 그 접근 시간에 도달합니다.
이 문제의 한 측면은 여기서 보이지 않습니다. 이 특정 테스트 프로그램으로는 측정하기 어렵습니다. 테스트가 메모리를 수정하므로 RFO 메시지를 기대해야 하지만, 두 개 이상의 스레드에서 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입니다. 두 스레드는 그리 나쁘지 않습니다. 그러나 네 스레드에서 마지막 테스트의 숫자는 두 스레드를 넘어 확장할 가치가 거의 없음을 보여줍니다. 추가 이득이 아주 작습니다. 데이터를 그림 3.21을 조금 다르게 표현하면 더 쉽게 볼 수 있습니다.
그림 3.22: 병렬화를 통한 속도 향상
그림 3.22의 곡선은 속도 향상 계수, 즉 단일 스레드 실행에 비한 상대 성능입니다. 가장 작은 크기는 측정이 충분히 정확하지 않아 무시해야 합니다. L2 및 L3 캐시 범위에서는 거의 선형 가속을 달성합니다. 각각 거의 2와 4에 도달합니다. 하지만 L3 캐시가 작업 집합을 담기에 충분하지 않을 때, 수치가 붕괴합니다. 두 스레드와 네 스레드의 속도 향상이 동일한 지점까지 붕괴합니다(표 3.3의 네 번째 열 참조). 이것이, 동일 메모리 컨트롤러를 사용하는 CPU 소켓이 네 개보다 많은 마더보드를 거의 볼 수 없는 이유 중 하나입니다. 더 많은 프로세서를 가진 머신은 다르게 만들어야 합니다(5장 참조).
이 숫자는 보편적이지 않습니다. 어떤 경우에는 마지막 레벨 캐시에 들어가는 작업 집합에서도 선형 속도 향상이 일어나지 않습니다. 사실, 테스트 프로그램만큼 스레드가 분리되어 있지 않은 것이 보통이므로, 이게 규칙입니다. 반면, 큰 작업 집합으로도 두 개 이상의 스레드의 이점을 취할 수 있습니다. 이렇게 하려면 고민이 필요합니다. 6장에서 몇 가지 접근법을 논의합니다.
하이퍼스레드(Symmetric Multi-Threading, SMT라 부르기도 함)는 CPU가 구현하며, 개별 스레드가 실제로 완전 병렬 실행되지 않는다는 점에서 특수한 경우입니다. 레지스터 집합을 제외한 거의 모든 실행 자원을 공유합니다. 개별 코어와 CPU는 여전히 병렬로 작동하지만, 각 코어의 하이퍼스레드들은 이 제한에 묶입니다. 이론적으로 코어당 스레드가 많을 수 있지만, 지금까지 인텔 CPU는 코어당 최대 두 개 스레드입니다. CPU는 스레드를 시분할합니다. 이것만으로는 큰 의미가 없습니다. 진짜 장점은, 현재 실행 중인 하이퍼스레드가 지연될 때(대부분 메모리 접근에 의한 지연) 다른 하이퍼스레드를 스케줄할 수 있다는 점입니다.
하이퍼스레드된 코어에서 두 스레드가 실행될 때, 프로그램이 단일 스레드보다 효율적인 경우는 두 스레드의 합산 실행 시간이 단일 스레드 실행 시간보다 짧을 때뿐입니다. 이는 보통, 단일 스레드에서 순차적으로 일어나는 서로 다른 메모리 접근의 대기 시간을 겹쳐서(overlap) 달성합니다. 간단한 계산으로 특정 속도 향상을 달성하기 위한 캐시 히트율의 최소 요구치를 구할 수 있습니다.
프로그램의 실행 시간은 캐시 계층이 하나뿐인 단순 모델로 다음처럼 근사할 수 있습니다([htimpact] 참조):
Texe = N[(1 − Fmem)Tproc + Fmem(Ghit Tcache + (1 − Ghit)Tmiss)]
변수의 의미는 다음과 같습니다:
N = 명령 수 Fmem = N 중 메모리를 접근하는 비율 Ghit = 로드 중 캐시 히트 비율 Tproc = 명령어당 사이클 수 Tcache = 캐시 히트 사이클 수 Tmiss = 캐시 미스 사이클 수 Texe = 프로그램 실행 시간
두 스레드를 사용하는 게 의미 있으려면, 두 스레드 각각의 실행 시간이 단일 스레드 실행 시간의 절반 이하여야 합니다. 양변에서 유일하게 바뀌는 변수는 캐시 히트 수입니다. 식을 풀어, 스레드 실행이 50% 이상 느려지지 않기 위해 필요한 최소 캐시 히트율을 구하면 그림 3.23의 그래프를 얻습니다.
그림 3.23: 속도 향상을 위한 최소 캐시 히트율
X축은 단일 스레드 코드의 캐시 히트율 Ghit입니다. 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 등 더 큰 캐시에는 물리 주소 태깅이 필요합니다. 이 캐시는 지연이 더 길고, 가상→물리 주소 변환이 제때 끝날 수 있습니다. 또한 이 캐시는 더 큽니다(즉, 비우면 잃는 정보가 많고, 주메모리 접근 지연 때문에 다시 채우는 데 오래 걸립니다). 자주 비우면 비용이 큽니다.
일반적으로, 이런 캐시의 주소 처리 세부를 알 필요는 없습니다. 바꿀 수 없고, 성능에 영향을 줄 모든 요인은 보통 피해야 하거나 높은 비용이 따릅니다. 캐시 용량을 넘기는 것은 나쁘고, 사용된 캐시 라인의 다수가 같은 세트에 몰리면 모든 캐시에서 초기에 문제가 발생합니다. 후자는 가상 주소 캐시에서는 피할 수 있지만, 물리 주소 태그를 사용하는 캐시에 대해서는 사용자 공간 프로세스가 피할 수 없습니다. 기억할 한 가지 세부는, 가능하다면 같은 물리 메모리 위치를 같은 프로세스에서 두 개 이상의 가상 주소로 매핑하지 말라는 것입니다.
또 다른 캐시 세부는 교체 정책입니다. 대부분의 캐시는 LRU(Least Recently Used) 요소를 먼저 퇴출합니다. 이는 언제나 좋은 기본 전략입니다. 연관도가 커질수록(그리고 연관도는 코어 수 증가로 앞으로 더 커질 수 있습니다), LRU 리스트 유지 비용이 커지고, 다른 전략이 채택될 수 있습니다.
캐시 교체에 관해서 프로그래머가 할 수 있는 일은 많지 않습니다. 캐시가 물리 주소 태그를 사용한다면, 가상 주소가 캐시 세트와 어떻게 대응하는지 알 방법이 없습니다. 모든 논리 페이지의 캐시 라인이 같은 캐시 세트에 매핑되어 캐시 대부분을 사용하지 못할 수도 있습니다. 가능한 한, OS가 이런 일이 너무 자주 일어나지 않도록 배치해야 합니다.
가상화의 등장으로 일은 더 복잡해졌습니다. 이제 OS조차 물리 메모리 할당에 대한 제어권이 없습니다. VMM(하이퍼바이저)이 물리 메모리 할당을 책임집니다.
프로그래머가 할 수 있는 최선은 a) 논리 메모리 페이지를 완전히 사용하고 b) 물리 주소를 최대한 다양화하기 위해 의미 있는 한 가장 큰 페이지 크기를 사용하는 것입니다. 큰 페이지 크기는 다른 이점도 있지만 이는 다른 주제입니다(4장 참조).
프로세서가 사용하는 데이터만 캐시되는 것이 아닙니다. 프로세서가 실행하는 명령도 캐시됩니다. 다만, 이 캐시는 데이터 캐시보다 훨씬 문제가 적습니다. 이유는 여러 가지입니다:
프로그래머가 따라야 할 규칙이 몇 가지 있지만, 대부분 도구를 어떻게 사용할지에 관한 것입니다. 6장에서 논의합니다. 여기에서는 명령 캐시의 기술적 세부만 이야기합니다.
CPU 코어 클럭이 급격히 증가하고 캐시(심지어 1차 캐시)와 코어 간 속도 차가 커진 이후, CPU는 파이프라인화되었습니다. 즉, 명령 실행이 여러 단계로 일어납니다. 먼저 명령이 디코드되고, 그다음 파라미터가 준비되며, 마지막에 실행됩니다. 이런 파이프라인은 매우 길 수 있습니다(인텔 Netburst 아키텍처는 20단계 이상). 긴 파이프라인은 파이프라인이 스톨(명령 흐름이 중단)되면, 다시 속도를 내는 데 시간이 걸린다는 뜻입니다. 다음 명령의 위치를 정확히 예측할 수 없거나(분기 예측 실패), 다음 명령을 로드하는 데 너무 오래 걸리는(예: 메모리에서 읽어야 하는) 경우 스톨이 발생합니다.
결과적으로 CPU 설계자는 분기 예측에 많은 시간과 칩 면적을 투자해 파이프라인 스톨을 최대한 줄입니다.
CISC 프로세서에서는 디코딩 단계도 시간이 걸릴 수 있습니다. x86·x86-64 프로세서는 특히 그렇습니다. 최근에는 1차 명령 캐시에 원시 바이트 시퀀스를 캐시하는 대신, 디코딩된 명령을 캐시합니다. L1i는 이 경우 “트레이스 캐시(trace cache)”라고 불립니다. 트레이스 캐싱은 캐시 히트 시 파이프라인의 초기 단계들을 건너뛸 수 있게 해주어, 특히 파이프라인 스톨에서 좋습니다.
앞서 말했듯, L2 이후 캐시는 코드와 데이터가 통합된(unified) 캐시입니다. 여기서는 코드가 바이트 시퀀스 형태로 캐시되며, 디코드되지 않습니다.
최고 성능을 내려면, 명령 캐시와 관련해 몇 가지 규칙만 따르면 됩니다:
이 규칙은 보통 컴파일러의 코드 생성에서 지켜집니다. 프로그래머가 할 수 있는 몇 가지는 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는 같은 프로세서에서 두 개의 스레드를 실행해, 프로세서의 두 하이퍼스레드에 각각 고정(pinning)한 결과입니다.
그림 3.25: P4 대역폭, 2 하이퍼스레드
그래프는 이전과 동일 스케일로, 차이를 강조합니다. 두 스레드를 동시에 측정하는 문제로 곡선이 약간 흔들립니다. 결과는 예상대로입니다. 하이퍼스레드는 레지스터를 제외한 모든 자원을 공유하므로, 각 스레드는 캐시와 대역폭을 절반만 사용할 수 있습니다. 즉 각 스레드가 대기를 많이 하며 다른 스레드에 실행 시간을 줄 수 있음에도, 다른 스레드도 메모리를 기다려야 하므로 차이가 없습니다. 하이퍼스레드를 최악으로 사용하는 경우를 보여줍니다.
그림 3.26: Core 2 대역폭
그림 3.24와 3.25와 비교하면, 인텔 Core 2 프로세서의 그림 3.26과 3.27은 상당히 다릅니다. 듀얼 코어 프로세서이며 L2를 공유하고, P4 머신보다 L2가 네 배 큽니다. 이는 쓰기/복사 성능의 하락이 더 늦게 나타나는 것을 설명합니다.
더 큰 차이도 있습니다. 작업 집합 범위 전체에서 읽기 성능은 최적의 사이클당 16바이트 주변에서 유지됩니다. 2^20 바이트 이후 읽기 성능의 하락은 작업 집합이 DTLB에 너무 커졌기 때문입니다. 이런 높은 숫자를 달성한다는 것은, 프로세서가 데이터를 프리페치해 제때 전송하는 것뿐 아니라, 데이터를 L1d로 프리페치한다는 뜻입니다.
쓰기/복사 성능도 극적으로 다릅니다. 프로세서는 write-through 정책을 사용하지 않으며, 쓴 데이터는 L1d에 저장되다가 필요할 때만 퇴출됩니다. 이는 사이클당 16바이트에 근접한 쓰기 속도를 허용합니다. L1d가 더 이상 충분하지 않으면 성능은 크게 떨어집니다. Netburst와 마찬가지로, 쓰기 성능은 읽기보다 훨씬 낮습니다. 높은 읽기 성능 때문에 차이는 더 커집니다. 사실 L2마저 충분하지 않으면 속도 차이는 20배까지 증가합니다! 이는 Core 2가 못한다는 뜻이 아닙니다. 오히려 항상 Netburst 코어보다 더 낫습니다.
그림 3.27: Core 2 대역폭, 2 스레드
그림 3.27에서는 두 스레드가 각각 두 코어에 하나씩 실행됩니다. 두 스레드는 반드시 완전히 동기화되지는 않았지만 같은 메모리에 접근합니다. 읽기 성능 결과는 단일 스레드와 다르지 않습니다. 멀티스레드에서는 흔한 조금 더 많은 흔들림이 보입니다.
흥미로운 점은 L1d에 들어가는 작업 집합 크기에서의 쓰기/복사 성능입니다. 그림에서 보듯, 성능은 데이터를 주메모리에서 읽어야 하는 것과 같습니다. 두 스레드가 같은 메모리 위치를 두고 경쟁하며, 캐시 라인에 대한 RFO 메시지를 전송해야 합니다. 문제는 이 요청이 L2 속도로 처리되지 않는다는 점입니다. 두 코어가 캐시를 공유함에도요. L1d 캐시가 충분하지 않으면, 수정된 엔트리가 각 코어의 L1d에서 공유 L2로 플러시됩니다. 그 시점에 성능은 크게 증가합니다. 이제 L1d 미스는 L2가 충족하며, 데이터가 아직 플러시되지 않았을 때만 RFO 메시지가 필요합니다. 이 때문에 해당 작업 집합 크기 범위에서 속도가 50% 감소합니다. 점근적 거동은 예상대로입니다. 두 코어가 같은 FSB를 공유하므로, 각 코어는 FSB 대역폭의 절반을 얻습니다. 즉 큰 작업 집합에서는 각 스레드의 성능이 단일 스레드의 절반 수준입니다.
동일 벤더의 프로세서 버전 사이에도 큰 차이가 있으므로, 다른 벤더 프로세서의 성능을 보는 것도 가치가 있습니다. 그림 3.28은 AMD family 10h Opteron의 성능을 보여줍니다. 이 프로세서는 64kB L1d, 512kB L2, 2MB L3를 갖습니다. L3는 프로세서의 모든 코어가 공유합니다. 성능 테스트 결과는 그림 3.28에서 볼 수 있습니다.
그림 3.28: AMD Family 10h Opteron 대역폭
첫 번째로 눈에 띄는 것은, L1d가 충분할 때 사이클당 두 명령을 처리할 수 있다는 점입니다. 읽기 성능은 사이클당 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: AMD Fam 10h 대역폭, 2 스레드
읽기 성능은 크게 영향을 받지 않습니다. 각 스레드의 L1d와 L2는 전과 같이 작동하고, 이 경우 L3 프리페치도 그다지 잘 되지 않습니다. 두 스레드는 목적상 L3를 과도하게 스트레스 주지 않습니다. 이 테스트에서 큰 문제는 쓰기 성능입니다. 스레드가 공유하는 모든 데이터는 L3를 거쳐야 합니다. 이 공유는 비효율적으로 보입니다. L3가 작업 집합 전체를 담기에 충분해도 비용은 L3 접근보다 상당히 큽니다. 그림 3.27과 비교하면, Core 2의 두 스레드는 해당 작업 집합 크기 범위에서 공유 L2 속도로 작동합니다. Opteron은 매우 좁은 범위에서만 이 수준의 성능에 도달하며, 그마저도 Core 2의 L2보다 느린 L3 속도에 겨우 접근하는 수준입니다.
3.5.2 임계 워드 우선 로드(Critical Word Load)
메모리는 캐시 라인 크기보다 작은 블록 단위로 주메모리에서 캐시로 전송됩니다. 오늘날 한 번에 64비트(=8바이트)가 전송되고, 캐시 라인 크기는 64 또는 128바이트입니다. 즉 캐시 라인당 8 또는 16번의 전송이 필요합니다.
DRAM 칩은 버스트 모드로 64비트 블록을 전송할 수 있습니다. 메모리 컨트롤러의 추가 명령(및 관련 지연) 없이 캐시 라인을 채울 수 있습니다. 프로세서가 캐시 라인을 프리페치한다면 이 방식이 아마 최선입니다.
프로그램의 데이터/명령 캐시 접근이 미스(즉, 처음 사용하는 데이터로 인한 강제 미스, 또는 캐시 크기 제한으로 인한 용량 미스)일 때는 상황이 다릅니다. 프로그램이 계속 실행하려면 캐시 라인의 어떤 워드가 필요한데, 그 워드가 캐시 라인의 첫 번째 워드가 아닐 수 있습니다. 버스트 모드와 DDR 전송에서도 개별 64비트 블록은 눈에 띄게 다른 시간에 도착합니다. 각 블록은 이전 블록보다 4 CPU 사이클 이상 늦게 도착합니다. 프로그램에 필요한 워드가 캐시 라인의 여덟 번째라면, 첫 워드 도착 후 추가로 30사이클 이상 기다려야 합니다.
항상 이럴 필요는 없습니다. 메모리 컨트롤러는 캐시 라인의 워드 순서를 바꿔 요청할 수 있습니다. 프로세서는 프로그램이 기다리는 워드, 즉 임계 워드(critical word)를 알려줄 수 있고, 메모리 컨트롤러는 이 워드를 먼저 요청할 수 있습니다. 워드가 도착하면, 나머지 캐시 라인이 도착하는 동안—캐시가 아직 일관 상태가 아니더라도—프로그램은 계속 실행할 수 있습니다. 이 기법을 Critical Word First & Early Restart라고 합니다.
오늘날 프로세서는 이 기법을 구현하지만, 불가능한 상황도 있습니다. 프로세서가 데이터를 프리페치할 때는 임계 워드를 알 수 없습니다. 프리페치 연산이 진행 중일 때 캐시 라인을 요청하면, 순서를 바꾸지 못하고 임계 워드를 기다려야 합니다.
그림 3.30: 캐시 라인 끝에 있는 임계 워드
이런 최적화가 있어도 임계 워드의 위치는 중요합니다. 그림 3.30은 순차/랜덤 접근의 Follow 테스트에서, 추적하는 포인터가 첫 워드에 있을 때 대비 마지막 워드에 있을 때의 느려짐을 보여줍니다. 요소 크기는 캐시 라인 크기에 대응하는 64바이트입니다. 숫자는 잡음이 크지만, 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 캐시의 절반이라서 선택했습니다. 이 프로세스는 한 코어에 고정됩니다. 두 번째 프로세스는 다른 코어에 고정되며, 가변 크기의 메모리 영역을 읽고 씁니다. 그래프는 사이클당 읽거나 쓴 바이트 수를 보여줍니다. 네 가지 그래프가 있으며, 백그라운드 프로세스의 read/write와, 측정 대상 프로세스의 read/write의 조합입니다. read/write 그래프는 2MB 작업 집합으로 항상 쓰기하는 백그라운드 프로세스, 그리고 가변 작업 집합으로 읽는 측정 프로세스를 의미합니다.
흥미로운 부분은 2^20에서 2^23 바이트 사이입니다. 두 코어의 L2 캐시가 완전히 분리되어 있다면, 모든 네 테스트의 성능이 2^21~2^22 바이트 사이에서 떨어질 것으로 기대할 수 있습니다. 즉 L2가 고갈될 때입니다. 그림 3.31에서 보듯 사실은 그렇지 않습니다. 백그라운드 프로세스가 쓰기일 때 특히 눈에 띕니다. 작업 집합이 1MB에 도달하기도 전에 성능이 악화되기 시작합니다. 두 프로세스는 메모리를 공유하지 않으므로, RFO 메시지를 생성하지 않습니다. 순수한 캐시 퇴출 문제입니다. 스마트 캐시 핸들링이 문제를 겪어, 코어당 체감 캐시 크기가, 이용 가능한 2MB보다는 1MB에 가깝게 됩니다. 만약 앞으로도 코어 간 공유 캐시가 남아 있다면, 스마트 캐시 핸들링 알고리즘이 개선되기를 바랄 수밖에 없습니다.
쿼드코어 프로세서에 두 개의 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 |
