Book chapter
Automatic data decomposition for message-passing machines
Languages and Compilers for Parallel Computing, pp.64-78
Lecture Notes in Computer Science, Springer Berlin Heidelberg
06/09/2005
DOI: 10.1007/BFb0032684
Abstract
The data distribution problem is very complex, because it involves trade-off decisions between minimizing communication and maximizing parallelism. A common approach towards solving this problem is to break the data mapping into two stages: an alignment stage and a distribution stage. The alignment stage attempts to increase parallelism, while the distribution stage attempts to decrease communication overhead. As opposed to previous approaches, we consider the alignment and distribution problems in a unified framework, and attempt to simultaneously maximize parallelism and minimize communication overhead. The problem becomes harder if dynamic remapping, multi-dimensional distributions, array replications and control flow are taken into account. This paper formulates the full data decomposition problem that addresses all these issues and presents a simple new algorithm to find the optimal solution of the dynamic data distribution problem, given the number of processors and a partitioning of the input program into phases. The algorithm runs efficiently for small search spaces (several hundreds of data distributions).
Details
- Title: Subtitle
- Automatic data decomposition for message-passing machines
- Creators
- Mirela Damian-Iordache - University of IowaSriram V. Pemmaraju - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- Languages and Compilers for Parallel Computing, pp.64-78
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/BFb0032684
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 06/09/2005
- Academic Unit
- Computer Science
- Record Identifier
- 9984259410202771
Metrics
27 Record Views