Minimum waste scheduling of dynamic variable-latency and non-manifest fuctional units

O. Mansour, Egbert Molenkamp, Th. Krol

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    101 Downloads (Pure)


    In this paper we address the problem of scheduling algorithms embodied with a mixture of nonmanifest-loops [1], variable-latency and fixed-latency units [2], [3] for high throughput DSP-applications. Nonmanifest loops are loops where the number of iterations needed for a calculation is data dependent and hence not known at compile time. The body of a non-manifest loop can either have fixed-latency or variable-latency. Variable latency units are hardware execution units, that will complete a given operation after a variable quantity of clock cycles. When designing an Application Specific Processor for high throughput applications, the task is to design the processor based on prior knowledge of the algorithm to be implemented. If the algorithm body can be represented as a directed acyclic graph, a static schedule can be obtained by assuming the worst case latency of the units. However such a schedule might be inefficient in terms of latency and throughput due to the worst case latency assumption. A dynamic hardware scheduler on the other hand can outperform a static scheduler by gaining those waisted clock cycles. In this paper we present a self scheduling hardware execution unit, based on ideas taken from dynamic data flow machines. This execution unit is capable of scheduling an algorithm body that contains a mixture of non-manifest loops, variable-latency and fixed-latency units without wasting any extra clock cycles.
    Original languageUndefined
    Title of host publication3rd PROGRESS workshop on Embedded Systems
    Place of PublicationUtrecht, Netherlands
    Number of pages8
    ISBN (Print)90-73461-34-0
    Publication statusPublished - Oct 2002
    Event3rd PROGRESS Workshop on Embedded Systems 2002 - Utrecht, Netherlands
    Duration: 24 Oct 200224 Oct 2002
    Conference number: 3

    Publication series

    PublisherSTW Technology Foundation


    Workshop3rd PROGRESS Workshop on Embedded Systems 2002
    Abbreviated titlePROGRESS


    • METIS-209134
    • EWI-2719
    • CAES-EEA: Efficient Embedded Architectures
    • IR-38173

    Cite this