Lawrence A. Crowl, Mark E. Crovella, Thomas J. LeBlanc, and Michael L. Scott, "Beyond Data Parallelism: The Advantages of Multiple Parallelizations in Combinatorial Search", Technical Report 92-80-06, Department of Computer Science, Oregon State University, Corvallis, Oregon, 97331-3202, December 1992
In this paper we consider alternative schemes for parallelizing combinatorial search, and examine the factors that influence the choice of parallelization for this important class of problems. Using subgraph isomorphism as a representative search problem, we show how the density of the solution space, the number of solutions desired, the number of available processors, and the underlying architecture affect the choice of an efficient parallelization. Our experiments, which span seven different shared-memory machines, eight parallelizations of the subgraph isomorphism algorithm, and a wide range of input graphs, show that there is no best parallelization for this problem: relative performance depends on each of these factors. In particular, on some machines and for some inputs, a sequential depth-first search of the solution space, applying data parallelism at each node in the search tree, performs best. On other machines or other inputs, parallel tree search, with no data parallelism, performs best. In still other cases, a hybrid solution, containing both parallel tree search and data parallelism works best. From these experiences we conclude that multiple parallelizations of a single algorithm may be needed to achieve the best performance over a range of machines, inputs, and problem demands, and that hybrid forms of parallelization (where data parallelism and tree parallelism are used in tandem) are needed in some applications.