When is Graph Reordering an Optimization?

Tuesday September 18, 2018
Location: CIC 4th floor Pather Hollow Conference Room
Time: 4:30PM-5:30PM

Graph Processing applications are notorious for their inefficient use of on-chip cache hierarchy due to an irregular memory access pattern. Real-world input graphs often exhibit structural properties that cause a subset of vertices to be accessed more frequently compared to all the vertices in the graph. Prior work on graph reordering techniques exploit these structural properties of graphs to relabel vertices, effectively changing the data layout of key graph data structures, in order to improve locality of the memory access stream. While many graph reordering techniques have been shown to be effective at reducing the graph application runtime, the reordering step can impose significant overheads; sometimes even causing an increase in end-to-end execution time.

In this talk, we identify lightweight reordering techniques that improve performance even after accounting for the overhead of reordering. We address a limitation of such lightweight reordering techniques – application and input graph dependent speedups – by performing a detailed characterization of the performance benefits from lightweight reordering across two graph benchmark suites using large real-world input graphs. Based on our analysis, we propose selective lightweight graph reordering that performs a low-overhead analysis to determine the structure of an input graph and only reorders graphs that are likely to achieve end-to-end benefit from reordering. Using our selective reordering mechanism, we were able to achieve speedups up to 1.75x while never causing a slowdown beyond 0.1%

Vignesh Balaji is a fourth year PhD student working with Professor Brandon Lucia. His current research interest is in exploring architectural techniques to improve the performance of irregular memory access applications like graph processing. His other research interests include cache coherence protocols and approximate computing.