Power optimization using divide-and-conquer techniques for minimization of the number of operations.
We develop an approach to minimizing power consumption of portable wireless DSP applications using a set of compilation and architectural techniques. The key technical innovation is a novel divide-and-conquer compilation technique to minimize the number of operations for general DSP computations. Our technique optimizes not only a significantly wider set of computations than the previously published techniques, but also outperforms (or performs at least as well as other techniques) on all examples. Along the architectural dimension, we investigate coordinated impact of compilation techniques on the number of processors which provide optimal trade-off between cost and power. We demonstrate that proper compilation techniques can significantly reduce power with bounded hardware cost. The effectiveness of all techniques and algorithms is documented on numerous real-life designs.
INTRODUCTION
1.1 Motivation
The pace of progress in integrated circuits and system design has been dictated by
the push from application trends and the pull from technology improvements. The
goal and role of designers and design tool developers has been to develop design
methodologies, architectures, and synthesis tools which connect changing worlds of
applications and technologies.
A preliminary version of this paper was presented at the 1997 ACM/IEEE International Conference
on Computer-Aided Design, San Jose, California, November 10-13, 1997.
Authors' addresses: I. Hong and M. Potkonjak, Computer Science Department, University of Cali-
fornia, Los Angeles, CA 90095-1596; R. Karri, Department of Electrical & Computer Engineering,
University of Massachusetts, Amherst, MA 01003.
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.
Recently, a new class of portable applications has been forming a new market
at an exceptionally high rate. The applications and products of portable wireless
market are defined by their intrinsic demand for portability, flexibility, cost sensitivity
and by their high digital signal processing (DSP) content [Schneiderman 1994].
Portability translates into the crucial importance of low power design, flexibility
results in a need for programmable platforms implementation, and cost sensitivity
narrows architectural alternatives to a uniprocessor or an architecture with a limited
number of off-the-shelf standard processors. The key optimization degree of
freedom for relaxing and satisfying this set of requirements comes from properties
of typical portable computations. The computations are mainly linear, but rarely
100 % linear due to either need for adaptive algorithms or nonlinear quantization
elements. Such computations are well suited for static compilation and intensive
quantitative optimization.
Two main recent relevant technological trends are reduced minimal feature size
and therefore reduced voltages of deep submicron technologies, and the introduction
of ultra low power technologies. In widely dominating digital CMOS technologies,
the power consumption is proportional to square of supply voltage (V dd ). The most
effective techniques try to reduce V dd while compensating for speed reduction using
a variety of architectural and compilation techniques [Singh et al. 1995].
The main limitation of the conventional technologies with respect to power minimization
is also related to V dd and threshold voltage (V t ). In traditional bulk silicon
technologies both voltages are commonly limited to range above 0.7V. However, in
the last few years ultra low power silicon on insulator (SOI) technologies, such as
SIMOX (SOI using separation of oxygen), bond and etchback SOI (BESOI) and
silicon-on-insulator-with-active-substrate (SOIAS), have reduced both V dd and V t
to well below 1V [El-Kareh et al. 1995; Ipposhi et al. 1995]. There are a number
of reported ICs which have values for V dd and V t in a range as low as 0.05V - 0.1V
[Chandrakasan et al. 1996].
Our goal in this paper is to develop a system of synthesis and compilation methods
and tools for realization of portable applications. Technically restated, the primary
goal is to develop techniques which efficiently and effectively compile typical
DSP wireless applications on single and multiple programmable processors assuming
both traditional bulk silicon and the newer SOI technologies. Furthermore, we
study achievable power-cost trade-offs when parallelism is traded for power reduction
on programmable platforms.
1.2 Design Methodology: What is New?
Our design methodology can be briefly described as follows. Given throughput,
power consumption and cost requirements for a computation, our goal is to find
cost-effective, power-efficient solutions on single or multiple programmable processor
platforms. The first step is to find power-efficient solutions for a single processor
implementation by applying the new technique described in Section 4. The second
step is to continue to add processors until the reduction in average power consumption
is not enough to justify the cost of an additional processor. This step
generates cost-effective and power efficient solutions. This straightforward design
methodology produces implementations with low cost and low power consumption
for the given design requirements.
The main technical innovation of the research presented in this paper is the first
approach for the minimization of the number of operations in arbitrary computa-
tions. The approach optimizes not only significantly wider set of computations than
the other previously published techniques [Parhi and Messerschmitt 1991; Srivastava
and Potkonjak 1996], but also outperforms or performs at least as well as other
techniques on all examples. The novel divide-and-conquer compilation procedure
combines and coordinates power and enabling effects of several transformations
(using a well organized ordering of transformations) to minimize the number of
operations in each logical partition. To the best of our knowledge this is the first
approach for minimization of the number of operations which in an optimization
intensive way treats general computations.
The second technical highlight is the quantitative analysis of cost vs power trade-off
on multiple programmable processor implementation platforms. We derive a
condition under which the optimization of the cost-power product using parallelization
is beneficial.
1.3 Paper Organization
The rest of the paper is organized in the following way. First, in the next sec-
tion, we summarize the relevant background material. In Section 3 we review the
related work on power estimation and optimization as well as on program optimization
using transformations, and in particular the minimization of the number
of operations. Sections 4 and 5 are the technical core of this paper and present
a novel approach for minimization of the number of operations for general DSP
computations and explore compiler and technology impact on power-cost trade-offs
of multiple processors-based low power application specific systems. We then
present comprehensive experimental results and their analysis in Section 6 followed
by conclusions in Section 7.
2. PRELIMINARIES
Before we delve into technical details of the new approach, we outline the relevant
preliminaries in this section. In particular, we describe application and computation
abstractions, selected implementation platform at the technology and architectural
level, and power estimation related background material.
2.1 Computational Model
We selected as our computational model synchronous data flow (SDF) [Lee and
Messerschmitt 1987; Lee and Parks 1995]. Synchronous data flow (SDF) is a special
case of data flow in which the number of data samples produced or consumed
by each node on each invocation is specified a priori. Nodes can be scheduled
statically at compile time onto programmable processors. We restrict our attention
to homogeneous SDF (HSDF), where each node consumes and produces exactly
one sample on every execution. The HSDF model is well suited for specification
of single task computations in numerous application domains such as digital signal
processing, video and image processing, broadband and wireless communications,
control, information and coding theory, and multimedia.
The syntax of a targeted computation is defined as a hierarchical control-data
flow graph (CDFG) [Rabaey et al. 1991]. The CDFG represents the computation as
a flow graph, with nodes, data edges, and control edges. The semantics underlying
the syntax of the CDFG format, as we already stated, is that of the synchronous
data flow computation model.
The only relevant speed metric is throughput, the rate at which the implementation
is capable of accepting and processing the input samples from two consecutive
iterations. We opted for throughput as the selected speed metric since in essentially
all DSP and communication wireless computations latency is not a limiting factor,
where latency is defined to be the delay between the arrival of a set of input samples
and the production of the corresponding output as defined by the specification.
2.2 Hardware Model
The basic building block of the targeted hardware platform is a single programmable
processor. We assume that all types of operations take one clock cycle for their
execution, as it is the case in many modern DSP processors. The adaptation of the
software and algorithms to other hardware timing models is straightforward. In the
case of a multi-processor, we make the following additional simplifying assumptions:
(i) all processors are homogeneous and (ii) inter-processor communication does
not cost any time and hardware. This assumption is reasonable because multiple
processors can be placed on single integrated circuit due to increased integration,
although it would be more realistic to assume additional hardware and delay penalty
for using multiple processors.
2.3 Power and Timing Models in Conventional and Ultra Low Power Technology
It is well known that there are three principal components of power consumption
in CMOS integrated circuits: switching power, short-circuit power, and leakage
power. The switching power is given by P switching
dd f clock , where ff is the
probability that the power consuming switching activity, i.e. transition from 0 to
1, occurs, CL is the loading capacitance, V dd is the supply voltage, and f clock is
the system clock frequency. ffC L is defined to be effective switched capacitance.
In CMOS technology, switching power dominates power consumption. The short-circuit
power consumption occurs when both NMOS and CMOS transistors are
"ON" at the same time while the leakage power consumption results from reverse
biased diode conduction and subthreshold operation. We assume that effective
switched capacitance increases linearly with the number of processors and supply
voltage can not be lowered below threshold voltage V t , for which we use several
different values between 0.06V and 1.1V for both conventional and ultra low power
technology.
It is also known that reduced voltage operation comes at the cost of reduced
throughput [Chandrakasan et al. 1992]. The clock speed T follows the following
is a constant [Chandrakasan et al. 1992]. The
maximum rate at which a circuit is clocked monotonically decreases as the voltage
is reduced. As the supply voltage is reduced close to V t , the rate of clock speed
reduction becomes higher.
2.4 Architecture-level Power Models for Single and Multiple Programmable Processors
The power model used in this research is built on three statistically validated and
experimentally established facts. The first fact is that the number of operations
at the machine code-level is proportional to the number of operations at high-level
language [Hoang and Rabaey 1993]. The second fact is that the power consumption
in modern programmable processors such as the Fujitsu SPARClite MB86934,
a 32-bit RISC microcontroller, is directly proportional to the number of operations,
regardless of the mix of operations being executed [Tiwari and Lee 1995]. Tiwari
and Lee [1995] report that all the operations including integer ALU instructions,
floating point instructions, and load/store instructions with locked caches incur
similar power consumption. Since the use of memory operands results in additional
power overhead due to the possibility of cache misses, we assume that the cache
locking feature is exploited as far as possible. If the cache locking feature can not
be used for the target applications, the power consumption by memory traffic is
likely to be reduced by the minimization of the number of operations since less operations
usually imply less memory traffic. When the power consumption depends
on the mix of operations being executed as in the case of the Intel 486DX2 [Tiwari
et al. 1994], more detailed hardware power model may be needed. However, it is
obvious that in all proposed power models for programmable processors, significant
reduction in the number of operations inevitably results in lower power. The final
empirical observation is related to power consumption and timing models in digital
CMOS circuits presented in the previous subsection.
Based on these three observations, we conclude that if the targeted implementation
platform is a single programmable CMOS processor, a reduction in the number
of operations is the key to power minimization. When the initial number of operations
is N init , the optimized number of operations is N opt , the initial voltage
is V init and the scaled voltage is V opt , the optimized power consumption relative
to the initial power consumption is ( Vopt
. For multiprocessors, assuming
that there is no communication overhead, the optimized power consumption for n
processors relative to that for a single processor is ( Vn
Vn are the
scaled voltages for single and n processors, respectively.
3. RELATED WORK
The related work can be classified along two lines: low power and implementation
optimization, and in particular minimization of the number of operations using
transformations. The relevant low power topics can be further divided in three
directions: power minimization techniques, power estimation techniques, and technologies
for ultra low power design. The relevant compilation techniques are also
grouped in three directions: transformations, ordering of transformations, and minimization
of the number of operations.
In the last five years power minimization has been arguably the most popular
optimization goal. This is mainly due to the impact of the rapidly growing market
for portable computation and communication products. Power minimization efforts
across all level of design abstraction process are surveyed in [Singh et al. 1995].
It is apparent that the greatest potential for power reduction is at the highest
levels (behavioral and algorithmic). Chandrakasan et al. [1992] demonstrated the
effectiveness of transformations by showing an order of magnitude reduction in several
DSP computationally intensive examples using a simulated annealing-based
transformational script. Raghunathan and Jha [1994] and Goodby et al. [1994]
also proposed methods for power minimization which explore trade-offs between
voltage scaling, throughput, and power. Chatterjee and Roy [1994] targeted power
reduction in fully hardwired designs by minimizing the switching activity. Chandrakasan
et. al. [1994], and Tiwari et. al. [1994] did work in power minimization
when programmable platforms are targeted.
Numerous power modeling techniques have been proposed at all levels of abstraction
in the synthesis process. As documented in [Singh et al. 1995] while there have
been numerous efforts at the gate level, at the higher level of abstraction relatively
few efforts have been reported.
Chandrakasan et al. [1995] developed a statistical technique for power estimation
from the behavioral level which takes into account all components at the layout level
including interconnect. Landman and Rabaey [1996] developed activity-sensitive
architectural power analysis approach for execution units in ASIC designs. Finally,
in a series of papers it has been established that the power consumption of modern
programmable processor is directly proportional to the number of operations,
regardless of what the mix of operations being executed is [Lee et al. 1996; Tiwari
et al. 1994].
Transformations have been widely used at all levels of abstraction in the synthesis
process, e.g. [Dey et al. 1992]. However, there is a strong experimental evidence
that they are most effective at the highest levels of abstractions, such as system
and in particular behavioral synthesis. Transformations only received widespread
attention in high level synthesis [Ku and Micheli 1992; Potkonjak and Rabaey 1992;
Walker and Camposano 1991].
Comprehensive reviews of use of transformations in parallelizing compilers, state-
of-the-art general purpose computing environments, and VLSI DSP design are given
in [Banerjee et al. 1993], [Bacon et al. 1994], and [Parhi 1995] respectively. The
approaches for transformation ordering can be classified in seven groups: local
(peephole) optimization, static scripts, exhaustive search-based "generate and test"
methods, algebraic approaches, probabilistic search techniques, bottleneck removal
methods, and enabling-effect based techniques.
Probably the most widely used technique for ordering transformations is local
(peephole) optimization [Tanenbaum et al. 1982], where a compiler considers only
a small section of code at a time in order to apply one by one iteratively and locally
all available transformations. The advantages of the approach are that it is fast and
simple to implement. However, performance are rarely high, and usually inferior
to other approaches.
Another popular technique is a static approach to transformations ordering where
their order is given a priori, most often in the form of a script [Ullman 1989]. Script
development is based on experience of the compiler/synthesis software developer.
This method has at least three drawbacks: it is a time consuming process which
involves a lot of experimentation on random examples in an ad-hoc manner, any
knowledge about the relationship among transformations is only implicitly used,
and the quality of the solution is often relatively low for programs/design which
have different characteristics than the ones used for the development of the script.
The most powerful approach to transformation ordering is enumeration-based
"generate and test" [Massalin 1987]. All possible combinations of transformations
are considered for a particular compilation and the best one is selected using branch-
7and-bound or dynamic programming algorithms. The drawback is the large run
time, often exponential in the number of transformations.
Another interesting approach is to use a mathematical theory behind the ordering
of some transformations. However, this method is limited to only several linear loop
transformations [Wolf and Lam 1991]. Simulated annealing, genetic programming,
and other probabilistic techniques in many situations provide a good trade-off between
the run time and the quality of solution when little or no information about
the topology of the solution space is available. Recently, several probabilistic search
techniques have been proposed for ordering of transformations in both compiler and
behavioral synthesis literature. For example, backward-propagation-based neural
network techniques were used for developing a probabilistic approach to the application
of transformations in compilers for parallel computers [Fox and Koller
1989] and approaches which combine both simulated annealing-based probabilistic
and local heuristic optimization mechanism were used to demonstrate significant
reductions in area and power [Chandrakasan et al. 1995].
In behavioral and logic synthesis several bottleneck identification and elimination
approaches for ordering of transformations have been proposed [Dey et al. 1992;
Iqbal et al. 1993]. This line of work has been mainly addressing the throughput
and latency optimization problems, where the bottlenecks can be easily identified
and well quantified. Finally, the idea of enabling and disabling transformations has
been recently explored in a number of compilation [Whitfield and Soffa 1990] and
high level synthesis papers [Potkonjak and Rabaey 1992; Srivastava and Potkonjak
1996]. Using this idea several very powerful transformations scripts have been
developed, such as one for maximally and arbitrarily fast implementation of linear
computations [Potkonjak and Rabaey 1992], and joint optimization of latency and
throughput for linear computations [Srivastava and Potkonjak 1994]. Also, the
enabling mechanism has been used as a basis for several approaches for ordering of
transformations for optimization of general computations [Huang and Rabaey 1994].
The key advantage of this class of approaches is related to intrinsic importance and
power of enabling/disabling relationship between a pair of transformations.
Transformations have been used for optimization of a variety of design and program
metrics, such as throughput, latency, area, power, permanent and temporal
fault-tolerance, and testability. Interestingly, the power of transformations is most
often focused on secondary metrics such as parallelism, instead on the primary
metrics such as the number of operations.
In compiler domain, constant and copy propagation and common subexpression
techniques are often used. It can be easily shown that the constant propagation
problem is undecidable, when the computation has conditionals [Kam and Ullman
1977]. The standard procedure to address this problem is to use so called conservative
algorithms. Those algorithms do not guarantee that all constants will be
detected, but that each data declared constant is indeed constant over all possible
executions of the program. A comprehensive survey of the most popular constant
propagation algorithms can be found in [Wegman and Zadeck 1991].
Parhi and Messerschmitt [1991] presented optimal unfolding of linear computations
in DSP systems. Unfolding results in simultaneous processing of consecutive
iterations of a computation. Potkonjak and Rabaey [1992] addressed the minimization
of the number of multiplications and additions in linear computations in
their maximally fast form so that the throughput is preserved. Potkonjak et al.
[1996] presented a set of techniques for minimization of the number of shifts and
additions in linear computations. Sheliga and Sha [1994] presented an approach for
minimization of the number of multiplications and additions in linear computations.
Srivastava and Potkonjak [1996] developed an approach for the minimization of
the number of operations in linear computations using unfolding and the application
of the maximally fast procedure. A variant of their technique is used in "conquer"
phase of our approach. Our approach is different from theirs in two respects.
First, their technique can handle only very restricted computations which are linear,
while our approach can optimize arbitrary computations. Second, our approach
outperforms or performs at least as well as their technique for linear computations.
4. SINGLE PROGRAMMABLE PROCESSOR IMPLEMENTATION: MINIMIZING THE
NUMBER OF OPERATIONS
The global flow of the approach is presented in subsection 4.1. The strategy is based
on divide-and-conquer optimization followed by post optimization step, merging of
divided sub parts which is explained in subsection 4.2. Finally, subsection 4.3
provides a comprehensive example to illustrate the strategy.
4.1 Global Flow Of the Approach
The core of the approach is presented in the pseudo-code of Figure 1. The rest of
this subsection explains the global flow of the approach in more detail.
Decompose a computation into strongly connected components(SCCs);
Any adjacent trivial SCCs are merged into a sub part;
Use pipelining to isolate the sub parts;
For each sub part
Minimize the number of delays using retiming;
If (the sub part is linear)
Apply optimal unfolding;
Else
Apply unfolding after the isolation of nonlinear operations;
Merge linear sub parts to further optimize;
Schedule merged sub parts to minimize memory usage;
Fig. 1. The core of the approach to minimize the number of operations for general DSP computation

The first step of the approach is to identify the computation's strongly connected
components(SCCs), using the standard depth-first search-based algorithm [Tarjan
1972] which has a low order polynomial-time complexity. For any pair of operations
A and B within an SCC, there exist both a path from A to B and a path from B
to A. An illustrated example of this step is shown in Figure 2. The graph formed
by all the SCCs is acyclic. Thus, the SCCs can be isolated from each other using
pipeline delays, which enables us to optimize each SCC separately. The inserted
pipeline delays are treated as inputs or outputs to the SCC. As a result, every
output and state in an SCC depend only on the inputs and states of the SCC.



Addition
Constant Multiplication
Functional Delay (State)
Variable Multiplication
Strongly Connected Component
Fig. 2. An illustrated example of the SCC decomposition step
Thus, in this sense, the SCC is isolated from the rest of the computation and it
can be optimized separately. In a number of situations our technique is capable
to partition a nonlinear computation into partitions which consist of only linear
computations. Consider for example a computation which consists of two strongly
connected components SCC 1 and SCC 2 . SCC 1 has as operations only additions
and multiplications with constants. SCC 2 has as operations only max operation
and additions. Obviously, since the computations has additions, multiplications
with constants and max operations, it is nonlinear. However, after applying our
technique of logical separation using pipeline states we have two parts which are
linear. Note that this isolation is not affected by unfolding. We define an SCC
with only one node as a trivial SCC. For trivial SCCs unfolding fails to reduce the
number of operations. Thus, any adjacent trivial SCCs are merged together before
the isolation step, to reduce the number of pipeline delays used.
where X, Y , and S are the input, output, and state vectors respectively
and A; B; C; and D are constant coefficient matrices.
Fig. 3. State-space equations for linear computations
The number of delays in each sub part is minimized using retiming in polynomial
time by the Leiserson-Saxe algorithm [Leiserson and Saxe 1991]. Note that smaller
number of delays will require smaller number of operations since both the next
states and outputs depend on the previous states. SCCs are further classified
as either linear or nonlinear. Linear computations can be represented using the
(2R\Gamma1)R
(2R\Gamma1)R
which gives the smaller value of
of multiplications for i times unfolded system
of additions for i times unfolded system
Fig. 4. Closed-form formula of unfolding for dense linear computation with P inputs, Q outputs,
and R states.
state-space equations in Figure 3. Minimization of the number of operations for
linear computations is NP-complete [Sheliga and Sha 1994]. We have adopted an
approach of [Srivastava and Potkonjak 1996] for the optimization of linear sub parts,
which uses unfolding and the maximally fast procedure [Potkonjak and Rabaey
1992]. We note that instead of maximally fast procedure, the ratio analysis by
[Sheliga and Sha 1994] can be used. [Srivastava and Potkonjak 1996] has provided
the closed-form formula for the optimal unfolding factor with the assumption of
dense linear computations. We provide the formula in Figure 4. For sparse linear
computations, they have proposed a heuristic which continues to unfold until there
is no improvement. We have made the simple heuristic more efficient with binary
search, based on the unimodality property of the number of operations on unfolding
factor [Srivastava and Potkonjak 1996].






iteration i iteration i+1 iteration i+2
Fig. 5. An example of isolating nonlinear operations from 2 times unfolded nonlinear sub part
When a sub part is classified as nonlinear, we apply unfolding after the isolation of
nonlinear operations. All nonlinear operations are isolated from the sub part so that
the remaining linear sub parts can be optimized by the maximally fast procedure.
All arcs from nonlinear operations to the linear sub parts are considered as inputs
to the linear sub parts, and all arcs from linear sub parts to the nonlinear operations
are considered as outputs from the linear sub parts. The process is illustrated in

Figure

5. All arcs denoted by i are considered to be inputs and all arcs denoted
by are considered to be outputs for unfolded linear sub part. We observe that if
every output and state of the nonlinear sub part depend on nonlinear operations,
then unfolding with the separation of nonlinear operations is ineffective in reducing
the number of operations.
Fig. 6. A motivational example for sub part merging
Sometimes it is beneficial to decompose a computation into larger sub parts than
SCCs. We consider an example given in Figure 6. Each node represents a sub
part of the computation. We make the following assumptions only specifically for
clarifying the presentation of this example and simplifying the example. We stress
here that the assumptions are not necessary for our approach. Assume that each
sub part is linear and can be represented by state-space equations in Figure 3. Also
assume that every sub part is dense, which means that every output and state in
a sub part are linear combinations of all inputs and states in the sub part with
no 0, 1, or -1 coefficients. The number inside a node is the number of delays or
states in the sub part. Assume that when there is an arc from a sub part X to
a sub part Y, every output and state of Y depends on all inputs and states of X.
Separately optimizing SCCs P 1 and P 2 in Figure 6 costs 211 operations from the
formula in Figure 4. On the otherhand, optimizing the entire computation entails
only 63.67 operations. The reason why separate optimization does not perform well
in this example is because there are too many intermediate outputs from SCC P 1 to
This observation leads us to an approach of merging sub parts for further
reducing the number of operations. Since it is worthwhile to explain the sub part
merging problem in detail, the next subsection is devoted to the explanation of the
problem and our heuristic approaches.
Since the sub parts of a computation are unfolded separately by different unfolding
factors, we need to address the problem of scheduling the sub parts. They should
be scheduled so that memory requirements for code and data are minimized. We
observe that the unfolded sub parts can be represented by multi-rate synchronous
dataflow graph [Lee and Messerschmitt 1987] and the work of [Bhattacharyya et al.
1993] can be directly used.
Note that the approach is in particular useful for such architectures that require
high locality and regularity in computation because it improves both locality and
regularity of computation by decomposing into sub parts and using the maximally
fast procedure. Locality in a computation relates to the degree to which a computation
has natural clusters of operations while regularity in a computation refers
to the repeated occurrence of the computational patterns such as a multiplication
followed by an addition [Guerra et al. 1994; Mehra and Rabaey 1996].
4.2 Subpart Merging
Initially, we only consider merging of linear SCCs. When two SCCs are merged,
the resulting sub part does not form an SCC. Thus, in general, we must consider
merging of any adjacent arbitrary sub parts. Suppose we consider merging of sub
parts i and j. The gain GAIN(i; j) of merging sub parts i and j can be computed as
follows: is the
number of operations for sub part i and COST (i; j) is the number of operations
for the merged sub part of i and j. To compute the gain, COST (i; j) must be
computed, which requires constant coefficient matrices A; B; C; and D for only the
merged sub part of i and j. It is easy to construct the matrices using the depth-first
search [Tarjan 1972].
Fig. 7. i times unfolded state-space equations
\Gamma 1c, or d
which gives the smaller value of i opt (
states in state group j
outputs in output group j
inputs that output group j depends on
inputs that state group j depends on
states that output group j depends on
states that state group j depends on
Fig. 8. Closed-form formula for unfolding; If two outputs depend on the same set of inputs and
states, they are in the same group, and the same is true for states.
The i times unfolded system can be represented by the state-space equations in

Figure

7. From the equations, the total number of operations can be computed
for i times unfolded sub part as follows. Let denote the number
of multiplications and the number of additions for i times unfolded system,
respectively. The resulting number of operations is N( ;i)+N(+;i)
because i times
unfolded system uses a batch of samples to generate a batch of
output samples. We continue to unfold until no improvement is achieved. If there
are no coefficients of 1 or \Gamma1 in the matrices A, B, C, and D, then the closed-form
formula for the optimal unfolding factor i opt and for the number of operations for
times unfolded system are provided in Figure 8.
While (there is improvement)
For all possible merging candidates,
Compute the gain;
Merge the pair with the highest gain;
Fig. 9. Pseudo-code of a greedy heuristic for sub part merging
Generate a starting solution S.
Set the best solution S
Determine a starting temperature T .
While not yet frozen,
While not yet at equilibrium for the current temperature,
Choose a random neighbor S 0 of the current solution.
Else
Generate a random number r uniformly from [0, 1].
Update the temperature T .
Return the best solution S  .
Fig. 10. Pseudo-code for simulated annealing algorithm for sub part merging
Now, we can evaluate possible merging candidates. We propose two heuristic
algorithms for sub part merging. The first heuristic is based on greedy optimization
approach. The pseudo-code is provided in Figure 9. The algorithm is simple. Until
there is no improvement, merge the pair of sub parts which produces the highest
gain.
The other heuristic algorithm is based on a general combinatorial optimization
technique known as simulated annealing [Kirkpatrick et al. 1983]. The pseudo-code
is provided in Figure 10. The actual implementation details are presented
for each of the following areas: the cost function, the neighbor solution generation,
the temperature update function, the equilibrium criterion and the frozen criterion.
Firstly, the number of operations for the entire given computation has been used
as the cost function. Secondly, the neighbor solution is generated by the merging
of two adjacent sub parts. Thirdly, the temperature is updated by the function
old . For the temperature T ? 200:0, ff is chosen to be 0.1 so
that in high temperature regime where every new state has very high chance of
acceptance, the temperature reduction occurs very rapidly. For
is set to 0.95 so that the optimization process explores this promising region more
slowly. For T  1:0, ff is set to 0.8 so that T is quickly reduced to converge to a local
minimum. The initial temperature is set to 4,000,000. Fourthly, the equilibrium
criterion is specified by the number of iterations of the inner loop. The number of
Fig. 11. An explanatory example
iterations of the inner loop is set to 20 times of the number of sub parts. Lastly,
the frozen criterion is given by the temperature. If the temperature falls below 0.1,
the simulated annealing algorithm stops.
Both heuristics performed equally well on all the examples and the run times
for both are very small because the examples have a few sub parts. We have used
both greedy and simulated annealing based heuristics for generating experimental
results and they produced exactly the same results.
Fig. 12. A simple example of # operations calculation
4.3 Explanatory Example: Putting It All Together
We illustrate the key ideas of our approach for minimizing the number of operations
by considering the computation of Figure 11. We use the same assumptions made
for the example in Figure 6.
The number of operations per input sample is initially 2081 (We illustrate how
the number of operations is calculated in a maximally fast way [Potkonjak and
Rabaey 1992] using a simple linear computation with 1 input X , 1 output Y , and
which is described in Figure 12). Using the technique of [Srivastava
and Potkonjak 1996] which unfolds the entire computation, the number can be
reduced to 725 with an unfolding factor of 12. Our approach optimizes each sub
part separately. This separate optimization is enabled by isolating the sub parts
using pipeline delays. Figure 13 shows the computation after the isolation step.
Since every sub part is linear, unfolding is performed to optimize the number of
operations for each sub part. The sub parts cost 120.75, 53.91,
114.86, 129.75, and 103.0 operations per input sample with unfolding factors 3, 10,
6, 7, and 2, respectively. The total number of operations per input sample for
the entire computation is 522.27. We now apply SCC merging to further reduce
the number of operations. We first consider the greedy heuristic. The heuristic
Fig. 13. A motivational example after the isolation step
considers merging of adjacent sub parts. Initially, the possible merging candidate
are which produce the gains of -51.48, -
112.06, -52.38, 122.87, and -114.92, respectively. SCC P 3 and SCC P 4 are merged
with an unfolding factor of 22. In the next iteration, there are now 4 sub parts and
4 candidate pairs for merging all of which yield negative gains. So, the heuristic
stops at this point. The total number of operations per input sample has further
decreased to 399.4. Simulated annealing heuristic produced the same solution for
this example. The approach has reduced the number of operations by a factor of
1.82 from the previous technique of [Srivastava and Potkonjak 1996], while it has
achieved the reduction by a factor of 5.2 from the initial number of operations.
For single processor implementation, since both the technique of [Srivastava and
Potkonjak 1996] and our new method yield higher throughput than the original,
the supply voltage can be lowered up to the extent that the extra throughput is
compensated by the loss in circuit speed due to reduced voltage. If the initial
voltage is 3.3V, then our technique reduces power consumption by a factor of 26.0
with the supply voltage of 1.48V while the technique of [Srivastava and Potkonjak
1996] reduces it by a factor of 10.0 with the supply voltage of 1.77V.
The scheduling of the unfolded sub parts is performed to generate the minimum
code and data memory schedule. The schedule period is the least common multiple
of (the unfolding factor+1)'s which is 3036. Let P 3;4 denote the merged sub part of
While a simple minded schedule (759P 1 , 276P 2 , 132P 3;4 , 1012P 5 ) to
minimize the code size ignoring loop overheads generates 9108 units of data memory
requirement, a schedule (759P 1 , 4(69P 2 , 33P 3;4 , 253P 5 which minimizes the data
memory requirement among the schedules minimizing the code size generates 4554
units of data memory requirement.
5. MULTIPLE PROGRAMMABLE PROCESSORS IMPLEMENTATION
When multiple programmable processors are used, potentially more savings in
power consumption can be obtained. We summarize the assumptions made in
Section 2: (i) processors are homogeneous, (ii) inter-processor communication does
not cost any time and hardware, (iii) effective switched capacitance increases linearly
with the number of processors, (iv) both addition and multiplication take one
clock cycle, and (v) supply voltage can not be lowered below threshold voltage V t ,
for which we use several different values between 0.06V and 1.1V. Based on these
assumptions, using k processors increases the throughput k times when there is
enough parallelism in the computation, while the effective switched capacitance increases
k times as well. In all the real-life examples considered, sufficient parallelism
actually existed for the numbers of processors that we used.
R )e , if k  R 2
Fig. 14. Closed-form condition for sufficient parallelism when using k processors for a dense linear
computation with R states
We observe that the next states, i.e., the feedback loops can be
computed in parallel. Note that the maximally fast procedure by [Potkonjak and
Rabaey 1992] evaluates a linear computation by first doing the constant-variable
multiplications in parallel, and then organizing the additions as a maximally balanced
binary tree. Since all the next states are computed in a maximally fast
procedure, in the bottom of the binary computation tree there exists more paral-
lelism. All other operations not in the feedback loops can be computed in parallel
because they can be separated by pipeline delays. As the number of processors
becomes larger, the number of operations outside the feedback loops gets larger to
result in more parallelism. For dense linear computations, we provide the closed-form
condition for sufficient parallelism when using k processors in Figure 14. We
note that although the formulae were derived for the worst case scenario, the required
number of operations outside the feedback loops is small for the range of
the number of processors that we have tried in the experiment. There exist more
operations outside feedback loops than are required for full parallelism in all the
real-life examples we have considered.
Now one can reduce the voltage so that the clock frequency of all k processors
is reduced by a factor of k. The average power consumption of k processors
is reduced from that of a single processor by a factor of ( V1
is a
scaled supply voltage for k processor implementation, and V k satisfies the equation
et al. 1992]. From this observation it is
always beneficial to use more processors in terms of power consumption with the
following two limitations: (i) the amount of parallelism available limits the improvement
in throughput and the critical path of the computation is the maximum
achievable throughput and (ii) when supply voltage approaches close to threshold
voltage, the improvement in power consumption becomes so small that the cost of
adding a processor is not justified. With this in mind, we want to find the number
of processors which minimizes power consumption cost-effectively in both standard
CMOS technology and ultra low power technology.
Since the cost of programmable processors is high, and especially the cost of
processors on ultra low power platforms such as SOI is very high [El-Kareh et al.
1995; Ipposhi et al. 1995], the guidances for cost-effective design are important. We
need a measure to differentiate between cost-effective and cost-ineffective solutions.
We propose a PN product, where P is the power consumption normalized to that
of optimized single processor implementation and N is the number of processors
number of processors
1.1 5.0 5.0 0.90 0.93 0.98 1.04 1.10 1.17 1.24 1.30 1.37
4.0 1.00 1.08 1.17 1.28 1.38 1.49 1.59 1.70 1.80
3.0 1.14 1.33 1.51 1.70 1.88 2.06 2.24 2.42 2.60
2.0 1.42 1.82 2.22 2.60 2.98 3.35 3.71 4.08 4.44
0.7 3.3 3.3 0.89 0.91 0.95 1.00 1.06 1.12 1.19 1.25 1.31
2.0 1.12 1.28 1.45 1.62 1.79 1.96 2.12 2.28 2.45
1.0 1.63 2.22 2.80 3.38 3.94 4.50 5.05 5.60 6.15
0.3 1.3 1.3 0.92 0.96 1.02 1.08 1.16 1.23 1.30 1.38 1.45
0.7 1.24 1.49 1.75 2.00 2.24 2.48 2.72 2.95 3.19

Table

I. The values of PN products with respect to the number of processors for various combinations
of the initial voltage V init , the scaled voltage for single processor V 1 , and the threshold
used. The smaller the PN product is the more cost-effective the solution is. If PN
is smaller than 1.0, using N processors has decreased the power consumption by
a factor of more than N. It depends on the power consumption requirement and
the cost budget for the implementation how many processors the implementation
should use. Table I provides the values of PN products with respect to the number
of processors used for various combinations of the initial voltage V init , the scaled
voltage for single processor V 1 , and the threshold voltage V t . V init is the initial
voltage for the implementation before optimization. We note that PN products
monotonically increase with respect to the number of processors.
Init. New IF From RP From IF From RP From
Design Ops [Sri96] Method [Sri96] [Sri96] Init. Ops Init. Ops
dist 48 47.3 36.4 1.30 23.0 1.32 24.2
chemical
modem 213 213 148.83 1.43 30.1 1.43 30.1
GE controller 180 180 105.26 1.71 41.5 1.71 41.5
APCM receiver 2238 N/A 1444.19 N/A N/A 1.55 35.4
Audio Filter 1 154 N/A 76.0 N/A N/A 2.03 50.7
Audio Filter 2 228 N/A 92.0 N/A N/A 2.48 59.7
Filter 1 296 N/A 157.14 N/A N/A 1.88 46.8
Filter 2 398 N/A 184.5 N/A N/A 2.16 53.7

Table

II. Minimizing the number of operations for real-life examples; IF - Improvement Factor,
Reduction Percentage, N/A - Not Applicable, [Sri96] - [Srivastava and Potkonjak 1996]
From the Table I, we observe that cost effective solutions usually use a few
processors in all the cases considered on both the standard CMOS and ultra low
power platforms. We also observe that if the voltage reduction is high for single
Vnew PRF
dist 5.0 1.1 3.76 2.33
3.3 0.7 2.70 1.96
1.3 0.3 1.10 1.84
chemical 5.0 1.1 3.61 2.65
3.3 0.7 2.61 2.21
1.3 0.3 1.07 2.04
DAC 5.0 1.1 3.81 2.72
3.3 0.7 2.50 2.75
1.3 0.3 1.00 2.69
modem 5.0 1.1 4.02 2.21
3.3 0.7 2.65 2.23
1.3 0.3 1.05 2.19
GE controller 5.0 1.1 3.65 3.21
3.3 0.7 2.39 3.25
1.3 0.3 0.96 3.16

Table

III. Minimizing power consumption on single programmable processor for linear examples;
Reduction Factor
processor case, then there is not much room to further reduce power consumption
by using more processors.
Based on those observations, we have developed our strategy for the multiple
processor implementation. The first step is to minimize power consumption for
single processor implementation using the proposed technique in Section 4. The
second step is to increase the number of processors until the PN product is below
the given maximum value. The maximum value is determined based on the power
consumption requirement and the cost budget for the implementation. The strategy
produces solutions with only a few processors, in many cases single processor for
all the real-life examples because our method for the minimization of the number
of operations significantly reduces the number of operations and in turn the supply
voltage for the single processor implementation, adding more processors does
not usually reduce power consumption cost-effectively. Our method achieves cost-effective
solutions with very low power penalty compared to the solutions which
only optimize power consumption without considering hardware cost.
6. EXPERIMENTAL RESULTS
Our set of benchmark designs include all the benchmark examples used in [Sri-
vastava and Potkonjak 1996] as well as the following typical portable DSP, video,
communication, and control applications: DAC - 4 stage NEC digital to analog
converter (DAC) for audio signals; modem - 2 stage NEC modem; GE controller
- 5-state GE linear controller; APCM receiver - Motorola's adaptive pulse code
Vnew PRF
APCM receiver 5.0 1.1 3.85 2.62
3.3 0.7 2.53 2.64
1.3 0.3 1.01 2.58
Audio Filter 1 5.0 1.1 3.34 4.54
3.3 0.7 2.03 4.43
1.3 0.3 0.88 4.45
Audio Filter 2 5.0 1.1 3.03 6.76
3.3 0.7 1.85 6.54
1.3 0.3 0.8 6.58
Filter 1 5.0 1.1 3.45 3.97
3.3 0.7 2.26 4.03
1.3 0.3 0.91 3.90
Filter 2 5.0 1.1 3.24 5.15
3.3 0.7 2.12 5.24
1.3 0.3 0.85 5.04
VSTOL 5.0 1.1 3.43 4.10
3.3 0.7 2.25 4.15
1.3 0.3 0.90 4.02

Table

IV. Minimizing power consumption on single programmable processor for nonlinear ex-
amples; PRF - Power Reduction Factor
modulation receiver; Audio Filter 1 - analog to digital converter (ADC) followed
by 14 order cascade IIR filter; Audio Filter 2 - ADC followed by
two ADCs followed by 10-order two dimensional (2D) IIR
two ADCs followed by 12-order 2D IIR filter; and VSTOL -
VSTOL robust observer structure aircraft speed controller. DAC, modem, and GE
controller are linear computations and the rest are nonlinear computations. The
benchmark examples from [Srivastava and Potkonjak 1996] are all linear, which
include ellip, iir5, wdf5, iir6, iir10, iir12, steam, dist, and chemical.

Table

II presents the experimental results of our technique for minimizing the
number of operations for real-life examples. The fifth and seventh columns of Table
II provide the improvement factors of our method from that of [Srivastava
and Potkonjak 1996] and from the initial number of operations, respectively. Our
method has achieved the same number of operations as that of [Srivastava and
Potkonjak 1996] for ellip, iir5, wdf5, iir6, iir10, iir12, and steam while it has reduced
the number of operations by 23 and 10.3 % for dist and chemical, respectively. All
the examples from [Srivastava and Potkonjak 1996] are single-input single-output
linear computations, except dist and chemical which are two-inputs single-output
linear computations. Since the SISO linear computations are very small,
Vnew PRF N PRF N PRF N PRF
dist 5.0 1.1 3.76 2.33 1 2.33 4 7.53 6 9.47
3.3 0.7 2.70 1.96 2 4.04 5 8.11 8 10.54
1.3 0.3 1.10 1.84 2 3.71 4 6.31 7 8.74
chemical 5.0 1.1 3.61 2.65 1 2.65 3 6.87 5 9.39
3.3 0.7 2.61 2.21 2 4.49 5 8.86 7 10.69
1.3 0.3 1.07 2.04 1 2.04 4 6.83 6 8.67
3.3 0.7 2.50 2.75 1 2.75 4 9.22 6 11.71
1.3 0.3 1.00 2.69 1 2.69 3 7.05 5 9.67
modem 5.0 1.1 4.02 2.21 2 4.45 4 7.56 7 10.45
3.3 0.7 2.65 2.23 2 4.56 5 9.07 7 10.97
1.3 0.3 1.05 2.19 1 2.19 4 7.22 6 9.13
GE 5.0 1.1 3.65 3.21 1 3.21 3 8.39 5 11.49
controller 3.3 0.7 2.39 3.25 1 3.25 4 10.49 6 13.20
1.3 0.3 0.96 3.16 1 3.16 3 8.05 5 10.92

Table

V. Minimizing power consumption on multiple processors for linear examples; PN T -
threshold PN product, N - # of processors, PRF - Power Reduction Factor
there is no room for improvement from [Srivastava and Potkonjak 1996]. Our
method has reduced the number of operations by an average factor of 1.77 (average
43.5 %) for the examples that previous techniques are either ineffective or inap-
plicable. Tables III and IV present the experimental results of our technique for
minimizing power consumption on single programmable processor of real-life examples
on various technologies. Our method results in power consumption reduction
by an average factor of 3.58.
For multiple processor implementations, Tables V and VI summarize the experimental
results of our technique for minimizing power consumption. We define
threshold PN product PN T to be the value of PN product, where we should stop
increasing the number of processors. When PN i.e., the power reduction by
the addition of a processor must be greater than 2 to be cost effective, in almost
all cases single processor solution is optimum. When PN T gets larger, the number
of processors used increases, but the solutions still use only a few processors which
result in an order of magnitude reduction in power consumption. All the results
clearly indicate the effectiveness of our new method.
7. CONCLUSION
We introduced an approach for power minimization using a set of compilation and
architectural techniques. The key technical innovation is a compilation technique
for minimization of the number of operations which synergistically uses several
Vnew PRF N PRF N PRF N PRF
APCM 5.0 1.1 3.85 2.62 1 2.62 4 8.64 6 10.92
receiver 3.3 0.7 2.53 2.64 2 5.29 4 8.95 7 12.33
1.3 0.3 1.01 2.58 1 2.58 3 6.81 6 10.32
Audio 5.0 1.1 3.34 4.54 1 4.54 3 11.12 4 13.22
Filter 1 3.3 0.7 2.03 4.43 1 4.43 2 7.99 4 12.38
1.3 0.3 0.88 4.45 1 4.45 2 8.07 4 12.56
Audio 5.0 1.1 3.03 6.76 1 6.76 2 11.88 4 18.04
Filter 2 3.3 0.7 1.85 6.54 1 6.54 2 11.26 3 14.45
1.3 0.3 0.8 6.58 1 6.58 2 11.38 3 14.64
Filter 1 3.3 0.7 2.26 4.03 1 4.03 3 10.32 5 14.04
1.3 0.3 0.91 3.90 1 3.90 3 9.55 4 11.34
Filter 2 3.3 0.7 2.12 5.24 1 5.24 3 12.82 4 15.22
1.3 0.3 0.85 5.04 1 5.04 2 8.99 4 13.79
3.3 0.7 2.25 4.15 1 4.15 3 10.60 5 14.40
1.3 0.3 0.90 4.02 1 4.02 3 9.76 4 11.58

Table

VI. Minimizing power consumption on multiple processors for nonlinear examples; PN T
threshold PN product, N - # of processors, PRF - Power Reduction Factor
transformations within a divide and conquer optimization framework. The new
approach not only deals with arbitrary computations, but also outperforms previous
techniques for limited computation types.
Furthermore, we investigated coordinated impact of compilation techniques and
new ultra low power technologies on the number processors which provide optimal
trade-off of cost and power. The experimental results on a number of real-life
designs clearly indicates the effectiveness of all proposed techniques and algorithms.



--R

Compiler transformations for high performance computing.
Automatic program parallelization.
A scheduling framework for minimizing memory requirements of multirate signal processing algorithms expressed as dataflow graphs.

Optimizing power using transformations.

Energy efficient programmable computation.
Design considerations and tools for low-voltage digital system design
Synthesis of low power DSP circuits using activity metrics.
Performance optimization of sequential circuits by eliminating retiming bottlenecks.
Silicon on insulator - an emerging high-leverage technology
Code generation by a generalized neural network.
Microarchitectural synthesis of performance-constrained

Scheduling of DSP programs onto multiprocessors for maximum throughput.
Maximizing the throughput of high performance DSP applications using behavioral transformations.
An advanced 0.5 mu m CMOS/SOI technology for practical ultrahigh-speed and low-power circuits
Critical path minimization using retiming and algebraic speedup.
Monotone data flow analysis frameworks.
Optimization by simulated annealing.


Synchronous dataflow.
Dataflow process networks.
Power analysis and minimization techniques for embedded dsp software.
Retiming synchronous circuitry.
A look at the smallest program.
Exploiting regularity for low-power design

Journal of VLSI Signal Processing
Static rate-optimal scheduling of iterative data-flow programs via optimum unfolding
Maximally fast and arbitrarily fast implementation of linear computations.
Multiple constant multi- plications: efficient and versatile framework and algorithms for exploring common subexpression elimination
Fast prototyping of data path intensive architectures.
Behavioral synthesis for low power.
Personal Communications.
Global node reduction of linear systems using ratio analysis.
Power conscious cad tools and methodologies: A perspective.
Transforming linear systems for joint latency and throughput optimization.
Power optimization in programmable processors and ASIC implementations of linear systems: Transformation-based approach
Using peephole optimization on intermediate code.
Depth first search and linear graph algorithms.
Power analysis of a 32-bit embedded microcontroller
In Asia and South Pacific Design Automation Conference
Power analysis of embedded software: a first step towards software power minimization.
Database and Knowledge-Base Systems
A Survey of High-level Synthesis Systems

ACM Transactions on Programming Languages
An approach to ordering optimizing transformations.
In ACM Symposium on Principles and Practice of Parallel Programming
A loop transformation theory and an algorithm to maximize parallelism.
--TR
Static Rate-Optimal Scheduling of Iterative Data-Flow Programs Via Optimum Unfolding
Power analysis of embedded software
Power optimization in programmable processors and ASIC implementations of linear systems
Global node reduction of linear systems using ratio analysis
Maximally fast and arbitrarily fast implementation of linear computations
Fast Prototyping of Datapath-Intensive Architectures

--CTR
Johnson Kin , Chunho Lee , William H. Mangione-Smith , Miodrag Potkonjak, Power efficient mediaprocessors: design space exploration, Proceedings of the 36th ACM/IEEE conference on Design automation, p.321-326, June 21-25, 1999, New Orleans, Louisiana, United States
Luca Benini , Giovanni De Micheli, System-level power optimization: techniques and tools, Proceedings of the 1999 international symposium on Low power electronics and design, p.288-293, August 16-17, 1999, San Diego, California, United States
Luca Benini , Giovanni de Micheli, System-level power optimization: techniques and tools, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.2, p.115-192, April 2000
power consumption;data flow graphs;portable wireless DSP applications;architectural techniques;DSP computations;compilation;divide-and-conquer compilation