Minimum Waste Scheduling of dynamic variable-latency and non-manifest functional units


Mansour, Omar and Molenkamp, Egbert and Krol, Thijs (2002) Minimum Waste Scheduling of dynamic variable-latency and non-manifest functional units. In: 3D progress workshop on Embedded Systems, 2002, October 24, 2002, Veldhoven, The Netherlands.

Abstract: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
Item Type:Conference or Workshop Item
Copyright:© STW Technology Foundation
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 209134