Datapath scheduling with multiple supply voltages and level converters.
We present an algorithm called MOVER (Multiple Operating Voltage Energy Reduction) to minimize datapath energy dissipation through use of multiple supply voltages. In a single voltage design, the critical path length, clock period, and number of control steps limit minimization of voltage and power. Multiple supply voltages permit localized voltage reductions to take up remaining schedule slack. MOVER initially finds one minimum voltage for an entire datapath. It then determines a second voltage for operations where there is still schedule slack. New voltages con be introduced and minimized until no schedule slack remains. MOVER was exercised for a variety of DSP datapath examples. Energy savings ranged from 0% to 50% when comparing dual to single voltage results. The benefit of  going from two to three voltages never exceeded 15%. Power supply costs are not reflected in these savings, but a simple analysis shows that energy savings can be achieved even with relatively inefficient DC-DC converters. Datapath resource requirements were found to vary greatly with respect to number of supplies. Area penalties ranged from 0% to 170%. Implications of multiple voltage design for IC layout and power supply requirements are discussed.
INTRODUCTION
A great deal of current research is motivated by the need for decreased power dissipation
while satisfying requirements for increased computing capacity. In portable
An earlier abbreviated version of this work was reported in the Proceedings of the 1997 IEEE
International Symposium on Circuits and Systems, Hong Kong.
This research was supported in part by ARPA (F33615-95-C-1625), NSF CAREER award
(9501869-MIP), ASSERT program (DAAH04-96-1-0222), IBM, AT&T/Lucent, and Rockwell.
Authors' address: School of Electrical and Computer Engineering Purdue University, West
Lafayette, Indiana, 47907-1285, USA
Permission to make digital or hard copies of part or all of this work for personal or classroom use is
granted without fee provided that copies are not made or distributed for profit or direct commercial
advantage and that copies show this notice on the first page or initial screen of a display along
with the full citation. Copyrights for components of this work owned by others than ACM must
be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on
servers, to redistribute to lists, or to use any component of this work in other works, requires prior
specific permission and/or a fee. Permissions may be requested from Publications Dept, ACM
Inc., 1515 Broadway, New York, NY 10036 USA, fax +1 (212) 869-0481, or permissions@acm.org.
c
1997 by the Association for Computing Machinery, Inc.
systems, battery life is a primary constraint on power. However, even in non-portable
systems such as scientific workstations, power is still a serious constraint
due to limits on heat dissipation.
One design technique that promises substantial power reduction is voltage scaling.
The term "voltage scaling" refers to the trade-off of supply voltage against circuit
area and other CMOS device parameters to achieve reduced power dissipation while
maintaining circuit performance. The dominant source of power dissipation in a
conventional CMOS circuit is due to the charging and and discharging of circuit
capacitances during switching. For static CMOS, the switching power is proportional
to
dd [Rabaey 1996]. This relationship provides a strong incentive to lower
supply voltage, especially since changes to any other design parameter can only
achieve linear savings with respect to the parameter change. The penalty of voltage
reduction is a loss of circuit performance. The propagation delay of CMOS is
approximately proportional to Vdd
[Rabaey 1996], where VT is the transistor
threshold voltage.
A variety of techniques are applied to compensate for the loss of performance
with respect to V dd including reduction of threshold voltages, increasing transistor
widths, optimizing the device technology for a lower supply voltage, and shortening
critical paths in the data path by means of parallel architectures and pipelining.
Data path designs can benefit from voltage scaling even without changes in device
technologies. Algorithm transformations and scheduling techniques can be used to
increase the latency available for some or all data path operations. The increased
latency allows an operation to execute at a lower supply voltage without violating
schedule constraints. "Architecture-Driven Voltage Scaling" is a name applied to
this approach.
A number of researchers have developed systems or proposed methods that incorporate
architecture driven voltage scaling [Chandrakasan et al. 1995; Raghunathan
and Jha 1994; Raghunathan and Jha 1995; Goodby et al. 1994; Kumar et al. 1995;
SanMartin and Knight 1995; Raje and Sarrafzadeh 1995; Gebotys 1995]. HYPER-
LP [Chandrakasan et al. 1995] is a system that applies transformations to the data
flow graph of an algorithm to optimize it for low power. Other systems accept the
algorithm as given and apply a variety of techniques during scheduling, module
selection, resource binding, etc. to minimize power dissipation. All of the systems
mentioned above try to exploit parallelism in the algorithm to shorten critical paths
so that reduced supply voltages can be used. Most systems [Chandrakasan et al.
1995; Raghunathan and Jha 1994; Raghunathan and Jha 1995; Goodby et al. 1994;
Kumar et al. 1995; Gebotys 1995] also minimize switched capacitance in the data
path.
Most voltage scaling approaches require that the IC operate at a single supply
voltage. Although substantial energy savings can be realized with a single minimum
supply voltage, one cannot always take full advantage of available schedule slack
to reduce the voltage. Non-uniform path lengths, a fixed clock period, and a fixed
number of control steps can all result in schedule slack that is not fully exploited.

Figure

