Computation Graphs

Computation graphs are a model of parallel computation similar to Process Networks. It is represented by a finite graph with a set of nodes, each associated with a function, a set of arcs , where a branch is a queue of data directed from one node to another. Four non-negative integers (A, U, W and T) are associated with each arc. 'A' is the number of tokens initially present in the arc, U is the number of tokens produced by the function associated with the node, W is the number of tokens consumed by the function associated with the node, T is a threshold that specifies the number of tokens that must be present in the arc before the function can be fired (obviously, T>=W).

Questions of termination and boundness are solvable for Computation Graphs, which turn out to be a restricted version of PN. It is interesting to note that Synchronous Dataflow Networks is a special case of Computation Graphs where T=W for all arcs.

2004-10-18