Half time seminar by Alireza Hadaddi: "Hiding Paging Latency in Large-Scale Graph Processing"

External reviewer: José Mairton Barros da Silva Júnior

Abstract: "Graph size growth is outpacing main memory, requiring graphs that do not fit in memory to be stored on denser but slower storage media. As a result, commodity large-scale graph processing often relies on virtual memory paging, leading to severe performance losses.

While non-commodity approaches, including out-of-core methods, can mitigate these losses, they require significant algorithmic modifications and may not be suitable for all graph algorithms. Our goal is to minimize these performance losses while keeping changes to graph algorithms minimal.

To achieve this, I will discuss our characterization of how graph algorithms interact with virtual memory systems and identify key performance bottlenecks. Then, based on our findings, I will introduce our simple yet effective proposal—thread overcommitment—that requires no modifications to the algorithm or virtual memory design. Next, I will introduce our approach for enabling large-scale graph processing on commodity servers using virtual memory with minimal changes to both graph algorithms and virtual memory mechanisms. Unlike conventional approaches, where threads are blocked on page faults, our application/OS co-design allows threads to continue processing while data is asynchronously paged in.

Finally, I will present performance results for both solutions and demonstrate how tailoring paging strategies to application behavior effectively hides page fault latencies.“