
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) equivalencepreserving 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 equivalencepreserving 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