Multithreaded Pruned Tree Search
in Distributed Systems
Yaoqing Gao and T. A. Marsland
*
Computing Science Department
University ofAlberta
Edmonton, Canada T6G 2H1
<gaoyq,tony>@cs.ualberta.ca
Abstract
Although eff i cient support for data-parallel applications is relatively well estab-
lished, it remains open how well to support irregular and dynamic problems where
there are no regular data structures and communication patterns. Tree search is central
to solving a variety ofproblems in artif i cial intelligence and an important subset ofthe
irregular applications where tasks are frequently created and terminated. In this paper,
we introduce the design ofa multithreaded distributed runtime system. Eff i ciency and
ease ofparallel programming are the two primary goals. In our system, multithreading
is used to specify the asynchronous behavior in parallel game tree search, and dynamic
load balancing is employed for eff i cient performance.
Keywords: Multithreaded computation, irregular problem, α - β search,
data dependency and dynamic scheduling
1 Introduction
Workstation networks are increasingly prevalent because oftheir versatility and the advan-
tage of high scalability and cost-effectiveness over parallel machines. Many distributed
programming systems such as PVM, P4, MPI, Linda and Express have been built. Most
of them handle only a process-based message-passing paradigm that ably supports data-
parallel applications with regular data structures and communication patterns. But, un-
fortunately, a large proportion of real-word applications are irregular. Pruned search, an
* The research was supported by the Natural Sciences and Engineering Research Council ofCanada.