Legality and Other Properties of Graph Models of Computations

Publisher Website
Google Scholar
Abstract
Directed graphs having logical control associated with each vertex have been introduced as models of computational tasks for automatic assignment and sequencing on parallel processor systems. A brief review of their properties is given. A procedure to test the “legality” of graphs in this class is described, and leads to algorithms for counting the number of all possible executions (AND-type subgraphs), and for evaluating the probability of ever reaching a given vertex in the graph. Numerical results are given for some example graphs.