Iteration bounds of single-rate data flow graphs for concurrent processing
Daniel Yuh Chao, D.T. Wang · IEEE Transactions on Circuits and Systems I Fundamental Theory and Applications · 1993
Single-rate data flow graphs (DFGs) are often used for modeling iterative concurrent activities. A DFG and its iteration bound are equivalent to a marked graph and cycle time of a Petri net, respectively. Ramamoorthy and Ho (1980) developed an efficient algorithm for checking the minimum cycle time against a predetermined performance requirement. This work presents a systematic procedure to find the iteration bound and the critical loop with time complexity O(n/sup 3/ log n) (n being the number of nodes), memory requirements of O(n/sup 2/), and subcritical loops with time complexity O(n/sup 3/). The next-critical loops are also studied because they may become the new critical loop if the look-ahead technique is used. The above procedure has been implemented in the C programming language which interfaces with a Petri net X-window tool to display the performance results.>