Recent developments in high-level synthesis.
We survey recent developments in high level synthesis technology for VLSI design. The need for higher-level design automation tools are discussed first. We then describe some basic techniques for various subtasks of high-level synthesis. Techniques that have been proposed in the past few years (since 1994) for various subtasks of high-level synthesis are surveyed. We also survey some new synthesis objectives including testability, power efficiency, and reliability.
Introduction
Very Large Scale Integrated Circuits (VLSI) technology provides densities of multiple- million
gates of random logic per chip. Chips of such complexity are very difficult, if not impossible,
to design using the traditional capture-and-simulate design methodology. Furthermore, VLSI
technology has also reached such a maturity level that it is well understood and no longer
provides a competitive edge by itself. Instead, time to market is usually equally, if not more,
important than area or speed. The industry has started looking at the product development
cycle comprehensively to reduce the design time and to gain a competitive edge in the time-
to-market race. Automation of the entire design process from conceptualization to silicon or
a describe-and-synthesize design methodology has become necessary [20].
As the complexities of chips increase, so will the need for design automation on higher
levels of abstraction where functionality is easier to understand and tradeoff is more influ-
ential. There are several advantages to automating part or all of the design process and
moving automation to higher levels. First, automation assures a much shorter design cycle.
Second, it allows for more exploration of different design styles since different designs can
be generated and evaluated quickly. Finally, if synthesis algorithms are well understood,
design automation tools may out-perform average human designers in meeting most design
constraints and requirements.
Synthesis is a translation process from a behavioral description into a structural descrip-
tion, similar to the compilation of a high level language program in C or Pascal into an
assembly program. Each component in the structural description is in turn defined by its
own (lower level) behavioral description. Synthesis, sometimes called design refinement, adds
an additional level of detail that provides information needed for the next level of synthesis
or for manufacturing of the design. This more detailed design must satisfy design constraints
supplied along with the original behavioral description or generated by a previous synthesis
step.
We define high level synthesis (HLS) as a translation process from a behavioral description
into a register-transfer level (RTL) structural description. High level synthesis has been
a very hot research topic over the past fifteen years. Comprehensive discussions of specific re-search
approaches to HLS can be found in [6, 20, 63, 96]. We concentrate on its development
over the past three years.
The rest of this paper is organized as follows. Section 2 describes the design flow of
VLSI when HLS is used. Section 3 outlines the tasks and basic techniques. In Section 4,
several new target architectures for HLS are surveyed. Advance in algorithmic techniques is
described in Section 5. In Section 6, we survey some new objective functions that recent HLS
systems are trying to optimize. Section 7 describes applications of HLS. Finally, Section 8
speculates on future directions of HLS.
Design Flow Using HLS
A behavioral description is used as the starting point for HLS. It specifies behavior in terms of
operations, assignment statements, and control control constructs in a hardware description
language (HDL) (e.g., VHDL [37] or Verilog [90]). An HDL differs from a software programming
language (e.g., C or Pascal) in its capability in expressing timing and concurrency
of hardware.
The output from a high level synthesizer consists of two parts: a datapath structure at
the register-transfer level (RTL), and a specification of the finite state machine to control the
datapath. At the RTL level, a datapath is composed of three types of components: functional
units(e.g., ALUs, multipliers, and shifters), storage units(e.g., registers and memory), and
interconnection units(e.g., busses and multiplexors). The finite state machine specifies every
set of microoperations for the datapath to perform during every control step.
In the first step of HLS, the behavioral description is compiled into an internal repre-
sentation. This process usually includes a series of compiler-like optimizations such as code
motion, dead code elimination, constant propagation, common subexpression elimination,
and loop unrolling. In addition, it may also apply some hardware-specific transformations
such as syntactic variances minimization, retiming, and those taking advantage of the associativity
and commutativity properties of certain operations. A control/data flow graph
(CDFG) is a commonly used internal representation to capture the behavior. The control-flow
graph (CFG) portion of the CDFG captures sequencing, conditional branching and
looping constructs in the behavioral description, while the data-flow graph (DFG) portion
captures data-manipulation activity described by a set of assignment statements (opera-
tions).
The following three steps form the core of transforming a behavior into a structure:
scheduling, allocation, and binding. Scheduling assigns operations of the behavioral description
into control steps. A control step usually corresponds to a cycle of the system clock,
the basic time unit of a synchronous digital system. Allocation chooses functional units
and storage elements from the component library. There may be several alternatives among
which the synthesizer must select the one that best matches the design constraints and maximizes
the optimization objective. Binding assigns operations to functional units, variables
to storage elements, and data transfers to wires or buses such that data can be correctly
moved around according to the scheduling.
These three tasks are closely interdependent with one another. For example, an optimal
scheduling of operations to control steps without explicit performance and cost information
of component allocation is impossible. Similarly, an optimal allocation of components cannot
be performed without exact information on operation concurrency. Furthermore, there exists
a performance/cost tradeoff by applying these tasks. For example, the most area efficient
design consists of the minimum number of slow components such that a larger number of
control steps is required to execute the desired function. On the other hand, allocating more
components allows exploiting parallel executions of operations so that a higher performance
can be achieved at the expense of higher area cost. By adjusting the constraint parameters,
the design space can be explored. One primary application of HLS is in helping the designers
with exploring the design space and hence evaluating multiple implementation alternatives
quickly.
3 Basic Techniques
Given a CDFG, we have to perform scheduling, allocation and binding to get a datapath.
A by-product of these tasks is a specification of the behavior of the controlling finite state
machine. In this section we survey some basic techniques for scheduling, allocation and
binding.
3.1 Scheduling
Scheduling assigns operations in the behavioral description into control steps. Within a
control step, a separate functional unit is required to execute each operation assigned to
that step. Thus, the total number of functional units required in a control step directly
corresponds to the number of operations scheduled into it. If more operations are scheduled
into each control step, more functional units are necessary, which results in fewer control steps
for the design implementation. On the other hand, if fewer operations are scheduled into
each control step, fewer functional units are sufficient, but more control steps are needed.
Thus, scheduling is an important task in HLS because it largely determines the tradeoff
between design cost and performance.
There are two classes of scheduling problems: time-constrained scheduling and resource-constrained
scheduling. Time-constrained scheduling minimizes the hardware cost when all
operations are to be scheduled into a fixed number of control steps. On the other hand,
resource-constrained scheduling minimizes the number of control steps needed for executing
all operations given a fixed amount of hardware.
Integer Linear Programming (ILP) formulations for both resource-constrained scheduling
and time-constrained scheduling [36] have been proposed. However, the execution time of the
algorithm grows exponentially with the number of variables and the number of inequalities.
In practice the ILP approach is applicable only to very small problems. Nevertheless, the
ILP approach has made the problems better understood.
Since the ILP method is impractical for large designs, heuristic methods that run efficiently
at the expense of the design optimality have been developed. Heuristic scheduling algorithms
usually uses two techniques: constructive approach and iterative refinement. There
are many approaches for constructive scheduling. They differ in the selection criteria used
to choose the next operation to be scheduled.
The simplest constructive approach is the as soon as possible (ASAP) scheduling. First,
operations are sorted into a list according to their topological order. Then, operations are
taken from the list one at a time and placed into the earliest possible control step. The
other simple approach is the as late as possible (ALAP) scheduling. The ALAP value for an
operation defines the latest control step into which an operation can possibly be scheduled. In
this approach, given a time constraint in terms of the number of control steps, the algorithm
determines the latest possible control step in which an operation must begin its execution.
The critical paths within the flow graph can be found by taking the intersection of the
ASAP and ALAP schedules such that the operations appear in the same control steps in
both schedules are on the critical paths.
In both ASAP and ALAP scheduling, no priority is given to operations on the critical
path so that those operations may be mistakenly delayed when resources limits are imposed
on scheduling. List scheduling overcomes this problem by using a global criterion for selecting
the next operation to be scheduled. One example of a global priority function is mobility
[70] which is defined as the difference between the ASAP and ASAP values of an operation.
The other example is urgency [22] which is defined as the minimum number of control steps
from the bottom that this operation can be scheduled before a timing constraint is violated.
In list scheduling, a list of ready operations is ordered according to the priority function and
processed for each state.
The force-directed scheduling (FDS) [72] is another example that uses a global selection
criteria to choose the next operation for scheduling. The FDS algorithm relies on the ASAP
and ALAP scheduling algorithms to determine the range of control steps for every operation.
Distribution graphs are then created to represent the probabilistic number of operations that
will be performed in the control step for each type of operation in each control step. The
main goal of the FDS algorithm is to reduce the total number of functional units used in the
implementation of the design. The algorithm achieves the objective by uniformly distributing
operations of the same type into all the available states.
We call algorithms similar to FDS "constructive" because they construct a solution without
performing any backtracking. The decision to schedule an operation into a control step is
made on the basis of a partially scheduled DFG; it does not take into account future scheduling
of operations into the same control step. Due to the lack of a look-ahead scheme and
the lack of compromises between early and late decisions, the resulting solution may not be
optimal. We can cope with this weakness by iteratively rescheduling some of the operations
in the given schedule. One example of this approach is proposed by [73] which is based
on the paradigm originally proposed for the graph-bisection problem by Kernighan and Lin
(KL) [41]. In this approach, an initial schedule is obtained using any scheduling algorithm.
New schedules is obtained by rescheduling a sequence of operations that maximally reduces
the scheduling cost. If no improvement is attainable, the process halts.
In the preceding discussions only blocks of straight line code have been considered. How-
ever, in addition to blocks of straight line code, a realistic design description usually contains
both conditional and loop constructs. Many approaches [43, 99] have been proposed to
schedule conditional constructs. For example, in [99] a conditional vector is used to identify
mutually exclusive operations so that an operation can be scheduled in different control steps
for different execution instances. Another approach is the path-based As Fast As Possible
(AFAP) scheduling [5] which first extracts all possible execution paths from a given behavior
and schedules them independently. The schedules for the different paths are then combined
by resolving conflicts among the execution paths. For loop constructs, different approaches,
such as pipelining [71], and loop folding [23], have been proposed.
3.2 Allocation and Binding
After scheduling, a datapath can be constructed in two steps: unit allocation and unit
binding. Some researchers call unit allocation and unit binding collectively as datapath
allocation. Unit allocation determines the number and types of RT components to be used in
the design. Since a real RT component library may contain multiple types of functional units,
each with different characteristics (e.g., functionality, size, delay and power dissipation), unit
allocation needs to determine the number and types of different functional and storage units
from the component library. Unit binding maps the operations, variables, and data transfers
in the scheduled CDFG into the functional, storage and interconnection units, respectively,
while ensuring that the design behavior operates correctly on the selected set of components.
Unit binding consists of three interdependent tasks: functional-unit binding, storage
binding, and interconnection binding. Functional-unit binding involves the mapping of operations
in the behavioral description into the set of selected functional units. Storage
binding maps data carriers (e.g., constants, variables and data structures like arrays) in the
behavioral description onto storage elements (e.g., ROMs, registers and memory units) in
the datapath. Interconnection binding maps every data transfer in the behavior into a set
of interconnection units for data routing.
There are three approaches to solve the allocation problem: constructive approaches,
which progressively construct a design while traversing the CDFG; decomposition approach-
es, which decompose the allocation problem into its constituent parts and solve each of them
separately; and iterative methods, which try to combine and interleave the solution of the
allocation subproblems.
A constructive approach starts with an empty datapath and builds the datapath gradually
by adding functional, storage and interconnection units as necessary. For example, EMUCS
[33] and MABAL [46] use a global criterion based on functional, storage and interconnection
costs to determine the next element to assign and where to assign it.
Although constructive algorithms are simple, the solutions they find can be far from
optimal. In order to improve the quality of the results, some researchers have proposed a
decomposition approach, where the allocation process is divided into a sequence of independent
tasks; each task is transformed into a well-defined graph-theoretical problem and then
solved with a proven technique. In the following, we describe allocation techniques based on
three graph-theoretical methods: clique partitioning, left-edge algorithm, and the weighted
bipartite matching algorithm.
Tseng and Siewiorek [92] divided the allocation problem into three tasks of storage,
functional-unit and interconnection allocation which are solved independently by mapping
each task to the well known problem of graph clique-partitioning. In the graph formulation,
operations, values or interconnections are represented by nodes. An edge between two nodes
indicates those two nodes can share the same hardware. Thus, the allocation problem, such
as storage allocation, can be solved as finding the minimal number of cliques in the graph.
Because finding the minimal number of cliques in the graph is an NP-hard problem, in [92]
a heuristic approach is taken.
Although the clique-partitioning method when applied to storage allocation can minimize
the storage requirements, it totally ignores the interdependence between storage and inter-connection
allocation. Paulin and Knight [72] extend the previous method by augmenting
the graph edges with weights that reflect the impact on interconnection complexity due to
register sharing among variables.
Kurdahi and Parker apply the left-edge algorithm [45] to solve the register-allocation
problem. Unlike the clique-partitioning problem, which is NP-complete, the left-edge algorithm
has a polynomial time complexity. Moreover, this algorithm allocates the minimum
number of registers. However, it cannot take into account the impact of register allocation
on the interconnection cost, as can the weighted version of the clique-partitioning algorithm.
Both the register and functional-unit allocation problems also can be transformed into
a weighted bipartite-matching algorithm [30]. In this approach, a bipartite graph is first
created which contains two disjoint subsets (e.g., one subset of registers and one of variables,
or one subset of operations and one of functional units), an edge connects two nodes in
different subsets represents the node in one subset can be assigned to the node of other
subset (e.g., the variable in the variable subset can be assigned to the register in the register
subset). Thus, the problem of matching each variable to a register is equivalent to the classic
job-assignment problem. In [30], a polynomial time maximum weight matching algorithm
is employed to solve the problem. The matching algorithm, like the left-edge algorithm,
allocates a minimum number of registers. It also takes partially into consideration the
impact of register allocation on interconnection allocation since it can associate weights with
the edges.
Given a datapath synthesized by constructive or decomposition methods, a further improvement
may be achieved by reallocation, an iterative refinement approach. The most straightforward
approach could be a simple assignment exchange using the pairwise exchange
or the simulated annealing method. In addition, a more sophisticated branch-and-bound
method can be applied by reallocating a group of different types of entities for datapath
refinement [91].
4.1 Multiport Memory
A multiport memory can support multiple read and/or write accesses simultaneously. Using
multiport memory gives the HLS more flexibility in binding variables to storages. Tradition-
ally, variables are grouped into registers, and registers into register files(memory modules)
before synthesizing interconnection between memory modules and functional units. Kim and
proposed placing emphasis on the interconnection. They try to minimize the inter-connection
first and then to group the variables to form the memory modules later. Lee and
Hwang [52] proposed taking multiport memory into account as early as during scheduling.
They defined a "multiport access variable" (MAV) for a control step, and let the scheduling
algorithm equalizes the MAVs across all control steps in order to achieve a better utilization
of the memory.
4.2 Distributed Storage
Most traditional HLS systems are targeted towards a centralized storage units. Every operation
must access its input operands from and write its output operands to the storage units.
For some regular iterative algorithms, this architecture may not be the optimal. Aloqeely
and Chen [3] proposed a sequencer-based datapath architecture. A sequencer is a stack or
queue connecting one functional unit to another. By letting variables intelligently "stay" in
or "flow" through sequencers in the datapath for future use, high quality datapath can be
synthesized for many signal processing and matrix computation algorithms. Furthermore,
less traffic is needed between the functional units and the central storage units, resulting
in a simple interconnection complexity. A similar concept called "data routing" has been
proposed for both HLS and code generation [48].
4.3 Partitioned Bus
Ewering [16] proposed a parameterized architecture called "partitioned busses." Busses are
partitioned into segments. Each functional unit and each storage unit is connected to one
of the segment. Most data transfers occur within a segment. Inter-segment transfers are
made possible through switches between segments. Since the loading of the bus is light,
the synthesized circuit is fast. Scheduling and allocation is done such that the amount of
inter-segment data transfer is minimized.
There have been quite significant advance in HLS algorithms and heuristics. Various methods
have been proposed for transforming the CDFG such that a high-quality circuit is easier to
synthesize. Several groups have extended the ILP formulation for more general scheduling
problem, more capability in handling large designs, or more problems besides scheduling.
Algorithms originally developed for other problems have been employed for HLS too. Several
groups proposed various neural network models for various HLS tasks. As the solution
techniques getting more powerful, it is no longer necessary to divide the synthesis problem
into multiple subtasks. A notable development is in performing all tasks together as a single
task in order to achieve better quality of design.
5.1 Behavioral Transformation
Transformations can be applied to the design representation at various stages of HLS. During
compilation of the input behavioral description into a control/data flow graph, several
compiler-like optimizations can be performed to remove the extraneous syntactic constructs
and redundancies. Flow-graph transformations are used to convert parts of the representation
from one style (e.g., control flow) to another (e.g., data flow) and to change the degree of
parallelism. Hardware-specific transformations use properties of register-transfer (RT) and
logic components to perform optimizations (e.g., replacing a data-flow graph segment that
increments a variable with an increment operation).
Since the flow-graph representation typically comes from an imperative language de-
scription, several standard compiler optimization techniques, such as constant folding and
redundant operator elimination, can be performed on the representation [2]. Arrayed variables
are another rich source of compiler level optimizations for HLS [24, 68]. Since arrays
in the behavioral representation get mapped to memories, a reduction in the number of array
accesses decreases the overhead resulting from accessing memory structures [42].
Certain compiler transformations are specific to the HDL used for describing the design.
For example, when VHDL is used for design description, several approaches proposed by [4]
can identify specific syntactic constructs and replace them with attributes on signals and
nets to indicate their functions. Furthermore, in order to reduce the syntactic variation
of descriptions with the same semantic, Chaiyakul et al. [8] proposed a transformation
technique using an Assignment Decision Diagrams (ADD) to minimize syntactic variance in
the description.
The graph capturing the behavior can be restructured. Tree height reduction is one of the
commonly used flow-graph transformations to improve the parallelism of the design. Tree
height reduction uses the commutativity and distributivity properties of language operators
to decrease the height of a long expression chain, and exposes the potential parallelism within
a complicated data-flow graph [31, 67].
Pipelining is another frequently applied transformation in HLS [71]. Other commonly
used transformations include loop folding [23, 88], software pipelining [26, 77], and retiming
Hardware-specific transformations at the logic, RT and system levels can be applied
to the intermediate representation. In general, these are local transformations that use
properties of hardware at different design levels to optimize the intermediate representation.
For example, at the logic level, we can apply local Boolean optimization techniques [13] to
the intermediate representation. At the RT level, we can use pattern matching to detect and
replace portions of the flow graph with simpler flow-graph segments. The pattern matching
transformations are based on RT semantics of the hardware components corresponding to
the flow-graph operators [85]. System level transformations can be used to divide parts of
the flow graph into separate processes that run concurrently or in a pipelined fashion [98].
5.2 Advance in ILP Formulation
Achatz [1] proposed an extension to the ILP formulation such that it can handle multi-functional
units as well as units with different execution times for different instances of the
same operation type.
Wang and Grainger [97] showed that the number of constraints in the original ILP formulation
can be reduced without reducing the explored design space. Therefore, the computation
can be more efficient or the formulation can be applicable to larger sized problems.
Chaudhuri et al [10] performed an in-depth formal analysis of the structure of the assign-
ment, timing, and resource constraints, evaluated the structure of the scheduling polytope
described by these constraints, and showed how to exploit that structure in a well-designed
ILP formulation. They also proposed how to improve a well-structured formulation by adding
new valid inequalities.
In the OSCAR system [50], a 0/1 integer programming model is proposed for solving
scheduling, allocation, and binding all together. Gebotys [21] proposed an integer programming
model for the synthesis of multichip architecture. Her model simultaneously deals with
partitioning, scheduling, and allocation. The search space is reduced by using a polyhedral
theory.
Wilson et al [95] generalized the ILP approach in an integrated solution to the scheduling,
allocation, and binding in datapath synthesis. A module may execute an arbitrary combination
of operations, possibly using different number of control steps for different type of
operations. Operations may be bounded to a variety of modules, possibly requiring different
number of control steps depending on the module chosen.
5.3 New Approaches
Ly et al [49] proposed an idea of "behavioral templates" for scheduling. A template locks
a number of operations into a relative schedule with respect to one another. It eases
the handling of timing constraints, sequential operation modeling, pre-chaining of certain
operations, and hierarchical scheduling.
Many neural net based scheduling algorithms have been proposed. ANSA [93] is a three-phase
neural network scheduler. Kawaguchi and Tokada [40] combined simulated annealing
and neural networks for the scheduling problem.
Genetic algorithms also find their application in high level synthesis. Dhodhi et al [12]
proposed a problem-space genetic algorithm(PSGA) for datapath synthesis. It performs
concurrent scheduling and allocation with the objective of minimizing a cost function of
the hardware resource and the total execution time. Heijligers et al [32]'s genetic algorithm
uses an encoding technique that is capable of allocating supplementary resources during
scheduling. They also paid attention to runtime efficiency by means of carefully-designed
analyzing methods.
Ly and Mowchenko [56] proposed adapting simulated evolution to high level synthesis.
Simulated evolution has been successfully applied in other CAD areas including routing, par-
titioning, and placement. SE-based synthesis explores the design space by repeatedly ripping
up parts of a design in a probabilistic manner and reconstructing them using application-specific
heuristics. It combines rapid design iterations and probabilistic hill climbing to
achieve effective design space exploration. The objects subject to ripping up and reconstruction
are operation-to-step assignments and various binding.
InSyn [87] combines allocation and scheduling of functional, storage, and interconnect
units into a single phase. It uses the concept of register state (free, busy, and undecided) for
optimizing registers in a partial schedule where lifetimes of data values are not yet available.
It alleviates bus contention by using reusable data values and broadcast, or selectively slowing
noncritical operations. InSyn can trade off distinct resource sets concurrently, i.e., it
can trade a functional unit for some registers, or vice versa. Estimation tools are utilized for
resource allocation, design space pruning, and evaluation of the synthesized results.
6 Advance in Objective Function
6.1 More Accurate Estimation
Traditional HLS systems characterize their synthesis results based on very crude estimation.
Area is estimated with the sum of the area of functional units, storage units and intercon-
nects. Timing is estimated assuming that wiring delay is insignificant. As we are moving
into deep submicron era, both wiring area and timing are no longer ignorable. Many estimation
methods have been proposed. Moreover, interaction between HLS and layout has been
Rim and Jain [84] proposed a performance estimation tool. Given a data flow graph, a set
of resources, resource delay, and a clock cycle, their tool computes a lower-bound completion
time for non-pipelined resource-constrained scheduling problems.
Chaudhuri and Walker [9] proposed an algorithm for computing lower bounds on the
number of functional units of each type required to schedule a data flow graph in a specified
number of control steps. The bounds are found by relaxing either the precedence constraints
or the integraty constraints on the scheduling problem. This bounding method is used
to estimate FU area, to generate resource constraints for reducing the search space, or in
conjunction with exact formulation for design space exploration.
Mecha et al [57] proposed a high level area estimation method targeted towards standard
cell implementation. They emphasized on predicting the interconnection area.
Fang and Wong [17] proposed simultaneously performing functional unit binding and
floorplanning. Munch et al [66] proposed an analytical approach to capture the placement
and binding problems in a single mixed ILP model. Targeted towards a linear bit-slice
architecture, the model is capable of minimizing the overall interconnect structure of the
datapath.
6.2 HLS for Testability
Testability at the high level can be enhanced by minimizing the number of self-loops (self-
adjacent registers). The main concern is in the trade-off between testability improvement
and area overhead.
Since multiplexors and buses can behave as switches, they can help reducing the test
costs. Gupta and Breuer [27] proposed taking advantages of multiplexors and buses to
reduce both the area overhead and test generation costs. They analyzed the locations of
switches during the selection of partial scan registers. They also utilized the switches to
setup paths for transporting test data.
Flottes et al [18] proposed a method to improve the testability by incorporating test constraints
during register allocation and interconnect network generation. They analyze the
testability of a design at the behavioral level in the presence of loops and control constructs.
Dhodhi et al [14] proposed a problem-space genetic algorithm (PSGA) for performing simultaneously
scheduling and allocation of testable functional units and registers under area,
performance and testability constraints. Mujumdar et al [65] proposed a two-stage approach
for binding for testability. First, they used a binder with test cost to generate a nearly loop-free
design. Then, they used a loop-breaking method to identify self-loops in the design, and
eliminate these loops by alternating the register and module binding.
et al [75] proposed methods for transforming a behavioral description so that
synthesis of the new description will requires less area overhead and partial scan cost. They
proposed a two-stage objective function for estimating the area and testability as well as for
evaluating the effects of a transformation. Then, they used a randomized branch-and-bound
steepest decent algorithm to search for the best sequence of transformations.
Testability can be improved via better controller design. Hsu, Rudnick, and Patel [34]
propose a controllability measure for high level circuit description and a high level synthesis-
for-testability technique. They improve the circuit testability by enhancing the controllability
of the control flow.
6.3 HLS for Low Power
Due to low power requirement in many portable applications such as notebook and mobile
phone as well as packaging cost consideration, low power design technology is becoming very
important in every aspect of VLSI design. A great deal of research effort has been spent on
circuit and logic design for low power [74]. There have been active research in the past few
years for HLS for low power.
For low power HLS, high level power estimation techniques are needed. Raghunathan et
al [79] propose some techniques for estimating switching activity and power consumption at
register-transfer level. They take into account the presence of glitching activity at various
data path and control signals.
Rabaey et al [80] propose an approach for high level design guidance for low power using
properties of given algorithms and architectures. Several relevant properties (operation coun-
t, the ratio of critical path to available time, spatial locality, and regularity) are identified.
Significant emphasis is placed on exploiting the regularity and spatial locality for the optimization
of interconnect power. Their scheduling, assignment and allocation techniques [61]
exploit the regularity and common computation patterns in the algorithm to reduce the
fan-ins and fan-outs of the interconnection wires, resulting in reduced bus capacitance and
simplified bus structure.
Raghunathan and Jha [81] proposed a datapath allocation method for low power. They
also take into account controller's effect on datapath power dissipation. Goodby et al [25]
proposed achieving low power via pipelining and module selection. Musoll and Cortadella
[64] proposed a scheduling and resource-binding algorithm for reducing the activity of the
function units by minimizing the transitions of their input operands. Kumar et al [38] measure
activities of operations and carriers in a behavioral specification by simulating the DFG
with user-supplied profiling stimuli. They select a module set and schedule that minimize
the switching activity.
Martin and Knight [58] applied several low power techniques in behavioral synthesis
including lowering supply voltage, disabling the clock of idle components, and architectural
trade-off.
6.4 HLS for Reliability
In many critical applications, fault-tolerance is very important. It is desirable that a system
is capable of self-recovery in the presence of transient faults. In a self-recovering microar-
chitecture, intermediate results are compared at regular intervals, and if correct saved in
registers (checkpoints). On the other hand, on detecting a fault, it rolls back to a checkpoint
and retries. Orailoglu and Karri [69] proposed a self-recovering microarchitecture synthesis
system. They proposed an algorithm for the selection of good checkpoints that have low
overhead while meeting the constraint on the number of clock cycles of a retry period.
Self-testing can be carried out concurrently with normal operations using otherwise idle
functional units. Singh and Knight [86] proposed a method to test hardware elements when
they are not used. It generates a circuit to cycle test vectors through the idle hardware and
produce a signature. Built-in self testing is achieved with reduced test-time overhead.
The hot-carrier reliability issue has also been dealt with in high level synthesis. Karnik et
al [39] proposed an iterative redesign method to improve the long-term reliability of a given
high level circuit. They used macro-models of standard circuit elements developed using a
reliability simulation tool. Reliability improvement is due to capacitance reduction.
6.5 Controller Issues
Traditionally, the control unit specification is generated after the datapath synthesis com-
pleted. Recently, some authors observed that there exists tradeoff between the controller and
the datapath. Rao and Kurdahi [82] proposed a hierarchical approach in which the control
logic overhead can be taken into account at each level of the hierarchy before the datapath
is fully synthesized. Their approach is most suitable for behavior consisting of regular algo-
rithm. Huang and Wolf [35] studied how datapath allocation affects controller delay. They
proposed an allocation approach that considers the controller's effect on the critical path
delay. Therefore, they are able to minimize the system clock length during allocation.
7 Applications of HLS
Over the years, HLS has been successfully applied for the designs of several narrow, application-specific
domains. For example, many HLS systems, such as Cathedral [55], Hyper [11] and
Phideo [54], provide a design environment targeted towards the digital signal processing
(DSP) applications with various levels of throughput requirements. In contrast to computational
intensive DSP designs, many other HLS systems, such as HIS [7], Callas [53] and
Olympus [62], have been targeted toward control-dominated circuit designs. In addition,
an HLS system Mimola/Honeywell [101] has been targeted toward instruction set processor
design. The System Architect's Workbench from CMU [89] has been used in designs for
automotive applications [19].
A high level synthesis tool even finds its use in education [83]. With a datapath synthesizer
capable of exploiting the design space, students are able to try different architectural
decisions and evaluate their effectiveness.
Recently, HLS has been used in embedded system design environment. A typical embedded
system consists of off-the-shelf instruction set processors, memory, and ASICs. Each
application is partitioned into two interacting parts: software on the instruction set processor
and hardware on the ASICs. Several approaches [15, 29] have been developed to tackle
the hardware-software codesign problems. An HLS tool is definitely needed to quickly give
the cost and performance figures of the synthesized ASIC.
With the advent of field-programmable hardware such as field programmable gate arrays
and field programmable interconnect components (FPICs), many designs are
implemented in FPGAs. Fast turn-around is more important to FPGA- than ASIC-based
implementation. Using HLS provides an unmatchable fast turn-around time.
Taking advantage of the re-programmability of FPGAs and FPICs, hardware emulation
provides a very fast means for design verification. Currently, most hardware emulators
take as inputs a logic-level structural description. With HLS, extensive verification can be
performed earlier in the design process. For example, in [100] an HLS scheme is used for
automatic mapping of behavioral description onto an ASIC emulation board.
In a custom computer, hardware resources are configured according to the characteristics
of the application programs. HLS is essential here in converting an algorithm or a code
segment into an FPGA/FPIC programming bitstream.
8 Future Directions
Although we have seen its many applications, HLS today is still not as indispensable as layout
or logic synthesis. For high level synthesis to move into mainstream design practice, its area
efficiency and performance level must be competitive with that of traditional approaches. A
possible approach is to embed more domain knowledge into the synthesizer. For instance,
many DSP-oriented HLS systems have been developed. Unfortunately, this approach has
one serious drawback. The more domain-specific a tool is, the smaller its customer base will
be. Since, HLS development is a difficult and complicate task, a small customer base may
not be able to support its healthy growth.
In the deep submicron era, wiring delay will dominate gate delay. Therefore, wiring
delay must be taken into account as early in the design process as possible. There is work
in dealing with the interaction between logic synthesis and layout. We have surveyed work
on simultaneous allocation and floorplanning. In the future, we shall see more interaction
between high level synthesis and layout. Every step of HLS should take layout into account.
With the rapid increasing in the integration level, we must prepare to deal with (com-
plicate) system-on-a-chip issues. It is impractical to design multi-million gate chips from
scratch. Therefore, it is essential to make good use of existing designs. A successful HLS
tool should provide a smooth mechanism for the user to reuse a wide variety of components.
We also have to pay attention to design verification. Although HLS is indeed effective
in reducing the time for synthesis, a quite significant portion of the design time is spent on
simulation and validation, which HLS does not provide any help to date. Since verification
at the higher level is more efficient than that at the lower level, a correctness-preserving HLS
design flow will significantly save validation time. Therefore, it will give the designer more
incentive to use HLS tools.



