Iteration bounds of single-rate data flow graphs for concurrent processing

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³ log n) (n being the number of nodes), memory requirements of O(n ²), and subcritical loops with time complexity O(n³). 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