[system programming] 캐시 메모리 (Cache Memory Organization and Operation)

본 게시글은

서울대학교 데이터사이언스대학원 정형수 교수님의

데이터사이언스 응용을 위한 컴퓨팅 시스템 강의를

학습을 목적으로 재구성하였습니다

---

 

저번 시간에 이어 오늘 배울 내용은

cache memory

 

저번시간에도 강조했지만

아주아주 중요한 내용이라고 한다

 

 

이런 내용을 오늘 주로 다룬다고한다

캐시 메모리가 어떻게 구조화되어있고

어떻게 작동하는지랑

캐시 메모리가 성능에 어느 정도로 큰 영향을 미치는지를

확인해본다고 한다

 

지난 시간에 배웠던 것을 복습해보자

자세한 내용을 확인하고싶다면

이전 게시글을 확인해보면 좋을 것 같다

 

데이터에는 기본적인 성질과도 같은 것이 있는데

그게 바로 Locality이고

temporal locality와 spatial locality가 있다

 

 

이렇게 생긴 메모리 계층구조에 대해 배웠었다

밑으로 내려갈수록 Exponential하게 속도가 느려진다

 

 

메모리 계층구조에서 위에 있는 메모리는

항상 아래에 있는 메모리의 캐시 역할을 한다

 

어떻게하면 프로그램에서 필요로 하는 데이터를

상단에 잘 올려보낼 것인가가 캐싱에 대한 문제이다

 

현재 프로그램이 필요로하는 data인

working set을 알아내는 것이

캐시에서 굉장히 중요한 문제이다

 

cache miss가 나는 경우는

크게 3가지로 정리된다고했다

이를 3C라고 한다

 

GEN5라고 하는 가장 최신 아키텍처의 구조이다

 

아래는 L2가 8개, L3가 1개 배치되어있다

두 구조의 전력 consumption을 한 번 확인해보라고하셨다

 

이건 우리 노트북에 흔히 들어가는

intel architecture의 단면이다

 

L1, L2, L3를 공유하는 구조를 확인해 볼 수 있다

그리고 밑에 memory controller가

DRAM으로 들어가있는 것을 확인할 수 있다

 

 

또 다른 intel 구조이다

p-core와 e-core를 함께쓰는 구조이다

 

 

저번 시간에 배웠던 set-associative cache 구조이다

 

E가 line의 수

S가 set의 개수이다

각 line은 block을 represent하고

각 block 안에 word가 들어가있다

 

set이 1개고 line을 전부 다 들어놓은게

fully-associative 구조라고했다

이는 conflict miss를 낮춰줄 수 있지만

전력 소모가 너무 크기 때문에

set을 나누는 set-associative cache 구조를 사용한다

 

intel의 구조는 1개의 set에

16개의 line이 있는 구조라고 한다

set index로 어떤 set인지 찾아들어간 뒤

line을 tag로 비교하면서 내가 찾는

데이터가 맞는지 확인하게 된다

 

 

여기서부터 이번 시간에 본격적으로 배울 내용이다

 

cache에서 데이터를 어떻게 읽는지

자세하게 알아보자

 

이전 수업에서도 자세하게 설명했듯이

CPU가 보내주는 address line에는

set index, tag, block offset이 담겨온다

 

여기서 set index로 우선 몇 번째 set에 갈지 찾고

그 다음 line을 돌면서 tag를 비교한다

만약 여기서 같은 tag가 나온다면

cache hit이 되고

해당 line의 data block에 접근해 데이터를 가져오게 된다

그런데 line의 data block에는

데이터가 여러 바이트가 있을 수 있기 때문에

address line에서 받아온 block offset으로

정확하게 몇 번째 byte를 가져올지 정하게 된다

 

 

direct mapped cache를 보자

line이 한 개의 set당 1개만 있는 구조가

(E = 1)

direct mapped cache라고 했다

여기서는 몇 번째 line인지 확인할 필요가 없으므로

그냥 바로 직진해서 앞에 있는 tag bit를 검사하면 된다

 

direct mapped cache가 어떻게 작동하는지

구체적으로 한 번 살펴보자

 

4비트짜리 address가 있고 E=1이다

set의 개수가 4개이므로

set index는 2비트로 오는 것을 확인할 수 있다

그러고 block offset은 1바이트이다

 

따라서 맨 처음에 address가 0000으로 들어온다고 가정해보자

그럼 우선 set index가 00이므로 set0을 가리킨다

그럼 이제 address line의 valid bit가 1인지 확인하고

