기말 대비용 정리 노트 (Lecture 3)

이번 강의 내용은 cache 관련이다. Cache를 공부하는 것은 cache data를 읽고 쓰는 것은 load/store 명령에 의한 것이며, load/store를 하는 동안 특정 명령에 문제가 생겼다면 CPU와 reordering buffer 상에서는 지워지더라도 cache를 사용한 흔적이 남기 때문에 이것을 security hole로서 활용할 수 있다. 후에 Out of Order Core Execution을 통해 invalid한 동작을 수반한 공격을 진행했을 때, core에서는 그 흔적이 깔끔하게 삭제되나, cache에는 공격의 흔적이 남는 것을 볼 것이다. 이제 cache 관련 내용을 살펴보자. 중요한 것은 는 것이다. 

 

2010년까지 CPU의 연산 능력은 꾸준히 증가하였지만, 메모링의 성능은 그에 비례해서 증가하지 않았다. 이에 따라 CPU의 연산 속도와 메모리에서 데이터를 공급하는 속도 사이의 간극이 점점 벌어지게 되었다. 메인 메모리인 DRAM은 용량이 크고 저렴하지만, 속도가 느린 단점이 있고, 레지스터는 빠르지만 용량이 작고, 비싸다는 단점이 있다. 우리가 원하는 것은 메모리와 레지스터의 장점을 모두 취하면서 중간의 간극을 줄이기 위한 중간 장치이며, 이것이 cache이다. 해당 간극의 폭이 넓어 cache도 계층화를 시켜 주로 L1, L2, L3로 나누어 운영한다.

 

multi-level cache를 운영하는 또다른 이유는 프로그램의 전형적인 패턴에 있다. 프로그램의 working set을 보면 시간 구간의 길이별로 어느 정도의 메모리를 활용하는지가 차이가 있다. L1 cache의 크기는 짧은 시간 구간 동안 프로그램의 working set의 크기를 기준으로 정해지며, L2 cache는 그보다 긴 구간 동안 프로그램의 working set을 기준으로 결정된다. 즉, working set의 레벨이 시간별로 차별화되는 프로그램의 특성에 의해 multi level cache로 운영하는 것이 합리적이기 때문에 cache도 계층화를 해놓은 것이다.

 

Cache의 핵심적인 아이디어는 locality에 의거하여 빈번하게 쓰이는 데이터를 프로세서 근처에 위치한 영역에 두어 빨리 접근이 가능하도록 하는 것이다. Temporal Locality는 한 번 쓰인 데이터가 다시 쓰이는 경향, Spatial Locality는 쓴 데이터의 옆 데이터를 사용하게 되는 경향이다. 드물게 스트리밍 같이 locality가 적은 데이터가 존재하기도 하지만, 주로 locality가 다 있기 때문에 cache로 연산상의 이득을 볼 수 있는 것이다.

 

Memory hierarchy 별로 접근할 수 있는 속도를 살펴보면 아래와 같다.

 

	Access Time	Capacity	Managed by
Registers	1 cycle	~500B	SW/compiler
L1 Cache	1 ~ 3 cycles	~64KB	HW
L2 Cache	5 ~ 10 cycles	1~10MB	HW
DRAM	~ 100 cycles	~10GB	SW/OS
Disk / Flash	10^4 ~ 10^7 cycles	~1TB	SW/OS

DRAM과 레지스터 사이의 간극은 cache로 극복한다고 하면, 디스크와 DRAM 사이의 간극은 옵테인이라는 DRAM보다는 느리지만 디스크보다는 빠른 persistent 메모리를 두어 cache와 마찬가지로 중간 장치를 두는 방식으로 극복한다. 또한 디스크 자체에서도 작은 DRAM 버퍼를 가지고 있어 디스크의 속도를 끌어올린다.

 

칩 자체를 살펴보면 큰 부분을 L3 cache가 차지하고 있는 것을 볼 수 있으며, 코어 내부를 봐도 L1과 L2 cache와 관련된 부분이 적지 않은 비중을 차지하고 있다. 실제 execution과 연산에 집중하는 영역은 전체 CPU에서 50% 미만이다.  

 

---

 

제일 간단하고 근본적인 cache의 구조로는 direct mapped cache를 들 수 있다. 해당 구조는 시험에 출제될 예정이라고 하니 잘 숙지하길 바란다. 

주소에서 상위 비트는 태그로, 중간 비트는 인덱스로, 하위 비트는 바이트 오프셋으로 쓰는 것을 확인할 수 있다. cache 내에 저장된 데이터가 32bit = 4Byte이니 바이트 오프셋으로 2비트가 요구된다. 위의 그림에 묘사된 cache는 1024개의 엔트리에 각 4B 데이터를 저장할 수 있으므로 4KB의 용량을 가지는 cache이다. 요즘 L1 cache는 커봐야 32~64KB의 용량을 가진다.

 

