Accession Number : AD0683393

Title :   THE FLOW GRAPH SCHEMATA MODEL OF PARALLEL COMPUTATION.

Descriptive Note : Doctoral thesis,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC

Personal Author(s) : Slutz,Donald R.

Report Date : SEP 1968

Pagination or Media Count : 254

Abstract : Flow Graph Schemata are introduced as uninterpreted models of parallel algorithms, operating asynchronously and reflecting physical properties inherent to any implementation. Three main topics are investigated: (1) determinacy, (2) equivalence, and (3) equivalence-preserving transformations on the control structure of a Flow Graph Schemata. A model is determinate if the results of a computation depend only on the initial values and not on any timing constraints within the model. Equivalence is undecidable in general, but for a large class of determinate Flow Graph Schemata which are in a maximum parallel form, equivalence is shown decidable. In equivalence-preserving transformations, sufficient tested conditions for equivalence are formulated that depend only on the portion of the structure to be transformed. Current and future computational systems are evaluated in terms of results obtained for Flow Graph Schemata. A number of interesting extensions of the work are suggested.

Descriptors :   (*DIGITAL COMPUTERS, MULTIPLE OPERATION), (*COMPUTER PROGRAMMING, *TIME SHARING), DATA PROCESSING, ALGORITHMS, MATHEMATICAL MODELS, EFFICIENCY, THESES

Subject Categories : Computer Programming and Software
      Computer Hardware
      Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE