In this paper we address the problem of scheduling non-manifest data dependant periodic loops for high throughput DSP-applications based on a streaming data model. In contrast to manifest loops, non-manifest data dependent loops are loops where the number of iterations needed in order to perform a calculation is data dependant and hence not known at compile time. For the case of manifest loops, static scheduling techniques have been devised which produce near optimal schedules . Due to the lack of exact run-time execution knowledge of non-manifest loops, these static scheduling techniques are not suitable for tackling scheduling problems of DSP-algorithms with non-manifest loops embedded in them. We consider the case where (a) apriori knowledge of the data distribution, and (b) worst case execution time of the non-manifest loop are known and a constraint on the total execution time has been given. Under these conditions dynamic schedules of the non-manifest data dependant loops within the DSP-algorithm are possible. We show how to construct hardware which dynamically schedules these non-manifest loops. The sliding window execution, which is the execution of a non-manifest loop when the data streams through it, of the constructed hardware will guarantee real time performance for the worst case situation. This is the situation when each non-manifest loop requires its maximum number of iterations.
|Title of host publication||Proceedings 2nd PROGRESS Workshop on Embedded Systems (Utrecht, The Netherlands, October 18, 2001)|
|Publisher||STW Technology Foundation|
|Publication status||Published - 2001|
Mansour, O., Etalle, S., & Krol, T. (2001). Scheduling and allocation of non-manifest loops on hardware graph-models. In F. Karelse (Ed.), Proceedings 2nd PROGRESS Workshop on Embedded Systems (Utrecht, The Netherlands, October 18, 2001) (pp. 153-160). STW Technology Foundation.