Unstructured Tree Search on SIMD Parallel Computers

George Karypis and Vipin Kumar
IEEE Trans. Parallel Distrib. Syst. 5(10): 1057-1072, 1994
Download Paper
In this paper, we present new methods for load balancing
of unstructured tree computations on large-scale SIMD machines,
and analyze the scalability of these and other existing schemes.
An efficient formulation of tree search on a SIMD machine
consists of two major components: (i) a triggering
mechanism, which determines when the search space redistribution
must occur to balance the search space over processors; and (ii) a scheme to
redistribute the search space.
We have devised a new redistribution mechanism and a new triggering
mechanism. Either of these can be used in conjunction with
triggering and redistribution mechanisms developed by other researchers.
We analyze the scalability of these mechanisms, and verify
the results experimentally.
The analysis and experiments show that our new load balancing
methods are highly scalable on SIMD architectures.
Their scalability is shown to be no worse than that of the
best load balancing schemes on MIMD architectures.
We verify our theoretical results by implementing the 15-puzzle problem
on a CM-2 SIMD parallel computer.
A short version of this paper appears in Supercomputing 1992.
Research topics: Parallel processing