[CS:APP 12] Cache Memories

12강|embed

어제 12화를 보고 머릿속으로 정리를 좀 하고나서 오늘 올립니다
CSAPP 수업을 듣거나 책을 읽지 않고, 이 과목을 들은 적 없는 사람들을 위해서
필요없는 부분은 최대한 쳐내고 가장 쓸모 있는 부분과 코딩 팁들을 정리해서 올립니다.

Cache는 지역성을 이용해 성능을 올린다

11화에서도 말했듯이, 프로그램이 나타내는 지역성에는 두가지가 있다.

하나는 temporal locality: 어떤 주소의 데이터를 반복해서 참조하는 것이다.
하나는 spatial locality: 어떤 주소 가까이의 데이터를 참조하는 것이다.

프로그램을 만들고 보니 이런 지역성이 나타나서, 하드웨어 설계자들은 이걸 이용해서 성능을 올리기 위해
cache라는 것을 만들어 낸다.

temporal locality를 잘 써먹으면 성능을 올릴 수 있다는 것은, cache라는 것이 존재한다는 것만 알아도 알 수 있다.
훨씬 빠른 저장장치에 이미 저장된 데이터를 여러번 울궈먹으면 당연히 성능이 올라갈 것이다.

^{참고로 cache memory는 아예 CPU안에 박혀 있다.}

그런데 프로그램에 spatial locality가 있으면 왜 성능이 향상될까?
잠시 한번 생각해 보자... 오늘의 질문이다

.
.
.
.
.
.
.
.
.
.
.
사실 이전 그림의 단순한 cache memory 구조로는 spatial locality에 의한 성능 향상의 원인을 알 수가 없다.
실제 캐시메모리가 작동하는 방식과 좀 더 자세한 내막을 알아야만 그 이유를 파악할 수 있다.

Cache Memory 구조

아마 하드웨어 제조자들이 프로그램에 spatial locality가 빈번하게 나타난다는 것을 알아채고
다음과 같은 구조와 기능을 갖도록 cache memory를 설계했을 것이다.

cache memory는 개념적으로는 bit들을 저장할 수 있는 2차원 배열이다.
이 2차원 배열에다가 하부 hierarchy에 있는 저장장치의 데이터들을 가져와서 임시로 저장한다.
(즉 main memory의 데이터들을 가져와 저장한다)
그런데 데이터들을 마구잡이로 담을 수는 없으니까 데이터 저장의 규칙을 세우기 위해 이 비트들을 쪼갠다.

2차원 배열을 S개의 set(행)으로 나누고
나뉘어진 S개의 set을 또 E개의 line들로 나눈다.
그러면 이 캐시메모리에는 S*E개의 line이 있다.

각 line 하나는 3가지 영역으로 나누어진다.

1. valid bit   v: 이 bit는 현재 line에 있는 데이터가 하부 hierarchy에서 가져온 데이터들인지 판별해 준다. 1이면 valid하다는 것.
2. tag bits  tag: 이 bit들은 데이터를 캐시에 쓰고 읽는데 필요한 플래그들이다
3.   cache block: 이 byte들이 바로 데이터가 저장되는 부분이다. 이 구조를 통해서 spatial locality를 이용한다.

여기서 cache block에 주목하라. 이 바이트열 때문에 spatial locality가 중요해진다.
일단 이건 나중에 다시 설명하겠다.

Cache로부터 데이터 읽어들이기

그럼 이렇게 생긴 캐시 메모리에서 어떻게 데이터를 읽어올까?

CPU는 메모리에서 데이터를 읽고 싶으면 저장장치 쪽으로 메모리 주소를 발싸한다.
걔는 메모리가 어떻게 생겼는지는 별로 관심이 없다. 일단 데이터만 가져다주면 되는 것임.
일진이 빵셔틀에게 관심이 있겠는가?

여튼 CPU에서 어떤 메모리 주소(64bits)를 캐시쪽으로 발싸했다고 생각하자.
그럼 이 둘 중 한 가지 상황이 일어난다

1. 이 메모리 주소의 데이터가 캐시에 있다면 cache hit!
   빵셔틀cache은 주머니에 있던 빵data을 일진 CPU에게 바로 줄 수 있다
2. 이 메모리 주소의 데이터가 캐시에 없다면 cache miss!
   빵셔틀cache은 매점main memory에 달려가서 빵data을 사와야 한다! ㅠㅠ

구체적인 과정

주소를 표현한 비트들을 3가지 부분으로 나눈다.

세 부분의 bits 중 t,s를 이용하여 캐시에 이 주소의 데이터가 저장되어 있는지 판단하고
마지막 b bits를 이용하여 캐시의 line의 블럭 어디서 부터 데이터를 읽을지 정한다.

1) 먼저 s bit들로 이 주소가 캐시의 어느 set에 있는지 판단한다.

2-1) 주소의 t bits와 1)에서 정한 set 안의 line들의 tag들과 비교한다. 이 비교는 t bits == tag가 나올 때까지 한다.
2-2\) t bits == tag인 line을 1)에서 찾은 set 안에서 찾아냈으며 그 line의 valid하다면(valid bit v == 1) cache hit이다!

