Optimizing Data Supply and Memory Management for Graph Applications in Post-Moore Hardware-Software Systems

Abstract

Graph structures naturally and efficiently capture relationships between entities, such as individuals in a social network, pages in the World Wide Web, and amino acids in protein molecules. However, despite the advances in computing over the past few decades, graph processing algorithms continue to pose data supply challenges for current hardware. Modern networks are sparse and evergrowing, and therefore many graph applications are characterized by irregular memory access patterns that trouble data supply and memory management schemes. As a result, these applications are severely bottlenecked by several long-latency memory accesses to off-chip memory. My dissertation aims to tackle these bottlenecks with three main thrusts. First, this dissertation offers a hardware-software co-design that pairs automated compiler techniques to slice programs along bottleneck memory accesses with modest architectural modifications. This approach, GraphAttack, achieves a 2.9x speedup and 8.6x gain in energy efficiency over modern latency tolerance approaches. Second, this dissertation proposes tailored cache management policies supported with flexible hardware to improve memory bandwidth pressure and minimize off-chip memory accesses. This domain-specific memory hierarchy approach, Graphfire, yields a 1.3x speedup over state-of-the-art cache management policies and 63.3x speedup when scaling up to 64 cores. Third, this dissertation introduces architectural support for operating system (OS) techniques to efficiently identify data worth backing with huge pages and alleviate significant address translation overheads that occur in irregular applications. This results in 1.2-1.4x speedups over base pages alone when backing only 1-4% of the application footprint with huge pages. The end of Moore’s Law has pushed computer architects to design and develop hardware and software to accelerate compute and aim for aggressive power and performance targets. However, data supply remains a challenge, particularly for memory-bound graph applications. Embracing hardware-software co-designs, my dissertation attacks the memory bottlenecks in graph processing workloads from multiple perspectives of the hardware-software stack to enable optimal performance. The techniques presented demonstrate the need to design properly equipped in-order technology and provide a path forward for tailored memory management for irregular applications in order to target a world where energy savings are critical for performance and scalability.