Parallel Search Made Simple

Abstract

. Search in constraint programming is a time consuming task. Search can be speeded up by exploring subtrees of a search tree in parallel. This paper presents distributed search engines that achieve parallelism by distribution across networked computers. The main point of the paper is a simple design of the parallel search engine. Simplicity comes as an immediate consequence of clearly separating search, concurrency, and distribution. The obtained distributed search engines are simple yet o#er substantial speedup on standard network computers. 1 Introduction Search in constraint programming is a time consuming task. Search can be speeded up by exploring several subtrees of a search tree in parallel by cooperating search engines called workers. The paper develops search engines that achieve parallelism by distributing workers across standard networked computers. The paper has two main points. The first point is to provide a simple, high-level, and reusable design for parallel s...