UBC Theses and Dissertations
Termination and storage requirements in a model for parallel computations Schnapp, Ivan
This paper deals with a graph-theoretic model for parallel computations as formulated by Karp and Miller. A necessary condition and a sufficient condition for self-termination of loops with unit loop gain are presented. For the special case that W=U the necessary and sufficient condition is derived. A direct procedure for testing termination properties of strongly connected graphs is presented. A method due to Reiter, for determining the maximum storage required for a computation graph, is extended to cover the general case.
Item Citations and Data