Optimizing Graph Applications with High-Dimensional Features: Software and Hardware Approaches = 고차원 특성 벡터 기반 그래프 어플리케이션들의 성능 최적화를 위한 소프트웨어 및 하드웨어 접근

다국어 초록 (Multilingual Abstract)

In recent years, graph applications demand fast accesses to massive data. Graph-based Approximate Nearest Neighbor Search (ANNS) is now a key operation in production search engines and Retrieval-Augmented Generation (RAG) systems. Sparse Matrix-Matrix Multiplication (SpMM) and Sampled Dense-Dense Matrix Multiplication (SDDMM) are fundamental kernels in various applications, such as Graph Neural Network (GNN). These workloads combine sparse graph traversal with accesses to large embedding matrices, which produce irregular, data-dependent accesses of high-dimensional vectors with little spatial or temporal locality and poor predictability. As a result, multi-level caches and conventional prefetchers are ineffective, and conventional systems become strongly memory-latency bound. This thesis addresses these memory latency issues shared by emerging graph applications.

This dissertation develops two techniques that optimize memory behavior in distinct scenarios, one in software and one in hardware. On the software side, we introduce a lightweight approximation for graph-based ANNS that exploits a key property of search: only a small subset of high-similarity neighbors materially affects the result. By performing low-cost, direction-aware screening to select only neighbors that are likely relevant, the method reduces unnecessary vector fetches and distance evaluations, thereby cutting memory-latency-dominated work. The technique incurs modest metadata overhead, is index-agnostic, and we validate it across multiple popular graph indices.

On the hardware side, we present VIPER, a prefetcher for SpMM and SDDMM. VIPER leverages software hints about the traversal and indirection structure to guide prefetching, bringing the right slices of high-dimensional vectors into the cache ahead of use. It integrates prefetch throttling to avoid overfetching, and uses L2 cache as a buffer, loading data early so that subsequent L1 misses are served as L2 hits rather off-core accesses, thereby making better use of available memory bandwidth and increasing effective memory-level parallelism. As a result, VIPER remains effective even at high vector dimensionality, where naive prefetchers typically struggle.

국문 초록 (Abstract)

최근 그래프 어플리케이션은 방대한 데이터에대한 빠른 접근을 요구하고 있다. 그래프 기반 근사 최근접 이웃 검색(Graph-based ANNS)은 이제 여러 검색 엔진과 검색 증강 생성 시스템에서 핵심 연산으로 자리 잡았다. 희소 행렬-행렬 곱(SpMM)과 샘플링된 밀집-밀집 행렬 곱셈(SDDMM)은 그래프 신경망(GNN)과 같은 다양한 응요에서 기본 커널로 사용된다. 이러한 워크로드는 희소 그래프 순회와 대규모 임베딩 행렬에 대한 접근을 결합하며, 그 결과 고차원 벡터에 대해 불규칙하고 데이터 의존적인 접근을 만든다. 이 때 공간 및 시간 지역성이 거의 없고, 접근 패턴의 예측 가능성도 매우 낮다. 그 경로가, 다단계 캐시와 기존 프리페처는 효과적으로 동작하지 못하고, 전통적인 시스템은 심각한 메모리 지연 병목에 직면하게 된다. 본 논문은 이러한 최신 그래프 어플리케이션들이 공유하는 메모리 지연 문제를 다룬다.

이 논문은 서로 다른 두 시나리오에서 메모리 동작을 최적화하는 두 가지 기법을 제안한다. 하나는 소프트웨어 측면, 다른 하나는 하드웨어 측면에서의 기법이다. 소프트웨어 측면에서는, 그래프 기반 근사 최근접 이웃 검색을 위한 경량 근사 기법을 제안한다. 이 기법은 검색 과정에서 실제로 결과에 의미 있게 기여하는 것은 소수의 고유사도 이웃에 불과하다는 핵심 특성을 이용한다. 방향 정보를 활용한 저비용의 선별을 통해, 실제로 관련성이 높을 이웃만을 선택함으로써, 불필요한 유사도 계산을 줄여, 메모리 지연에 병목이 걸리는 작업량을 감소시킨다. 이 기법은 메타데이터 오버헤드가 작고 특정 인덱스 구조에 종속되지 않으며, 여러 널리 사용되는 그래프 인덱스들에 대해 그 효과를 검증하였다.

