A Closer Look at Lightweight Graph Reordering. Graph analytics power a range of applications in areas as diverse as finance, networking and business logistics. A common property of graphs used in the domain of graph analytics is a powerlaw distribution of vertex connectivity, wherein a small number of vertices are responsible for a high fraction of all connections in the graph. These richlyconnected (hot) vertices inherently exhibit high reuse. However, their sparse distribution in memory leads to a severe underutilization of onchip cache capacity. Prior works have proposed lightweight skewaware vertex reordering that places hot vertices adjacent to each other in memory, reducing the cache footprint of hot vertices. However, in doing so, they may inadvertently destroy the inherent community structure within the graph, which may negate the performance gains achieved from the reduced footprint of hot vertices. In this work, we study existing reordering techniques and demonstrate the inherent tension between reducing the cache footprint of hot vertices and preserving original graph structure. We quantify the potential performance loss due to disruption in graph structure for different graph datasets. We further show that reordering techniques that employ finegrain reordering significantly increase misses in the higher level caches, even when they reduce misses in the lastlevel cache. To overcome the limitations of existing reordering techniques, we propose DegreeBased Grouping (DBG), a novel lightweight reordering technique that employs a coarsegrain reordering to largely preserve graph structure while reducing the cache footprint of hot vertices. Our evaluation on 40 combinations of various graph applications and datasets shows that, compared to a baseline with no reordering, DBG yields an average application speedup of 16.8% vs 11.6% for the bestperforming existing lightweight technique.

Optimizing Ordered Graph Algorithms with GraphIt. Many graph problems can be solved using ordered parallel graph algorithms that achieve significant speedup over their unordered counterparts by reducing redundant work. This paper introduces a new prioritybased extension to GraphIt, a domainspecific language for writing graph applications, to simplify writing highperformance parallel ordered graph algorithms. The extension enables vertices to be processed in a dynamic order while hiding lowlevel implementation details from the user. We extend the compiler with new program analyses, transformations, and code generation to produce fast implementations of ordered parallel graph algorithms. We also introduce bucket fusion, a new performance optimization that fuses together different rounds of ordered algorithms to reduce synchronization overhead, resulting in 1.2times3times speedup over the fastest existing ordered algorithm implementations on road networks with large diameters. With the extension, GraphIt achieves up to 3times speedup on six ordered graph algorithms over stateoftheart frameworks and handoptimized implementations (Julienne, Galois, and GAPBS) that support ordered algorithms.