캐시와 정렬 알고리즘간 관계

'The Influences of Caches on the Performance of Sorting '리뷰

 O(nlogn) 정렬 알고리즘이 O(n)정렬 알고리즘보다 빠르다??

1. Introduction:

Cache miss penalty의 문제가 performance에 큰 영향을 미침 & instruction count를 최소화 하기 위한 알고리즘이 필요.

ex) radix sort는 lowest instruction count가 있으나, poor cache performance로 인해 merge sort, quicksort에 비해 성능이 떨어진다.

이 논문의 목적은 4개의 정렬 알고리즘: heapsort, mergesort, quicksort, radixsort 를 cache의 측면에서 개선(메모리 최적화를 통한 성능개선), 분석한다.

비교를 위해 4000~409600 keys, 64 bit integers를 랜덤으로 선택.

Matrics for evaluations:

1. Instruction count
2. Cache misses
3. 현대 메모리 시스템에서의 성능 평가

2. Caches:

Cache 설계를 위한 파라미터:

1. Capacity: 하나의 cache에 수용 가능한 바이트 수
2. Block size: 한번 메모리에서 load될때, 바이트 수
3. Associativity: cache내부에서 block 배치 방법
4. Replacement policy: cache에서 어떤 block를 remove할지.

3. Design and evaluation methodology

Dynamic instruction counts: 각 instruction 실행시 삽입하여 instruction count를 계산.

Cache performance는 각 load, store 마다 call을 삽입하여 추적후 계산.

각 알고리즘별 성능 평가

Mergesort:

base mergesort

왼쪽부터 instructions count, cache misses count, time 측

Radix sort:

input array size가 cache capacity를 돌파하는 순간, cache miss 비율이 급증.

Conclusion:

cache performance가 sorting algorithm의 performance의 많은 영향을 미침.

ex) radix sort는 low instruction count에도 불구하고 poor locality로 인하여 mergesort, quircksort에 비해 performance가 떨아진다

ex) multi mergesort는 base mergesort에 비해 instruction count가 75%많지만, 70%더 빠른 것으로 확인.

Large data set에 대하여 memory-tuned quicksort(메모리 최적화를 위해 개선된 quick sort), multi-mergesort가 radixsort에 비해 좋은 성능을 낸다.

 

아래는 각 알고리즘의 instruction count, cache miss