Parallel and concurrent search for fast AND/OR tree search on multicore processors

This paper proposes a fast AND/OR tree search algorithm using a multiple paths parallel and concurrent search scheme for embedded multicore processors. Currently, not only PCs or supercomputers but also information appliances such as game consoles, mobile devices and car navigation systems are equipped with multicore processors for better cost performance and lower power consumption. However, the number of processor cores and the amount of memories in embedded multicore processors are limited for lowering power consumption and chip costs. Development of parallel application programs on embedded multicore processors requires exploitation of parallelism and effective utilization of small memories. The proposed algorithm allows us to search in parallel many paths including lowly evaluated nodes and paths including highly evaluated nodes. The algorithm also uses depth-first search, working on small memories. The proposed algorithm is applied for a tsume-shogi (Japanese chess problem) solver as a typical AND/OR tree search problem on an embedded multicore processor system, NEC Electronics NaviEngine with four ARM processor cores. Evaluation results for 100 problems show that the proposed algorithm executed on two processor cores is 2.36 times faster, and executed on four processor cores is 4.17 times faster than the sequential algorithm on the average.