| Center for Embedded Computer Systems | Computer Science and Engineering |
| Microelectronic Embedded Systems Laboratory | University Of California, San Diego |
|
| |
The design flow through the SPARK framework is as follows: SPARK accepts a behavioral description of a design in ANSI-C, creates the intermediate representation, runs a data dependency analysis pass, schedules the design, binds the resources, performs control synthesis, and finally generates an output in register-transfer level VHDL. The passes and transformations that are used can be controlled by the designer using scripts.
An overview of the SPARK framework is shown in Figure 1 below.
|
| Scheduling | Resource Binding | Code Generation | SPARK IR |
SPARK takes a behavioral description in ANSI-C as input -- currently with the restrictions of no pointers, no function recursion, and no irregular control-flow jumps. As shown in Figure 1 above, SPARK also takes additional information as input, such as a hardware resource library, resource and timing constraints and user directives for the various heuristics and transformations. SPARK stores the input behavior in a hierarchical and multi-layered intermediate representation (IR) that retains the structural information (if-then-else, for-loop constructs) given in the input description along with information on operations and data dependencies. This is critical for enabling coarse-level transformations and making global decisions about code motion.
We first apply a set of coarse-grain and fine-grain code transformations to the input description during a pre-synthesis phase before performing the traditional high-level synthesis tasks of scheduling, allocation and binding. The transformations in the pre-synthesis phase include (a) coarse-level code restructuring by function inlining and loop transformations (loop unrolling, loop fusion et cetera), (b) transformations that remove unnecessary and redundant operations such as common sub-expression elimination (CSE), copy propagation, and dead code elimination (c) transformations such as loop-invariant code motion, induction variable analysis (IVA) and operation strength reduction, that reduce the number of operations within loops and replace expensive operations (multiplications and divisions) with simpler operations (shifts, additions and subtractions).
The pre-synthesis phase is followed by the scheduling and allocation phase. Resource allocation and module selection are done by the designer and are given as input to the synthesis tool through a hardware resource library. The scheduler is organized into two parts: the heuristics that perform scheduling and a transformations toolbox. The transformations toolbox contains speculative code motion transformations, the Percolation and Trailblazing code motion techniques, dynamic renaming of variables et cetera. The synthesis transformations include chaining operations across conditional blocks, scheduling on multi-cycle operations, resource sharing et cetera.
Besides the traditional high-level synthesis transformations, the scheduling phase also employs several compiler transformations applied ``dynamically'' during scheduling. These dynamic transformations, such as dynamic CSE and dynamic copy propagation, exploit the new opportunities created by code motions. A branch balancing technique also dynamically adds scheduling steps in conditional branches to enable code motions, specifically those code motions that duplicate operations in conditional branches.
Passes from the toolbox are called by a set of heuristics that guide how the code refinement takes place. The heuristics and the underlying transformations that they use are kept completely independent. This allows the heuristics to employ the various transformations as and when required, thus enabling a modular approach that allows the easy development of new heuristics.
The scheduling phase is followed by a resource binding and control synthesis phase. This phase binds operations to functional units, ties the functional units together (interconnect binding), allocates and binds storage (registers), generates the steering logic and generates the control circuits to implement the schedule. The focus of our resource binding approach is to minimize the interconnect between functional units and registers. After binding, we generate a finite state machine controller for the scheduled and bound design.
Finally, a back-end code generation pass generates register-transfer level (RTL) VHDL. This RTL VHDL belongs to the subset of VHDL that is synthesizable by commercial logic synthesis tools. This enables our synthesis framework to complete the design flow path from architectural design to final design netlist. Note that, the output VHDL is structural with all operations bound to resources (components in VHDL) and variables bound to registers.
SPARK also has back-end code generation passes that generate ANSI-C and behavioral VHDL. These behavioral output codes represent the scheduled and optimized design. The output ``C'' can be used in conjunction with the input ``C'' to perform functional verification and also, to improve visualization for the designer on the affects of the transformations applied by SPARK on the design.
An overview of high-level synthesis (HLS) is shown in Figure 2 above. The idea is to start with a behavioral description in a high-level language -- in our case, we choose the "C" programming language as a starting point -- and capture the behavior in an intermediate representation that captures both the data and control dependencies. This behavior is then systematically refined and "synthesized" into an architecture consisting of a datapath, memory and a control unit, along with the interconnections. The number of hardware components are also given as input to the HLS tool. Thus, a designer may allocate 2 adders and one multiplier to map the entire behavior on. The HLS tool then does scheduling, wherein operations from the behavioral description are assigned time steps or cycles in which they execute. Next, the HLS tool does resource binding. In this step, operations are mapped or bound to a particular hardware component (one of the two adders or the multiplier in our example), variables are bound to registers, data transfers are mapped to buses and so on. Next, a control generation pass creates the controller that generates the signals to implement the schedule and control the data routing in the data path.