tag bit와 set0의 tag를 비교해야한다

그런데 이게 cold miss가 났다고 해보자

그렇다면 set0의 data block에는

저 M[0-1]에 해당하는 데이터가 담기게 되는 것이다

 

그럼 그 다음 두번째를 잘 보자

address line이 0001이 들어왔다

아까와 동일하게 set index가 00이라 set0을 가리키고

tag는 0이된다

그럼 아까 전에 cache의 set0에 valid bit도 1이고

tag도 0으로 저장해주었으므로

이는 모든 정보가 일치하게 되어서

cache hit이 된다

 

그런 다음 세 번째인 0111을 확인해보자

가운데 11이 set index라

이는 가장 큰 set3을 가리킨다

그 다음에 tag가 0인데 아무 저장되어있는 데이터가 없다고하자

그럼 cold miss가 발생하게 되고

해당 자리에는 원래 원하는 데이터인 M[6-7]이 들어가게 된다

 

네 번째도 마찬가지로 cold miss가 발생하게되고

이제 마지막을 확인해보자

 

0000이 들어오게 되면

첫 번째 set0을 찾아가게 된다

그런데 첫 번째에서 이전에 원래 데이터를 밀어내버려서

내가 기존에 찾고싶었던 데이터가 없게 된다

이게 바로 miss conflict이다

그래서 이렇게 번갈아가면서 하게 되면

끊임없는 miss conflict가 발생하게 된다

 

 이렇게 Line이 2개만 되더라도 conflict miss를

많이 줄일 수 있게된다

 

cache에서 데이터를 찾아오는 로직은

앞과 동일하다

 

 

line이 2개 있는 경우이다

이렇게 다 전기를 공급해줘야해서

power가 많이 소모된다고 한다

 

 

그렇다면 앞에 예시와 다르게

set은 2개지만 line이 2개인

2-way set associative cache 경우를 살펴보자

담고있는 block data의 사이즈는 고정이다

또한 set index는 set이 2개 뿐이므로

1비트만 사용하면 된다

 

처음꺼는 0000인데 안에 저장된 데이터가 없으므로

cold miss가 발생한다

두번째는 동일하게 0번째 set인데

tag가 00인걸 찾으므로

아까 앞서 저장해줬던 데이터 line이 일차하기 때문에

cache hit이 된다

 

세 번째의 경우도 cold miss가 발생하는데

1번째 set에 01 tag로 데이터가 저장되게 된다

그런 다음 네 번째는 set0에 들어가게 되는데

tag가 01이기 때문에 일치하는게 없어서

miss가 뜨게 된다

 

마지막으로 0000이 들어오게 되면

이전 사례같은 경우는 데이터를 밀어버렸었기 때문에

conflict miss가 발생했었는데

이번에는 0번째 set에서 00인 경우가

덮어씌워지지않았기 때문에

cache hit이 발생하게 된다

 

따라서 way를 한개만 늘려도

이렇게 conflict miss 확률을 낮출 수 있게 된다

 

실제 4 way set associative cache의 로직이다

 

line이 4개이고

중간에 있는 8 비트를 set selector로 사용한다

해당 위치의 set circuit에서 tag가 들어가서

tag bit와 equality check를 수행한다

그리고 거기서 나온 결과를

valid bit와 다시 AND를 시킨다

그런 다음 그 4개를 동시에 계산한 뒤

결과를 다 모아서

멀티플렉서가 누구껄 뽑을지 뽑아서 나가게 되는데

1을 뱉어준 친구가 hit이기 때문에

그걸 가져가게 될 것이다

 

 

지금까지 본건 cache read인데

그렇다면 cache write은 어떻게 될까?

 

cache write의 경우는

내가 현재 캐시에 담고있나?

이전에 담은 적이 있나?

캐시에 담아야하나

에 따라서 정책이 달라진다고 한다

 

cpu는 write에 대해서 2가지 policy를 갖고있는데

첫 번째가 어차피 write은 메인메모리에 들어가야하므로

바로바로 쓰자는 정책이

write-through policy이고

두 번째는 일단 캐시에 buffer처럼 담아둔 다음

cache가 overflow가 나면 한 개씩 밀려나는 구조로 가자는게

write-back policy이다

현재 CPU는 write back policy를 채택하고있다고 한다

 

또한 write-miss가 날 경우

allocate를 할거냐 안할거냐에 따라

write-allocate, no-write-allocate로 나뉜다고한다

 

아무튼 write는 이러한 복잡성 때문에