끝까지 비교해 보았으나 주소의 t bits == tag 인 line이 set에 존재하지 않았다면 cache miss이다!
데이터가 캐시에 없다할지라도 요청한 CPU에게는 데이터를 줘야하니까... 캐시는 하부 메모리에서 값을 가져와야 한다.

이 경우 set안의 line 중 하나를 골라서 데이터를 비우고 하부 메모리에서 값을 가져와 덮어 쓴다.
이 때 어느 line을 고르느냐는 하드웨어 만든 놈 맘대로(replacement policy)인데, 보통 가장 덜 참조되는 line을 고른다(Least Recently Used, LRU)

3)마지막으로 주소의 b bits를 이용하여 cache block에서 어느 바이트부터 읽을지 정한다.

이렇게 하여 캐시를 읽을 수 있다.

Cache가 Spatial Locality를 활용하는 법

그리고 이제는 알 수 있다.

캐시는 어떻게 해서 프로그램의 spatial locality를 통해 성능을 향상시키는가?
왜 stride-1 reference pattern이 stride-2 reference pattern보다 이론적으로는 약 2배 빠른가?

그것은 cache block의 존재, 그리고 cache를 읽는 방식 때문이다!

예를 들어서 stride-1 과 stride-2를 비교해 보자.

char arr[10] = {0,100,200,300,400,500,600,700,800,900};

10개짜리 char배열에 접근하여 데이터를 캐시에서 CPU로 가져올 때,
캐시 블럭의 크기가 5 byte라고 하자. 그러면 다음과 같은 그림을 그릴 수 있다.

그래서 stride-1이 이론적으로는 2배쯤 성능이 높은 것이다.

이렇게 하드웨어 제조사는 cache block이라는 구조를 만들어서, 프로그램의 spatial locality를 활용하여 성능을 올렸다.

...솔직히 이 부분의 제 설명이 잘 이해가 될지 모르겠습니다.
CMU에서 제공하는 ppt로 슬라이드쇼 한번 보시는 게 이해가 빠르실 거 같습니다.

실제로는 이렇게 생긴 애들이 계층구조를 이룹니다...
L0에 데이터가 없으면 L1에서 가져오고, 거기에도 없으면 L2에도 가져오고, 거기에도 없으면 L3, 거기에도 없으면
최악으로 메인메모리까지 내려가서 가져옵니다. 이거 완전 다단계

Cache를 잘 써먹는 C 코드 짜기

솔직히 여기까지 글 읽었으면 이런 생각일 것.

"그래 뭐 알겠다. 지역성이 중요하고 템포랄, 스패샬,.... 니가 그렇다는데 그런 거겠지. "
"그런데 C 코드는 어떻게 짜야 하는데?"

캐시메모리는 모두 하드웨어에 의해 자동으로 처리되는 부분이고
프로그래머에게는 보이지 않는다.

그러나 캐시에 대한 지식이 있으면 캐시를 잘 울궈먹는 코드를 짤 수 있다!

C에서는...

1. 실행이 가장 빈번히 실행되는 코드의 부분(함수)을 찾는다
   • 덜 실행되는 부분은 캐시에 올라가봤자 금방 빠져 나간다...
2. 그 함수에서 내부 루프에서의 캐시 미스를 줄인다
   • 반복되는 레퍼런스는 temporal locality 측면에서 좋다
   • stride-1 reference pattern을 사용하면 spatial locality 측면에서 좋다.
   • loop바디가 작으면 동일한 인스트럭션들에 여러번 접근할 수 있어 temporal locality 측면에서 좋다.
3. 왠만하면 지역변수를 쓰자. 성능 측면에서도 고려해 볼 측면이 있다.
   • C에서 지역변수는 보통 **register(L0)**에 값을 넣어 저장한다.
   • 그러나 전역변수는 무조건 register에 **주소(참조)**를 넣어 접근한다.

temporal locality를 이용하여 최적화하는 스킬 중 가장 유명한 것이 blocking이다.

이걸 쓰면 다음 코드를

이렇게 바꾼다

for문이 잔뜩인데 오히려 빨라진다. 왜?? 딱 캐시에 들어갈 만큼 잘라서(blocking) 계산하는 거거든...
잘 모르겠으면 CSAPP책과 이전 글에 올린 ppt를 참고하세욧 ^_^

진짜 끗. ㅎㅎㅎㅎ 힘들었으

과거 블로그 댓글
프로그래밍 갤러리 댓글

추가

• 글의 흥미를 유지하기 위해 독자에게 질문을 던졌다. 실제 공부할 때도 도움되는 스킬이다.
• 시간적 지역성을 통한 최적화는 캐시의 존재만으로 이해할 수 있다. 하지만 공간적 지역성은 어떻게 써먹는가? 이 질문에 답하기 위한 지식을 정리한 게 이 글이다.
• 책과 강의에는 캐시에서 데이터를 읽는 과정 뿐 아니라 쓰는 과정도 나온다. 하지만 위 질문에 답하는 데는 필요 없는 지식이므로 과감히 생략했다.

했던 lab 과제: https://github.com/KUR-creative/cachelab