--R

"Extended 0/1 LP Formulation for the Scheduling Problem in High Level Synthesis,"
Compilers: Principles
"Sequencer-Based Datapath Synthesis of Regular Iterative Algorithms,"
"An Optimizer for Hardware Synthesis,"
"Path-Based Scheduling for Synthesis,"
High Level VLSI Synthesis
"The IBM High Level Synthesis System,"
"High Level Transformation for Minimizing Syntactic Variances,"
"Computing Lower Bounds on Functional Units Before Scheduling,"
"Analyzing and Exploiting the Structure of the Constraints in the ILP Approach to the Scheduling Problem,"
"HYPER: An Interactive Synthesis Environment for High Performance Real Time Applications,"
"Datapath Synthesis Using a Problem-Space Genetic Algorithm,"
"A New Look at Logic Synthesis,"
"High Level Synthesis of Data Paths for Easy Testability,"
"Hardware-Software Codesign of Embedded Controllers Based on Hardware Extraction,"
"Automatic High Level Synthesis of Partitioned Busses,"
"Simultaneous Functional-Unit Binding and Floorplan- ning,"
"High Level Synthesis for Easy Testabil- ity,"
"Industrial Extensions to University High Level Synthesis Tools: Making It Work in the Real World,"
High Level Synthesis - Introduction to Chip and System Design
"An Optimization Approach to the Synthesis of Multichip Architec- tures,"
"Applicability of a Subset of Ada as an Algorithmic Hardware Description Language for Graph-Based Hardware Compilation,"
"Loop Winding - A Data Flow Approach to Functional Pipelining,"
"Address Generation for Array Access Based on Modulus m Counter,"
"Microarchitecture Synthesis of Performance- Constrained Low-Power VLSI Designs,"
"An Efficient Microcode Compiler for Application Specific DSP Processors,"
"Partial Scan Design of Register-Transfer Level Circuits,"
"Partitioning of Functional Models of Synchronous Digital Systems,"
"System Level Synthesis using Re-Programmable Components,"
"Data Path Allocation Based on Bipartite Weighted Matching,"
"Tree-Height Minimization in Pipelined Architectures,"
"High Level Synthesis Scheduling and Allocation Using Genetic Algorithms,"
"A Method of Automatic Data Path Synthesis,"
"Enhancing High-Level Control-Flow for Improved Testability,"
"How Datapath Allocation Affects Controller Delay,"
"A Formal Approach to the Scheduling Problem in High Level Synthesis,"
Standard VHDL Language Reference Manual
"Profile-Driven Behavioral Synthesis for Low-Power VLSI Systems,"
"High-Level Hot Carrier Reliability-Driven Synthesis using Macro-Models,"
"Operation Scheduling by Annealed Neural Network- s,"
"An Efficient Heuristic Procedure for Partitioning Graph,"
"Integrating program transformations in the memory-based synthesis of image and video algorithms,"
"A Scheduling Algorithm for Conditional Resource Sharing - A Hierarchical Reduction Approach,"
"A New Approach to the Multiport Memory Allocation Problem in Datapath Synthesis,"
"REAL: A Program for Register Allocation,"
"Data Path Tradeoff using MABAL,"
"CHOP: A Constraint-Driven System Level Par- titioner,"
"Data Routing: A Paradigm for Efficient Datapath Synthesis and Code Generation,"
"Scheduling Using Behavioral Tem- plates,"
"OSCAR:Optimum Simultaneous Schedul- ing, Allocation and Resource Binding Based on Integer Programming,"
"Architectural Partitioning for System Level Partitioner,"
"A Scheduling Algorithm for Multiport Memory Minimization in Datapath Synthesis,"
"The Siemens High Level Synthesis System CALLAS,"
"PHIDEO: A Silicon Compiler for High Speed Algorithms,"
"Architectural Synthesis for Medium and High Throughput Signal Processing with the New CATHEDRAL Environment,"
"Applying Simulated Evolution to High Level Synthe- sis,"
"A Method for Area Estimation of Data Path in High Level Synthesis,"
"Power-Profiler: Optimizing ASICs Power Consumption at the Behavioral Level,"
"Using Bottom-Up Design Techniques in the Synthesis of Digital Hardware from Abstract Behavioral Descriptions,"
"Incorporating Bottom-Up Design into Hardware Synthesis,"
"Exploiting Regularity for Low-Power Design,"
"The Olympus Synthesis System for Digital Design,"
The Synthesis Approach to Digital System Design
"Scheduling and Resource Binding for Low Power,"
"Incorporating Testability Considerations in High Level Synthesis,"
"Optimum Simultaneous Placement and Binding for Bit-Slice Architectures,"
"Incremental Tree Height Reduction for High Level Syn- thesis,"
"Flow Graph Representation,"
"Coactive Scheduling and Checkpoint Determination During High Level Synthesis of Self-Recovering Microarchitectures,"
"Design Tools for Intelligent Silicon Compilation,"
"Sehwa: A Software Package for Synthesis of Pipelined from Behavioral Specifications,"
"Force-Directed Scheduling for the Behavioral Synthesis of ASICs,"
"Fast and Near Optimal Scheduling in Automatic Data Path Synthesis,"
"Power Minimization in IC Design: Principles and Applications,"
"Synthesis-for-testability using Transformations,"
"Optimizing Resource Utilization Using Transformation,"
"Rephasing: A Transformation Technique for the Manipulation of Timing Constraints,"
"Estimating Power Dissipation of VLSI Signal Processing Chip: the PFA technique,"
"Register-Transfer Level Estimation Techniques for Switching Activity and Power Consumption,"
"Design guidance in the power dimension,"
"Behavioral Synthesis for Low Power,"
"Controller and Datapath Trade-offs in Hierarchical RT-Level Synthesis,"
"Using HYPER to Teach Datapath Design Techniques in an ASIC Design Course,"
"Lower-Bound Performance Estimation for the High Level Synthesis Scheduling Problem,"
"Optimizations in High Level Synthesis,"
"Concurrent Testing in High Level Synthesis,"
"InSyn: Integrated Scheduling for DSP Applications,"
"A Transformation-based Method for Loop folding,"
Algorithmic and Register-Transfer Level Synthesis: The System Architect's Workbench
The Verilog Hardware Description Language
"Data Path Construction and Refinement,"
"Automatic Synthesis of Data Path on Digital Sys- tems,"
"ANSA: A New Neural Net Based Scheduling Algorithm for High Level Synthesis,"
"Specification Partitioning for System Design,"
"An ILP Solution for Optimum Scheduling, Module and Register Allocation, and Operation Binding in Datapath Synthesis,"
Survey of High Level Synthesis
"The Reduction of the Number of Equations in the ILP Formulation for the Scheduling Problem in High Level Synthesis,"
"Behavioral Transformations for Algorithmic Level IC Design,"
"A Resource Sharing Control Synthesis Method for Conditional Branches,"
"High Level Synthesis in a Rapid-Prototype Environment for Mechantronic Systems,"
"MDS: The Mimola Design Method,"
--TR
Compilers: principles, techniques, and tools
Optimizations in high level synthesis
REAL: a program for REgister ALlocation
Data path allocation based on bipartite weighted matching
Data path tradeoffs using MABAL
Industrial extensions to university high level synthesis tools
Fast and near optimal scheduling in automatic data path synthesis
Incremental tree height reduction for high level synthesis
High-level synthesis
Specification partitioning for system design
High-level synthesis in a rapid-prototype environment for mechatronic systems
High-level transformations for minimizing syntactic variances
Integrating program transformations in the memory-based synthesis of image and video algorithms
Simultaneous functional-unit binding and floorplanning
Analyzing and exploiting the structure of the constraints in the ILP approach to the scheduling problem
Sequencer-based data path synthesis of regular iterative algorithms
Incorporating testability considerations in high-level synthesis
OSCAR
Power-profiler
Scheduling using behavioral templates
Rephasing
Partial scan design of register-transfer level circuits
A new approach to the multiport memory allocation problem in data path synthesis
Scheduling and resource binding for low power
High-level synthesis scheduling and allocation using genetic algorithms
A scheduling algorithm for multiport memory minimization in datapath synthesis
Synthesis-for-testability using transformations
Power minimization in IC design
Computing lower bounds on functional units before scheduling
Register-transfer level estimation techniques for switching activity and power consumption
Exploiting regularity for low-power design
Enhancing high-level control-flow for improved testability
Data routing
Concurrent testing in high-level synthesis
Controller and datapath trade-offs in hierarchical RT-level synthesis
How datapath allocation affects controller delay
The Verilog hardware description language (4th ed.)
Using bottom-up design techniques in the synthesis of digital hardware from abstract behavioral descriptions
Flow graph representation
The Synthesis Approach to Digital System Design
High-Level VLSI Synthesis
Algorithmic and Register-Transfer Level Synthesis
An Optimizer for Hardware Synthesis
The Olympus Synthesis System
Profile-Driven Behavioral Synthesis for Low-Power VLSI Systems
Behavioral Synthesis for low Power
Microarchitectural Synthesis of Performance-Constrained, Low-Power VLSI Designs
High-level synthesis for easy testability
A method of automatic data path synthesis
A new look at logic synthesis
Address Generation for array access based on modulus m counters
PHIDEO