데이터를 찾을 주소가 주어지면, 요구하는 주소에 대해서 cache내에 해당하는 인덱스로 찾아간 뒤에 valid bit와 tag가 일치하는지를 확인한다. tag를 확인하는 것은 중간 비트가 동일하다면 동일한 인덱스의 엔트리로 연결되기 때문에 aliasing 문제를 방지하기 위해서이다. 만약 둘 다 valid하다면 hit이고, 해당 엔트리의 데이터를 가져올 수 있다. Direct mapped cache는 주소가 주어지면 지정된 위치에 데이터가 있거나, 아니면 cache에 아예 없거나 둘 중 하나이다. 

 

이제 Cache에 대한 몇 가지 질문들과 그에 대한 답을 살펴보자.

Cache Miss가 나면 머신의 동작은? (+ Multi-level inclusion)

L1 cache에서 찾는 것을 실패하면 L2 cache에서, L2에서도 실패하면 L3, L3에서도 실패하면 메모리에서 데이터를 찾는다. 데이터를 메모리에서 찾은 다음에는 찾은 데이터를 cache에 적재하도록 한다. 적재를 할 때도 가장 상위 cache에만 적재할지, 모든 cache에 적재할지는 cache의 종류, Inclusive cache와 Exclusive cache에 따라 나뉜다.

 

Inclusive cache는 상위 cache에 있는 데이터는 더 낮은 단계의 하위 cache에도 존재하는 cache이다. 때문에 메모리에서 가져온 데이터를 모든 단계의 cache에 수록하며, 상위 단계에서 evict가 된 데이터는 하위 단계에서는 evict되지 않고 남지만, 하위 단계에서 evict가 되면 상위 단계로 back invalidation을 보내 inclusion을 유지한다. 따라서 이 경우, 모든 cache에 메모리에서 가져온 데이터가 적재된다. Exclusive cache는 상위 cache와 하위 cache 사이에 겹치는 블럭이 존재하지 않도록 관리하며, 상위 cache에서 데이터가  evict되면 하위 cache로 밀려나도록 만든다. 따라서 이 경우에는 가장 상위 cache에만 데이터가 적재된다. 해당 분류는 HW를 만드는 곳에서 결정하며, OS가 임의로 변경하지 못한다. 주로 Intel은 Inclusive 방식으로 cache를 만들며, AMD는 Exclusive 방식으로 만든다. 지금은 두 방식이 혼재된 방식으로 만들어진다고 한다.

 

처음에는 cache의 용량을 보다 잘 활용할 수 있는 exclusive 방식이 자연스러웠을 것이다. inclusive 방식이 유용한 이유는 cache coherence 때문이다. 코어 간에 공유된 데이터에 대해 한 코어(A)에서 그 값을 변경하고, 다른 코어(B)에서 그 값을 읽으려고 할 때, inclusive 방식이라면 그 값이 다른 코어에서 변경되어 write back으로 hold 되어 있는지의 여부를 판단하기 위해 다른 코어의 L2 cache에 그 값이 있는지 여부만 판단하면 된다. 만약 L2에 있다면 L1에도 당연히 있을 것이며, L2에 없다면 L1에도 없을 것이기 때문이다. 만약 이것이 exclusive 방식이었다면 L2에 없더라도 L1까지 확인해야 되기 때문에 이러한 확인 작업이 많아질수록 코어에 가해지는 부담이 증가할 것이다.

Write 시도에 Cache Hit이 되면 해당 write는 어디까지 반영되어야 하는가?

우선 이에 대해 답을 하기 위해서는 write policy의 종류에 대해 알아야한다. 

 

• Write-back policy : cache의 데이터만 write하고 해당 데이터가 cache에서 evict될 때 메모리로 내용을 반영한다.
• Write-through policy : 데이터 변화가 cache와 메모리 모두에 일괄적으로 반영된다.

따라서 policy 별로 다르다고 할 수 있다. inclusive/exclusive cache 분류에 따르면, exclusive에서는 값이 한 곳에서만 유지되기 때문에 문제가 없으나, inclusive에서 특정 값만 바뀌는 것은 문제로 보일 수 있다. 그러나 정의에 따르면 값이 동일하게 유지되는 것은 inclusion의 필수 요건이 아니며, 값이 유지될 경우를 value inclusion이 유지된다고 하여 따로 분류한다. write through일 경우에는 애초에 데이터가 cache와 메모리 모두에 일괄적으로 write되기 때문에 일반적인 inclusive cache도 값이 같게 유지된다. 우리가 사용하는 cache는 주로 write-back policy를 채택한다.

