© 2002 by British Computer Society
Optimal Scheduling of Digital Signal Processing Data-flow Graphs using Shortest-path Algorithms
1 Department of Computer and Internet Engineering, P.O. Box 3030, Jordan University of Science and Technology, Irbid 22110, Jordan Email: ali@just.edu.jo 2 Department of Electrical and Computer Engineering, Concordia University, Montreal, Quebec, Canada H3G 1M8
This paper introduces a novel technique to obtain a schedule for a cyclic data-flow graph (DFG) onto a multiprocessor system. The optimality criteria considered in this scheduling technique are the maximum throughput, minimum input–output (I/O) delay, and minimum hardware resources. In this technique, an all-pair longest path algorithm is used to evaluate the relative firing times of the nodes of the given DFG. The proposed technique for finding these times is quite simple to implement and it has lower time complexity than all the previously proposed techniques. The technique is tested on various benchmark problems to demonstrate its optimal performance. All the optimality criteria are achieved on all the tested benchmarks. However, finding a minimum hardware resource schedule is an NP complete problem, and thus cannot be theoretically ensured. A formal proof of achieving both the throughput and the I/O delay optimality simultaneously is given, and an efficient technique to ensure this is also presented. This technique is quite simple and can be used to ensure delay optimality in any scheduling technique.