Designing a heuristic cross-architecture combination for breadth-first search

Yang You, David Bader, Maryam Mehri Dehnavi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 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. An 155x 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 an 695x speedup compared the worst switching point.

Original languageEnglish (US)
Title of host publicationProceedings - 43rd International Conference on Parallel Processing, ICPP 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages10
ISBN (Electronic)9781479956180
StatePublished - Nov 13 2014
Externally publishedYes
Event43rd International Conference on Parallel Processing, ICPP 2014 - Minneapolis, United States
Duration: Sep 9 2014Sep 12 2014

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918


Conference43rd International Conference on Parallel Processing, ICPP 2014
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics
  • Hardware and Architecture


  • Combination
  • Cross-architecture Optimization
  • Data-intensive
  • Graph Algorithm
  • Kepler K20x GPU
  • Knights Corner MIC
  • Regression Analysis


Dive into the research topics of 'Designing a heuristic cross-architecture combination for breadth-first search'. Together they form a unique fingerprint.

Cite this