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>N_{total}</math>과 이미 GPU memory로 migrate된 child node 크기인 <math>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>N_{migrated}</math>가 갱신된다. 각 non-leaf node는 자기 subtree에서 얼마나 많은 child node가 GPU memory에 있는지를 알 수 있다.

; Proactive prefetch
: 어떤 non-leaf node에서 <math>N_{migrated}</math>가 <math>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를 적용한다.

[[분류: GPU Unified Virtual Memory]]