08. Cache Optimizations (Advanced Computer Architectures, SNU CSE)

서울대학교 컴퓨터공학부 유승주 교수님의 "고급 컴퓨터 구조" 강의를 필기한 내용입니다.

• 목차

Cache Size vs Associativity §

• 보통 memory size 가 커지면 물리적인 거리가 멀어져 access time 이 늘어나고,
• Cache 의 set associativity 에 따라서도 복잡도가 늘어나 access time 이 늘어난다.
• 그래서 위 그래프를 보면 hit 일때의 access time 을 보여주는 것인데, cache size 가 커질수록 access time 이 늘어나는 경향성을 보이고, 같은 cache size 일 때는 assiciativity 가 늘어남에 따라서도 access time 이 늘어나는 경향성을 볼 수 있다.
• 하지만 cache size 가 작아지는 것은 cache miss rate 을 늘리기에, $AvgLatency=HitTime+MissRate\times MissTime$ 을 고려하여 적당한 수준의 cache size 와 associativity 를 결정해야 한다.

Way Prediction §

• 위의 그래프를 보면 direct mapped cache (1-way) 의 경우에 latency 가 아주 짧은 것을 알 수 있다.
• 그래서 만약에 set-associative cache 에서 어떤 way 에 접근해야 할 지를 예측할 수 있다면, 모든 way 에 접근하지 않고 해당 way 에만 접근하면 되니까 direct mapped cache 의 latency 를 가져올 수 있다.
• 이때의 아이디어는 PC 이다: instruction 의 경우에는 jump 만 없으면 무조건 sequential 하게 접근하고, 하나의 cacheline 에는 여러개의 데이터 (통상의 64byte cacheline 이면 8개의 64bit instruction 이 담겨있으므로) 가 있으므로 한번 instruction 을 가져온 뒤에는 그 다음부터는 여러번에 걸쳐 해당 way 에 접근하게 된다.

• 따라서 위와 같은 전략을 취할 수 있다:
  • 모든 way 에 대한 read 와 이전에 접근한 데이터의 way 에 대한 read 를 모두 보내, 이전에 접근한 데이터의 way 에 대해서는 multiplexor 를 거치지 않게 하고 모든 way 에 대해서는 multiplexor 를 거치게 한다.
  • 만약 동일한 way 에 대해 hit 이면 훨씬 빠르게 종료되고 이것이 hit 이 아닐지라도 일반적인 N-way 에 대한 access time 이 그대로 적용되므로 손해볼 게 없는 셈.

• 그래서 이 때에는 hit 에도 fast hit 과 slow hit 두가지가 존재하게 된다.
• 정확도가 꽤나 높다고 한다: 위에서도 말한것 처럼 instruction fetch 의 경우에 jump 만 없다면 sequential access 를 하기 때문에 85% 정도의 accuracy 를 가진다고 한다.

Lowering Cache Power Consumption §

• 동일한 원리를 이용해 cache 의 power consumption 을 낮출 수도 있다.
• CPU 는 이미 instruction decode 를 하기 때문에, 다음에 실행할 instruction 이 jump 인지 아닌지 (즉, sequential 인지 아닌지) 를 알고 있고, 따라서 cache 에 SEQ signal 을 같이 보내면 cache 는 해당 way 에서만 찾으면 된다.
• 이렇게 하면 이전에 봤던 way 에서만 lookup 하면 되기 때문에 해당 way 의 memory 에만 접근하면 되고, 따라서 tag 에도 접근할 필요가 없어 power consumption 이 많이 줄어든다.
• 이 방법은 현재에도 ARM 기반 모바일 아키텍쳐에서 사용된다고 한다.

Way Guard §

• Way Guard 는 간단히 말하면 way prediction 을 할 때, Bloom filter 를 사용해서 lookup 할 way 를 걸러내자는 아이디어이다.
• 일단 Many-way architecture 부터 살펴보자.

Serial Tag-Data Access §

• 지금까지는 아래 그림처럼 Tag-Data 를 parallel 하게 접근하는 방식을 배워왔다.

• 근데 이것은 L1 Cache 에서만 쓰인다. L1 cache 에서는 latency 를 위해 이 방식을 취하지만 L2 이상부터는 cache size 가 크기 때문에 way 개수를 늘리기 위해 이런식으로 Tag-Data 를 serial 하게 접근하는 방식을 취한다.