--CTR
Davide Bruni , Alessandro Bogliolo , Luca Benini, Statistical design space exploration for application-specific unit synthesis, Proceedings of the 38th conference on Design automation, p.641-646, June 2001, Las Vegas, Nevada, United States
Yoichi Yuyama , Masao Aramoto , Kazutoshi Kobayashi , Hidetoshi Onodera, An SoC architecture and its design methodology using unifunctional heterogeneous processor array, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.737-742, January 27-30, 2004, Yokohama, Japan
Gang Wang , Wenrui Gong , Brian DeRenzi , Ryan Kastner, Design space exploration using time and resource duality with the ant colony optimization, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
Hashem Hashemi Najaf-Abadi, A procedure for obtaining a behavioral description for the control logic of a non-linear pipeline, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.86-91, January 27-30, 2004, Yokohama, Japan
G. Economakos , P. Oikonomakos , I. Panagopoulos , I. Poulakis , G. Papakonstantinou, Behavioral synthesis with systemC, Proceedings of the conference on Design, automation and test in Europe, p.21-25, March 2001, Munich, Germany
J. Ramanujam , Sandeep Deshpande , Jinpyo Hong , Mahmut Kandemir, A Heuristic for Clock Selection in High-Level Synthesis, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.414, January 07-11, 2002
M. Narasimhan , J. Ramanujam, A fast approach to computing exact solutions to the resource-constrained scheduling problem, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.4, p.490-500, October 2001
Apostolos A. Kountouris , Christophe Wolinski, Hierarchical conditional dependency graphs as a unifying design representation in the CODESIS high-level synthesis system, Proceedings of the 13th international symposium on System synthesis, September 20-22, 2000, Madrid, Spain
G. Economakos , G. Papakonstantinou , P. Tsanakas, AGENDA: an attribute grammar driven enviornment for the design automation of digital systems, Proceedings of the conference on Design, automation and test in Europe, p.933-934, February 23-26, 1998, Le Palais des Congrs de Paris, France
A. C. Zawada , N. L. Seed , P. A. Ivey, Continuous and high coverage self-testing of dynamically re-configurable systems, Parallel Computing, v.28 n.7-8, p.1155-1178, August 2002
Apostolos A. Kountouris , Christophe Wolinski, Efficient scheduling of conditional behaviors for high-level synthesis, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.3, p.380-412, July 2002
Alexander G. Dean, Software thread integration for embedded system display applications, ACM Transactions on Embedded Computing Systems (TECS), v.5 n.1, p.116-151, February 2006
VLSI design;high level synthesis;design methodology;design automation