[ACA] Improving Cache Performance

이때까지 Memory Hierarchy에 대해서 알아보았다. 그리고 메인 메모리에서 캐시 메모리에 매핑하는 방법, CPU에서 데이터를 메모리에 쓰는 방법에 대해서 알아보았다. 그러면 메모리는 계층 구조를 갖고 있다는 것은 알겠는데, 캐시 메모리도 계층 구조를 갖고 있을까? 답은 Yes다. 캐시 메모리도 다음과 같은 'Cache Hierachy'를 갖고 있다.

Cache Hierarchy

최근에 개발되고 있는 프로세서들은 보통 세개의 캐시를 갖고 있다. 이들은 각각 L1 Cache, L2 Cache, L3 Cahce라는 이름으로 불리는데, 이러한 계층 구조를 설계했을 때 장점은 무엇일까? 우리가 메모리 계층 구조를 왜 생각했는 지를 돌아보면 된다. 우리는 메모리의 사이즈는 크게, 처리 속도는 빠르게 메모리를 이용하고 싶어서 계층 구조를 통해 착시를 주었다. 캐시도 이와 같이, 실제로는 빠르면서 큰 캐시 메모리라는 것이, 속도와 사이즈 사이에 trade-off가 있기 때문에 계층을 나누어 착시를 주는 것이다. 이제 각 계층의 캐시들이 어떤 특징을 갖고 있는지 알아보자.

 

L1 Cache

- L1 Hit time은 clock cycle time에 영향을 미친다.

- Hit time이 굉장이 중요하다.

- 작고, 빠르고, 낮은 associativity를 갖고 있다.

 

L2 Cache

- Access time이 L1보다 덜 중요하다.

- 크고, 느리다.

- 큰 associativity를 갖고 있다. 이는 L2 Cache가 느리기 때문이다.

- Tag storage와 data storage에 순차적으로 접근한다. 이는 병렬적으로 처리할 수 있지만, 병렬로 처리하면 에너지 소모가 더 커지고, 핀과 와이어가 더 필요하다. 이때 코스트가 상당히 증가한다고 한다. 안정성도 문제인데, 이건 물리학적인 문제다. 데이터를 읽고 쓰는 것은 전압의 문제인데, 핀이 여러개가 되면 전압이 불안정해지고 이걸 보조해주기 위한 유닛이 붙는다. 그러면 배보다 배꼽이 더 커지는 상황이 오는 것이다.

 

하드웨어 구조는 다음과 같다. L1 Cahce는 명령어 캐시와 데이터 캐시가 나뉘어져있고, 프로세서에 내장되어있다. L2 Cache는 프로세서 밖에 있으며, L3 Cache는 코어들이 공유하는 캐시다. 그리고 L3 Cache는 메인 메모리와 매핑한다.

 

지금까지 Cache Hierachy와 각 계층의 캐시가 어떤 특징을 갖고 있는지 알아보았다. 이제 우리가 원하는 것은 캐시 메모리의 성능을 향상시키는 것이다. 그러면 캐시의 성능은 어떻게 향상시킬 수 있을까? 뭔가를 '향상시킨다'고 이야기하려면 성능상 향상이 있는지를 알려주는 지표가 있어야하고 그것이 측정 가능해야한다. 캐시 메모리에서는 Hit rate, Miss rate을 통해 이를 측정한다.

 

Hit rate

: Memory hiearchy에서 접근했을 때, Hit가 난 비율 = Hits/Accesses

 

Hit Time (= Hit latency)

: 현재 레벨의 블록에 접근하는데 걸리는 시간 + Hit/Miss를 결정하는데 걸리는 시간

 

Miss rate

: Memory hiearchy에서 접근했을 때, Hit가 나지 않은 비율 = 1 - Hit rate

 

Miss penalty

: 낮은 계층의 블록에 접근하는 데 걸리는 시간 + 블록을 미스가 난 계층으로 전송하는 데 걸리는 시간 + 미스가 난 계층에 블록을 넣는데 걸리는 시간 + 리퀘스터에게 블록을 보내는 데 걸리는 시간

다시 이야기해서 캐시에서 미스가 나면, 메인 메모리까지 가서, 데이터를 가져오고, 캐시를 업데이트하고, CPU까지 가져가는데 걸리는 시간을 말한다.

 

위에서 보았듯이, 캐시 미스가 일어났을 때 받게되는 Miss Penalty는 Hit time보다 훨씬 크다. Miss Penalty >> Hit Time

최대한 미스가 덜 나는 것이 우리가 바라는 방향일텐데, 미스가 나는 경우는 어떤 것이 있을까? 3Cs라고 해서 Compulsory, Capacity, Conflict Miss 총 세가지로 분류할 수 있다.

 

Compulsory Miss

: 캐시에 최초로 접근을 할 때 생기는 미스다. 처음에는 캐시가 비어있으니 발생한다. 이는 캐시의 사이즈를 키워서 해결할 수 없다. 하드어나 소프트웨어적으로 prefetcher를 구현하는 것으로 해결할 수 있다.

 

Capacity Miss

: 캐시의 용량이 부족할 때 생기는 미스다. 프로그램 실행 중에 데이터의 양이 캐시의 크기보다 클 때 발생한다. 캐시의 사이즈를 키우거나 데이터를 압축, 코드를 수정해서 해결할 수 있다.

 

Conflict Miss

: 캐시에서 Set의 Way가 부족할 때 생기는 미스다. 그러니까 데이터1과 데이터2가 같은 캐시 주소를 할당받아서 발생한다. 이는 코드에 패딩이나 스트라이드를 추가하거나, 데이터의 크기를 변경하여 해결할 수 있다.

 

이제, 메모리 시스템의 성능을 분석할 때 사용하는 'Average memory access time (AMAT)'을 알아보자. 

 

AMAT

= hit rate x hit time + miss rate x miss latency

= hit rate x hit time + miss rate x (hit time + miss penalty)

= hit time + miss rate x miss penalty

 

그러면 multi-level cache인 경우에는 어떻게 될까?

AMAT = HitTime of L1 + MissRate of L1 x MissPenalty of L1

MissPenalty of L1 = HitTime of L2 + MissRate of L2 x MissPenalty of L2

MissPenalty of L2 = HitTime of L3 + MissRate of L3 x MissPenalty of L3

 

이를 살펴보면, L2, L3가 상대적으로 느리지만 Miss Rate이 중첩되어 곱해지기 때문에, Miss penalty를 감쇄할 수 있는 것이 보인다. 즉, Cache Hierarchy를 통해 캐시 메모리의 사이즈는 크게, 속도는 빠르게, 전반적인 성능의 향상을 가져올 수 있는 것이다.

 

AMAT을 다시 살펴보면 총 3개의 항이 있다. 이 세개의 항의 값을 줄이는 것이 캐시 메모리의 성능을 향상시키는 것과 직결된다. 그러면 각각은 어떻게 줄일 수 있을까? 

 

Reducing the hit time

- 작은 캐시 사이즈

- Directed mapped cache

- 작은 블록

 

Reducing miss rate

- 큰 캐시 사이즈

- Associativity를 올린다.

- 큰 블록

- 좋은 eviction/insertion 정책

 

Reducing miss penalty

- 작은 블록

- 큰 블록에는 중요한 워드를 먼저 배치해준다.

- 멀티 레벨 캐시

 

다음 포스팅에서는 캐시 최적화를 위해 어떤 테크닉이 사용되는지 알아보도록 하겠다.