Beyond Data Parallelism: The Advantages of Multiple Parallelizations in Combinatorial Search
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1993
- Accession Number
- ADA265008
Entities
People
- Lawrence A. Crowl
- Mark E. Crovella
- Michael L. Scott
- Thomas J. Leblanc
Organizations
- University of Rochester