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

Report Date:

1993-04-01

Pagination or Media Count:

23.0

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.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE