The partitioning of QSDF computation graphs (Q1117692)

In a previous paper the quasi synchronous data flow (QSDF) model of computation was presented. A data flow graph is partitioned into disjoint directed paths, called computation paths, with the object of permitting a processor to execute along such a path in a sequential manner as far as possible. Such sequential execution will be facilitated to the extent that each operator along the path, when encountered by the executing processor, will have been supplied with any operand(s) it may require from nodes on other computation paths. If such is found not to be the case, execution of the path must be suspended and will be resumed at such time as the operand arrives. In this paper, the question of how best to effect such a partition is addressed. A definition of optimality under the QSDF execution discipline is obtained and a closed form for the value of the cardinality of the partition is derived. An algorithm for obtaining an optimal partition is presented and some properties of the resulting partition are examinend. Only static program behavior is considered in the analysis.