Tree-based Neighboring Prefetcher

TBNp는 Tree-based Neighboring Prefetcher의 약자로, NVIDIA UVM에서 Unified Virtual Memory page fault overhead를 줄이기 위해 사용하는 tree 기반 neighboring prefetcher이다. GPU가 host memory에 있는 UVM page를 접근하면 far-fault가 발생하고, UVM driver가 해당 page를 GPU memory로 migrate한다. TBNp는 이때 fault가 난 page만 가져오는 것이 아니라, 같은 tree 안의 주변 page도 함께 가져와 이후 far-fault를 줄이려는 mechanism이다.

개요

GPU Unified Virtual Memory에서는 GPU memory보다 큰 working set을 host memory까지 확장해 실행할 수 있다. 하지만 GPU가 host memory에 있는 page를 처음 접근하면 far-fault handling이 필요하고, 이 과정은 GPU execution의 critical path에 들어간다. TBNp는 far-fault가 반복해서 발생하는 것을 줄이기 위해 spatial locality를 가정하고 neighboring page를 미리 migrate한다.

TBNp는 다음 구조를 갖는다.

UVM virtual address space를 2 MB VABlock 단위로 나눈다.
각 2 MB VABlock을 5-level full binary tree로 관리한다.
leaf node는 64 KB basic block이며, TBNp의 최소 migration unit처럼 동작한다.
non-leaf node는 subtree 전체 크기인 [math]\displaystyle{ N_{total} }[/math]과 이미 GPU memory로 migrate된 child node 크기인 [math]\displaystyle{ N_{migrated} }[/math]를 metadata로 가진다.
subtree에서 migrate된 비율이 50%를 넘으면, locality가 높다고 보고 남은 child node들을 proactive하게 prefetch한다.

즉 TBNp는 page fault stream을 보고 "이 근처도 곧 쓸 것이다"라고 추정한다. 이 추정을 tree metadata로 관리하기 때문에, 단순히 fixed-size window를 prefetch하는 방식보다 hierarchy별 locality를 표현할 수 있다.

동작 방식

Far-fault 발생: GPU가 resident하지 않은 UVM page를 접근하면 far-fault가 발생한다. UVM driver는 fault가 난 page가 포함된 TBNp leaf node를 찾는다.

Leaf-node migration: conventional TBNp에서는 leaf node가 64 KB이므로, 4 KB page 하나에서 fault가 나도 같은 64 KB leaf node 안의 나머지 page까지 GPU memory로 migrate한다. 이 단계만으로도 같은 leaf 안의 후속 page fault를 줄일 수 있다.

Tree metadata update: migration이 일어나면 leaf에서 root 방향으로 [math]\displaystyle{ N_{migrated} }[/math]가 갱신된다. 각 non-leaf node는 자기 subtree에서 얼마나 많은 child node가 GPU memory에 있는지를 알 수 있다.

Proactive prefetch: 어떤 non-leaf node에서 [math]\displaystyle{ N_{migrated} }[/math]가 [math]\displaystyle{ N_{total} }[/math]의 50%를 넘으면, TBNp는 그 subtree의 나머지 leaf node도 GPU memory로 prefetch한다. 예를 들어 같은 2 MB VABlock의 앞쪽 leaf들이 이미 많이 migrate되었다면, 나머지 인접 leaf도 곧 접근될 것이라고 본다.

Far-fault amortization: TBNp의 목적은 한 번의 far-fault handling 동안 여러 page를 함께 가져와, 이후 발생할 수 있는 여러 on-demand far-fault를 제거하는 것이다. GPU workload가 sequential 또는 dense spatial access를 보이면 이 전략이 잘 맞는다.

왜 tree를 쓰는가

GPU memory access는 CPU prefetcher가 가정하는 instruction-local cache miss stream과 다르게, 많은 warp와 SM에서 bursty하게 발생할 수 있다. 개별 load instruction 단위로 fine-grained access pattern을 추적하면 metadata와 driver communication 비용이 커진다. 반대로 TBNp는 page migration이라는 coarse-grained UVM event를 tree 구조로 묶어, batch 단위 locality와 prefetch aggressiveness를 비교적 간단하게 조절한다.

Tree-based prefetching이 GPU의 bursty memory behavior에 잘 맞고, prefetch aggressiveness를 hierarchical하게 조절할 수 있기 때문에 TBNp가 최근 NVIDIA GPU UVM에서 중요하게 사용되고 있다.

한계

Homogeneous configuration: conventional TBNp는 모든 application, kernel, data object에 같은 tree configuration을 적용한다. Forest 논문에서 다룬 baseline은 2 MB tree와 64 KB leaf node를 사용한다. 그러나 실제 workload에서는 어떤 object는 linear streaming이고, 어떤 object는 sparse irregular access를 보인다. 하나의 tree size와 leaf size가 모든 object에 최적일 수 없다.

Unnecessary migration: TBNp는 locality를 가정하고 neighboring page를 미리 가져온다. 하지만 sparse access에서는 64 KB leaf 안에서도 실제로 쓰는 4 KB page가 일부뿐일 수 있다. 이 경우 migration된 page가 eviction 전까지 한 번도 접근되지 않을 수 있고, GPU memory capacity를 불필요하게 점유한다.

Oversubscription에서 memory pressure 악화: GPU memory가 oversubscribed된 상황에서는 prefetch가 항상 좋은 것이 아니다. 잘못 prefetch된 page가 GPU memory를 차지하면 유용한 page가 밀려나고, 이후 다시 migrate되면서 page thrashing이 생긴다. Forest 논문은 일부 benchmark에서 migrated page의 5%에서 48%가 eviction 전까지 전혀 접근되지 않았다고 보고한다.

Eviction policy와의 상호작용: conventional UVM eviction은 GPU-side actual access recency가 아니라 far-fault event history에 의존한다. 따라서 TBNp가 불필요한 migration을 만들면 eviction candidate도 왜곡될 수 있다. Prefetcher와 eviction policy는 독립된 문제가 아니라 같은 GPU memory capacity를 두고 상호작용한다.

Access pattern obliviousness: TBNp는 page fault와 migration state는 보지만, data object의 semantic이나 GPU-side access sequence를 직접 이해하지 않는다. 그래서 같은 application 안에서 kernel마다 object access pattern이 달라져도 동일한 policy를 적용한다.