Open Collections

UBC Theses and Dissertations

UBC Theses Logo
Featured Collection

UBC Theses and Dissertations

Termination and storage requirements in a model for parallel computations Schnapp, Ivan

Abstract

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 Metadata

Title
Termination and storage requirements in a model for parallel computations
Creator
Schnapp, Ivan
Publisher
University of British Columbia
Date Issued
1970
Description
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.
Genre
Thesis/Dissertation
Type
Text
Language
eng
Date Available
2011-05-17
Provider
Vancouver : University of British Columbia Library
Rights
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
DOI
10.14288/1.0102044
URI
http://hdl.handle.net/2429/34610
Degree
Master of Applied Science - MASc
Program
Electrical and Computer Engineering
Affiliation
Applied Science, Faculty of; Electrical and Computer Engineering, Department of
Degree Grantor
University of British Columbia
Campus
UBCV
Scholarly Level
Graduate
Aggregated Source Repository
DSpace

Item Media

Item Citations and Data

Rights

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.