Scheduling and Allocation of Non-Manifest Loops on Hardware Graph-Models

O. Mansour, Sandro Etalle, Th. Krol

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

    32 Downloads (Pure)

    Abstract

    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 dependant 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) a-priori 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 languageUndefined
    Title of host publication2nd PROGRESS workshop on Embedded Systems
    EditorsF. Karelse
    Place of PublicationUtrecht, The Netherlands
    PublisherSTW
    Pages153-160
    Number of pages8
    ISBN (Print)90-73461-26-X
    Publication statusPublished - Oct 2001
    Event2nd PROGRESS Workshop on Embedded Systems 2001 - Veldhoven, Netherlands
    Duration: 18 Oct 200118 Oct 2001
    Conference number: 2

    Publication series

    Name
    PublisherSTW Technology Foundation

    Workshop

    Workshop2nd PROGRESS Workshop on Embedded Systems 2001
    Abbreviated titlePROGRESS
    CountryNetherlands
    CityVeldhoven
    Period18/10/0118/10/01

    Keywords

    • EWI-957
    • periodic loops
    • Non-manifest loop scheduling
    • dynamic hardware scheduling
    • IR-36875
    • METIS-203304

    Cite this

    Mansour, O., Etalle, S., & Krol, T. (2001). Scheduling and Allocation of Non-Manifest Loops on Hardware Graph-Models. In F. Karelse (Ed.), 2nd PROGRESS workshop on Embedded Systems (pp. 153-160). Utrecht, The Netherlands: STW.