비트가 늘어나게된다

cache read와 다른 비트 중에 하나가

바로 dirty bit인데

예전의 read같은 경우는 conflict miss가 발생하면

그냥 해당 위치에 overwrite을 해버렸는데

write는 데이터가 날라가면 안되기 때문에 그렇게하면 안된다

그래서 이게 read인지 write인지 확인하기 위해

dirty bit가 필요하다

그래서 cache 설계가 복잡해지게 된다

 

그렇다면 만약 다른 코어에서

해당 데이터를 원한다면 어떻게 해야할까?

왜냐하면 현대의 CPU는 cache write-back policy를

택하고 있다고 했는데

원래라면 write되는 데이터는 main memory에 써져야한다

그래서 썼다고 생각한 데이터를

다른 코어에서 다시 load해야할 일이 있을 수도 있는데

이런 경우 어떤 방식을 취하게 될까?

 

우선 다른 코어에서 어떤 데이터를 load해야하면

cache를 가장 우선적으로 확인하게 된다

그런데 L1 miss, L2 miss, L3 miss가 발생하고

main memory에서도 가져오려하지만 miss가 발생한다

왜냐?

우리는 다른 코어의 cache 안에 write-back 되어있기 때문이다

 

그래서 이런 상황을 막기 위해서

cache끼리는 서로 snooping(감시)를 한다

서로 내부적으로 신호를 tapping하고 있다가

다른 코어에서 이 주소를 가져다달라고 신호를 보내면

내 캐시에 그 주소가 있는지 계속 감시하고있다가

주소가 있으면 바로 forwarding 시켜준다

이 과정을 cache snooping protocol이라고 한다

 

이러한 snooping protocol이 필요한 이유는

근본적으로 write-through를 하지 않고

write-back을 하기 때문이다

각자 core의 cache에만 일단 write back을 하기 때문에

memory에는 최신상태의 데이터가 없을 수도 있기 때문에

코어들끼리 coherency를 하는 것이 매우 중요해진다

따라서 이걸 해결하는 방법이 cache coherency protocol이고

MOESI같은 것들이 대표적이다

 

MOESI protocol은 간단하게 설명하면

각 cache line이 modified, owned, exclusive, invalid 등

각 상태를 갖고 있어서

이건 수정된건지, 나만 알고있는건지, 무효인지 등을 체크하는 방식이다

 

여기서 몇 가지 우리가 실수할 수 있는 문제들을 설명해주셨는데

첫 번째가 invalidation 문제이다

우리가 c언어에서 코딩할 때 가끔 shared variable을 쓸 일이 있는데

shared variable을 쓰면 단점이

공유된 변수를 모든 코어가 같이 쓰면

이는 반드시 invalidate를 일으켜야한다

우리가 1 byte만을 바꿔줘도

cache는 line 단위로 변경되기 때문에

line 전체가 invalidate 되어버린다

 

또한 false sharing 문제도 발생할 수 있는데

서로 다른 변수를 쓰고 있는데

변수가 같은 cache line에 들어가게 되어서

read-only 변수같은 경우는 바꿀 일이 없음에도

write variable 때문에 invalidate가 될 수가 있다

그래서 개발자 입장에서는

나는 변수를 바꾼 적이 없는데 왜 자꾸

cache miss 되는지 답답할 수가 있다

 

그래서 보통 변경이 일어나는 변수 뒤에다가

read-only 변수를 선언하면

cache가 왕창왕창 miss된다고 한다

이게 cache miss 좀 되면 어때서라고 생각하지만

cache hit되면 5 cycle이면 끝나는걸

cache miss가 되면 한 개당 100 cycle이상이 날라간다고한다

이게 쌓이다보면 성능이 압도적으로 차이가 나게 되는 것이다

 

따라서 프로그래밍을 할 때 write variable이 있으면

write variable 뒤에 곧바로 read-only를 선언하지말고

c언어 같은 경우는 aligned 64를 선언한다음

variable 뒤에다 padding을 붙여서 간격을 두라고 한다

그럼 적어도 read variable과 1 cache line정도는 차이가 나게 된다고한다..

 

아무튼 여기서의 결론은

cache write는 이렇게 굉장히 복잡하고 섬세하게 설계가 되어있다

하지만 우리가 배우는건 정말 수박 겉핥기 수준이라고한다

 

 

아까 말했던 false sharing에 관한 내용이다

write variable을 shared variable로 쓰는 경우

모든 cache line이 invalidate가 되어버려서

성능이 굉장히 저하된다

 

 