Write 시도에 Cache Miss가 되면 머신의 동작은?

정확히는 write hit이 나던, miss가 나던 write의 대상이 되는 값은 store buffer라는 곳에 들어간다. write operation이 retire 되었다는 판단은 store buffer에 들어갔는지 여부로 판별하게 된다. 이후 store buffer에서 값을 내려보내는 것이기 때문에 만약 cache에 해당 값을 넣을 위치가 없다면 (miss) OS가 정한 아래의 정책에 따라 동작이 결정된다.

 

• Write allocate (aka fetch on write) : 우선 수정이 필요한 원본 데이터를 cache로 올린 뒤, 해당 데이터를 cache에서 수정하는 방식으로 한다. 해당 방식에서는 read miss와 유사한 동작이 수반된다.
• No-write allocate (aka write-no-allocate or write around): cache에 데이터가 없다고 하면, 메모리에 직접 값을 write하고 cache로는 적재하지 않는다. 해당 방식으로는 read miss일 경우에만 데이터가 cache로 올라간다.

이는 데이터의 이용 방식에 따라 다르게 설정할 수 있도록 만든 것으로, 옛날 데이터가 필요하지 않는 스트리밍, buffer 계열에서는 굳이 데이터를 cache로 올릴 필요가 없기 때문에 바로 목표 지점에 쓰는 것이 효율적이다.

 

Write allocate를 한 번 더 나눌 수 있는데 Cache block이 요구하는 데이터의 양보다 큰 경우 나머지 데이터를 채워넣는 방법에 관한 것이다. 이를 해결하는 법으로는 하위 cache로 내려가 block의 나머지를 채울 데이터를 찾거나, 그냥 비워두는 법이 있다. 전자를 fetch on miss, 후자를 no fetch on miss라고 하며, 전자는 당장의 overhead가 생기나 cache 상 추가적인 요구사항은 없고, 후자는 cache 엔트리 상 실제로 어디까지 valid한지를 표기하는 bit가 요구된다.

 

여기까지 Write Miss가 났을 때 cache의 대응별로 cache를 분류한 것을 정리하면 아래와 같은데,

분류가 복잡하지만 우리가 주로 접하는 cache는 write-back, write allocate, fetch on miss 조합이라고 생각하면 된다. 

 

---

 

이제 본격적으로 cache의 performance를 설명하기 위해 CPU와 마찬가지로 정량화를 해보자. 데이터가 cache에 있으면 hit time만 고려하면 되지만, 실제로는 일정 비율만큼 miss가 나기 때문에 그 비율과 miss가 될 경우 추가로 데이터를 가져오기 위한 비용인 miss penalty를 곱해서 더해주게 된다. miss penalty는 하위 cache에 해당 데이터가 있을 경우 이를 hit하는 시간 또는 해당 데이터가 없다는 것을 확인하는데 걸리는 시간이 된다.

 

AWAT (average memory access time) = hit time + miss rate * miss penalty

 

Cache Miss에는 3가지 종류(3C)가 있다.

 

• Cold miss : 한 번도 해당 데이터를 건들인적이 없어 데이터를 cache로 올려야 하는 경우
• Capacity miss : cache의 크기가 working set보다 작아 eviction된 데이터에 접근하는 경우, cache의 크기가 컸으면 발생하지 않았을 수 있다.
• Conflict miss : ​cache에서 ​동일한 엔트리를 서로 다른 두 주소가 번갈아 가면서 사용하게 되서 발생하는 miss

이 중 아키텍처는 cold와 capacity miss에 주로 집중하면 된다. 

 

파워 파트는 CPU와 마찬가지로 생략하지만 cache가 상강히 많은 파워를 잡아먹는다는 것은 알아두도록 하자. 이는 CPU에서 반 이상을 cache가 차지하고 있으며, 전기가 지속적으로 흘러야 값이 유지가 되는 구조를 가지고 있기 때문이다.

 

퍼포먼스 상으로 cache의 성능을 증가시킬 아래와 같은 아이디어를 생각해볼 수 있다.

 

• 각 엔트리의 용량을 늘린다 (large block size)
• 엔트리 수를 늘린다. (larger cache)
• read를 write보다 우선시한다.
• associative caches

다만 block size는 꾸준히 64B로 유지가 되고 있으며, cache 용량은 32KB(L3), 1M(L2)에서 많이 늘지 않고 있다. 또한 엔트리의 수를 증가하면 hit time이 늘어날 수는 있기 때문에 무작정 늘리는 것만이 능사가 아니다. 또한 set-associative cache도 요즘 cache에는 기본적인 메타로서 적용되고 있다.

