Premium
MR‐search: massively parallel heuristic search
Author(s) -
Schütt Thorsten,
Reinefeld Alexander,
Maier Robert
Publication year - 2013
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.1833
Subject(s) - computer science , massively parallel , parallel computing , heuristics , iterative deepening depth first search , beam search , heuristic , incremental heuristic search , search algorithm , distributed computing , algorithm , artificial intelligence , operating system
SUMMARY MR‐Search is a framework for massively parallel heuristic search. Based on the MapReduce paradigm, it efficiently utilizes all available resources: processors, memories, and disks. MR‐Search uses OpenMP on shared memory systems, Message Passing Interface on clusters with distributed memory, and a combination of both on clusters with multi‐core processors. Large graphs that do not fit into the main memory can be efficiently processed with an out‐of‐core variant. We implemented two node expansion strategies in MR‐Search: breadth‐first frontier search and breadth‐first iterative deepening A*. With breadth‐first frontier search, we computed large and powerful table‐driven heuristics, so‐called pattern databases that exceed the main memory capacity. These pattern databases were then used to solve random instances of the 24‐puzzle with breadth‐first iterative deepening A* on systems with up to 4093 processor cores. MR‐Search is conceptually simple. It takes care of data partitioning, process scheduling, out‐of‐core data merging, communication, and synchronization. Application developers benefit from the parallel computational capacity without having the burden of implementing parallel application code. Copyright © 2011 John Wiley & Sons, Ltd.