reference: "프로그래머가 몰랐던 멀티코어 CPU 이야기" / 김민장, "Computer System A Programmers'Perspective" / 랜달 E.브라이언트
캐시가 잘 작동할 수 있는 원리: 데이터 접근의 지역성을 효과적으로 이용
과거 1996년의 펜티엄 프로세서는 100MHz로 작동했고, 그때의 메모리 클록 속도는 66MHz, 100MHz 정도로 별 차이가 없었다. 그러나 프로세서의 클록 속도는 메모리보다 훨씬 빨라지기 시작했다. 2009년 프로세서는 2~3GHz인데 메모리의 클록 속도는 553MHz에서 800MHz밖에 되지 않는다.
현대의 CPU 캐시는 온 칩(on-chip) 캐시라고도 부른다. 과거 반도체 기술이 부족했을 땐 L2 캐시가 칩 밖, 메인보드에 있었다. 이런 캐시를 오프 칩(off-chip) 캐시라고 한다. 그러나 이제는 일부 특수 목적의 프로세서를 제외하고는 모두 칩 안으로 캐시가 올라와있다.
이런 여러 이유로 프로세서가 메인 메모리(DRAM)에서 데이터를 읽고 쓰는 것은 긴 시간이 걸리고 캐시가 절실한 이유가 된다. 실제 컴퓨터 성능의 병목 지점은 DRAM이나 하드디스크와 같은 데이터 입출력에 있다. 아무리 계산을 빠르게 하고 싶어도 데이터를 빠르게 가져올 수 없다면 무용지물이다. 캐시가 있기에 지금의 고성능 컴퓨터가 있다고 말해도 과언이 아니다.
캐시는 CPU에만 있는 것이 아니다. 일반적으로 메모리 계층 구조에서 속도, 공간, 가격 차이가 있는 두 계층 사이라면 캐시는 있을 수 있다. 예를 들어, 하드 디스크에도 캐시가 있다. DRAM 내에는 행 버퍼(row buffer)가 있다. 소프트웨어로 눈을 돌리면 캐시는 너무나 많은 곳에서 찾을 수 있다. 운영체제 파일 시스템에도 여러 버퍼와 캐시가 있다. 서버 시스템에도 다양한 계층의 캐시를 두어 응답 속도를 높인다. 가까운 웹브라우저에도 캐시가 중요한 역할을 한다.
그렇다면 캐시가 잘 작동할 수 있는 원리는 무엇일까? 캐시는 데이터 사용에 있어 "지역성(locality)"이라는 특성을 이용한 장치이다. 이 지역성은 **시간적 지역성(temporal locality)과 공간적 지역성(spatial locality)으로 구분된다.
- 시간적 지역성은 지금 어떤 데이터를 사용했다면 가까운 미래에 다시 사용할 확률이 높다는 것을 가리킨다.
- 공간적 지역성은 어떤 데이터가 사용된다면 그와 인접한 데이터에 접근할 것 같음을 뜻한다.
결국 지역성은 특성/원리를 뜻한다.
for(int i=0; i < N; i++){
data[i] = data[i-1] + 1;
}
// data[1]이 첫 번째 순환에서 값이 갱신되면 그 다음 순환에서 피연산자로서 읽힌다. <= 시간적 지역성
// data[1]부터 data[N-1]까지 접근한다. <= 공간적 지역성CPU 캐시는 바로 이 데이터 접근의 지역성을 효과적으로 이용한다. 데이터 접근의 시간적 지역성을 위해 캐시는 최근에 쓴 데이터를 보관한다. 가까운 미래에 이 데이터가 다시 사용된다면 빠르게 줄 수 있다. 공간적 지역성은 데이터를 캐시에 넣을 때 그 데이터만 넣는 것이 아니라 그와 인접한 데이터도 함께 가져와서 해결한다.
일반적인 캐시 구조
source: https://hwannny.tistory.com/96
일반적인 소프트웨어 캐시를 이야기해보자면, 캐시는 접근 속도, 대역폭, 단위 용량 당 가격 등 성능 차이가 뚜렷한 두 계층 사이에서 지역성을 활용해 자주 쓰이거나 인접한 자료를 잠시 저장한다. 캐시 모듈을 만든다고 할 때 어떠한 인터페이스가 필요한지 생각해보면, 먼저 (1) 캐시에서 원하는 데이터를 찾거나 (2) 새로운 데이터를 추가하는 함수가 필요하다. 캐시는 대부분 공간이 제한적이므로 캐시가 가득 찬 상태에서 새로운 데이터를 넣어야 할 때, (3) 이전 데이터 중 일부를 교체할 수 있는 정책이나 알고리즘이 필요하다.
정리하자면 캐시는 다음과 같은 인터페이스과 알고리즘을 제공해야 한다.
1) 캐시에서 원하는 데이터를 찾는 검색 인터페이스
2) 새로운 데이터를 추가하는 삽입 인터페이스
3) 교체할 수 있는 정책이나 알고리즘
캐시 관련 용어
캐시 히드: 캐시에 원하는 데이터가 있을 때
캐시 미스: 찾지 못하였을 때
미스 패널티(miss penalty): 캐시 미스 시 직접 해당 데이터를 찾아와 넣어야 하는 비용.
히트 레이턴시(hit latency): 캐시가 적중해도 원하는 자료를 가져오는데 역시 비용이 필요. 이 비용을 뜻함
일반적인 소프트웨어 기반 캐시 시스템 구조에서 캐시는 여러 캐시 엔트리로 구성된다. 각 엔트리는 실제 캐시하는 데이터와 부가 정보가 있다. 부가 정보는 캐시 구현에 따라 달라지겠지만 일반적으로 (1) 실제 저장되는 데이터, (2) 태그(tag, 인식표), (3) 캐시 찾기에 관련된 정보(포인터 같은 것), (4) 캐시 교체에 관련된 정보(예를 들어, 언제 얼마나 이용되었는가), (5) 기타 정보가 필요하다.
캐시는 크기가 제한되어 있어 캐시가 가득 찼을 때, 기존의 캐시 엔트리 중 일부를 교체하는 알고리즘이 필요하다. 간단히 예를 들면, 가장 오랫동안 쓰이지 않은 캐시 엔트리를 삭제하고 빈 공간을 만들면 된다. 교체 정책에 따라 단순한 카운터만 필요할 수도 있고, 다양하고 복잡한 자료구조가 필요하기도 한다. 캐시를 설계한다면 캐시 엔트리 구조를 정하고 최적의 탐색 방법, 그리고 교체 정책을 정의해야 한다.
CPU 캐시, 혹은 하드웨어 캐시도 기본적인 개념은 소프트워에 캐시와 동일하다. 그러나 CPU 캐시는 일반적으로 SRAM(Static Random Access Memory)으로 만들어지는데 DRAM에 비해 제조 비용이 비싸서 최대한 공간을 아껴야만 한다. 또한, CPU 캐시를 만드는데 해시 테이블처럼 포인터로 연결된 자료구조를 순회하거나 갱신하는 것은 매우 어렵다. 캐시 탐색에 있어 복잡한 해시 함수도 쓰기 어렵다. 캐시 교체에 필요한 부가 정보도 그 양을 줄여 비트 단위로 관리하고, 교체 알고리즘도 최대한 간단히 만들어야 한다. 그렇지 않다면 캐시 레이턴시가 지나치게 길어진다.
CPU 캐시의 기본적인 설계
앞선 글을 정리하자면, CPU 캐시(이하 캐시)는 메인 메모리와 레지스터 파일 사이의 큰 속도 격차를 줄이려고 프로세서 내에 있는 작지만 매우 빠른 기억장치이다. 캐시는 데이터 접근의 시간적/공간적 지역성을 활용한다. 캐시로 데이터를 메모리에서 가져오는데 필요한 시간(메모리 레이턴시)을 크게 줄일 수 있다. 아래 글부터 CPU 캐시를 앞서 살펴본 일반적인 캐시 설계 기준에 맞추어 생각해본다.
요즘 프로세서는 캐시가 여러 계층으로 있다. L1(Level 1, 일차), L2(Level 2, 이차) 캐시는 현대 프로세서 구조에서는 일반적이 되었고, L3(Level 3, 삼차) 캐시까지 있는 CPU도 쉽게 볼 수 있다. 보통 마지막 레벨의 칩 내 캐시를 특별히 LLC(Last Level Cache)라고도 부른다. LLC 이후는 시간이 매우 오래 걸리는 칩 밖의 메모리 계층으로 이동해야 하기에 특별히 구분된다.
여러 계층의 캐시를 두는 것은 캐시 접근 속도와 용량 사이의 trade-off가 있어 여러 단계를 두면 성능이 더 좋아지기 때문이다. 프로세서가 메모리 시스템에 데이터를 요청하면 L1 캐시부터 찾는다. 여기서 찾지 못하면 L2에게 다시 요청하고, LLC까지 도달해도 없다면 비로소 메인 메모리로 가서 데이터를 가져온다. 이 데이터는 캐시에 보관되고 최종으로 프로세서에게 반환된다. 일반적으로 L1 캐시는 명령어와 데이터를 분리해 저장하는 것이 더 효과적이어서 많은 프로세서들이 이런 방식을 취한다. 그러나 L2 캐시 이상은 보통 데이터와 코드를 분리하지 않고 한꺼번에 저장한다.
캐시 설계에서 풀어야 하는 네 가지 문제
- 검색 방법: 주어진 데이터가 캐시에 있는지 어떻게 알아낼 것인가?
- 배치 정책: 주어진 데이터가 캐시 어디에 자리 잡을 것인가?
- 교체 정책: 캐시에 빈 공간을 어떻게 마련할 것인가?
- 쓰기 정책: 데이터를 쓰는 작업은 어떻게 다룰 것인가?
캐시 라인(cache line) 또는 캐시 블록(cache block)
이전 일반적 캐시 구조에서 설명한 캐시 엔트리와 같은 개념이다. 그런데 이 캐시 라인에 저장되는 데이터의 단위 크기는 1바이트나 4바이트가 아닌 그보다 큰 32, 64, 128 바이트가 일반적이다. 이것은 공간 지역성을 활용하기 위해서이다. 첫 번쨰 캐시 미스를 겪을 때 인접한 데이터도 같이 캐시에 올림으로써 이전 for문 예시와 같이 캐시 적중률을 높인다. 그리고 여기에는 캐시 엔트리 설명에서도 보았듯 태그나 부가 정보가 덧붙는다.
많은 프로세서의 (인텔 및 AMD) 캐시 라인 크기가 64바이트이다. 캐시 라인 크기가 너무 작으면 공간 지역성 활용이 낫다. 그러나 너무 커도 문제가 되는데 데이터를 가져오는데 그만큼 시간이 오래 걸린다.
(컴퓨터 시스템 구조론 참고)
캐시의 기본 단위를 언급할 때, 두 가지 이유 때문에 블록이라는 용어보다는 라인이라는 용어가 사용된다.
(1) 캐시 라인과 같은 수의 데이터 단어들을 포함하고 있는 주기억장치 블록과의 혼동을 피하기 위해
(2) 캐시 라인은 주기억장치 블록과 마찬가지로 K개의 데이터 단어들만 포함하고 있을 뿐 아니라 태그와 제어 비트들도 파함하고 있기 때문.
각 라인의 제어 비트는 캐시에 적재된 이래 수정된 적이 있는지, cache coherency 관련 정보를 위해 사용된다.
태그와 제어 비트들을 제외한 라인의 길이는 라인 크기(line size)이다.
1. 캐시 검색 방법
32비트 프로세서에서 64바이트 캐시 라인이라면 캐시 라인은 6천만 개(2^32/2^6 = 2^26)가 넘는다. 임의의 주소값이 넘어오면 6천만 개의 가능 캐시 라인 중 하나가 선택될 것이다. 임의의 주소값이 넘어오면 6천만개의 가능 캐시 라인 중 하나가 선택될 것이다. 그러나 캐시의 크기는 L1 캐시는 고작 32KB 정도, 가장 큰 L2/L3 캐시도 메가 바이트 단위이다. 저장할 수 있는 캐시 라인 수는 수백 개에서 수만개밖에 안된다. 따라서 6천만 개의 캐시 라인 주소를 캐시가 가진 수만큼 매핑할 수 있어야 한다. 이상적으로는 해시 테이블 같은 자료구조가 필요하다. 그런데 CPU 캐시는 소프트웨어 캐시처럼 일반적인 해시 테이블로 구성하기 어렵고 단순히 캐시 라인의 배열로 구성된다. 또한 하드웨어에서는 소프트웨어의 복잡한 해시 함수를 만들기는 너무 비용이 크다. 그래서 아주 간단하게, 주어진 주소를 단순 분해해서 캐시 자료구조로 매핑한다. 주어진 주소가 있으면 캐시는 세 부분 (1) 태스(tag), (2) 인덱스(index), (3) 오프셋(offset)으로 나누어 쓴다.
예를 들어 512(2^9)의 캐시 라인이 있는 캐시라면 가운데 9비트만큼이 인덱스에 해당한다. 그리고 최상위 비트 중 나머지 부분을 태그로 활용한다. 태그는 인식표와 같은데 인덱스로 찾아진 캐시 라인이 내가 정말 원하는 값인지 확인하는데 쓰인다. 마지막으로 데이터 주소의 하위 비트 일부는 오프셋으로 쓴다. 오프셋은 캐시 라인 내에서 원하는 데이터를 가리키는데 필요하다. 예를 들어 64바이트 캐시 라인이라면 6비트(2^6 = 64)만큼이 오프셋 영역이 된다.
인덱스를 가운데 영역으로, 태그를 최상위 영역으로 택한 이유는 캐시 매핑 시 충돌을 적세 하기 위해서다. 해시 테이블에 비유하면 충돌이 적은 해시 함수를 만드는 것과 같다. 만약 인덱스와 태그의 순서가 바뀌었다고 생각해보자, 보통 연속된 데이터에 접근할 때 최상위 부근의 숫자들은 잘 바뀌지 않을 것이다. 그렇다면 수많은 다른 메모리 주소가 같은 인덱스를 갖게 되어 충돌이 잦아져 캐시의 성능이 크게 저하된다.
2. 캐시 배치 정책
같은 인덱스를 가지는 메모리 주소는 오직 한 곳에만 배치될 수 있다. 그런데 이런 구존느 같은 인덱스를 가지는 여러 개의 메모리 주소가 충돌을 일으킬 수 있는 문제가 있다. 예를 들어, 같은 인덱스를 같는 0xA00과 0xB00의 데이터가 번갈아가며 접근될 때 항상 캐시 미스가 일어난다. 이러한 충돌을 최소화하고자 한 인덱스에 여러 개의 캐시 공간을 할당한다.
이러한 캐시 배치 정책에는 3가지가 있다.
(1) 직접 사상 캐시(direct-mapped): 한 인덱스에 캐시 라인 하나 할당하는 배치 정책
(2) 집합 연관 캐시(set-associative): 한 인덱스가 N개의 캐시 라인 내에서 대응할 수 있는 배치 정책
(3) 완전 연관 캐시(fully-associated): 캐시 어디에도 할당할 수 있는 배치 정책.
집합 연관 캐시는 하나의 인덱스가 여러 개의 캐시 라인에 들어갈 수 있는데, 이때 여러 개가 N이라면 N-way(웨이) 집합 연관 캐시라고 부른다. N을 연관도(associativity)라 한다. N개의 캐시 라인은 하나의 세트(set)를 이룬다.
직접 사상과 완전 연관은 N-웨이 집합 연관 캐시의 양 극단이다. 집합 연관 캐시의 장점은 캐시 충돌을 줄일 수 있다는데 있다. 앞서 살펴본 두 개의 주소 예시도 2-웨이만 되더라도 캐시 충돌 미스를 없앨 수 있다. 현대 고성능 프로세서는 보통 8-웨이, 24-웨이 같은 연관도가 높은 캐시 구조도 쉽게 찾아볼 수 있다.
32비트 프로세서에서 64바이트 캐시 라인을 갖는 32KB 캐시를 예로 들어본다. 32KB 캐시는 총 32K(2^15)/64(2^6) = 512(2^9)개의 라인을 저장할 수 있다. 직접 사상에서는 512개의 세트가 있다 생각하면 되고, 4-웨이 집합 연관 캐시에서는 512(2^9)/4(2^2) = 128(2^7)개의 세트가 있다. 따라서 인덱스 비트도 9비트에서 7비트로 줄었다. 세트 인덱스를 먼저 구하고, 이 세크에 있는 4개의 캐시 라인을 모두 태그로 검색해 원하는 데이터가 있는지 찾는다.
연관도를 높이면 캐시 충돌을 줄일 수 있으나 그만큼 전력과 트랜지스터 비용이 증가하므로 적절한 타협점을 찾아야 한다.
캐시 배치 알고리즘은 사실 해시 테이블과 다를 것이 없다. 다만 하드웨어에서 소프트웨어 해시 테이블처럼 가변 리스트를 가질 수 없어서 고정된 개수의 리스트를 가지고 있다고 보면 된다. N-웨이 집합 연관 캐시는 각 원소마다 N개의 고정 길이를 가진 해시 테이블 구조로 보면 된다.
3. 캐시 교체 정책
같은 크기의 캐시에서 캐시 적중률(hit rate)은 캐시 연관도에도 영향을 미치지만 캐시 교체 정책(cache replacement policy)이 상당히 중요한 역할을 한다. 캐시 교체 정책은 직접 사상 캐시(direct mapping cache)에서는 의미가 없다. 어차피 인덱스 하나가 갈 수 있는 곳은 하나여서 이미 어떤 데이터가 그 자리르 차지하고 있다면 무조건 이 데이터가 삭제된다. 그러나 집합 연관 사상 캐시(set associate mapping cache)는 최대 N개 중 하나를 골라 없애야 하므로 어떤 정책을 쓸 것인지 결정해야만 한다.
캐시 세트에 빈 공간이 있다면 그 자리에 새로운 캐시 데이터를 채우면 된다. 그렇지 않다면 그 캐시 세트에 있는 데이터 중 하나를 보내야 한다. 가장 단순한 방법으로 랜덤하게 아무 녀석이나 쫒아낼 수도 있다. 이때는 어떠한 부가 정보도 기록할 필요가 없다. 그러나 이러할 경우 성능이 좋게 나올리 없다. 무언가 합리적인 정책을 생각해야 한다. 이상적인 최고의 정책은 '앞으로' 가장 오랫동안 사용되지 않을 캐시 라인을 내보내는 것이다. 그런데 이것은 미래에 일어날 일을 미리 알아야 하므로 완벽한 구현이 불가능한 정책이다. 대신 지금까지 일어난 과거 정보로 추론할 수 있다. 여러 정책이 있지만 일반적으로 가장 최근에 사용되지 않은 캐시 라인을 없애는 것이 효과적으로 알려져 있다. 이 정책을 LRU(Least Recently Used)(가장 오랫동안 사용되지 않은 것을 교체)라 부른다. 비슷한 정책으로 캐시 라인의 접근 빈도를 따지는 LFU(Least Frequently Used), 단순한 FIFO(First in First out, like queue) 정책도 있다.
LRU 정책의 소프트웨어적인 구현 방법은 매우 직관적이다. LFU는 접근할 때마다 카운터 값을 증가시키고, FIFO는 큐 자료구조를 쓰면된다. LRU는 캐시 라인마다 마지막으로 접근된 시각, 타임 스탬프(time stamp)를 기록한다. 타임 스탬프는 CPU 사이클 값이다. 그리고 교체가 필요할 때, 캐시 라인의 타임 스탬프를 비교해 가장 작은 라인을 삭제하는 것이다. 그러나 하드웨어에서 이러한 구현 방식은 실현되기 어렵다. CPU 사이클은 쉽게 조 단위로 증가하므로 32비트보다 큰 정수형이 필요하다. 캐시 라인마다 이런 큰 카운터를 두는 것은 비용이 무척 크다. 다행히 N-웨이 집합 연관 캐시라면 각 캐시 라인마다 Log2N 비트의 카운만 있으면 LRU를 구현할 수 있다.
(자세한 설계와 알고리즘은 story 12 참고)
4. 캐시 쓰기 정책
캐시에서 데이터를 읽는 것은 여지껏 살펴본 캐시 탐색, 배치, 교체 정책을 그대로 따르면 된다. 그러나 쓰기는 생각할 문제가 더 있다. 캐시에 데이터를 쓸 때 먼저 두 가지 정책을 생각할 수 있다.
1. Write-Through(라이트 쓰루): 캐시 쓰기가 있을 때, 메모리 또는 아래 계층의 캐시로 바로 반영할 수 있다.
2. Write-Back(라이트 백): 변경된 데이터를 일단 캐시가 들고 있다가 나중에 캐시에서 쫓겨날 때 비로소 메모리를 갱신할 수도 있다.
라이트 백이 라이트 쓰루에 비해 가지는 장점은 자명하다. 라이트 쓰루 정책은 캐시를 쓸 때마다 아래 계층의 캐시나 메모리를 반영해야 하므로 레이턴시가 길다. 반면, 라이트 백 캐시는 구현이 약간 복잡해진다. 캐시 라인 마다 '더티 비트(dirty bit)'를 둔다. 처음에 이 값은 0으로 시작하며 후에 캐시 라인이 쓰여지면 더티 비트를 켠다. 갱신된 데이터가 캐시에만 있고 아직 메모리에 최종 반영되지 않았음을 뜻한다. 그러다가 캐시 라인이 교체되면 비로소 메모리에 바뀐 값을 쓴다. 일반적으로 대부분의 캐시는 라이트 백 쓰기 정책을 쓴다. 예외적으로 L1 명령어 캐시는 흔히 라이트 쓰루를 쓴다. 프로그램 명령어 코드는 보통 거의 수정이 이루어지지 않기 때문이다.(굳이 라이트 백을 써서 더티 비트를 관리할 필요가 없기 때문?)
캐시 쓰기 정책은 운영체제나 파일 입출력 프로그래밍에서도 쉽게 찾아볼 수 있다. 일반적인 하드 디스크는 기본적으로 쓰기 캐시, 라이트 백 정책의 쓰기 캐시가 켜져 있다. 하드 디스크에 바로 쓰지 않고 일단 메모리에 쓰기 캐시를 두고 거기에 데이터를 모은다. 캐시가 다 차면 주기적으로 이 내용을 디스크로 내보낸다. 그런데 이 정책은 USB 메모리 스틱처럼 빈번히 탈착되는 저장 장치에 오히려 나쁘다. USB 메모리를 컴퓨터에서 뽑을 때는 반드시 아직까지 반영되지 않은 쓰기 캐시를 처리해야 한다. 만약 쓰기 캐시가 켜져 있을 때, USB 메모리를 뽑고 싶을 때는 반드시 안전한 하드웨어 제거를 거쳐야만 한다. 그래야 쓰기 캐시가 디스크로 저장(flush)될 수 있다. 그래서 USB 메모리는 기본적으로 쓰기 캐시를 쓰지 않도록 설정된다.