• 즉, 우선 tag 를 parallel 하게 접근해서 어떤 way 인지 확정하고, 그 다음에 해당 way 에 대한 data 에 접근하는 것.
• L2 이상부터는 16, 32 way 등 way 의 개수가 아주 많기 때문에 power consumption 을 줄이기 위해 다소 latency 는 높더라도 위와 같은 방식을 사용한다.
• 하지만 이렇게 하더라도 power consumption 은 다소 높을 수 있다. 왜냐면 tag 는 결국에는 모두 접근해야 하기 때문.

• 위 그림을 보면 tag 가 하나에 4byte 에 불과하긴 하지만 16-way 이기 때문에 tag 에 접근하는 데에만 64byte 를 읽어야 한다.
• 이것을 어떻게 하면 더 줄일수 있을까? 가 way guard 의 시발점이다.

Counting Bloom Filter §

• 우선 Counting Bloom Filter 라는 것은 그냥 Bloom Filter 인데 access count 까지 하는 것이다.

• 그래서 위와 같이 Bloom filter entry 가 두개 있는 경우에 0x100 와 0x300 이 접근했을때의 counter 값은 2 가 되고, 뒤이어 0x200 가 접근하면 counter 값이 0 이기 때문에 0x200 는 한번도 접근한 적이 없구나 (즉, miss 이구나) 를 알 수 있게 되는 것이다.
• 즉, 이 상황은 true negative 인 것.

• 반대로 conflict 에 의해 false positive 도 발생한다. 이때는 통상의 bloom filter 에서처럼 hit 인지 아닌지 직접 확인해줘야 하는 것.
• 참고로 이러한 bloom filter 를 Non-membership Function 이라고 한다. 즉, 포함되어 있다 (membership) 는 정보는 확실하게 알 수 없지만, 포함되어 있지 않다 (non-membership) 는 정보는 확실하게 알 수 있게 해주는 함수인 것.

Way Guard Mechanism §

• 그래서 이 Counting Bloom Filter 를 각 way 마다 배치해서 확실하게 miss 인 way 에 대해서 filtering 하는 위와 같은 구조를 Way Guard 라고 한다.
  • 위 그림에서는 4-way 가 예시로 그려져 있고, 위쪽에 4개의 way guard 가 있는 것을 확인할 수 있을 것이다.
• 이때 저 counter 에 대한 wraparound 및 cache evict 시에 어떻게 작동할지는 아주 복잡한 engineering 이 필요하다.
  • 왜냐면 wraparound 가 되지 않으면 다시 0 이 되기 때문에 miss 라고 잘못 판단하거나
  • Evict 시에는 저 counter 값을 내려주거나 해야 되기 때문
  • Naive 하게는 warparound 를 할 때 해당 counter 에 해당하는 cacheline 을 전부 flush 해버리고 0 이되게 할 수도 있다 (당연히 성능은 구리다).
  • 구체적인 것은 궁금하면 직접 찾아보자.

Pipelining §

• 이거는 별 내용은 없다. 그냥 위에서 말한 L2 이상의 cache 에서 Tag-Data serial access 를 할 때,

• 위 그림처럼 Tag 와 Data access 를 pipeline 으로 하여 latency 를 줄이고자 하는 것이다.
  • 위 그림에서 구체적인 것은 강의에서 다루지 않았기 때문에 넘어가자.

Non-Blocking Cache §

• Non-Blocking Cache 혹은 Lockup-free Cache 는 말 그대로 miss 시에 service 가 중단되지 (blocking) 않는 cache 를 말한다.

• 즉, miss 가 발생했을 때 다른 hit 은 여전히 빠르게 처리되고 (hit under miss)
• Miss 가 발생했을 때 다른 miss 가 나도 이놈이 parallel 하게 처리되어 (miss under multiple misses) 전체적인 miss penalty 가 작아진다.

Miss State Holding Register (MSHR) §

출처: Kroft, 1981

• 이런 Non-blocking cache 를 구현하는 방법중 하나가 Miss State Holding Register (MSHR) 이다.
• 위 그림에서 가운데 보면 Miss Info Holding Register 가 있는데, 이놈이 동일한 역할을 한다.
• 이놈이 하는 것은 어떤 miss 가 처리되고 있는지 추적하여 위에서 말한 Non-blocking service 를 제공해주거나,
• 만약에 address 는 다르지만 해당 address 에 대한 cacheline 이 이미 miss 로 처리되고 있다면 동일한 request 가 lower memory 로 날라가지 않게 해준다.

