ABSTRACT

Digital signal processing algorithms are repetitive in nature. These algorithms are described by iterative data flow graph (DFG) where nodes represent tasks and edges represent communication. Execution of all nodes of the DFG once completes iteration. Successive iteration of any node are executive with a time displacement referred to as the iteration period. For all recursive signal processing algorithms, there exists an inherent fundamental lower bound on the iteration period referred to as the iteration period bound or the iteration period. This bound is fundamental to an algorithm and is independent of the implementation architecture. In other words it is impossible to achieve an iteration period less than the bound even when infinite processors are available to execute the recursive algorithm. Iteration bound need to be determined in rate-optimal scheduling of iterative data flow graph. The iteration bound determination has to pre-order repeatedly in the scheduling phase of the high level synthesis. In recursive constrained scheduling a given processing algorithm is scheduled to achieve the minimum iteration period using the given hardware resources. In order to execute operation of the processing algorithm in parallel, the required number of processors or functional units required to execute the operation in parallel may be larger than the number of available resources. Generally the precedence to be assigned is not unique. Hence the iteration bound should be determined for every possible precedence to check which precedence leads to the final schedule with the minimum iteration period. Consequently the iteration bound may have to be computed many times and it is important to determine the iteration bound in minimum possible time.

Keywords: - DSP Algorithms, DFG, Iteration Bound, LPM, MCM.