하드웨어 측면에서는 SpMM과 SDDMM을 대상으로 하는 프리페처인 VIPER를 제안한다. VIPER는 순회 및 인다이렉션 구조에 대한 소프트웨어 힌트를 활용하여 프리페칭을 안내하고, 사용할 시점에 앞서 적절한 양의 고차원 벡터가 캐시에 미리 올라오도록 한다. 또한, 오버페칭을 방지하기 위해 프리페치 스로틀링을 통합하고, L2 캐시를 다음 프리페치 데이터의 버퍼로 활용하여 더 이른 시점에 적재함으로써 이후 L1 캐시 미스가 오프코어 접근이 아닌 L2 히트로 처리되도록 한다. 이를 통해 사용 가능한 메모리 대역폭을 더 잘 활용하고, 실질적인 메모리 수준 병렬성을 높인다. 그 결과, VIPER는 단순한 프리페처들이 일반적으로 어려움을 겪는 고차원 벡터 그래프 워크로드에서도 지속적으로 높은 효과를 유지할 수 있다.

목차 (Table of Contents)

• Abstract i
• Contents iii
• List of Figures vi
• List of Tables x
• Chapter 1 Introduction 1
• 1.1 Motivation 1
• 1.2 Dissertation Overview 2
• 1.3 Bibliographic Remarks 3
• Chapter 2 Background 5
• 2.1 Memory Latency Bottleneck in Emerging Graph Applications 5
• 2.2 Previous Works to Alleviate Memory Latency Bottleneck 9
• Chapter 3 Angular Distance-Guided Neighbor Selection for Graph-Based Approximate Nearest Neighbor Search 11
• 3.1 Introduction 11
• 3.2 Background and Motivation 14
• 3.2.1 Approximate Nearest Neighbor Search 14
• 3.2.2 Graph-based ANNS 14
• 3.2.3 Bottleneck Analysis of ANNS 16
• 3.2.4 Related Work 18
• 3.3 Angular Distance-guided Search for Graph-based ANNS (ADANNS) 20
• 3.3.1 Estimating Similarity Scores with Approximate Angular Distance 21
• 3.3.2 Neighbor Selection of ADA-NNS 22
• 3.3.3 Efficient Neighbor Selection of ADA-NNS 24
• 3.3.4 Overhead Analysis of ADA-NNS 26
• 3.3.5 Time Complexity Analysis 26
• 3.4 Evaluation 28
• 3.4.1 Experimental Setup 28
• 3.4.2 Throughput Evaluation 30
• 3.4.3 Amount of Similarity Computations 32
• 3.4.4 Ablation Study 32
• 3.4.5 Sensitivity Study 34
• 3.4.6 Memory Overhead 35
• 3.4.7 Computational Cost for Preprocessing 36
• 3.5 Conclusion 37
• Chapter 4 VIPER: Vector Indirect Memory Prefetcher for SpMM and SDDMM 39
• 4.1 Introduction 39
• 4.2 Background and Motivation 41
• 4.2.1 SpMM and SDDMM 41
• 4.2.2 Analysis of SpMM and SDDMM 45
• 4.2.3 Indirect Memory Prefetching Techniques 46
• 4.3 Design of VIPER 51
• 4.3.1 Overview 51
• 4.3.2 Programming VIPER 52
• 4.3.3 DFS-style Indirection Graph Traversal 54
• 4.3.4 Prefetch Throttling 58
• 4.3.5 Prefetch Forwarding to L2 Cache 59
• 4.3.6 System-Level Issues 60
• 4.4 Evaluation 61
• 4.4.1 Methodology 61
• 4.4.2 Performance Results 63
• 4.4.3 Sensitivity Study 68
• 4.4.4 Hardware Overhead 70
• 4.5 Related Work 70
• 4.6 Conclusion 73
• Chapter 5 Conclusion 74
• 5.1 Summary 74
• 5.2 Future Directions 75
• Bibliography 78
• 국문초록 97