Breadth-First Search (BFS) is widely used in many real-world applications including computational biology, social networks, and electronic design automation. The combination method, using both top-down and bottom-up techniques, is the most effective BFS approach. However, current combination methods rely on trial-and-error and exhaustive search to locate the optimal switching point, which may cause significant runtime overhead. To solve this problem, we design an adaptive method based on regression analysis to predict an optimal switching point for the combination method at runtime within less than 0.1% of the BFS execution time.
Revised: April 23, 2015 |
Published: June 18, 2014
Citation
You Y., S. Song, and D.J. Kerbyson. 2014.An Adaptive Cross-Architecture Combination Method for Graph Traversal. In Proceedings of the 28th ACM international conference on Supercomputing (ICS'14), June 10-13, 2014, Munich, Germany, 169-169. New York, New York:Association for Computing Machinery.PNNL-SA-108310.doi:10.1145/2597652.2600110