Scheduling and allocation of non-manifest loops on hardware graph-models

O. Mansour, S. Etalle, T. Krol

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

Abstract

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 [1]. 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.
Original languageEnglish
Title of host publicationProceedings 2nd PROGRESS Workshop on Embedded Systems (Utrecht, The Netherlands, October 18, 2001)
EditorsF. Karelse
PublisherSTW Technology Foundation
Pages153-160
ISBN (Print)90-73461-26-X
Publication statusPublished - 2001

Fingerprint Dive into the research topics of 'Scheduling and allocation of non-manifest loops on hardware graph-models'. Together they form a unique fingerprint.

  • Cite this

    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.