Match and Move, an Approach to Data Parallel Computing
Abstract
The match operation, introduced by G. Sabot, is a parallel primitive describing a communication pattern. For two vectors of keys, called the 'source' and 'destination,' a path is indicated for each element of the source to each destination element having an equal key. The result of the match operation is a data structure called a 'mapping' encapsulating these paths. A move operation sends data from the sites of a source data vector through the paths of the mapping to a destination data vector. If the mapping is many-to-one, a combining function, such as add, max or min, specifies how collisions are resolved at the destination sites. The match and move operations provide a unified set of parallel primitives that at once satisfy the conflicting demands of generality and efficiency. This dissertation illustrates the generality of the approach by showing many algorithms implemented with match, focusing on algorithms for graphs, sparse matrices, and binary tree structures. These types of problems are characterized as involving dynamic structural change, and are typically difficult to implement on parallel architectures. By using the framework allowed by the match operation, the algorithms are straightforward and simple to understand. Because match and move may be implemented efficiently on many different parallel and vector architectures, algorithms expressed in this manner achieve architecture independence. In addition, because there are many implementation strategies for the operators available for a given machine, they provide a level of implementation independence. This level of abstraction is supported without sacrificing absolute performance however.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1992
- Accession Number
- ADA259915
Entities
People
- Thomas J. Sheffler
Organizations
- Carnegie Mellon University