Rabbit Order: Just-in-Time Parallel Reordering for Fast Graph Analysis
Authors:
- Junya AraiJAJunya Arai
- Hiroaki ShiokawaHSHiroaki Shiokawa
- Takeshi YamamuroTYTakeshi Yamamuro
- Makoto OnizukaMOMakoto Onizuka
- Sotetsu IwamuraSISotetsu Iwamura
- 1 May 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15302075,p. 22-31
Abstract
Ahead-of-time data layout optimization by vertex reordering is a widely used technique to improve memory access locality in graph analysis. While reordered graphs yield better analysis performance, the existing reordering algorithms use significant amounts of computation time to provide efficient vertex ordering, hence, they fail to reduce end-to-end processing time. This paper presents a first algorithm for just-in-time parallel reordering, named Rabbit Order. It reduces end-to-end runtime by achieving high locality and fast reordering at the same time through two approaches. The first approach is hierarchical community-based ordering, which exploits the locality derived from hierarchical community structures in real-world graphs. Our ordering fully leverages low-latency cache levels by mapping hierarchical communities into hierarchical caches. The second approach is parallel incremental aggregation, which improves the runtime efficiency of reordering by decreasing the number of vertices to be processed. In addition, this approach utilizes lightweight atomic operations for concurrency control to avoid locking overheads and achieve high scalability. Our experiments show that Rabbit Order significantly outperforms state-of-the-art reordering algorithms.Keywords
This publication has 26 references indexed in Scilit:
- SlashBurn: Graph Compression and Mining beyond Caveman CommunitiesIEEE Transactions on Knowledge and Data Engineering, 2014
- Hypergraph Partitioning Based Models and Methods for Exploiting Cache Locality in Sparse Matrix-Vector MultiplicationSIAM Journal on Scientific Computing, 2013
- Social Based Layouts for the Increase of Locality in Graph OperationsLecture Notes in Computer Science, 2011
- Optimization of sparse matrix–vector multiplication on emerging multicore platformsParallel Computing, 2009
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Near linear time algorithm to detect community structures in large-scale networksPhysical Review E, 2007
- CHALLENGES IN PARALLEL GRAPH PROCESSINGParallel Processing Letters, 2007
- A Reordering for the PageRank ProblemSIAM Journal on Scientific Computing, 2006
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- Nested Dissection of a Regular Finite Element MeshSIAM Journal on Numerical Analysis, 1973