Designing and implementing a heuristic cross-architecture combination for graph traversal

Yang You, Haohuan Fu, David Bader, Guangwen Yang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Breadth-First Search (BFS) is widely used in real-world applications including computational biology, social networks, and electronic design automation. The most effective BFS approach has been shown to be a combination of top-down and bottom-up approaches. Such hybrid techniques need to identify a switching point which is conventionally found through expensive trial-and-error and exhaustive search routines. We present an adaptive method based on regression analysis that enables dynamic switching at runtime with little overhead. We improve the performance of our method by exploiting popular heterogeneous platforms and efficiently design the approach for a given architecture. A 155× speedup is achieved over the standard top-down approach on GPUs. Our approach is the first to combine top-down and bottom-up across different architectures. Unlike combination on a single architecture, a mistuned switching point may significantly decrease the performance of cross-architecture combination. Our adaptive method can predict the switching point with high accuracy, leading to 7× speedup compared to the switching point in average case (1000 switching points).

Original languageEnglish (US)
Pages (from-to)95-105
Number of pages11
JournalJournal of Parallel and Distributed Computing
StatePublished - Oct 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


  • Combination
  • Cross-architecture optimization
  • Data-intensive
  • Graph algorithm
  • Kepler K20x GPU
  • Knights corner MIC
  • Regression analysis


Dive into the research topics of 'Designing and implementing a heuristic cross-architecture combination for graph traversal'. Together they form a unique fingerprint.

Cite this