Runahead A*: Speculative Parallelism for A* with Slow Expansions.

A * suffers from limited parallelism. The maximum level of traditional parallelism in A * is the same as the degree of the search graph nodes, which is too small in many applications. As such, A * cannot fully leverage the multithreading capabilities of modern processors. In this paper, we go beyond traditional parallelism and introduce speculative parallelism for A *. We observe that A *'s node expansions exhibit predictable patterns in applications like path planning. Based on this observation, we propose Runahead A * ( RA* ). When a node is being expanded, RA* predicts future likely-to-be-expanded nodes, performs their corresponding computation on separate threads, and memoizes the computation results. Later when a predicted node is selected for expansion, rather than performing its computation, the memoized results are used, saving significant time in slow-expansion applications. We study five applications of A* . We show that when its prediction accuracy is high, RA * offers significant speedup over vanilla A * for slow-expansion applications. With 16 threads, RA *'s speedup for such applications ranges from 3.1× to 14.1×. We also study and provide insight into when, why, and to what extent node expansions are predictable. We provide an implementation of RA * at: https://github.com/cmu-roboarch/runahead-astar/