CPU Cache: address translation

이 글에서는 캐쉬의 주소 변환 과정의 종류 그리고 각 종류의 장단점과 ARM architecture에서는 어떻게 그 단점들을 보완하고 있는지 알아보겠다.

 

ARM®Cortex®-A Series, Version: 1.0, Programmer’s Guide for ARMv8-A, Figure 11-2 Cache terminology

캐쉬는 메모리 (DRam) 접근이 CPU의 속도에 비해 너무 느리기에 그 시간을 단축하기 위해서 만든 하드웨어이다. 위 그림과 같이 주소와 그에 상응하는 데이터를 저장하고 CPU의 메모리 읽기, 쓰기 처리 속도 향상에 아주 큰 1등 공식 하드웨어이다. 사실 캐쉬에 대해서 설명하려면

• Full associative, Set-way associative
• Eviction Policy (LRU)
• Data fetch algorithm (Spacial and Tempral Locality)
• etc

이와 같은 내용들을 모두 설명해야 하지만, 이 글에서는 Cache에서 주소 관리 방법에 따른 특징들에 대해서 알아보겠다.

컴퓨터에서 주소라하면 가상 주소 (Virtual Address) 와 물리주소 (physical Address)가 있다. 위 그림에서도 주소라는 말만 있을 뿐, 가상 주소와 물리 주소 중 어떤 것을 주소로 사용하고 있는 지에 대한 설명은 빠져있다. 그 이유는 사실 Cache를 만드는 사람이 원하는데로 만들면 되기 때문이다. 그러나 물론 산업에서 주로 사용하는 주소는 정해져있다. 이제부터 어떤 주소를 사용하면 어떤 특징이 있는지, 그리고 내가 주로 일하는 ARM architecture에서는 어떠한 방법으로 주소를 관리하고있는지에 대해서 알아보겠다. 

 

캐쉬에서 주소를 사용하는 방법은 가상주소만을 사용할 수도 있고, 물리주소를 사용할 수도 있고 또는 혼용해서 사용할 수 있다. 이 조합으로 알아보면:

• PIPT: Physical Indexed Physical Tagged
• VIVT: Virtual Indexed Virtual Tagged
• VIPT: Virtual Indexed Physical Tagged
• PIVT: Physical Indexed Virtual Tagged

이렇게 크게 4가지의 주소 변환 방법이 있다. Indexed와 Tagged는 위 그림에서 보이는 Tag와 Index를 의미하는 것으로 가상주소나 물리주소의 일부분을 가져와 Tag 또는 Index로 사용하는 것을 뜻한다.

 

조금 귀찮아져서 공부한 내용을 간략히 정리해보면:

• PIPT: 문제 없이 항상 사용할 수 있지만 성능이 조금 느리다
• VIVT: MMU (TLB) 접근을 하지 않아도 되서 빠르다. 하지만, synonym[1]과 homonym[2] 문제가 생긴다
• VIPT: PIPT와 VIVT의 장점을 가지고 있다. synonym과 homonym의 문제를 어느정도 해결한다
• PIVT: 성능은 PIPT 처럼 느리고, synonym과 homonym문제도 그대로 갖고 있어 사실 사용하지않는다

[1] synonym: 하나 이상의 가상 주소가 하나의 물리주소와 매핑되는 문제, 예를 들어 mmap API를 통해서 여러 가상 주소가 하나의 물리 주소에 매핑 횔 수 있게 된다.

[2] homonym: 하나의 가상 주소가 여러 물리주소와 매핑 되는 문제, 예를 들어 A 쓰레드가 context-out되고 B쓰레드가 context-in 되었을 때, A쓰레드가 사용하던 data (가상 주소 0xFFFF_0000에 해당하는)가 캐쉬에 남아있고, B 쓰레드가 0xFFFF_0000에 해당하는 data 를 사용하면 B는 원치 않는 data에 접근하게 된다. 이는 context-switch 할 때, cache clean&invalidation을 통해서 해결할 수 있다.

사실 homonym 문제는 context-switch 할 때 cache operation을 통해서 극복이 가능하므로 문제가 없다. 하지만 synonym의 경우는 cache operation을 통해서 극복이 불가하다.

 

VIPT 에서 synonym 문제와 그에 해결 방법

64비트 아키택쳐를 기준으로 가상 주소는 64비트를 가지고 있고 아래와 같은 형식으 캐쉬에서 사용된다고 해보자.

이 때, Tag (물리주소로 부터 가져온) 와 Index (가상주소로 부터 가져온) 사이에 겹치는 비트들이 있으면, 그 비트의 2제곱승 만큼 synonym 현상이 발생할 수 있다.

64bit architecture address format in cache

이러한 문제가 있음에도 불구하고 index 비트를 Tag와 겹치면서 까지도 늘리고 싶은 이유는 cache의 총 크기를 늘리기 위해서이다 (cache total size = Page size * # of associatives). 따라서 synonym 현상을 피하기 위해서 운영체제에게 cache coloring [3] 을 통해 극복하게 하거나 Tag와 Index간의 겹치는 부분을 없애므로써 해결할 수 있다.

 

[3] 간단히 말해, overlapped 된 비트에 대해서 가상 주소와 물리 주소를 같에 할당하는 것이다.

 

ARM 아키택쳐에서는 Hardware 내부적으로 해결하는 모습을 보이고 있다. 사실 어떻게 이 문제를 해결하는지는 모르지만, Manual 에서 찾아보면 어떤 cache type이든 간에 PIPT의 동작이 똑같음을 보장해 준다고 한다. 뇌피셜로는 아마 Cache access할 때 다른 cache-line간의 look-up을 통해 해결하고 있을 것 같다 (그게 아니면 사실 해결 방법이 따로 있어 보이지는 않는다).