그렇다면 아까 address에서

set index는 늘 가운데에 있던데

혹시 이렇게 하는 이유가 있을까?

 

결과적으로는 달라지는게 없지만

behavior가 달라진다고 한다

 

 

뭐가 어떻게 달라지는지

구체적으로 그림으로 표현한 부분이다

cache가 총 16byte인데

block size는 4라서 set도 4개가 된다

 

set이 4개니까 set index bit는 2개가 되고

64 byte 메모리 구조에서 주소가 6 bit이므로

tag는 2비트, offset도 2비트가 된다

 

결론적으로 set selector가 가운데에 와야하는 이유는

메모리 주소 순서와 cache set 순서가

순서대로 골고루 가게 해서 cache miss를 줄일 수 있기 때문이다

 

아래에서 그림으로 더 자세하게 살펴보자

 

 

이게 현재 우리가 쓰고있는

가운데 2bit set selector 구조이다

 

set selector가 가운데에 가게되면 차례대로

00, 01, 10, 11의 순서로 반복되게 되는데

stride가 set의 개수인 4만큼 돌면서

위의 색과 같이 분산된다

따라서 쟤네가 각 set에 들어가기 위한

기회가 분산되는 것이다

 

 

하지만 set selector가 가장 앞에 나오게되면

이렇게 된다

가운데가 tag bits고 가장 앞 2개가 set selector인데

00의 경우가 set의 개수만큼 쫘악 깔리고

그다음 01의 경우 쫘악

그다음 10의 경우 .. 이렇게 나열되게 된다

 

이렇게 sequencial하게 나열되는데

이렇게 되면 계속해서 conflict가 발생하게 된다

 

교수님의 연구실에서 지금 이 문제와 관련된 연구를

진행하고 계신다고 한다..

 

 

intel의 core i7 cache hierarchy를 살펴보자

i cache가 가장 빠르고

8 way가 있다

 

L2는 8 way가 있는 것을 확인할 수 있다

 

 

cache performance를 측정하는 metrics다

 

miss ratio는 1에서 hit를 뺀 것이다

miss penalty는 cache miss가 났을 때

데이터를 다시 찾아올때까지 걸리는 시간인데

보통 50에서 200사이클까지 걸린다고 한다

 

cache의 성능을 측정하는 부분에선

1% 차이가 굉장히 크다고 한다

 

99% hit된 것과 97% hit된 것의

cycle 차이를 보면 2배 가까이 된다고 한다

 

cache miss가 한 번 발생하게되면

우리가 지불해야하는 cycle이 대략 100개정도 가까이 되기 때문이다

 

 

아무튼 그래서 cache 성능을 끌어올리는 것은

굉장히 굉장히 중요하다

 

locality를 잘 살리는 프로그래밍을 하도록하자

 

아키텍처 분야에서는 4%, 5%라는 성능 향상이

아주 큰 성취라고 한다

 

지금까지 cache opration에 대해서 알아봤으므로

이제 구체적으로 memory access 법에 대해 알아보자

 

여기서 memory mountain이라는 개념이 나오는데

memory access를 어떻게 하냐에 따라

퍼포먼스가 어느정도로 바뀌는지 측정하는 것이다

 

 

첫 번째 예시를 한 번 살펴보자

위 코드 같은 경우는 stride를 각각 1, 2, 3, 4씩 줬을 때의

cache behavior를 측정한 것이다

 

stride를 늘릴 수록 당연히 cache behavior가 안좋아진다

당연히 spatial locality가 사라지기 때문이다

그리고 이 stride 크기가

cache block size를 넘는 순간

성능이 완전히 차이가 나게 된다

 

 

위의 코드로 spatial locality를 기준으로

측정을 했을 때 그래프가 위와 같이 그려진다고 한다

 

위에서 주목해야할건

stride를 늘릴수록 성능도 떨어지지만

데이터 사이즈를 늘리기 시작하면 성능이 계단식으로 떨어진다

이게 L1의 capacity를 넘어갈 때 뚝 떨어지고

L2 capacity를 넘어갈 때 뚝 떨어지듯이

각 cache memory capacity를 넘을 때마다

계단식으로 떨어지게된다

따라서 이걸 memory mountain이라고 부른다

 

또한 위 그래프를 보면서

아 각 L1, L2, L3의 사이즈가 저만큼이구나도

측정할 수 있게 된다

 

아무튼 캐시를 잘 활용하는 것은 매우매우 중요한 일이라고한다

 

 

