Optimum and sub-optimum scheduling of DSP algorithms

Abstract:  Abstract The author applies both heuristic and optimum (B&B) approaches to schedule DSP algorithms. Heuristic approach can produce a nearly optimal schedule in most of the cases. But, the effectiveness of different heuristic rules on scheduling of a given algorithm cannot be predicted in advance of the solution. Thus, it is advisable and economically practical to employ several heuristic rules schedulings and then choose the schedule that comes closest to meet desired completion time. However, it can not be claimed that the optimum schedule is obtainable by these methods. For optimum scheduling a branch and bound algorithm is used. This algorithm could efficiently find optimal solutions for the simple structures tested. As complex DSP algorithms usually are composed of simpler blocks, this approach can be used to schedule these blocks if the timing of the algorithm is critical