or=blue>the Internet Archive. Yahoo! is not affiliated with the authors of this page or responsible for its content.
Voltage Island-Driven Floorplanning Voltage Island-Driven Floorplanning
Qiang Ma and Evangeline F. Y. Young
Department of Computer Science and Engineering
The Chinese University of Hong Kong
Email:
{qma,fyyoung}@cse.cuhk.edu.hk
Abstract Energy efciency has become one of the most important
issues to be addressed in todays System-on-a-Chip (SoC) designs.
One way to lower the power consumption is to reduce the supply
voltage. Multi-supply voltage (MSV) is thus introduced to provide higher
exibility in controlling the power and performance trade-off. In region-
based MSV, circuits are partitioned into voltage islands where each
island occupies a contiguous physical space and operates at one supply
voltage. These tasks of island partitioning and voltage level assignments
should be done simultaneously in the oorplanning process in order to
take those important physical information into consideration. In this
paper, we consider this core-based voltage island driven oorplanning
problem including islands with power down mode, and propose a
method to solve it. Given a candidate oorplan solution represented by
a normalized Polish expression, we are able to obtain optimal voltage
assignment and island partitioning (including islands with power down
mode) simultaneously to minimize the total power consumption. Simulated
annealing is used as the basic searching engine. By using this approach,
we can achieve signicant power savings (up to 50%) for all data sets,
without any signicant increase in area and wire length. Our oorplanner
can also be extended to minimize the number of level shifters between
different voltage islands and to simplify the power routing step by placing
the islands in proximity to the corresponding power pins.
I. I
NTRODUCTION
Energy efciency has become one of the most important issues to
be addressed in todays System-on-a-Chip (SoC) designs because of
the increasing power density and the wide use of portable systems.
There are two kinds of power consumption: dynamic and leakage.
Dynamic power is caused by the charging and discharging of the
load capacitance during switching. Leakage power is due to the
sub-threshold currents when a device is turned off. There are many
techniques to reduce power consumption. One of the most effective
methods is by lowering the voltage supply. Multi-voltage design is
thus introduced to provide just enough power to support different
functional operations. Both dynamic and leakage power consumption
can be reduced in multi-voltage designs. For dynamic power, since
the consumption is proportional to the square of the voltage, a minor
adjustment to the voltage level can result in a signicant reduction.
For leakage power, the consumption can be reduced by powering
down parts of a chip when the functions are inactive.
Multi-voltage designs involve the partitioning of a chip into areas
called voltage islands that can be operated at different voltage
levels, or be turned off when idle. With the use of voltage islands,
the chip design process is becoming more complicated. We need to
solve the problems of island partitioning, voltage assignment and
oorplanning simultaneously under area, power, timing and other
physical constraints. These problems must be solved at the same time
since their results will signicantly affect each other. In addition,
there are other issues to be considered. For example, the voltage
islands should be placed close to the power pins in order to minimize
the power routing complexity and the IR drop. Besides, each island
requires level shifters to communicate with others and overhead in
area and delay will be resulted. These additional issues have created
many new challenges in generating oorplans for designs using
voltage islands. An example is shown in Figure 1. In this example,
the possible voltage levels of each core and groupings of similar
inactive periods (to generate islands with power down mode) are
shown on the right hand side. Assuming that the number of islands
is three, one possible partitioning is to group cores A, B and C
as one island operating at voltage 1.0V, core D on its own as one
island at voltage 1.5V and cores I, K, L and M as one island at
1.2V. Notice that other cores will be operated at the chip-level voltage
and the island containing I, K, L and M can be powered down
during sleep. A candidate oorplan solution for such a partitioning
and voltage assignment is shown on the left hand side.
There are several previous papers addressing similar voltage island-
driven oorplanning problem. One recent work is by Lee et al. [3].
Given a netlist without reconvergent fanouts, voltage assignment
(with two voltage levels of VDDL and VDDH) is rst performed
on the netlist according to the timing requirement before the oor-
planning step. Level shifters are then inserted into the nets according
to the voltage assignment result when a VDDL block drives a VDDH
block. At last, a power-network aware oorplanner is invoked to
pack the blocks such that the power-network resource, estimated as
the sum of the perimeters of the voltage islands, will be minimized.
As a result, blocks in the same voltage island will be placed close
to each other. In their approach, the voltage assignment step and
the oorplanning step are done separately. Hu et al. [2] have also
considered this simultaneous island partitioning, voltage assignment
and oorplanning problem in SoC designs. Simulated annealing is
used as the basic searching engine. Given a candidate solution,
perturbations are performed to split an island, change the voltage
of an island or change all the islands of one voltage to another
voltage. Chip-level oorplanning is then performed to nd a oorplan
in which compatible islands (islands with the same voltage) are likely
to be adjacent. An island merging process is then applied to reduce
the number of islands. At the end, island-level oorplanning is done
to each newly formed island to shrink its area. The whole process
is repeated until a satisfactory solution is obtained. Their approach
does not consider islands with power down mode and the search
space is large. Mak and Chen [7] have also addressed this problem
on SoC designs. Given a oorplanning input, the voltage assignment
and island partitioning problem is formulated as a 0-1 integer linear
program. In their approach, a few candidate oorplan solutions are
generated based on metrics like area and interconnect cost, then
voltage assignment and partitioning are performed on these candidate
oorplans using the ILP approach to identify the best candidate
solution. A fragmentation cost (number of adjacent cores operating
at different voltages) is used to model the power network complexity
but this cost is not related to the number of islands directly. There
are other works addressing issues like reliability [4] and temperature
reduction [5] in SoC voltage island partitioning and oorplanning.
For island partitioning, Wu et al. [6] and Ching et al. [8] minimized
the number of voltage islands after placement.
In this paper, we propose a oorplanning method for SoC designs
that is tightly integrated with the island partitioning and voltage
1-4244-1382-6/07/$25.00 ©2007 IEEE
644 assignment steps. Simulated annealing is used with normalized Polish
expression [1] as the oorplan representation.
1
Normalized Polish
expression is used because the slicing tree is a suitable data structure
on which island partitioning and voltage assignment can be done
optimally and efciently given one slicing oorplan. Simulated an-
nealing is adopted to perform the random search. In each step of
the annealing process, a candidate oorplan solution is generated
on which optimal island partitioning and voltage assignment will be
performed simultaneously to compute the smallest possible power
consumption for that candidate oorplan solution. This is done by
dynamic programming with an efcient cost table update technique.
In this way, we can integrate the three steps closely, and reduce the
searching space (instead of doing voltage assignment by the move
operations of the annealing process as in [2]). In this oorplanning
framework, we can also generate islands with power down mode to
optimize the total power consumption further. Our oorplanner can
be extended to consider the number of level shifters and the ease
of power network routing (proximity to power pins and shapes of
voltage islands). By using this approach, we can achieve signicant
power savings (up to 50%) for all data sets, without any signicant
increase in area and wire length.
We will dene the problem in section II, then the methodology
used will be discussed in section III. Experimental results will be
reported in section IV before the conclusion and discussion in the
last section.
II. P
ROBLEM
F
ORMULATION
In this problem, we are given a set of n cores with areas
A
1
, A
2
. . . A
n
and aspect ratio bounds [l
i
, u
i
]
for i = 1 . . . n. Each
core i is associated with a power table T
i
that species the legal
voltage levels for the core and the corresponding average power
consumption values. The