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


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a265008.pdf


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