A NEW REDUCTION APPROACH FOR MULTIRATE DATA-FLOW GRAPH

摘要

The iteration bound (IB) of a multirate data-flow graph (MRDFG) N can be determined by considering the equivalent single-rate data-flow graph (SRDFG) N' of N. Ito et al. proposed a novel algorithm to remove node/edge redundancies taking extra time and memory, and in the worst case, no reduction may be available. Furthermore, it is unclear how to schedule removed nodes and discover phenomena of SRDFG-equivalence - as in our earlier paper without node/edge redundancies - and loop-combination under specific markings. We explain and explore the condition for loop-combination by illustrating simple cases without transformation. Rather than duplicating and removing redundant nodes/edges individually, we reduce them in a loop-wise fashion (reduce the nodes/edges in a loop as a whole) with fewer nodes/edges. We further fold several duplicated loops of the same loop into a single one; thus reducing more nodes/edges - not possible using Ito el al.'s approach. We break the WMG into a number of loop-combination-free islands and duplicate each island a number of times. Each transition t' in the duplicated island represents some consecutive executions of the same transition t in the original WMG; thus each kth execution of t can be scheduled avoiding the scheduling deficiency suffered in the approach by Ito et al. If two consecutive executions of t is represented by the same t' in one island Π{sub}i but different t' in another island Π{sub}j, then we say the two islands are incompatible - fixed by expanding t' in Π{sub}i into two transitions with an intermediate place. Further reducing the computation time, we compute the final IB to be the maximal among iteration bounds of all islands with a time complexity faster by a factor of f{sup}2 where/is the average number of islands.