provides examples of each type of bottleneck. When there are non-uniform
path lengths, the critical (longest) path determines the minimum supply voltage
even though the shorter path could execute at a still lower voltage and meet timing
constraints. When the clock period is a bottleneck, some operations only use part
of a clock period. The slack within these clock periods goes to waste. Additional
voltages would permit such operations to use the entire clock period. Finally, a fixed
number of control steps (resulting from a fixed clock period and latency constraint)
may lead to unused clock cycles if the sequence of operations does not match the
number of available clock cycles.
A3
Unused
Slack
Unused
Slack
A3
Unused
Slack
Non-Uniform
Path Length
Period
Number of
Control Steps
A3
A4Fig. 1. Examples of scheduling bottlenecks
Literature on multiple voltage synthesis is limited, but this is changing. Publications
that address the topic include [Raje and Sarrafzadeh 1995], [Gebotys
1995], and [Johnson and Roy 1996]. Raje and Sarrafzadeh [Raje and Sarrafzadeh
1995] schedule the data path and assign voltages to data path operators so as to
minimize power given a predetermined set of supply voltages. Logic level conversions
are not explicitly modeled in their formulation. Gebotys [Gebotys 1995] used
an integer programming approach to scheduling and partitioning a VLSI system
across multiple chips operating at different supply voltages. Johnson [Johnson and
Roy 1996] used an integer program to choose voltages from a list of candidates,
schedule datapath operations, model logic level conversions, and assign voltages
to each operation. Chang and Pedram [Chang and Pedram 1996] address nearly
the same problem, applying a dynamic programming approach to optimize non-pipelined
datapaths and a modified list scheduler to handle functionally pipelined
datapaths.
2. DATAPATH SPECIFICATIONS
A datapath is specified in the form of a data flow graph (DFG) where each vertex
represents an operation and each arc represents a data flow or latency constraint.
This DFG representation is similar to the "sequencing graph" representation described
by DeMicheli [DeMicheli 1994] except that hierarchical and conditional
graph entities are not supported.
The DFG is a directed acyclic graph, G(V; E), with vertex set V and edge set
Each vertex corresponds one-to-one with an operator in the data path. Each
edge corresponds one-to-one with a dependency between two operators: a data
flow, a latency constraint, or both. Associated with each vertex is an attribute
that specifies the operator type such as adder, multiplier, or null operation (NO-
OP). Associated with each edge is an attribute that indicates a latency constraint
between the start times of the source and destination operations. A positive value
indicates a minimum delay between operation start times. The magnitude of a
negative value specifies a maximum allowable delay from the destination to the
source. Figure 2 provides a simple example of a datapath specification and defines
elements of the DFG notation.
Maximum Latency
of 1 Sample Period
Data Flow
[Min. Latency Clock Cycles]
Adder
2's Complement
Multiplier
source
sink
Fig. 2. Sample datapath specification and key to notation
Two types of NO-OP's are used which we will refer to as ``transitive'' and "non-
NO-OP's. The term ``transitive'' is used to indicate that a NO-OP
propagates signals without any delay or cost. Neither type of NO-OP introduces
delay or power dissipation. Both serve as vertices in the DFG to which latency
constraints can be attached. The transitive NO-OP is treated as if signals and
their logic levels are propagated through the NO-OP.
3. MOVER SCHEDULING ALGORITHM
MOVER will generate a schedule, select a user specified number of supply voltage
levels, and assign voltages to each operation. MOVER uses an ILP method to evaluate
the feasibility of candidate supply voltage selections, to partition operations
among different power supplies, and to produce a minimum area schedule under
latency constraints once voltages have been selected. The algorithm proceeds in
several phases. First, MOVER determines maximum and minimum bounds on the
time window in which each operation must execute. It then searches for a minimum
single supply voltage. Next, MOVER partitions datapath operations into two
groups: those which will be assigned to a higher supply voltage and those which
will be assigned to a lower supply voltage. The high voltage group is initially fixed
to a voltage somewhat above the minimum single voltage. MOVER then searches
for a minimum voltage for the lower group. The voltage of the lower group is fixed.
A new minimum voltage for the upper group is sought. To find a three supply
schedule, partition the lower voltage group and search for new minimum voltages
for bottom, middle, and upper groups.
3.1 ILP Formulation
At the core of MOVER is an integer linear program (ILP) that is used repeatedly
to evaluate possible supply voltages, partition operations between different power
supplies, and produce a schedule that minimizes resource usage. In each case,
MOVER analyzes the DFG and generates a collection of linear inequalities that
represent precedence constraints, timing constraints, and resource constraints for
the datapath to be scheduled. A weighted sum of the energy dissipation for each
operation is used as the optimization objective when partitioning operations or
evaluating the feasibility of a supply voltage. A weighted sum of resource usage
serves as the optimization objective when minimizing resources. The inequalities
and the objective function are packed into a matrix of coefficients that are fed into
an ILP program solver (CPLEX). MOVER interprets the results from CPLEX and
annotates the DFG to indicate schedule times and voltage assignments.
The architectural model assumed by MOVER is depicted in Figure 3. All operator
outputs have registers. Each operator output feeds only one register. That
register operates at the same voltage as the operator supplying its input. All level
conversions, when needed, are performed at operator inputs.
operator
operator
operator register level
converter
Fig. 3. MOVER architectural model
MOVER's ILP formulation works on a DFG where voltage assignments for some
operations may already be fixed. For operations not already fixed to a voltage, the
formulation chooses between two closely spaced voltages so as to minimize energy.
The voltages are chosen to be close enough together that level conversions from
one to the other can be ignored. Consequently, level conversions only need to be
accounted between operations fixed to different voltages and on interfaces between
fixed and unfixed operations.
3.2 ILP Decision Variables
Three categories of decision variables are used in the MOVER ILP formulation.
One set of variables of the form x i;l;s indicates the start time and supply voltage
assignment for each operator that has not already been fixed to a particular supply
voltage. x begins execution on clock cycle l
using supply voltage s. Under any other condition, x i;l;s will equal zero. The
supply voltage selection is limited to two values where selects the lower and
selects the higher candidate voltage. Another set of variables, x i;l , indicates
the start time of operations for which the supply voltage has been fixed. x
indicates that operation i starts at clock cycle l. Under any other condition, x i;l will
equal zero. The last group of variables, a m;s , indicates the allocation of operator
resources to each possible supply voltage. a m;s will be greater than or equal to the
number of resources of type m that are allocated to supply voltage s. In this case,
s can be an integer in the range (1; # fixed supplies corresponds to
the new candidate supply voltages. s ? 2 corresponds to supply voltages that have
already been fixed.
3.3 Objective Functions
The objective function (equation 1) estimates the energy required for one execution
of the data path as a function of the voltage assigned to each operation. Consider
the energy expression split into two parts. The first nested summation counts the
total energy contribution associated with operations not already fixed to a supply
voltage. The second nested summation counts the total energy contribution of
operations that are already fixed to a particular supply voltage.
For each operation j that has not been fixed to a supply voltage (e.g.,
the first nested summation accumulates the energy of operation j (onrg(j; s
the register at the output of operation j (rnrg(s j ; fanout j )), and any level conversions
required at the input to is the index of the supply
voltage assigned to operation j. fanout j is the fanout capacitive load on operation
j. c reg is the input capacitance of a register to which the operation output
is connected. The decision variables x j;l;s are used to select which lookup table
values for operator, register, and level conversion energy are added into the total
energy. We must sum over both candidate supply voltages s j and all clock cycles l
in the possible execution time window R j of operation j. E conv is the set of DFG
arcs that may require a level conversion, depending on voltage assignments. V oper
is the set of DFG vertices that are not NO-OPs. V fix is the set of DFG vertices
(operations) that have been fixed to a particular voltage. V free is the set of vertices
that have not previously been fixed to a voltage.
For each operation j that has been fixed to a supply voltage, we again accumulate
the energy of each operation, register, and level conversion. The only difference
from the expression for free operations is that now all voltages in the expression
are constants determined prior to solving the ILP formulation. Consequently, the
index s j can be removed from the summation and the decision variable x.
j2Vfree "Voper
x j;l;s \Theta
j2Vfix "Voper
x j;l \Theta
conversion energy at the input
of free and fixed operations respectively. c in i
is the input capacitance of operation
i.
ij(i;j)2Econv and i2Vfix
ij(i;j)2Econv and i2Vfree
cnrg fix
ij(i;j)2Econv and i2Vfix
ij(i;j)2Econv and i2Vfree
Equation 4 is the objective function used when minimizing resource usage. Here,
a m;s indicates the minimum number of operators of type m with supply voltage s
needed to implement a datapath. Each operation of type m is considered to have an
area of aream . M oper represents the set of all operation types excluding NO-OPs.
The summation accumulates an estimate of the total circuit resources required to
implement a datapath.
m2Moper
aream \Theta a m;s (4)
3.4 ILP Constraint Inequalities
Equation 5 guarantees that only one start time l is assigned to each operation i
for which the supply voltage is already fixed. Equation 6 guarantees that only one
start time l and supply voltage s can be assigned to each operation i that does not
have a supply voltage assignment.
Equation 7 guarantees that the voltage of a transitive NO-OP j matches the
voltage of all operations supplying an input to the transitive NO-OP. V trnoop is the
set of vertices in the DFG corresponding to transient NO-OP's. E is the set of all
arcs in the DFG.
l
Equation 8 enforces precedence constraints specified in the DFG. Simplified versions
of the constraint can be used if the source or destination operations are fixed to
a voltage. This constraint is an adaptation of the structured precedence constraint
shown by Gebotys [Gebotys 1992] to produce facets of the scheduling polytope.
Each arc (i; j) with a latency lat i;j - 0 specifies a minimum latency from the start
of operation i to the start of operation j. Equation 8 defines the set of precedence
constraint inequalities corresponding to DFG arcs where the source and destination
operations are both free (not fixed to a voltage). Simplified versions of this
constraint are used when source or destination operations are fixed to a voltage.X
del i;s i +l
l 1 =0
l 2 =l
Equation 9 enforces maximum latency constraints specified in the DFG. Each
arc (i; j) with a latency lat i;j ! 0 specifies a maximum delay from operation j to
operation i. Equation 9 defines the set of maximum latency constraint inequalities
corresponding to arcs where the source and destination operations are both
fixed to a voltage). Simplified versions of this constraint are used when
source or destination operations are fixed to a voltage. The remaining equations
are simplifications of equation 9.X
l 2 =l\Gammalat i;j +1
Equations 10 and 11 ensure that resource usage during each time step does not
exceed the resource allocation given by a m;s . The expressions on the left computes
the number operations of type m with supply voltage s that are executing concurrently
during clock cycle l. a m;s indicates the number of type m resources that have
been allocated to supply voltage s. Equation 10 enforces the resource constraint
enforces the constraint for fixed operations. Free
operations are allowed to take on one of two candidate voltages. These resource
constraints can be easily modified to support functional pipelining with a sample
period of l samp by combining the left hand sides for l, l
l
l 1 =l\Gammadel i;s i +1
- a m;s i
l
l 1 =l\Gammadel i;s i +1
- a m;s i (11)
Table

I. Voltage search algorithm
1. Choose starting voltages V2 and
2. Create matrix of ILP constraint inequalities.
3. Obtain minimum energy solution to inequalities.
The solution will provide a schedule, a mapping of V1 or V2 to each
operator, an energy estimate, and an area estimate for the datapath.
4a. If a solution was found, then
If most operations were assigned to V1 , then
Choose new candidate voltages midway between V1 and V lo .
Go to step 2.
else
There must be little or no benefit to assigning operations to V1
Fix all operations to V2
4b. else (if the problem was infeasible)
Choose new candidate voltages midway between V2 and Vhi .
Go to step 2.
Equation 12 enforces the user specified resource constraints. maxres(m) represents
the total number of resources of type m (regardless of voltage) that can be
permitted. The left side expression accumulates the number of resources of type m
that have been allocated to all supply voltages. The total is not allowed to exceed
the user specified number of resources.
a m;s - maxres(m) 8m 2 M oper (12)
3.5 Voltage search
MOVER searches a continuous range of voltages when seeking a minimum voltage
one, two, or three power supply design. The user must specify a convergence
threshold V conv that is used to determine when a voltage selection is acceptably
close to minimum. Let V hi and V lo represent the current upper and lower bound
on the supply voltage.
When searching for a minimum single supply voltage, all operations are initially
considered to be free (not fixed to a voltage). When searching for a minimum set of
two or three supply voltages, MOVER considers one power supply at a time. The
voltage will be fixed for any operations not allocated to the supply voltage under
consideration. Table I outlines the voltage search algorithm.
3.6 Partitioning
Partitioning is the process by which MOVER takes all free operations in the DFG
and allocates each to one of two possible power supplies. Partitioning is not performed
until a single minimum supply voltage is known for the group of operations.
supply voltage for the free operations. Choose two
candidate supply voltages (V a and V b ) one slightly above V 1 and the other slightly
below.
Set up the ILP constraint inequalities. Obtain a minimum energy schedule.
Operations will only be assigned to V a if there is schedule slack available. There
may be several ways that the operations can be partitioned. In such a case, the
optimal ILP solution will maximize the energy dissipation of the lower voltage group
(i.e., put the most energy hungry operations in the lower voltage group). This will
tend to maximize the benefit from reducing the voltage of the lower group.
Given a successful partition, operations assigned to V a will be put into the lower
supply voltage group and operations assigned to V b will be put into the higher
supply voltage group.
The partition will fail if all operations are allocated to the lower supply voltage,
all operations are allocated to the higher supply voltage, or the ILP solver exceeds
some resource limit. The first situation indicates that the minimum single voltage
could be a bit lower. In this event, MOVER lowers the values of V a and V b by Vconvand tries the partition again. Lowering V a and V b too far leads to a completely
infeasible ILP problem. The second situation indicates that there is not enough
schedule slack available for any operations to bear a further reduction in voltage.
In this case, MOVER terminates. The only remedies for the third situation are
to either increase resource and time limits on the ILP solver or make the problem
smaller.
4. CHARACTERIZATION OF DATAPATH RESOURCES
The results presented in this paper make use of four types of circuit resources: an
adder, multiplier, register, and level converter. MOVER requires models of the
energy and delay of each type of resource as a function of supply voltage, load
capacitance, and average switching activity. Each type of resource was simulated
in HSPICE using 0.8 micron MOSIS library models with the level 3 MOS model.
Energy dissipation, worst case delay, and input capacitances were measured from
the simulation. All resources were 16 bits wide. Load capacitance on each output
was 0.1pF. Input vectors were generated to provide 50% switching activities.
4.1 Datapath operators and registers
During optimization, operation energies and delays are scaled as a function of the
voltage assignment being evaluated. Energy dissipation (E) for each operator and
register scales with respect to supply voltage as
Table

II. Nominal energy and delay values used by MOVER
Resource Energy d
dC Energy Delay d
Delay Cin
Type [pJ] [pJ/pF] [ns] [ns/pF] [pF]
ADDER 84 200 12.0 3.5 0.021
MULTIPLIER 2966 200 18.5 3.33 0.095
REGISTER 312 200 0.48 2.25 0.045
is the energy dissipation of the operator or register measured at the
nominal supply voltage V 0 .
Delay each operator and register scale with respect to supply voltage as
\Theta
where t p0 is the propagation delay measured at the nominal supply voltage V 0 .
The energy and delay scaling factors were derived directly from the CMOS energy
and delay equations described by Rabaey [Rabaey 1996]. Energy and delay are also
scaled linearly with respect to the estimated load capacitance on output signals.

Table

II gives the model parameters used by MOVER for each type of resource.
Note that the register delay given here is just the propagation time relative to a
clock edge. Register setup time is treated as part of the datapath operator delays.
4.2 Level conversion
Whenever one resource has to drive an input of another resource operating at a
higher voltage, a level conversion is needed at the interface. Four alternatives were
considered to accomplish this: omit the level converter, use a chain of inverters
at successively higher voltages, use an active or passive pullup, or use a differential
cascode voltage switch (DCVS) circuit as a level converter [Chandrakasan
et al. 1994; Usami and Horowitz 1995]. We omit the level converter for step-down
conversions and use the DCVS circuit for step-up conversions. Given appropriate
transistor sizes, this circuit exhibits no static current paths and it can operate over
a full 1.5V to 5.0V range of input and output supply voltages.
A model was needed that could accurately indicate the power dissipation and
propagation delay of the DCVS level converter as a function of the input logic
supply voltage V 1 , output logic supply voltage V 2 , and load capacitance. The circuit
was studied both analytically and from HSPICE simulation results to determine
a suitable form for the model equations. Coefficients of the equations were then
calibrated so that the model equations would produce families of curves closely
matching simulation results for V 1 ranging from 1:5V to 5V and
These are the ranges of supply voltages for which a level converter is needed. Typical
energy dissipation of the level converter was found to be on the order of 5 to 15pJ
per switching event per bit, given a 0.1pF load. Typical propagation delays range
were approximately 1ns for level conversions such as 3.3V to 5V or 2.4V to 3.3V.
Propagation delays become large as the input voltage of the level converter falls
towards 2V T . A 2.5V to 5V conversion had a delay of about 2.5ns. A 2V to 5V
conversion had a delay of nearly 5ns.
All transistors 0.8u length
and 4.0u width except where
noted
M2N
M3N
M1N
IN
Fig. 4. DCVS Level Converter
5. RESULTS
5.1 Datapath examples
ILP schedule optimization results are presented for six example data paths: a four
point FFT (FFT4), the 5th order elliptic wave filter benchmark (ELLIP) [Rao
1992], a 6th order Auto-Regressive Lattice filter (LATTICE), a frequency sampled
filter (FSAMP) with three 2nd order stages and one 1st order stage, a direct form
9 tap linear phase FIR filter (LFIR9), and a 5th order state-space realization of an
IIR filter (SSIIR). In the FFT data path, complex signal paths are split into real
and imaginary data flows. For all other data paths, the signals are modeled as non-complex
integer values. All data flows were taken to be 16 bits wide. Switching
activities at all nodes were assumed to be 50%, i.e., the probability of a transition
on any selected 1 bit signal is 50% in any one sample interval.
Each example was modeled for one sample period with data flow and latency
constraints specified for any feedback signals. Any loops that start and finish
within the same sample period were completely unrolled. Any loops spanning
multiple sample periods were broken. A data flow passing from one sample period
to the next was represented by input and output nodes in the DFG connected by
a backward arc to specify a maximum latency constraint from the input to the
output. A 20ns clock was specified for all examples. Latency constraints were
specified so that the data introduction interval equals the maximum delay from the
input to the output of the data path.
5.2 MOVER Results

Figure

presents energy reduction results. The left-most column identifies the
particular datapath topology and indicates the number of operations (additions,
Name Lat/Clks +/x 1 2 3 [min]
Datapath Max Max Voltages Exec(host) Min Lat.,Unlim. Resources
Energy ratio vs. 1 supply,
Energy
adds NR NR - 0.27(1)
2.3 3.6 - 0.23(1) 1144
2.3 3.6 0.40(1) 1148
2.3 3.6 - 0.48(1) 1233
1.9 2.4 3.6 0.72(1) 1235
26 adds 2.3 3.6 - 1.53(2) 2206
1.9 2.4 3.6 2.65(2) 2181
2.3 3.6 - 3.43(2) 1631
1.9 2.4 3.6 5.30(2) 1600
2.3 3.6 - 3.77(2) 1963
NR NR NR 6.02(2)
2.3 3.6 - 50.6(2) 1237
NR NR NR 101.(2)
adds 3.5 4.9 - 0.72(2) 13904
mults 3.0 3.5 4.9 1.40(2) 12538
NR NR NR 4.10(2)
3.0 3.5 4.9 6.88(2) 14342
2.3 3.0 3.6 59.9(2) 8480
14 adds 4.2 4.8 - 2.28(1) 15882
9 mults NR NR NR 4.57(1)
38 del 11/11 - 3.6 - 2.10(1) 8828
2.4 3.0 3.6 8.85(1) 5401
2.3 3.0 3.6 9.82(1) 6263
2.4 3.0 - 6.00(1) 5768
1.6 3.0 3.0 9.60(1) 6191
8 adds 3.5 4.9 - 0.72(1) 6344
5 mults 3.0 3.5 4.9 1.38(1) 5683
8 del 8/8 - 3.6 - 0.43(1) 4923
2.3 3.6 - 0.98(1) 2415
2.3 3.0 3.6 1.48(1) 3434
2.4 3.0 - 1.47(1) 3213
1.6 3.0 3.1 2.37(1) 3717
adds 3.0 4.9 - 0.52(1) 15770
mults NR NR NR 0.83(1)
2.4 3.0 3.6 4.67(1) 6250
NR NR NR 1.25(1)
Fig. 5. Multi-voltage Energy Savings
multiplications, and sample period delays) performed in one iteration of the data-
path. "Max Lat/Clks" specifies the maximum latency (equal to the data sample
rate) and the maximum number of control steps (Clks), both given in terms of the
number of clock cycles. "Max +/-" specifies the maximum numbers of adder and
multiplier circuits permitted in the design. Values of "-" indicate that unlimited
resources were permitted. The columns headed by "Voltages 1 2 3" indicate
the supply voltages selected by MOVER. A "-" is used to fill voltage columns "2"
or "3" in those cases where a one or two supply voltage result is presented. The
string "NR" in voltage columns "1" and "2" indicates that a solution with two
supply voltages could not be obtained. "NR" in all three columns indicates that a
solution with three supply voltages could not be obtained. The "Exec" column reports
the minutes of execution time (Real, not CPU) required to obtain the result.
The number in parenthesis identifies the type of machine used to obtain the result.
"(1)" indicates a SPARCserver 1000 with 4 processors and 320MB of RAM. "(2)"
indicates a Sparc 5 with 64MB of RAM.
The bar graph down the center represents the normalized energy consumption of
each test case. Each energy result is divided by the single supply voltage, unlimited
resource, minimum latency result to obtain a normalized value. Single supply
voltage results are shown with black bars. All other results are shown in gray. This
style of presentation is intended to visually emphasize the effect of different latency,
resource, and supply voltage constraints on the energy estimate. The right-most
column presents the absolute energy estimate in units of

Figure

6 presents area penalty results. All but two columns have the same meaning
as the corresponding columns in figure 5. The only exceptions are the bar graph
and the "area" column on the right. The "area" value is a weighted sum of the minimum
circuit resources required to implement the datapath schedule. The resources
(all bits wide) were weighted as follows: adder=1, multiplier=16, register=0.75,
and level converter=0.15. These weights are proportional to the transistor count
of each resource. Each area value was divided by the area estimate for the corresponding
single voltage result. Each single voltage result is shown as a black bar.
Two and three voltage results are shown in gray.
5.3 Observations
The preceding results permit several observations to be made regarding the effect
of latency, circuit resource, and supply voltage constraints on energy savings, area
costs, and execution time. Because our primary objective has been to minimize
energy dissipation through use of multiple voltages, we are especially interested in
the comparison of multiple supply voltage results to minimum single supply voltage
results. Energy savings ranging from 0% to 50% were observed when comparing
multiple to single voltage results. Estimated area penalties ranged from a slight
improvement to a 170% increase in area. Actual area penalties could be higher,
since our estimate only considers the number of circuit resources used. There is
not a clear correlation between energy savings and area penalty when looking at
the complete set of results. Sometimes a substantial energy savings was achieved
with minimal increased circuit resources, other times even a small energy savings
incurred a large area cost.
Name Lat/Clks +/x 1 2 3
Area ratio vs. 1 supply [adder=1]
Area
adds NR NR -
2.3 3.6 - 30.4
2.3 3.6 30.4
2.3 3.6 - 22.8
1.9 2.4 3.6 22.8
4/4 12/- 2.3 - 14
26 adds 2.3 3.6 - 12.65
1.9 2.4 3.6 12.8
2.3 3.6 - 13.3
1.9 2.4 3.6 16.9
2.3 3.6 - 12.85
1.9 2.4 3.6
2.3 3.6 - 11.8
1.9 2.4 3.6
adds 3.5 4.9 - 88.8
mults 3.0 3.5 4.9 89.85
NR NR NR
3.0 3.5 4.9 39.1
2.3 3.0 3.6 41.85
14 adds 4.2 4.8 - 136.2
9 mults NR NR NR 169.4
38 del 11/11 - 3.6 - 83.75
2.4 3.0 3.6 120.15
2.3 3.0 3.6 89.95
2.4 3.0 - 88.2
1.6 3.0 3.0 90.1
8 adds 3.5 4.9 - 94.8
5 mults 3.0 3.5 4.9 98.1
8 del 8/8 - 3.6 - 42.75
2.3 3.6 - 87.3
2.3 3.0 3.6 47
2.4 3.0 - 45.55
1.6 3.0 3.1 47.3
adds 3.0 4.9 - 174
mults NR NR NR
2.4 3.0 3.6 181.75
NR NR NR
Fig. 6. Multi-voltage Area Penalties
If we consider the impact of latency constraints alone, effects on area and energy
are easier to observe. In most cases, multiple voltage area penalties were greatest
for the minimum latency unlimited resource test cases. We can also observe that
increasing latency constraints always led to the same or lower energy for a given
number of supply voltages. However, the effect of latency constraints on the single
vs. multiple voltage trade-off varied greatly from one example to another. Results
for multiple voltages are most favorable in situations where the single supply voltage
solution did not benefit from increased latency, perhaps due to a control step
bottleneck such as illustrated earlier in figure 1.
The effect of resource constraints on energy savings are also relatively easy to
observe. Not surprisingly, resource constraints tended to produce the lowest area
penalties. The only reason for any area penalty at all in the resource constrained
case is that sometimes the minimum single supply solution does not require all of
the resources that were permitted. Energy estimates based on resource constrained
schedules were consistently the same or higher than estimates based on unlimited
resource schedules.
The results presented previously do not include energy or area costs associated
with multiplexers that would be required to support sharing of functional units
and registers. However, an analysis of multiplexer requirements for most of these
schedules indicated that multiplexers would not have changed the relative trade-off
between number of voltages, energy dissipation, and circuit area. In a few cases
the energy and area costs were increased substantially (up to 50% for energy and
108% for area), but the comparison between one, two, and three voltages was always
either similar to the earlier results or shifted somewhat in favor of multiple voltages.
The maximum energy savings was 54%, and the average was 32% when comparing
two supply voltages to one. The maximum area penalty was 132% and the average
was 42%. Results for three supply voltages, at best, were only slightly better than
the two supply results.
Multiplexer costs were estimated in the following manner. A simple greedy algorithm
was used to assign a functional unit to each operation and a register to
each data value. Given this resource binding, we determined the fan-in to each
functional unit and register. Assuming a pass-gate multiplexer implementation, we
estimated worst case capacitance on signal paths, total gate capacitance switched
by control lines, and relative circuit area as a function of the fan-in and data bus
width. A single pass gate, turned on, was estimated to add a 5fF load to each data
input bit and 5fF to the control inputs of a multiplexer. The circuit area for a pass
gate was taken to be 0:07\Theta (the area of one bit slice of a full adder). Multiplexer
capacitances and area were added to the costs already used by MOVER. MOVER
was then used to generate a new datapath schedule that accounts for these costs. In
some cases, supply voltages had to be elevated slightly relative to previous results
in order to compensate for increased propagation delays.
6. DESIGN ISSUES
There are several design issues that a designer will need to take into consideration
when a multiple voltage design is targeted for fabrication. In particular, the effects
of multiple voltage operation on IC layout and power supply requirements should
be considered. In this section, we will discuss the issues and identify improvements
that would allow MOVER to more completely take them into account.
6.1 Layout
Following are some ways that multiple voltage design may affect IC layout.
(1) If the multiple supplies are generated off-chip, additional power and ground
pins will be required.
(2) It may be necessary to partition the chip into separate regions, where all operations
in a region operate at the same supply voltage.
(3) Some kind of isolation will be needed between regions operated at different
voltages.
There may be some limit on the voltage difference that can be tolerated between
regions.
Protection against latch-up may be needed at the logic interfaces between regions
of different voltage.
design rules for routing may be needed to deal with signals at one voltage
passing through a region at another voltage.
Isolation requirements between different voltage regions can probably be adequately
addressed by increased use of substrate contacts, separate routing of power
and ground, increased minimum spacing between routes (for example, between one
signal having a 2V swing and another with a 5V swing), and slightly increased
spacing between wells. While these practices will increase circuit area somewhat,
the effect should be small in comparison to increased circuitry (adders, multipliers,
registers, etc.) needed to support parallel operations at reduced supply voltages.
Area for isolation will be further mitigated by grouping together resources at a particular
voltage into a common region. Isolation is then only needed at the periphery
of the region.
Some of these layout issues can be incorporated into multiple voltage scheduling.
Perhaps the greatest impact will be related to grouping operations of a particular
supply voltage into a common region. Closely intermingled operations at different
voltages could lead to complex routing between regions, increased need for level
conversions, and increased risk of latch-up. Assigning highly connected operations
to the same voltage could not only improve routing, but should also lead to fewer
voltage regions on the chip, less space lost to isolation between voltage regions, and
fewer signals passing between regions operating at different voltages.
6.2 Circuit Design
There are some circuit design issues that still need to be addressed by MOVER
including alternative level converter designs and control logic design.
Alternative level converter designs such as the combined register and level converter
should be considered. The DCVS converter design considered in this paper
does not exhibit static power consumption, but short circuit energy is a problem.
Delays and energy also increase greatly as the input voltage to the level converter
becomes small.
MOVER makes assumptions about datapath control and clocking that are convenient
for scheduling and energy estimation, but will require support from the
control logic. It is assumed that the entire control of the datapath is accomplished
through selective clocking of registers and switching of multiplexers. This will require
specially gated clocks for each register.
6.3 Power Supplies
Before implementing a multiple voltage datapath, some decisions must be made
regarding the voltages that can be selected and the type of power supply to be
used. Regarding voltage selection, we must decide how many supplies to use and
determine whether or not non-standard voltages are acceptable. Regarding the type
of power supply, we will only consider the choice between generating the voltage
on-chip or off-chip. All of these choices will depend largely on the application. If
on chip heat dissipation is a primary constraint, voltages would be generated off
chip and DC-DC conversion efficiency would be a low priority. If battery life is the
bottleneck, DC-DC conversion efficiency will determine whether or not multiple
voltages will reap an energy savings.
A simple analysis provides some insight into the conditions under which a new
supply voltage could be justified. In a battery powered system, we would need a
DC to DC converter to obtain the new voltage. Let - represent the efficiency of
the DC to DC converter. The efficiency can be most easily described as the power
output to the datapath divided by the power input to the DC-DC converter.
This model does not explicitly represent the effect of the amount of loading or
choice of voltages on converter efficiency. For now, we are only trying to determine
the degree of converter efficiency needed in order to make a new supply voltage
viable. Conversely, given a DC-DC converter of known efficiency, we want to know
how much voltage reduction is needed to justify use of the converter.
Let ff represent the fraction of switched capacitance in the datapath that will
be allocated to the new supply voltage. V 1 represents the primary supply voltage.
represents the new reduced supply voltage under consideration. E 1 represents
the energy dissipation of the datapath operating with the single supply voltage V 1 .
The energy E 1 can be split into a portion, ff representing the circuitry that will
run at voltage V 2 , and a remaining portion will continue to run at
When the new supply voltage V 2 is introduced, the first term in equation
be scaled by the factor V 2V 2. The new datapath energy dissipation (ignoring DC-DC
becomes:
However, the energy lost in the DC-DC converter equals the energy of the circuitry
operating at V 2 divided by the efficiency of the converter.
A bit of algebraic manipulation will reveal the system energy savings (including
converter losses) as a function of ff, -, V 1 , and V 2 .
lost
Consider a simple example. Let
Suppose 60% of the circuit can operate at voltage V 2 . Given an ideal DC-DC
converter, the energy savings would be 36%. However, when the converter efficiency
is considered, the savings drops more than a half to 17%. The break-even point
occurs when 2. For the last example, the converter efficiency has to be at
least 41% to avoid losing energy. In practice, the break-even point will be somewhat
higher due to logic level conversions that will be required within the datapath.
The preceding analysis suggests that a DC to DC converter does not have to be
exceedingly efficient in order to achieve energy savings. Had the voltage reduction
been merely from 3.3V to 3.0V, DC-DC converter efficiency would have to be at least
83%. Converter designs are available that easily exceed this efficiency requirement.
Stratakos et al. [Stratakos et al. 1994] designed a DC-DC converter that achieves
better than 90% efficiency for a 6V to 1.5V voltage reduction.
7. CONCLUSIONS
In this paper we have presented MOVER, a tool which reduces the energy dissipation
of a datapath design through use of multiple supply voltages. An area
estimate is produced based on the minimum number of circuit resources required
to implement the design. One, two, and three supply voltage designs are generated
for consideration by the circuit designer. The user has control over latency
constraints, resource constraints, total number of control steps, clock period, voltage
range, and number of power supplies. MOVER can be used to examine and
trade-off the effects of each constraint on the energy and area estimates.
MOVER iteratively searches the voltage range for minimum voltages that will be
feasible in a one, two, and three supply solution. An exact ILP formulation is used
to evaluate schedule feasibility for each voltage selection. The same ILP formulation
is used to determine which operations are assigned to each power supply.
MOVER was exercised for six different datapath specifications, each subjected
to a variety of latency, resource, and power supply constraints for a total of 70
test cases. The test cases were modest in size, ranging from 13 to 26 datapath
operations and 2 to 24 control steps. The results indicate that some but not all
datapath specifications can benefit significantly from use of multiple voltages. In
many cases, energy was reduced substantially going from one to two supply voltages.
Improvements as much as 50% were observed, but 20-30% savings were more typical.
Adding a third supply produced relatively little improvement over two supplies, 15%
improvement at most. Results from MOVER are comparable and in many cases
better than results obtained using the MESVS (Minimum Energy Scheduling with
Voltage Selection) ILP formulation presented in [Johnson and Roy 1996]. Behavior
with respect to latency, resource, and supply voltage constraints is similar between
MOVER and MESVS. The improvement relative to a pure ILP formulation is due
to the fact that ILP formulation could only select from a discrete set of voltages,
whereas MOVER can select from a continuous range of voltages.

ACKNOWLEDGMENTS

We would like to thank James Cutler for his programming work, the low power
research group at Purdue, and the anonymous reviewers for their critiques.



--R

Optimizing power using transformations.
Design of portable systems.
Energy minimization using multiple supply voltages.
Synthesis and Optimization of Digital Circuits.
Optimal VLSI Architectural Synthesis: Area
An ILP model for simultaneous scheduling and partitioning for low power system mapping.
Microarchitectural synthesis of performance-constrained
Optimal selection of supply voltages and level conversions during data path scheduling under resource constraints.

Digital integrated circuits
Behavioral synthesis for low power.
An iterative improvementalgorithm for low power data path synthesis.
Variable voltage scheduling.
The fifth order elliptic wave filter benchmark.


Clustered voltage scaling technique for low-power design
--TR
Optimal VLSI architectural synthesis
Power-profiler
Clustered voltage scaling technique for low-power design
Variable voltage scheduling
An iterative improvement algorithm for low power data path synthesis
Digital integrated circuits
Energy minimization using multiple supply voltages
Synthesis and Optimization of Digital Circuits
Profile-Driven Behavioral Synthesis for Low-Power VLSI Systems
Optimal Selection of Supply Voltages and Level Conversions During Data Path Scheduling Under Resource Constraints
Behavioral Synthesis for low Power
Microarchitectural Synthesis of Performance-Constrained, Low-Power VLSI Designs

--CTR
Saraju P. Mohanty , N. Ranganathan , Sunil K. Chappidi, Simultaneous peak and average power minimization during datapath scheduling for DSP processors, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA
Tohru Ishihara , Hiroto Yasuura, Voltage scheduling problem for dynamically variable voltage processors, Proceedings of the 1998 international symposium on Low power electronics and design, p.197-202, August 10-12, 1998, Monterey, California, United States
Ling Wang , Yingtao Jiang , Henry Selvaraj, Scheduling and optimal voltage selection with multiple supply voltages under resource constraints, Integration, the VLSI Journal, v.40 n.2, p.174-182, February, 2007
Ali Manzak , Chaitali Chakrabarti, A low power scheduling scheme with resources operating at multiple voltages, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.10 n.1, p.6-14, 2/1/2002
Ling Wang , Yingtao Jiang , Henry Selvaraj, Scheduling and Partitioning Schemes for Low Power Designs Using Multiple Supply Voltages, The Journal of Supercomputing, v.35 n.1, p.93-113, January   2006
Dongxin Wen , Ling Wang , Yingtao Jiang , Henry Selvaraj, Power optimization for simultaneous scheduling and partitioning with multiple voltages, Proceedings of the 7th WSEAS International Conference on Mathematical Methods and Computational Techniques In Electrical Engineering, p.156-161, October 27-29, 2005, Sofia, Bulgaria
Ashok Kumar , Magdy Bayoumi , Mohamed Elgamel, A methodology for low power scheduling with resources operating at multiple voltages, Integration, the VLSI Journal, v.37 n.1, p.29-62, February 2004
Amitabh Menon , S. K. Nandy , Mahesh Mehendale, Multivoltage scheduling with voltage-partitioned variable storage, Proceedings of the international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea
Woo-Cheol Kwon , Taewhan Kim, Optimal voltage allocation techniques for dynamically variable voltage processors, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
Saraju P. Mohanty , N. Ranganathan , Sunil K. Chappidi, ILP models for simultaneous energy and transient power minimization during behavioral synthesis, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.1, p.186-212, January 2006
Inki Hong , Miodrag Potkonjak , Mani B. Srivastava, On-line scheduling of hard real-time tasks on variable voltage processor, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.653-656, November 08-12, 1998, San Jose, California, United States
Inki Hong , Darko Kirovski , Gang Qu , Miodrag Potkonjak , Mani B. Srivastava, Power optimization of variable voltage core-based systems, Proceedings of the 35th annual conference on Design automation, p.176-181, June 15-19, 1998, San Francisco, California, United States
Ling Wang , Yingtao Jiang , Henry Selvaraj, Multiple voltage synthesis scheme for low power design under timing and resource constraints, Integrated Computer-Aided Engineering, v.12 n.4, p.369-378, October 2005
Shaoxiong Hua , Gang Qu, Approaching the Maximum Energy Saving on Embedded Systems with Multiple Voltages, Proceedings of the IEEE/ACM international conference on Computer-aided design, p.26, November 09-13,
Woo-Cheol Kwon , Taewhan Kim, Optimal voltage allocation techniques for dynamically variable voltage processors, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.1, p.211-230, February 2005
Gang Qu, What is the limit of energy saving by dynamic voltage scaling?, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
Hsueh-Chih Yang , Lan-Rong Dung, On multiple-voltage high-level synthesis using algorithmic transformations, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
Deming Chen , Jason Cong , Yiping Fan , Junjuan Xu, Optimality study of resource binding with multi-Vdds, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
Saraju P. Mohanty , N. Ranganathan, Energy-efficient datapath scheduling using multiple voltages and dynamic clocking, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.2, p.330-353, April 2005
Deming Chen , Jason Cong , Junjuan Xu, Optimal module and voltage assignment for low-power, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
Liqiong Wei , Zhanping Chen , Mark Johnson , Kaushik Roy , Vivek De, Design and optimization of low voltage high performance dual threshold CMOS circuits, Proceedings of the 35th annual conference on Design automation, p.489-494, June 15-19, 1998, San Francisco, California, United States
Deming Chen , Jason Cong , Junjuan Xu, Optimal simultaneous module and multivoltage assignment for low power, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.2, p.362-386, April 2006
Krishnan Srinivasan , Karam S. Chatha, Integer linear programming and heuristic techniques for system-level low power scheduling on multiprocessor architectures under throughput constraints, Integration, the VLSI Journal, v.40 n.3, p.326-354, April, 2007
Diana Marculescu , Anoop Iyer, Application-driven processor design exploration for power-performance trade-off analysis, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
DSP;low power design;multiple voltage;datapath scheduling;power optimization;scheduling;high-level synthesis;level conversion