Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing

摘要: This paper gives a graph-theoretic model for the description and analysis of parallel computations. Within model, computation steps correspond to nodes graph, dependency between is represented by branches with which queues data are associated. First, it shown that each such graphGrepresents unique computation, determined independently operation times. Next, methods determining whether terminates finding number performances step developed. The maximal strongly connected subgraphs G loops within these play aooutnal role in this analysis. For example, use made result either every snbgroph performed an infinite times, or none is. Finally, necessary sufficient conditions lengths remain bounded derived.