위의 그림은 4-way set-associative cache로서, set-associative cache는 direct mapped cache와 유사하지만 데이터가 존재할 수 있는 위치가 set으로 존재하여 원하는 데이터가 set의 어디에든 위치할 수 있다는 특징이 있다. 이는 프로그램에서 stride 패턴으로 메모리에 접근할 경우 특정 인덱스에 집중되어 conflict miss가 발생할 여지를 줄여준다. 단점은 파워와 latency 측면 모두에서 hit time이 증가한다는 것이다.

 

---

 

다양한 cache의 형태를 살펴보자.

Victim Cache

victim cache는 주 cache 옆에 위치하는 작은 fully-associative cache(전체 엔트리 중 어디에도 들어갈 수 있다)로서 엔트리가 완전히 evict되기 전에 잠시 보관하는 역할을 한다. set-associative cache가 감당할 수 없는 정도의 중복 엔트리 접근 패턴에 대해서도 victim cache에서 임시 보관을 해주기 때문에 보완이 되며, L2보다 빠르게 값을 복원할 수 있다 (3 cycle 이내). 이런 식으로 퍼포먼스에 중대한 역할을 하여 튜링상도 수상했다고 한다.

Pseudo-Associative Cache

set-associative cache와 direct mapped cache의 중간 위치에 해당하는 cache로 set-associative cache에서는 한 set에 해당하는 모든 엔트리를 parallel하게 접근해서 확인하여 접근하는 것과 달리 각 way를 순차적으로 탐색한다. 1번 way에서 우선 탐색하고 원하는 엔트리가 없다면, 2번 way로 넘어가 다시 탐색하는 것이다. 어느 way에 위치해서 탐색 시간이 일관적이었던 set-associative cache와 달리 앞 way에 위치하는 빈도가 높다면 hit 타임을 더 빠르게 하여 더 빨리 데이터를 찾을 수 있다. 일반적으로는 순차 way 탐색으로 인한 시간이 더 늘어나서 잘 사용되지 않는다.

Skew-Associative Cache

일반적으로 cache는 주소를 3분할하여 중간 비트를 인덱스로 하여 각 way에 위치한 엔트리를 찾았다. skew-associative cache에서는 각 way별로 인덱스의 hashing을 다르게 하여 엔트리가 각 way마다 다른 인덱스에 위치할 수 있도록 한다. 이러면 conflict miss를 줄일 수 있는 여지가 있다.

 

---

 

마지막으로 cache optimization 기법들을 몇 가지 알아보자.

Critical Word First

Cache 엔트리에서 cache block은 데이터가 존재하거나 존재하지 않을 최소 단위이다. 예를 들어 cache block의 크기가 64 Byte라고 두고, word 사이즈는 32 bit이라 두자. 한 cache block 내에는 총 64 * 8 / 32 = 16개의 word가 들어있는 것이다. 프로세서는 이러한 word 중 필요한 word를 critical word로 지정할 수 있다. 그러면 해당 critical word를 우선적으로 cache로 읽어 프로세서로 전달한다. critical word의 값을 받아 프로세서는 계속 일할 수 있고 나머지 값들도 순서대로 cache block내로 fetch된다. 이것이 critical word first이다.

 

이러한 과정이 필요한 이유는 성능을 증대시킬 수 있기 때문이다. 첫 번째 word를 fetch하는데는 8 cycle, 나머지 후속 word를 fetch하는데는 2 cycle이 든다고 하자. CWF가 적용되면 프로세서는 8 cycle 후에 작업으로 복귀할 수 있고, 전체 cache block은 38 cycle 뒤에 교체된다. 만약 CWF가 적용되지 않은 상태라면 프로세서는 최악의 경우 전체 cache block이 교체되는 38 cycle 뒤에 작업을 재시작하게 될 수 있다. 주로 block의 크기가 크고 bandwidth가 낮을때 유용하다.

Non-blocking Cache

Non-blocking cache의 주요 아이디어는 cache miss가 나서 데이터를 읽어오는 도중에 CPU를 stall시키지 말고, 다른 cache access를 허용함으로서 CPU가 멈추는 시간을 최소화하여 cache bandwidth를 증가시키는 것이다. 이를 위해 만들어진 아키텍처가 MSHR (Miss Status Handling Register)이며, miss가 발생하면 왜 발생했는지, 어디서 발생했는지를 기억하는 레지스터이다. Miss가 나면 miss가 난 block address, block offset, 데이터를 기억해둔다. 요청된 cache block이 후에 준비가 되면 레지스터에 기록된 offset에 따라 요청한 값을 반환한다.