Arm Linux Kernel Hacks

누군가 평소에 자주 들르는 카페에 다시 갈 가능성이 있을까요? 한 번도 안 간 사람보다 다시 갈 확률이 높을 것입니다. 이와 유사하게 프로그램이 특정 명령어나 특정 변수를 반복적으로 사용하는 패턴을 시간 지역성(temporal locality)이라고 합니다. 프로그램이 실행될 때 특정 명령어나 변수에 자주 접근하면 가까운 미래에 사용할 것을 대비해 사용된 명령어나 데이터를 캐시에 미리 로딩합니다.

앞에서 예시로 든 예제 코드를 보면서 시간 지역성에 대해 알아봅시다.

01 static int arr[10];
02 int sum = 0;
03 int weight = 10;
04
05 for (i = 0; i < 10; i++) {
06 sum += arr[i] + weight;
07 }

06번째 줄은 arr[] 배열의 &a[0] ~ &a[9] 주소에 있는 배열의 데이터를 읽어서 sum에 더하는 루틴입니다. 데이터에 접근하는 패턴을 자세히 관찰하면 다음과 같은 사실을 확인할 수 있습니다.

weight 지역 변수가 위치한 주소에 반복적으로 접근할 확률이 높다.

이런 특징을 활용해 &a[1] ~ &a[9] 주소에 있는 데이터를 로딩할 때 &weight 주소에 있는 데이터를 미리 로딩하면 속도 개선 효과를 얻을 수 있습니다. 이처럼 다시 접근할 것으로 예상되는 데이터를 미리 로딩해 캐시를 설계할 수 있는데, 이를 시간 지역성이라고 합니다.

시간 지역성을 활용한 다양한 알고리즘이 제안됐는데, 그중 프리페칭이 가장 널리 알려진 알고리즘입니다. 프리페칭은 최근에 CPU 코어에서 접근한 주소 접근 이력을 참고해 더 많은 양의 데이터를 미리 페치하는 기법입니다.