A STUDY OF A MODEL FOR PARALLEL COMPUTATIONS.
Abstract
The report deals with a model for parallel computations as formulated by Karp and Miller. A computation is viewed as a directed graph(computation graph) in which a node represents an operation to be performed upon data on the node input branches with the results of this operation being placed upon the output branches. An integer linear program is given for the determination of the maximum storage required by a computation graph G. The concept is introduced of an admissible schedule defining valid node initiation times. A maximal computation rate 'quasi periodic' schedule is given for the case that G is required to compute synchronously, i.e. at integer times. Finally, for more general computation graphs, an analysis of the so-called free admissible schedule is given. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1968
- Accession Number
- AD0678957
Entities
People
- Raymond Reiter
Organizations
- University of Michigan