프로그램을 코딩할 때에 우리는 종종 컴퓨터 구조를 무시하거나, 망각하고 코딩하는 경우가 종종 있다. 이렇게 프로그래머들이 컴퓨터 구조를 무시하는 이유는 내가 판단하기에 크게 두가지이다. 첫째는 잘 몰라 서이고, 둘째는 프로그래밍 생산성(productivity)을 증가시키기 위해 잘 추상화된, 즉 high-level abstraction을 제공하는 프로그래밍 언어의 사용 으로 인해서이다. 즉 프로그램 성능에 관한 문제를 완전히 또는 상당 부분 컴파일러나 인터프리터에게 맡겨버림으로써 더이상 컴퓨터 구조에 대한 고민을 하지 않아서이다. Java만 해도 포인터를 없앰으로써 메모리 관리에 대한 고민을 더이상 하지 않게 하지 않았는가? 이러한 프로그래밍 언어의 abstraction은 프로그램의 생산성은 크게 향상시켜 주었다. 하지만 프로그램의 성능(performance)에 대한 고민을 한다면, 저수준의 추상화를 제공하는 다른 프로그래밍 언어를 이용해 컴퓨터 구조에 잘맞는 프로그램의 작성이 요구될 것이다. 그리고 그것이 내가 생각하는 C/C++, Assembly가 아직도 성능이 우선시 되는 여러 프로그래밍 분야, 특히 시스템 프로그래밍에 널리 이용되는 이유이다.
프로그램을 코딩할 때에 왜 컴퓨터 구조를 고려해야 하는지 여기에 그 이유가 있다.
그림 1. Multi-level Caches in Computer Systems
그림 1은 컴퓨터 시스템의 캐시 구조를 개념적으로 도식화한 것이다. 프로세서는 instruction이나 data를 보관할 register와 L1 cache를 가지며, 또한 L2 cache를 갖는다. 어떤 CPU는 L1 cache로 Instruction cache와 data cache를 따로 가지는 경우도 있으며 또는 Unified L1 cache 하나만을 가지는 경우도 있다. L2 Cache는 현재 대부분의 CPU는 on-chip으로 되어 있으며, 간혹 어떤 CPU들은 Off-chip L3 cache를 갖는 경우도 있다. 메인 메모리는 I/O BUS를 통해 CPU 및 다른 디바이스들과 연결되며, Disk 또한 I/O BUS를 통해 연결된 Disk controller를 통해 연결된다. BIOS(Basic IO System)을 제외한 컴퓨터 시스템의 운용들에 필요한 거의 모든 프로그램과 데이터는 초기 디스크에 저장되어 있으며, 필요에 따라 프로세서에 의해 요구된다.
우리가 익히 알다시피 디스크는 용량(capacity)와 $/MBytes 는 우수한 반면에 속도(speed)는 늦은 저장매체이다. (사실 속도는 latency와 bandwidth 두 요소에 의해 결정된다.)
따라서, 필요한 데이터 접근을 위해 매번 CPU가 disk controller에 데이터를 요청한다면, CPU는 디스크가 해당 데이터를 제공하기 위해 필요한 시간(latency + read time+ delivery time)동안 아무일도 하지 못하는 stall 상태에 놓이게 된다. CPU는 가급적 놀리지 않아야 코드의 성능 향상이 있다.
따라서, 현대의 컴퓨터 시스템은 다단계의 캐시 구조를 가진다. 자주, 빈번하게 쓰이는 데이터들은 보다 상위의, 용량은 좀더 작고, $/MBytes는 보다 비싸며, 속도는 보다 빠른, 메인 메모리에 캐싱을 하는 것이다. 데이터베이스에서는 이렇게 디스크에서 메모리로 올려진 데이터들을 버퍼라고 얘기를 하기도 하며, 또 혹자는 메모리 캐시라고도 얘기하기도 한다.
메모리 또한, 접근 속도가 시스템 캐시(L2) 보다 느리므로, 메모리에서 또 다시 자주 사용되는 데이터나 루틴은 다시 L2로 캐시한다. 그리고 L2는 L1으로 L1는 프로세서의 레지스터로.... 결과적으로 컴퓨터 구조는 다음과 같은 메모리 계층(memory hierarchy)를 갖게 된다.
그림 2. Memory Hierarchy
최근까지 많은 컴퓨터 프로그램의 성능 향상은 주로 디스크와 메모리 간의 속도 차이를 극복하기 위한 방안으로 진행되어 왔다. 즉 느린 속도를 개선하기 위해 많이 쓰이는 데이터를 메모리에 가져다 놓기 위한 노력이 있어왔는데 대표적인 것이 Buffer Management(LRUK 등), B+-tree, R-tree와 같은 disk-resident indexing 기법들이 있을 수 있겠다. 실상 최근까지 데이터베이스 및 정보 관리 분야에서의 거의 모든 문제들은 이러한 디스크와 메모리 간의 gap을 어떻게 극복하느냐를 주된 관심으로 가졌으며, Jim Gray는 이러한 디스크와 메모리 간의 gap에 대해 저 유명한 Five Minute Rule[5] 로 매 5분 내에 다시 이용될 디스크 페이지는 메모리에 캐시하도록 제시했었다. 또, 디스크라는 storage는 latency 자체가 크게 성능 개선이 이루어지지 않아 왔던 관계로, 이러한 기법들이 지금까지도 아주 잘 먹혀 들어갔던 것도 사실이다. (Latency와 Bandwidth의 차이는 [1]을 참조)
그림 3. Memory Wall
하지만, 최근의 경향을 보면 이제는 메모리 또한 bottleneck이 되어 가고 있다는 것이다[2]. 메모리 월(Memory Wall)이라고도 불리는 이 현상의 설명을 위해 그림 3을 보자.
그림 3은 한 instruction 수행을 위해 요구되는 clock 수의 개선 경향과, 메인메모리로 사용되는 DRAM의 접근에 필요한 clock 타임을 비교한 것이다. 메모리 용량의 증가는 메모리 칩 내부에 더 많은 내부 공간을 가진다는 것이며, 접근할 내부 공간의 증가는 더 많은 system clock을 필요로 한다. CPU의 system clock이 매년 크게 향상되어서, 실제 메모리 접근에 필요한 시간은 줄어든다 할지라도, 메모리 접근에 필요한 절대적인 clock 수는 증가한다라는 것이다. 예를 들어 한 프로그램이 100 Instruction으로 구성되고 프로그램이 필요한 데이터를 위해 각 LOOP마다 메모리에 1번씩 접근,메모리에 10번 access를 한다고 하자. 2010년 기준으로 100 Instruction 처리는 4.2 clock만에 끝나는 반면, 한번의 메모리 접근을 위해서는 1000 clock이 요구된다. 즉, 메모리에서 데이터를 읽어들여 CPU의 레지스터에 올리기 전까지 CPU는 995.8 clock 동안 아무런 일을 하지 않고 노는 stall 상태에 빠지게 된다. 이 후 두 번째 LOOP부터는 레지스터, L1, L2 cache에 접근하여 데이터를 읽어들이던가 아니면 또다시 메모리에 접근하겠다.
물론 매 LOOP마다 메모리에서 데이터를 가져온다면, 이 같은 현상이 반복될 것이다.
따라서 이러한 메모리와 CPU 간의 속도 차이는 L1, L2 시스템 캐시의 효과적인 이용을 고민하게 한다. 마치 예전에 디스크와 메모리 사이의 갭을 극복하고자 했던 것과 마찬가지로 말이다.
그림 4와 5는 이러한 고민이 왜 필요한지 여실히 보여준다.
그림 4. Memory Mountain of Pentium III Xeon
그림 4는 1999년 출시되었던 Intel의 Pentium III Xeon 을 탑재한 컴퓨터 구조에서 메모리와 L1, L2 시스템 cache 간의 데이터 처리량(throughput)의 차이를 보여준다.
그림 5. Memory Mountain of Intel Core 2 Duo T9300
그림 5는 2008년 1분기에 출시된 Intel Core 2 Duo T9300(2.5GHz Clock speed, 2X 32KB On-chip L1 D-Cache, 2 X 32KB On-chip L1 I-Cache, 6MB Unified L2 Cache) 을 탑재한 컴퓨터 시스템에서 메모리와 L1, L2 시스템 캐시에서의 데이터 처리량을 보인다.
먼저 그림 4의 Xeon 에서의 L1, L2, Mem간의 단위 시간 당 처리량을 보면, Stride-1인 경우 메모리는 200 MB/S 이하, L2 Cache는 700MB/S 이상, L1 Cache는 1000MB/S 이상을 상회한다.
최근에도 이 상황은 달라지지 않았다. 그림 5의 Core 2 Duo의 경우 Stride-1에서 메모리는 4,000MBps/S
L1 Cache는 8,000MBps/S, L2 Cache는 10,000 MBps/S로 이 경향은 그대로 유지되고 있다. (이 실험은 멀티코어에서의 병렬성은 이용하지 않고, sequential programming하여 코어 두 개 중 하나만 이용한 경우로 보인다. 그 이유는 나중에 설명한다.)
빈번하게 사용되는 데이터는 캐시에 올려놓음으로써, 가급적 메모리에 접근하지 않고, 프로그램을 수행하는 것이 보다 프로그램 성능을 향상시킬 수 있다. 하지만, 시스템 캐시에서의 데이터 또는 instruction의 배치(placement)와 교체(replacement)는 H/W에 의해 결정이 되므로, 우리가 임의로 어떠한 프로그램이 다루는 코드나 데이터를 임의로 캐시에 배치하기는 곤란하다. 하지만, 캐시되기에 좋게 프로그램을 작성할 수 있는 방법은 있다. 즉, Cache-aware한, 또는 Cache-friendly한 프로그램을 작성하는 것이다. 그러면, 어떻게 해야 cache-friendly한 프로그램을, cache-aware한 알고리즘을 작성할 수 있을까? 위 데이터 차트들에 그 힌트가 있다.
먼저 그림 4를 보면, L1 cache와 L2 cache, memory가 서로 다른 능선들을 그리는 것을 볼 수 있다.
어떤 한 프로그램의 data가 모두 L1 cache에 저장되어 있다면 최대 1000MB/S의 처리량으로 프로그램이 처리될 수 있을 것이다. 반대로 어떤 한 프로그램의 data가 모두 memory에 저장되어 있고 L1, L2에 의해 cache되지 못한다면, 200MB/S 정도의 처리량 밖에 얻지 못한다.
이번에는 작업 데이터 크기(working set size)를 보자. working set size에 따라 달라지는 처리량은 시스템 캐시의 크기와 관련이 있다. L1 d-cache의 크기가 16KB이므로, 16kB를 넘는 작업 데이터는 당연히 L1 d- cache에 담을 수 없으므로 L2 cache에 담고, L2 cache에 접근하게 된다. 또한, 512KB L2 cache를 넘는 데이터는 종국엔 메모리에 접근해서 가져오게 된다. 결국, 16KB, 512KB의 작업 데이터 크기를 경계로 능선이 구분된다.
또다른 현상은 stride의 수에 기인한다. stride란 해당 작업 데이터가 메모리 공간에 서로 인접해 있어 한번의 scan으로 읽혀지는지, 아니면 나뉘어져 있는지를 구분한다. 즉, stride-1은 모든 데이터가 서로 메모리 공간에 인접해 있다는 것이며(data[0], data[1], ...data[n]), stride-2는 작업 데이터가 1개 공간씩 떨어져 있다.(data[0], data[2], data[4], ,,,, data[n]). 즉, stride-k은 data[0], data[k], data[2k], ....로
메모리에서 이전 데이터와 k만큼 떨어져 있는 데이터를 읽는다.
stride-1에서는 데이터가 서로 인접해 있으므로, data를 sequential scan 하기 용이하며 결과적으로 처리량도 제일 높다. stride-k에서 k가 증가하면 증가할 수록, 데이터가 서로 떨어져 있게 되어 메모리의 처리량은 떨어진다. 하지만 L2 cache는 어떨까? L2 cache에서는 처리량이 떨어지다가 stride-8 부터는 평지를 이룬다. 이것은 한 캐시 라인이 가지는 캐시 블록 크기와 관계가 있다. 여기에서 한 캐시 라인의 block size는 8word(32bytes)이다. stride-1일 때는 8개의 인접해 있는 word들이 한 캐시라인에 캐싱될 것이고, stride-2일 때는 4개의 인접해 있는 word들이 한 캐시라인에 캐싱될 것이다. stride-8일 때는 1개의 word만이 한 캐시라인에 캐싱된다. 따라서 stride-8인 경우는 8개의 cache line을 읽어야만 8 word를 복구시킬 수 있다. stride-8 이상의 경우에도 물론 8개의 cache line을 읽어야 한다. (word 단위 이하로 잘라서 캐싱하지는 않기 때문이다).
프로그램은 로컬리티(locality)를 가진다. locality란, 프로그램은 최근에 이용했거나 참조한 인스트럭션이나 데이터를 다시 이용하는 경향을 보인다는 것이다. 이러한 로컬리티는 크게 temporal과 spatial로 나뉜다.
- Temporal locality: 최근에 참조한 아이템은 가까운 미래에 다시 참조되는 경향이 있다.
- Spatial locality : 인접해 있는 항목들은 한 번에 같이 참조되는 경향이 있다.
전체 캐시 크기(total cache size)는 temporal locality를 이용에 힌트를 준다. 즉 임의 프로그램이 작업 데이터를 반복적으로 읽어야 하는 경우, 한번에 참조하는 최대 데이터의 크기를 전체 캐시 크기 단위에 맞추어 블록 단위로 처리하면, 메모리 접근을 상대적으로 많이 피할 수 있으므로 성능 향상을 시킬 수 있다는 점이다.
두 번째로는 시스템 캐시의 캐시 크기는 spatial locality의 이용에 힌트를 준다.캐시 라인 크기에 맞추어서 데이터들을 서로 메모리 공간에 인접시키면, 프로그램이 데이터를 캐시에서 읽어 들일 때 여러 캐시 라인이 아닌, 한 캐시 라인 단위로 읽어들임으로써 성능 향상을 시킬 수 있다. 이는 포인터 이용에 관한 우리의 일반적 습관들을 다시 한번 고민하게도 한다.
다음 글에서는 행렬 곱셈과, Cache-aware한 B+트리, 해싱과 같은 예를 통해 로컬리티의 향상이 어떻게 프로그램의 성능을 개선하는지 보인다.
참고 문헌
[1] Latency Lags Bandwidth, David A. Patterson, Communications of ACM, 2004
[2] Hitting the Memory: Implications of the Obvious, ACM SIGARCH Computer Architecture News, Bill Wulf and Sally Mckee, 1995
[3] Query co-Processing on Commodity Processors, Anastassia Ailamaki and et al., A tutorial in ICDE 2006.
[4] Computer Architecture: A Quantitative Approach The 4th Edition, John L. hennesy and David A. Patterson, 2007
[5] The 5 Minute rule for trading memory for disc accesses and the 10 byte rule for trading memory for CPU time, Jim Gray, SIGMOD Record, 1987
Acknowledgement
이 글에서 참조한 그림 1,2,4 는 Computer Systems: A Programmer's Perspectivem Prentice Hall, 2002의 instructor's material에서 발췌함. 그림 5는 Wikipedia에서 발췌함. 그림 3는 참고 문헌 [3]의 저자들의 Lecture slides에서 발췌함.
