캐시란
캐시는 보다 크고 느린 디바이스에 저장된 데이터 객체를 위한 준비 영역으로 사용하는 작고 빠른 장치이다.
이를 사용하는 과정을 cashing 이라고 한다.
메모리 계층구조의 중심 개념에는 각 k에 대해, 레벨 k에 있는 보다 빠르고 더 작은 저장장치가 레벨 k+1에 있는 더 크고 느린 저장장치를 위한 캐시서비스를 제공한다.
유명한 메모리 계층 구조의 사진이다.
로컬 디스크는 네트워크 너머 원격 디스크로부터 가져온 파일에 대한 캐시로 서비스 하며, 메인 메모리는 로컬 디스크 상의 데이터에 대한캐시로 서비스하는 식으로 가장 작은 캐시인 CPU 레지스터 집합에 이를때까지 지속된다.
위 그림이 메모리 계층 구조에서 일어나는 동작방식이다.
블록이라고 하는 저장장치에 연속된 데이터 객체 블록으로 나뉜다. 각 블록은 유일한 주소 또는 이름을 가지고, 자신을 다른 블록과 구분해준다.
k레벨 에서는 k+1레벨에서의 부분집합 사본을 포함한다.
L2와 L1 간의 전송은 일반적으로 수십 바이트의 블록을 사용한다.
L5 와 L4간 전송은 수백 또는 수천 바이트를 갖는 블록을 사용한다.
이런 긴 접근 시간을 줄이기 위해 더 큰 블록을 사용하는 추세라고한다. ㅎ
캐시 적중
어떤 프로그램이 레벨 k+1로부터 특정 데이터 객체 d를 필요로 할 때, 먼저 현재 레벨 k에 저장된 블록들 중의 하나에서 d를 찾는다.
만약 d가 레벨 k에서 우연히 캐시 되어 있으면 이 경우를 캐시 적중이라고 부른다.
메모리 계층구조의 본성에 의해 이것은 레벨 k+1에서 d를 읽는 것 보다 더 빠르다.
캐시미스
하지만 만약 데이터 객체 d가 레벨k에서 캐시 되지 않았다면 캐시 미스가 발생한 것이다.
미스가 존재할 때, 레벨 k에서 캐시는 레벨 k+1에 있는 캐시로부터 d를 포함하는 블록을 가져오며, 만일 레벨k 캐시가 이미 꽉 찬 상태라면 기존 블록에 덮어쓰기도 한다.
기존 블록을 덮어쓰는 과정은 블록을 교체하거나 추출하는 것으로 알려져 있다.
추출되는 블록을 희생블록이라고 부른다. 어떤 블록을 교체할지에 관한 결과는 캐시교체정책에 의해 정해진다.
예를들어 랜덤 교체정책을 사용하면 랜덤으로 희생블록을 선택하고, LRU교체정책을 갖는 캐시는 가장 과거에 접근한 블록을 선택한다.
캐시 미스의 종류
만일 레벨 k에서 캐시가 비어 있다면 모든 데이터 객체를 접근하려는 시도는 미스를 유발하게 된다.
비어있는 캐시는 종종 cold cache라고 불리며, 이런 종류의 미스들은 강제적인 미스 또는 콜드 미스라고 한다.
미스가 있을때는 k에서 k+1로부터 가져온 블록을 어디에 저장할지 배치정책을 구현하는데,
가장 유연한 배치정책은 k+1로부터 가져온 모든 블록을 레벨k의 어떤 블록에도 저장될 수 있도록 하는 것인데,
하드웨어로 구현되었고 속도가 가장 중요한 메모리 계층구조의 높은 곳에 위치한 캐시에 대해서 이러한 정책은 대개 구현하는 데 비용이 너무 많이드는데 그것은 랜덤으로 배치한 블록들의 위치를 찾는데 드는 비용이 크기 때문이다.
그래서 하드웨어 캐시는 일반적으로 레벨 k+1에서 특정 블록을 레벨 k에 있는 블록의 작은 부분집합으로 제한하는 단순한 배치정책을 구현한다.
이런 종류의 제한적인 배치 전력은 충돌미스 유형을 유도된다.
캐시관리
메모리 계층구조의 핵심은 각 레벨에 있는 저장장치가 다음 낮은 렙레을 위한 캐시라는점이다.
각 수준에서 일정형태의 논리회로가 캐시를 관리해야한다.
예를들어 컴파일러는 캐시계층구조의 최상위 레벨인 레지스터 파일을 관리한다.
이것은 미스가 존재할 때 언제 로드를 발급할지 결정하고, 어떤 레지스터가 이 데이터를 저장할지 결정한다.
레벨 L1,L2,L3의 캐시들은 캐시에 구현된 하드웨어 로직으로 관리된다.
가상메모리를 사용하는 시스템에서 DRAM 메인메모리는 디스크에 저장된 데이터 블록에 대한 캐시 서비스를 제공하고,
운영체제 소프트웨어와 CPU의 주소번역 하드웨어의 조합으로 관리된다.
캐시 메모리
초기 컴퓨터는 세 단계의 메모리 게층구조를 가졌지만, 현대와서는 CPU와 메인메모리 간의 커져가는 차이로 인해 L1캐시 라고 부르는 작은 SRAM 캐시 메모리를 CPU 레지스터 파일과 메인 메모리 사이에 끼워넣게 되었다.
기본 캐시 메모리 구조
각 메모리 주소가 M = 2^m개의 고유의 주소를 구성하는 m비트를 갖는 컴퓨터 시스템에 대해 생각해보면,
캐시는 S = 2^s개의 캐시집합의 배열로 구성된다.
각각 집합은 E개의 캐시 라인들로 이루어진다.
각 라인은 B = 2^b바이트의 데이터 블록, 해당 라인이 있는 의미의 여부를 포함하는 유효비트 1개 , 캐시 라인에 저장된 블록을 구분하는 태그비트로 구성된다.
만약 CPU가 메인메모리 주소A에서 하나의 워드를 읽으라는 load 인스트럭션을 받는다면, CPU 주소A를 캐시로 보낸다.
만약 캐시가 해당 워드의 사본을 주소A에 가지고 있다면, 즉시 CPU에 워드를 보낸다.
그러면 캐시는 어떻게 주소 A에 해당 워드 사본을 가지고 있는지 알까? 라는 의문을 가지게 된다.
캐시는 요청된 워드를 간단히 주소비트만 조사해서 찾아낼 수 있도록 구성되어 있으며, 매우 단순한 해시함수를 사용하는 해시 테이블과 유사하다.
직접매핑 캐시
캐시는 집합당 캐시 라인의 수 E에 의해 서로 다른 클래스로 구분된다.
집합당 정확히 한개의 라인을 갖는경우는 직접 매핑캐시 라고 알려져 있다.
만약 우리에게 CPU, 레지스터 파일, L1캐시, 메인 메모리를 갖는 시스템이 주어졌다면
CPU가 메모리 워드 w를 읽는 인스트럭션을 실행할 때, 이 워드를 L1 캐시에서 요청한다. 만일 L1캐시가 w의 복사본을 가지고 있다면 L1 캐시 적중이 되고, 캐시는 빠르게 w를 뽑아내서 CPU로 보낸다.
반대로 캐시 미스가 발생하면 CPU는 L1캐시가 메인메모리로 부터 w를 포함하고 있는 블록의 사본을 요청하는 동안 기다려야한다.
요청한 블록이 메모리에서 도착하게 되면, L1캐시는 이 블록을 자신의 캐시 라인 한개에 저장하고 w를 추출해서 CPU로 보낸다.
캐시가 어떤 요청이 적중인지 미스인지 결정하고, 요청한 워드를 뽑아내기 위해 수행하는 작업은 다음의 세 단계로 이루어진다.
1. 집합 선택
2. 라인 매칭
3. 워드 추출
집합선택
캐시는 s개의 집합 인덱스 비트를 w의 주소중에서 뽑아낸다.
비부호형 정수로 나타나지고, 이것이 하나의 집합 배열의 인덱스와 같아진다.
라인 매칭
전 단계에서 집합i를 선택했다고 생각하고 다음 단계는 워드w의 사본이 집합 i에 포함된 캐시라인에 있는지 결정하는 것이다.
직접매핑 캐시에서 집합당 한 개의 라인만 있기 때문에 쉽고 빠르다.
w의 사본은 유효비트가 설정되고, 캐시 라인의 태그가 w의 주소에 있는 태그와 일치하기만 하면 이 라인에 들어 있게 된다.
이 라인의 유효비트 valid가 1이고 그래서 태그와 블록들이 유효하다는 것을 알게된다.
반면 0이면 캐시미스를 받게 된다.
워드 선택
캐시 적중이 발생하면 w가 블록 내 어딘가에 있다는 것을 알게된다.
마지막 단계는 원하는 워드가 블록 내 어디에서 시작하는지 결정한다.
블록 오프셋 비트는 원하는 첫 바이트의 오프셋을 제공한다. 캐시를 라인들의 배열로 보는 방식을 다시 적용하면 블록을 바이트의 배열로 생각할 수 있고, 바이트 오프셋은 배열 내 인덱스로 볼 수 있다.
위 예제에서는 w의 사본이 블록 내의 4번째 바이트에서 시작한다는 것을 나타낸다.
직접매핑 캐시에서 충돌미스
float dotprod(float x[8],float y[8])
{
flaog sum = 0.0;
int i;
for (i = 0;i<8;i++)
sum += x[i] * y[i];
return sum;
}
위 함수는 x와 y에 대해 좋은 공간 지역성을 가지고 캐시적중이 많이 일어난다고 생각할수 있지만, 꼭 그렇지는 않다.
변수 sum 이 실제로는 CPU레지트서 내에 저장될 것이고, 메모리 참조를 하지 않는다고 가정하면 이러한 가정하에
x[i]와 y[i]는 동일한 캐시 집합에 매핑될 것이다.
실행될 때, 철 번째 루프의 실행에서 x[0]를 차조하면 미스가 되고, x[0] - x[3]을 포함하는 블록이 집합0에 로드되고, 다음 참조는 y[0]인데 다시 미스가 나 y[0]-y[3]을 포함하는 블록을 집합 0으로 복사하게 되는데 이 과정을하면서 전에 x들의 값이 지워진다.
이렇게 반복실행되므로 우리는 충돌 미스를 가지게 된다.
미래에 발생하는 x와 y에 대한 모든 참조는 블록 x와 y를 오고 가면서 thrash하는 충돌미스를 발생시키게 되는데
Thrashing은 캐시가 같은 집합의 캐시 블록들의 로드와 축출을 반복하는 경우를 말한다.
좋은 공간지역성을 가지며, 캐시에 x[i]와 y[i]를 위한 블록들을 보관하기 위한 캐시 공간이 있음에도 불구하고 블록들이
동일한 캐시 집합에 매핑 되기 때문에 발생하며, 2~3배 까지의 성능 저하를 가져오기도 한다.
집합 결합성 캐시
직접매핑 캐시의 충돌 미스 문제는 각 집합이 정확히 하나의 라인만을 가져야하는 제한에서 생긱게된다.
집합결합성 캐시는 이 제한을 완화해서 각 집합이 하나이상의 캐시 라인을 갖는다.
집합결합성캐시의 집합의 선택
집합의 선택은 직접매핑 캐시와 동일하며, 집합 인덱스 비트들은 집합을 나타낸다.
집합결합성 캐시의 라인매칭과 워드선택
요청한 워드가 집합에 있는지 결정하기 위해 여러 개의 라인의 태그와 유효비트를 조사해야 하기 때문에 직접매핑보다 집합결합성의 캐시의 라인매칭이 더 번거롭다.
보통 메모리는 값들의 배열로, 주소를 입력으로 받아서 해당 주소에 저장된 값을 리턴해준다. 반대로 결합성 메모리는 key,value 쌍의 배열로 ket를 입력받아서 (key,value)쌍 들중에서 입력 키와 매칭되는 쌍에 있는 값을 리턴한다.
그래서 집합결합성 캐시의 각 집합을 키들이 태그와 유효비트가 결합되어 있으며, 값들은 블록의 내용인 하나의 작은 결합성 메모리로 간주될 수 있다.
집합 결합성캐시에서 미스발생시 라인교체
CPU가 요청한 워드가 해당 집합의 라인 어디에도 저장되어 있지 않다면 미스가 발생한 것으로, 캐시는 해당 워드를 포함하는 블록을 메모리에서 선입해야한다.
그러나 일단 캐시가 그 블록을 가져오면, 어떤 라인을 교체해야 할까?
비어있다면 좋은 선택지지만, 아니라면 CPU가 교체되어 나간 블록을 안찾기를 바래야하는게 좋을것 이다.
코드에서 캐시 교체 정책 지식을 활용하는것은 굉장히 어려운일이다.
나중에 시간이 된다면 LFU(최소빈도사용)정책과 LRU(마지막 사용시점이 오래된 것 교체)정책에 대해 좀더 깊게 공부해보자.
완전결합성 캐시
완전결합성 캐시는 모든 캐시 라인들을 갖는 하나의 집합으로 구성된다.
완전결합성캐시의 집합의 선택
완전결합성 캐시에서 집합의 선택은 매우 간단한데 단 하나의 집합만 있기 때문이다. 주소에는 집합 인덱스 번호가 없고, 주소와 태그블록 오프셋으로만 나누어진다.
완전결합성 캐시의 라인매칭과 워드선택
집합 결합성 캐시와 동일하게 동작한다.
차이는 규모에서 나며 캐시 회로가 많은 수의 태그를 병렬로 검색하므로 크기가 큰 동시에 결합성 캐시를 만드는 것은 어렵고 비용이 많이든다.
그 결과 완전결합성 캐시는 가상메모리 시스템에서 페이지 테이블 엔드리들을 캐싱하는 TLB(translation look-aside buffers) 와 같이 작은 캐시에서만 사용하는것이 적절하다.
캐시 친화적 코딩
지역성을 배웠으니 어떤 경우에 좋은 지역성을 가지는 코드들은 더 낮은 미스 비율을 갖게 되며 , 더 낮은 미스 비율을 갖는 프로그램들은 미스비율을 갖는 프로그램들보다 더 빨리 실행되는 경향을 보인다.
그래서 좋은 프로그래머라면 캐시 친화적인 코딩을 익혀둘 필요가 있다.
캐시 친화적인 프로그래밍을 위한 접근법은 다음과 같다.
1. 공통적인 경우를 빠르게 동작하게 만들어라.
프로그램들은 대부분의 시간을 몇 개의 핵심 함수들에서 소모한다. 이 함수들은 대부분 시간을 몇 개의 루프에서 보낸다.
그래서 핵심함수들의 내부 루프에 집중하고 나머지는 무시한다.
2. 각 내부 루프의 캐시 미스 수를 최소화해라. Load와 store의 총수가 같다는 등의 다른 것들이 동일하다면 우수한 미스 비율을 갖는 루프들이 더 빨리 동작한다.
int sumvec(int v[N])
{
int i, sum = 0;
for (i = 0;i<N;i++)
sum += v[i];
return sum;
}
전에 배운 sumvec 을 다시 봐보면
과연 이 함수가 캐시 친화적인가? 라는 의문을 던져봐야한다.
먼저 지역변수 i와 sum 에 대해서 루프 본체는 좋은 시간 지역성을 갖는 점에 주목해야한다. 사실 이들은 지역변수이기 때문에 어느정도 최적화된 컴파일러라면 이들을 레지스터 파일, 즉 메모리 계층구조의 최상위 계층에 캐싱할 것이다.
벡터 v에 대한 stride-1 참조에 대해 생각해보면,
만일 캐시가 B블록 크기를 갖는다면, stride-k 참조 패턴은 루프 반복 실행당 min[1,(wordsize * k)/B]의 평균 미스횟수를 나타낸다.
'정글' 카테고리의 다른 글
| (TIL 25일차) 가상 메모리1 (0) | 2023.05.18 |
|---|---|
| TIL(24일차) 프로세스 (0) | 2023.05.18 |
| (TIL22일차) 저장장치 (0) | 2023.05.17 |
| TIL(21일차) 메모리 할당기 제작 기초 (1) | 2023.05.17 |
| TIL(20일차) 동적 메모리 할당 (0) | 2023.05.14 |
