ITERATION BOUNDS OF SINGLE-BATE DATA-FLOW GRAPHS FOR CONCURRENT PROCESSING

Single-rate data flow graphs (DFGs) [1], [13] are often used for model ing iterative concurrent activities. A DFG and its iteration bound are equivalent to a marked graph and cycle time of a Petri net, respectiv ely. Ramamoorthy and Ho [25] developed an efficient algorithm for chec king the minimum cycle time against a predetermined performance requir ement. This work presents a systematic procedure to find the iteration bound [2], [15], [24], [26] and the critical loop with time complexit y O(n(3) log n) (n being the number of nodes), memory requirements of O(n(2)), and subcritical loops with time complexity O(n(3)). The next- critical loops are also studied because they may become the new critic al loop if the look-ahead technique [24] is used. The above procedure has been implemented in the C programming language which interfaces wi th our Petri net X-window tool to display the performance results.