Stack splitting: A technique for efficient exploitation of search parallelism on share-nothing platforms

We study the problem of exploiting parallelism from search-based AI systems on share-nothing platforms, i.e., platforms where different machines do not have access to any form of shared memory. We propose a novel environment representation technique, called stack-splitting, which is a modification of the well-known stack-copying technique, that enables the efficient exploitation of or-parallelism from AI systems on distributed-memory machines. Stack-splitting, coupled with appropriate scheduling strategies, leads to reduced communication during distributed execution and effective distribution of larger grain-sized work to processors. The novel technique can also be implemented on shared-memory machines and it is quite competitive. In this paper we present a distributed implementation of or-parallelism based on stack-splitting including results. Our results suggest that stack-splitting is an effective technique for obtaining high performance parallel AI systems on shared-memory as well as distributed-memory multiprocessors.