아까 말했듯이 stride가 올라갈수록

성능이 또 쭈욱 떨어지는 것을 볼 수 있다

 

stride가 8을 넘으면 계속 일정한 성능을 보이는 것을 볼 수있는데

이는 miss ratio가 1.0

즉, 모든 데이터가 다 cache miss가 나서

그냥 동일한 성능을 보이게 되는 것이다

cache에서 더이상 가져올 데이터가 없고

모든 데이터를 main memory로 access해서 가져오기 때문에

동일한 성능이 측정된다

 

 

우리가 머신러닝 딥러닝에서 많이하게되는

matmul인 행렬곱을 할 때

이 input 순서를 어떻게 하냐에 따라서

성능이 굉장히 달라지게 된다

 

위 코드가 우리가 보통 흔히 생각하는

matrix multiplication을 해주는 코드이다

 

 

이런 행렬곱 코드에서

miss rate를 계산해보자

 

matrix multiply는 위와 같이 구성이 된다

 

우리가 앞에서 봤던 ijk 순서로 행렬곱을 수행해보자

위 경우는 row-wise의 경우인데

보통 row-wise로 할 경우는 cache miss가 상대적으로 작다

 

하지만 column-wise의 경우

보통 최악의 성능을 보이며

cache miss가 거의 100%정도 발생한다..

 

 

double이 4개라 block size가 32b라 했을 때

B는 100% cache miss가 발생한다

위를 보면 row-wise의 경우 cache miss가 25%

B의 경우 100% 발생하는 것을 확인할 수 있다

 

 

그럼 이제 순서를 바꿔서

kij로 계산하는 경우를 살펴보자

 

우선 가장 먼저 i,k로 point를 고정하고

그다음 row로 먼저 곱한 다음

그게 i번째에 나열된 다음

곱해준 것을 c에다가 하나씩 더해준다

 

이럴 경우 B가 25% miss

C도 25% miss이고

A는 0% miss가 발생해서

위 경우보다 성능이 더 좋아지게 된다

 

 

그 다음 세 번째 방법이다

 

B를 고정하고 계산을 하는 것인데

A와 C도 column-wise로

엄청나게 miss가 발생한다

 

앞에서 봤던 각각의 miss rate를 정리한 것이다

 

 

위 3가지 경우들을 그래프로 표현한 것이다

여기서 y축은 linear한 값이 아니다

한 마디로 엄청나게 차이가 크게 난다는 뜻이다

 

따라서 앞으로 코딩을 할 때 이런식으로

반드시 cache behavior와 memory access를

이해하는 방식으로 코딩을 하라고 하셨다

 

 

위처럼 matrix multiplication은

위처럼 3가지 경우로 나뉠 수 있는데

과연 이렇게 하는게 최선일까?

 

 

위처럼 계산하는 경우도 한 번 살펴보자

 

a는 access 할 때 stride로 수행하고

b는 모두 cache miss가 발생한다

 

 

이걸 계산을 한 번 해보자

통상적으로 쓰는 64바이트 캐시를 기준으로 한다면

8바이트씩 access 할 때 8분의 1의 stride를 갖게 된다

 

처음에는 8의 n이 나고

그 뒤에건 전부다 cache miss가 나게 된다

 

 

따라서 위 방식은 별로 좋은 방식이 아니다

그래서 다른 새로운 방식을 시도해보자

block 단위로 matrix multiplication을 실행해보는 것이다

 

행렬곱 연산은 block 단위로 쪼개서 수행할 수 있다

c에서의 한 point를 얻기 위해서는

저 sizes의 row와 column을 곱하면 된다

그럼 그걸 위해서 어떻게 자르냐?

B제곱이라고 하는 block이 cache에 fit할 수 있게 자른다

 

이런식으로 하면 cache miss가 줄어서

성능이 확연히 좋아진다고 한다

 

 

각 block은 8분의 b 제곱만큼 miss가 난다

그럼 each block에 대해서 그 개수가

n분의 B짜리 2개와

그게 한 block 당 b제곱 * 8개만큼 있기 때문에

위 ppt slide처럼 곱해준다

그럼 결과가 nB/4가 나오게 된다

 

 

아무튼 이런 방식으로 계산하게 돼서

total miss가 위와 같이 나오게 된다

 

우리가 가장 처음 해줬던 non-blocking 방식과

방금봤던 blocking 방식의 cache miss를 비교했을 때

큰 차이가 나게 된다

 

그래서 matmul software에서는

block multiplication하는 방식을 채택하여 사용하고있다