Accession Number : AD0678957

Title :   A STUDY OF A MODEL FOR PARALLEL COMPUTATIONS.

Descriptive Note : Report for Oct 64-Jun 67,

Corporate Author : MICHIGAN UNIV ANN ARBOR SYSTEMS ENGINEERING LAB

Personal Author(s) : Reiter,Raymond

Report Date : NOV 1968

Pagination or Media Count : 200

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)

Descriptors :   (*DATA PROCESSING, MULTIPLE OPERATION), (*COMPUTER PROGRAMMING, MULTIPLE OPERATION), DATA STORAGE SYSTEMS, LINEAR PROGRAMMING, MATHEMATICAL MODELS, SCHEDULING, AUTOMATA, GRAPHICS, THESES

Subject Categories : Computer Programming and Software
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE