CRI Doctoral Forum Lecture, 2008-2009

Abstract:

Traditionally, scheduling algorithms for software instructions concentrated on problems such as optimal register usage, branch elimination and instruction level parallelism. However, in the context of hardware synthesis, scheduling algorithms optimize entirely different set of constraints. In hardware synthesis, design frequency, size and power consumption are affected by parameters such as reuse of modules, wire length, longest gate chain, etc. Usually, in high level hardware synthesis, all functional units of the same type have a fixed known ``length'' (number of stages) and the scheduler mainly determines when each unit is activated. We focus on scheduling techniques for the high-level synthesis of pipelined functional units where the number of stages of these operations is a free parameter of the synthesis. This problem is motivated by the ability to create pipelined functional units, such as multipliers, with different pipe lengths. These units have different characteristics in terms of parallelism level, frequency, latency, etc.

This work presents the variable pipeline scheduler (VPS). The ability to synthesize variable pipelined units expands the known scheduling problem of high-level synthesis to include a 2D search for a minimal number of hardware units (operations) and their desired number of stages. The proposed search procedure is based on algorithms that find a local minima in a d-dimensional grid, thus avoiding the need to evaluate all possible points in the space. We have implemented a C language compiler for VPS. Our results demonstrate that using variable pipeline units can reduce the overall resource usage and improve the execution time when synthesized onto an FPGA.