Accession Number : ADA265008
Title : Beyond Data Parallelism: The Advantages of Multiple Parallelizations in Combinatorial Search
Descriptive Note : Technical rept.
Corporate Author : ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE
Personal Author(s) : Crowl, Lawrence A ; Crovella, Mark E ; LeBlanc, Thomas J ; Scott, Michael L
Report Date : Apr 1993
Pagination or Media Count : 23
Abstract : Two popular myths concerning parallel programming are: (1) there is a best parallelization for a given application on a given class of machine; and (2) loop-based data parallelism captures all useful parallelizations. We challenge these myths by considering alternative parallelizations of combinatorial search, examining the factors that determine the best-performing option for this important class of problems. Using subgraph isomorphism as a representative search problem, we show how the density of solution space, the number of solutions desired, the number of available processors, and underlying architecture affect the choice of an efficient parallelization. We conclude that there is no one best parallelization that suffices over a range of machines, inputs, and precise problem specifications. As a corollary, we argue that programming environments should not focus exclusively on data parallelism, since parallel tree search or hybrid forms of parallelism may perform better for some applications.
Descriptors : *COMPUTER PROGRAMMING , *PARALLEL PROCESSING , ALGORITHMS , PROBLEM SOLVING , SEARCHING
Subject Categories : Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE