Parallel Breadth First Search with On-GPU Asynchronous Scheduling

This paper explores the application of an on-GPU thread-data remapping method in evaluating a parallel breadth-first search algorithm, along with a CPU-synchronized queue-based implementation, and their behavior under different workloads. The performance between the on-GPU application and queue-based algorithms were compared against each other. Since graphs can be directed or undirected, performance characteristics were derived from each case, with traversal across directed graphs generally faster. In addition, two approaches to global synchronization were evaluated against each other.