Out-of-Core Parallel Frontier Search with MapReduce

摘要

Applying the MapReduce programming paradigm to frontier search yields simple yet efficient parallel implementations of heuristic search algorithms. We present parallel implementations of Breadth-First Frontier Search (BFFS) and Breadth-First Iterative-Deepening A~* (BF-IDA~*). Both scale well on high-performance systems and clusters. Using the iV-puzzle as an application domain, we found that the scalability of BFFS and BF-IDA~* is limited only by the performance of the I/O system. We generated the complete search space of the 15-puzzle (≈10 trillion states) with BFFS on 128 processors in 66 hours. Our results do not only confirm that the longest solution requires 80 moves [10], but also show how the utility of the Manhattan Distance and Linear Conflicts heuristics deteriorates in hard problems. Single random instances of the 15-puzzle can be solved in just a few seconds with our parallel BF-IDA~*. Using 128 processors, the hardest 15-puzzle problem took seven seconds to solve, while hard random instances of the 24-puzzle still take more than a day of computing time.