1. Intro
Cache data를 prefetching하는 방법으로 Hardware based prefetching 혹은 Software based prefetching을 활용할 수 있다.
Hardware based prefetching은 Instruction stream과 Program의 Execution 시 요청되는 data address를 mornitoring하여,
access하는 data의 regularity를 hardware mechanism에 의해 검출하는 prefetching을 말하고,
Software based prefetching은 컴파일러가 프로그래머에 의해 prefetch instruction이 추가된 코드를 컴파일 하여
static instruction stream 상에 prefetch 명령어를 추가하고,
application을 실행할 때 해당 instruction을 issue하여 prefetch 동작을 수행하는 prefetching을 말한다.
이 두 가지 Concept 중에서 software prefetching에 대하여 알아보고, 장단점을 파악해보자.
2. Utilization Software prefetching
Software prefetching은 컴파일러의 도움으로 regular access patterns에 대한 prefetching을 수행함에 있어 큰 장점을 갖고 있다.
아래의 예시 코드를 보자.
다음의 코드를 Compiler directed prefetching을 한다고 가정하면,
|
for (int i=0; i<1024; i++) {
array1[i] = 2 * array1[i];
} |
각, iteration 마다 array1의 i번 째 element가 access되고, 프로그래머는 prefetch instruction을 추가함으로써,
이 후 발생하는 iteration에 대해 elements를 미리 D-Cache (Data cache)로 prefetch 할 수 있다.
|
for (int i=0; i<1024; i++) {
prefetch (array1 [i + k]);
array1[i] = 2 * array1[i];
} |
위의 예제 코드처럼, prefetch instruction을 추가할 때, 현재 access 되는 data를 기준으로,
prefetching 할 data의 위치를 나타내는 stride인 k는 2개의 factor에 의존한다.
● Cache miss penalty
- Cache miss 발생 시, low hierarchy의 memory로 access 하는 과정에서 발생하는 latency
- Spatial locality를 갖는 data의 경우 miss 발생으로 인한 여러 번의 memory access penalty 방지를 위해
미리 data를 loading 함으로써 해당 latency를 hiding할 수 있다.
● for loop 내에서 looping을 한 번 iteration 수행하는 cycles
- Loop 내부의 연산을 처리하기 위해 필요한 execution cycles
위의 factor에 대해 single iteration을 7 cycles, cache miss penalty를 49 cycles라고 가정하면,
k = cache miss penalty / single iteration cycles
k = 7를 얻을 수 있다. 이 것은 현재 access하는 data에서 7만큼 떨어진 data를 미리 prefetch하는 것을 의미한다.
이 것을 통해, 처음부터 7회의 loop에 대해서는 하나의 element가 하나의 cache line에 해당한다는 가정하에 cold miss가 발생할 수 있으나,
이후 data access에 대해서는 100% cache hit을 만들 수 있다.
아래의 그림을 확인해 보자.
그림에서 M은 cache miss, F는 필요한 data를 functional instruction에 가져왔을 때 처리되는 latency, stall은 cache miss penalty를 의미한다.
처음 7개의 loops는 cold miss에 의해 불가피하게 발생하는 latency duration이고, 이 것은 어쩔 수 없이 용인해야하지만,
이 후 지속적인 cache hit을 통해 execution delay를 줄일 수 있다.
3. Pros and Cons
Pros: 일정한 stride를 가진 regular access patterns의 경우 좋은 성능을 발휘할 수 있음
Cons: 프로그래머가 prefetch instruction을 삽입하고 stride를 결정해야 하는데,
이 때 2가지 factor인 cache miss penalty와 single iteration cycles를 system 내부에서 정확히 파악하기 어려움
prefething을 위한 별도의 compiler 수정이 필요함
Reference
Cache prefetching from wikipedia and free encyclopedia