Multi-Banked Cache §

• 위 그림에서 보이는 것처럼 L2 cache 의 경우에 여러개의 bank (즉, memory) 로 구성하기도 한다.
• 그리고 각 bank 는 서로 다른 address space 를 담당하게 된다.
  • 즉, address 의 일부 bit 를 사용하는 hashtable 인 셈이다.
• 이렇게 하면 여러 L2 cache request 가 parallel 하게 처리될 수 있게 된다.

Avoiding Bank Conflict §

• 하지만 저 bank 들 각각이 서로 다른 address space 를 담당하고 있기 때문에 운이 없으면 하나의 bank 에 request 가 몰리게 되는 상황이 발생할 수 있댜.
  • 이때를 Bank Conflict 라고 한다.

• 이것을 해결하는 방법은 강의에서는 다루지 않고, 그냥 padding 을 활용하는 방법만을 소개한다.
  • 위 그림에서처럼 array size 가 재수없게 bank conflict 를 유발하는 경우, padding 을 넣어 (즉, array size 를 살짝 더 키워) 모든 request 가 bank 에 고르게 분배되게 하여 bank conflict 를 피하는 방법이다.

Line Fill Buffer §

• Latency hiding 을 적용하면 이렇게도 할 수 있다.

• Cache miss 가 나면 해당 cacheline 을 갖고와야 할 텐데, 지금 당장 CPU 가 원하는 address 의 데이터를 먼저 갖고와 Line Fill Buffer 에 넣어 CPU 가 가져가게 한다.
  • 이렇게 “CPU 가 지금 당장 필요로 하는 데이터” 를 Critical Word 라고 하고,
  • 이러한 데이터를 먼저 갖고오는 것을 Critical Word First 라고 한다.
  • 위 그림에서는 오른쪽에 파란색 화살표가 가리키는 데이터가 Critical Word 라고 하자.
• 이 Line Fill Buffer 는 Critical Word 부터 해서 차근차근 채워지고, 만약 CPU 가 다음 word (위 그림에서는 빨간색 화살표) 에 접근할 때는 이미 이놈이 Line Fill Buffer 에 올라와 있기 때문에 CPU 는 여기에서 바로 읽어가면 된다.
• 이 Line Fill Buffer 는 다음 cache miss 가 날때까지 여기에 있다가, cache miss 가 나면 원래의 way 로 복사되며 비워지고 miss 에 대한 데이터가 또 채워진다.
• 이런식으로 lower level cache 에서의 data transfer 와 CPU 에서의 data consumption 을 overlap 할 수 있다.
• 또한, 이렇게 하면 Line Fill Buffer 의 크기는 아주 작기 때문에 power consumption 도 많이 줄일 수 있다.

Write Merging (Coalescing) §

• Write Merging (Write Coalescing) 은 cache 와 lower level cache 사이에 write buffer 를 두어서 lower level cache 로 내려가기 전에 잠깐 저장해두는 역할을 한다.
• 이렇게 하면 다음번의 write request 에도 동일하게 write buffer 의 내용이 overwrite 되기 때문에 여러번의 write 을 merge 해서 lower level 로 내려보내는 효과가 나기에 효율적이다.
• 또한 read 시에도 cache miss 가 발생했을 때 우연히 write buffer 에 있을 수도 있기 때문에 second chance 의 여지를 줄 수도 있다.
• 이 write buffer 의 내용은 write buffer 가 가득 차 evict 될 때 lower level cache 로 내려간다.

Compiler Optimization §

• 여기서는 loop 관련 optimization 세개를 소개하는데, 그중 두개는 Loop fusion 와 Loop fission 이다.
• 나머지 하나는 아래 그림에서의 예제로 보여지는 Array Merging 이다.

• 여기에서는 key-value 자료구조에서 key array 와 value array 각각을 만드는 것과 key-value pair array 를 만드는 것 간의 차이를 보여준다.
  • 따로 array 를 구성했을 때에는 key 에 접근할 때와 value 에 접근할때 두번의 cache miss 가 발생하지만
  • 이것을 합치게 되면 key-value pair 에 대한 한번의 cache miss 만 발생하게 된다.
• 이런식으로 array 를 합쳐서 cache miss 를 줄이는 것을 Array Merging 이라고 한다.