학술논문

When is Graph Reordering an Optimization? Studying the Effect of Lightweight Graph Reordering Across Applications and Input Graphs
Document Type
Conference
Source
2018 IEEE International Symposium on Workload Characterization (IISWC) Workload Characterization (IISWC), 2018 IEEE International Symposium on. :203-214 Sep, 2018
Subject
Computing and Processing
Arrays
Sorting
Layout
Rabbits
Program processors
Kernel
Language
Abstract
Graph processing applications are notorious for exhibiting poor cache locality due to an irregular memory access pattern. However, prior work on graph reordering has observed that the structural properties of real-world input graphs can be exploited to improve locality of graph applications. While sophisticated graph reordering techniques are effective at reducing the graph application runtime, the reordering step imposes significant overheads leading to a net increase in end-to-end execution time. The high overhead of sophisticated reordering techniques renders them inapplicable in many important use cases wherein the input graph is processed only a few times and, hence, cannot amortize the overhead of reordering. In this work, we identify lightweight reordering techniques that improve performance even after accounting for the overhead of reordering. We first conduct a detailed performance evaluation of these lightweight reordering techniques across a range of applications to identify the characteristics of applications that benefit the most from lightweight reordering. Next, we address a major impediment to the general adoption of these reordering techniques - input-dependent speedups – by linking the speedup from lightweight reordering to structural properties of the input graph. We leverage the structure dependence of speedup to propose a low-overhead mechanism to determine whether a given input graph would benefit from reordering. Using our selective lightweight reordering, we show maximum end-to-end speedup of up to 1.75x and never cause a slowdown beyond 0.1%.