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

Abstract — In this paper we address the problem of scheduling algorithms embodied with a mixture of non-manifest-loops [1], variable-latency and fixed-latency units [2], [3] for high throughput DSP-applications. Non-manifest 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 com-plete 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 assump-tion. 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 dy-namic 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. Keywords—Non-manifest loop scheduling, variable la-tency functional units, dynamic hardware scheduling, self scheduling hardware units. I