Optimizing Communication by Compression for Multi-GPU Scalable Breadth-First Searches

The Breadth First Search (BFS) algorithm is the foundation and building block of many higher graph-based operations such as spanning trees, shortest paths and betweenness centrality. The importance of this algorithm increases each day due to it is a key requirement for many data structures which are becoming popular nowadays. When the BFS algorithm is parallelized by distributing the graph between several processors the interconnection network limits the performance. Hence, improvements on this area may benefit the overall performance of the algorithm. This work presents an alternative compression scheme for communications in distributed BFS processing. It focuses on BFS processors using General-Purpose Graphics Processing Units.

• Publication year

  2017

• Venue

  arXiv.org

• Publication date

  2017-04-03

• Fields of study

  Computer Science, Engineering

• Identifiers
  arXiv 1704.00513
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Web Information Systems Engineering

  2019cited by this paper
• High Performance Computing

  2016cited by this paper
• fitdistrplus: An R Package for Fitting Distributions

  2015cited by this paper
• Dynamic parallelism for simple and efficient GPU graph algorithms

  2015cited by this paper
• Compressing Inverted Index Using Optimal FastPFOR

  2015cited by this paper
• Accelerating an MPI Lattice Boltzmann code using OpenACC

  2015cited by this paper
• The Endgame for Moore's Law: Architecture, Algorithm, and Application Challenges.

  2015influential reference
• Enterprise: breadth-first graph traversal on GPUs

  2015cited by this paper
• Revisiting Clustered Microarchitecture for Future Superscalar Cores

  2015cited by this paper
• Gunrock: a high-performance graph processing library on the GPU

  2015cited by this paper
• MapGraph: A High Level API for Fast Development of High Performance Graph Analytics on GPUs

  2014cited by this paper
• SIMD compression and the intersection of sorted integers

  2014influential reference
• On Inverted Index Compression for Search Engine Efficiency

  2014cited by this paper
• Optimizing Collective Operations in Hybrid Applications

  2014cited by this paper
• GPU-Aware Intranode MPI_Allreduce

  2014cited by this paper
• NUMA-optimized parallel breadth-first search on multicore single-node system

  2013cited by this paper
• Parallel distributed breadth first search on GPU

  2013influential reference
• Distributed Memory Breadth-First Search Revisited: Enabling Bottom-Up Search

  2013cited by this paper
• Decoding billions of integers per second through vectorization

  2012influential reference
• Compression and Sieve: Reducing Communication in Parallel Breadth First Search on Distributed Memory Systems

  2012influential reference
• Too much PIE is bad for performance

  2012cited by this paper
• Breaking the speed and scalability Barriers for Graph exploration on distributed-memory machines

  2012cited by this paper
• Searching web data: An entity retrieval and high-performance indexing model

  2012cited by this paper
• A quantitative study of irregular programs on GPUs

  2012cited by this paper
• Highly scalable graph search for the Graph500 benchmark

  2012cited by this paper
• Scalable GPU graph traversal

  2012cited by this paper
• SIMD-based decoding of posting lists

  2011cited by this paper
• An in-depth analysis of stochastic Kronecker graphs

  2011cited by this paper
• Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units

  2011influential reference
• Computer Architecture, Fifth Edition: A Quantitative Approach

  2011cited by this paper
• Searching for a Parent Instead of Fighting Over Children : A Fast Breadth-First Search Implementation for Graph 500

  2011cited by this paper
• Index compression using 64-bit words

  2010influential reference
• Inverted index compression and query processing with optimized document ordering

  2009influential reference
• Compressing term positions in web indexes

  2009cited by this paper
• The exponential complexity of satisfiability problems

  2009cited by this paper
• Challenges in building large-scale information retrieval systems: invited talk

  2009cited by this paper
• Performance of compressed inverted list caching in search engines

  2008cited by this paper
• Adaptive Tuple Differential Coding

  2007cited by this paper
• zipfR: Word Frequency Modeling in R

  2007cited by this paper
• A Mathematical Theory of Communication

  2006influential reference
• Super-Scalar RAM-CPU Cache Compression

  2006influential reference
• Blue Gene/L torus interconnection network

  2005cited by this paper
• A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L

  2005cited by this paper
• Optimization of Collective Communication Operations in MPICH

  2005cited by this paper
• Compressing Inverted Files

  2004cited by this paper
• Inverted Index Compression Using Word-Aligned Binary Codes

  2004influential reference
• Interprocedural optimizations for improving data cache performance of array-sensitive embedded applications

  2003cited by this paper
• Compression of inverted indexes For fast query evaluation

  2002cited by this paper
• Managing gigabytes (2nd ed.): compressing and indexing documents and images

  1999cited by this paper
• Compressing and indexing documents and images

  1999cited by this paper
• Cramming More Components Onto Integrated Circuits

  1998cited by this paper
• Inverted files versus signature files for text indexing

  1998cited by this paper
• Compressing relations and indexes

  1998influential reference
• Block-Oriented Compression Techniques for Large Statistical Databases

  1997cited by this paper
• [서평]「Computer Organization and Design, The Hardware/Software Interface」

  1997influential reference
• Design patterns: elements of reuseable object-oriented software

  1994influential reference
• First draft of a report on the EDVAC

  1993cited by this paper
• Structured Computer Organization

  1976cited by this paper
• On Computable Numbers, with an Application to the Entscheidungsproblem.

  1937cited by this paper

• Optimizing communication for a 2D-partitioned scalable BFS

  2016influential citation