370

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 14, NO. 4, APRIL 2006

Toward Architecture-Based Test-Vector Generation

for Timing Verification of Fast Parallel Multipliers
Henrik Eriksson, Member, IEEE, Per Larsson-Edefors, Member, IEEE, and Daniel Eckerbert, Member, IEEE

AbstractFast parallel multipliers that contain logarithmic partial-product reduction trees pose a challenge to simulation-based
high-accuracy timing verification, since the reduction tree has
many reconvergent signal branches. However, such a multiplier
architecture also offers a clue as how to attack the test-vector
generation problem. The timing-critical paths are intimately
associated with long carry propagation. We introduce a multiplier
test-vector generation method that has the ability to exercise
such long carry propagation paths. Through extensive circuit
simulation and static timing analysis, we evaluate the quality
of the test vectors that result from the new method. Especially
for fast multipliers with a pronounced carry propagation, the
timing-critical vectors manage to stimulate a path, which has a
delay that comes close to the true worst case delay. We investigate
the complexity and run-time for the test-vector generation, and
derive timing-critical vectors up to a factor word length of 54 bits.
Index TermsArray multiplier, circuit simulation, critical
path, Dadda (DAD) multiplier, delay, over-turned stairs (OTS)
multiplier, static timing analysis (STA), test vectors, three-dimensional method (TDM) multiplier, timing verification, Wallace
(WAL) multiplier.

I. INTRODUCTION
EXT to functional verification, the primary concern for the
designer is to establish that the circuit fulfills its timing
requirements. Arithmetic circuits, among them the multiplier,
often have a decisive impact on overall system timing in electronic systems. When considering simulation-based timing verification, it turns out that test-vector generation for fast multipliers is a very challenging task. The reason is that the partial-product reduction tree of the multiplier has many reconvergent signal branches, and those make identification of the paths
that exhibit the longest delays, the critical paths, extremely difficult.
When using established computer-aided design (CAD) strategies to predict nonfunctional circuit properties, the highest accuracy is obtained by employing circuit-level simulation. Cir-

Manuscript received March 6, 2005; revised December 18, 2005. This work
was supported by INTELECT and the Circuit Initiative at Chalmers University
of Technology.
H. Eriksson was with the VLSI Research Group, Department of Computer
Science and Engineering, Chalmers University of Technology, Gothenburg
SE-412 96, Sweden. He is now with SPSwedish National Testing and
Research Institute, Boras SE-501 15, Sweden.
P. Larsson-Edefors is with the VLSI Research Group, Department of Computer Science and Engineering, Chalmers University of Technology, Gothenburg SE-412 96, Sweden.
D. Eckerbert was with the VLSI Research Group, Department of Computer
Science and Engineering, Chalmers University of Technology, Gothenburg
SE-412 96, Sweden. He is now with IMEGOthe Institute of Microelectronics,
Gothenburg, Gotenburg SE-411 33, Sweden.
Digital Object Identifier 10.1109/TVLSI.2006.874297

cuit-level simulation is indeed time consuming, especially when

test patterns grow large, but in exchange it gives very accurate
figures on power dissipation, noise robustness, delay characteristics, etc. The advantage of circuit simulation over static timing
analysis is that it offers the capability to capture time-domain
dependencies between active devices, logic wiring, as well as
power distribution networks. Circuit simulation is the obvious
choice when we need to account for, for example, delay incurred by wire crosstalk. Circuit simulation is the only choice
in situations when unorthodox circuit techniques are used, such
as when power gating features are deployed in logic circuits.
Static timing analysis (STA) methods offer an altogether different approach to timing verification, in that they represent
a test-vector-independent and deterministic way to reveal the
signal propagation path(s) that are critical and find the actual
delay associated with these path(s). However, since the device
and wire models used in transistor-level STA tools have to be
simplified, the delay figures obtained are not as accurate as those
that can be obtained from a circuit simulator. Furthermore, STA
methods for transistor-level netlists have limitations in what
transistor topologies can be analyzed, such as circuits for the
emerging area of power gating.
To find a practical way to utilize the accuracy offered by circuit simulation, we clearly need to constrain simulation run-time
by limiting the size of the test pattern. The ideal approach would
be to generate only one test-vector combination, which would
exercise a circuit path that either represents a single critical path
or belongs to the class of critical paths. For multipliers this is an
unsolved problem, and unless and until a solution emerges, STA
will remain the only practical option for timing verification.
In the following, we will present work on test-vector generation for the purpose of obtaining the worst case delay in circuit
simulation of fast multipliers. Our approach is unique in that it
is based on identification of structural properties of the multiplier architecture. Section II provides a review of static timing
analysis and circuit simulation for timing verification, as well as
a brief introduction to multipliers. Following that, in Section III,
our new method for finding critical vectors is presented and in
Section IV the vectors generated by this method are evaluated.
The paper is concluded in Section V.
II. PRELIMINARIES
A. STA Versus Circuit Simulation for Timing Analysis
One might expect STA tools to be able to report critical vectors since those tools find critical paths. If so, these vectors
could be used in a circuit-level simulator to get accurate delay
values. There are, however, three complications to this ideal
timing-verification flow. First, transistor-level STA tools are not

1063-8210/$20.00 2006 IEEE

ERIKSSON et al.: TOWARD ARCHITECTURE-BASED TEST-VECTOR GENERATION FOR TIMING VERIFICATION OF FAST PARALLEL MULTIPLIERS

fully compatible with innovative circuit techniques, effectively

blocking STA as a route to test-vector generation for some circuits. Second, STA tools are based on algorithms that do not explicitly consider the input vectors, and, therefore, vectors may
not be provided.1 Third, even in the event of an STA tool that
provides vectors, thosedeep critical vectors are based on simplified transistor and wire models.2 Further, since such vectors are
not based on architectural analysis, they need to be redefined
subsequent to even slight changes to the implementation.
A different approach to fusing STA and circuit simulation is
based on identifying the critical path and its circuits. A netlist
of a subcircuit, which represents the identified critical path and
adjacent transistors, can be used in circuit simulation to provide
more accurate delay values. This method works as long as the
STA tool finds the true critical paths and not the pseudocritical
ones, which may result from the simplifications made to implement a faster tool [1].
Due to an ever increasing level of integration, deep-submicron effects in combination with increasing transistor counts,
make circuit-level simulators too slow for exhaustive searches
and STA tools too inaccurate. Therefore, there are, in principle,
only two things that can be done to obtain more accurate timing
data. Either one tries to improve the accuracy of the STA tools or
one tries, as Cheng proposes [2], to find clever ways of deriving
timing-critical vectors to use during circuit-level simulation.
To increase the speed of STA tools, assumptions such as
single-input transition, slope approximation, and the choice of
a propagation signal based on a single voltage-time point are
made. These assumptions were evaluated by McMurchie and
Sechen and they showed that the delays provided by STA tools
can be optimistic by as much as 30% for conventional static
CMOS gates [3]. Their solution is waveform-based timing
analysis (WTA) [3], where they use an advanced (macro-level)
transistor model for their devices and propagate waveforms
rather than slopes; the latter is the case in conventional STA
tools. McMurchie and Sechen claim that the delay penalty
(compared to a conventional STA tool) incurred by their
method is acceptable.
Another approach to improve the accuracy of timing analysis
is proposed by Song et al. [4]. Here, transistors are modeled as
two-port networks to improve accuracy compared to simpler but
faster Elmore calculations. This enables the handling of multiple
switching inputs. Obviously, this more complex model reduces
the speed of the analysis. Other publications within the timing
analysis research field are regarding statistical timing analysis
[5]. Here, gate delays are modeled as random variables and the
results from the tool represent bounds on circuit delays.
Although the discussed methods are useful extensions to improve existing STA methods, it is doubtful if there are viable
ways to acquire timing data which is accurate when compared
to circuit simulation. When higher order effects are added to
1To some degree, STA tools consider vectors. If instructed, many STA tools
can perform false-path elimination to remove critical paths that are logically
impossible. False paths happen to be very common in XOR-dominated circuits
such as multipliers.
2Concerning, e.g., crosstalk between wires, if wire capacitance data exists,
the STA tool assumes worst case switching conditions and splits the capacitance into two; one connected to each wire. This is an inaccurate and pessimistic
method.

371

models, not only the accuracy, but also the run-time of STA will
approach that of circuit simulators.
We believe a more profound impact on timing verification can
be achieved if suitable test vectors for simulation-based timing
verification could be derived. In subsequent sections, we present
some compelling indications that knowledge about the inherent
structure of the multiplier architecture can be used to generate
timing-critical test vectors.
B. Brief Review of the Parallel Multiplier
Although being such an important component, there has been
relatively little progress in the development of new multipliers.
To a large extent, fast multipliers are still based on the work by
Wallace [6] and Dadda [7].
Three distinctive steps are common for all multipliers:
1) partial-product generation; 2) compression of partial
products in a reduction tree or an array; and 3) fast final
vector-merging addition. In the most straightforward case, the
partial-product bits are formed using conventional AND gates.
Fewer product bits for the same word length can be achieved
by using Booth [8] or modified Booth [9] encoding, however,
the effectiveness of these strategies has been questioned [10].
We briefly discuss the proposed method in the context of Booth
encoding in Section III-F, after the method has been introduced
and described.
In the design of a reduction tree, two things need to be considered: 1) which kind of compressor circuit is to be used and
2) how these circuits should be interconnected to achieve short
delay. A compressor, or counter circuit, counts the number of
ones on its input terminals and compresses that number to a
smaller number of ones at the output terminals. The simplest
compressor is a conventional full-adder cell, but more complex
compressors have been presented [11][13].
Concerning the interconnections, there is an inverse relationship between the length of the critical path and the complexity of
the wiring. In most cases, simpler wiring implies longer delay.
This relationship is perfectly illustrated in the ripple-carry array
multiplier [14], which has a simple wiring scheme but a long
critical path. One example of the other extreme is the Wallace
multiplier, which has a complex wiring scheme but a short critical path.
Regarding the final vector-merging adder, the fastest adder
available, e.g., a carry-lookahead adder, could be used to achieve
a minimal delay. However, the delays of the least significant
product bits will then be unnecessarily long. Hardware would
be wasted and, consequently, also area and power. To obtain
the overall optimal delay, the final adder has to be carefully tailored to the delay profile of the primary outputs from the partial-product reduction tree. Design methods pertaining to the
final adder are discussed by Oklobdzija et al. [10].
In the present paper, we will restrict the selection of compression circuits to half adders (HAs) and full adders (FAs). Oklobdzija et al. [10] and Wang et al. [15] have both derived the op, in a
timal (minimum) number of compressor circuits,
reduction tree, using HAs and FAs only

372

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 14, NO. 4, APRIL 2006

Fig. 2. Generation of critical test vectors. The ps represent partial-product bits

and the cs represent carry bits output from the previous column. The generation
starts from the left-most side. Bits a ; a ; b , and b all need to be one to start
the propagation. To keep the propagation alive, a column must contain, after all
incoming carry bits have arrived, at least two ones and, additionally, the total
number of ones must be an even number.

quence. However, finding that vector combination is a very difficult task, since it depends on the underlying multiplier architecture. The triangular placement (Fig. 1) suggests a heuristic:
the worst horizontal propagation path is twice the length of the
vertical path. Hence, we need to find vectors that stimulate a
carry to propagate across the columns.3
A. Previous Method
Fig. 1. Six-bit multipliers: different shapes for different compressor placements (triangle, rhomb, and rectangle). The LSB of the product is produced by
compressor number 1, and the MSB is obtained from compressor number 10,
hence, carry signals would propagate from the left to the right. In the triangular
and the rhomboid placements, a certain significance level is represented by
a column, while such a level is represented by a diagonal in the bottom,
rectangular one.

An elegant approach to determine vectors that stimulate carry

propagation was presented by Rlling [16]. The idea is as follows. For an -bit multiplier, choose two vectors and
and
A multiplication yields

Here,
is the size of the multiplier (in bits) and
is
the number of HAs. This lower bound actually corresponds to
the hardware usage in e.g., Dadda, three-dimensional method
(TDM), and array multiplier schemes.
The compressors can be placed in many ways: triangular
placement, rhomboid placement, or rectangular placement
(Fig. 1). The Manhattan (rectilinear) distance between the cells
in the triangular matrix is taken to be a normalized wire length.
We assume a triangular placement, which makes the derivation
of critical vectors more transparent to the reader. A triangular
placement slightly favors some multiplier schemes and slightly
penalizes others, but this effect will be insignificant for the
result of this paper. A long (critical) wire will remain long
regardless of placement.
III. A METHOD FOR FINDING CRITICAL TEST VECTORS
In order to find worst case delays using circuit simulation,
a circuit needs to be stimulated by a worst case test vector se-

Here, and can be selected to stimulate a carry propagation

to column
. The drawback is
from column
that propagation will only occur in roughly one fourth of the
columns in the multiplier.
B. New Method
We propose another approach to derive timing-critical vectors that stimulate long-carry propagation. The new approach
is based on a restricted search. If we assume that the previous
input vectors were zero, the least significant four bits (
,
and ) need to be one, to set up a carry propagation (Fig. 2). In
3A small disclaimer though: the sum delay of an FA cell is usually (at least
for the mirror adder [14]) roughly twice the carry delay. That means that the
horizontal and vertical paths are equally important and this is true for the array
multipliers. For the logarithmic multipliers there will be a logarithmic compression in the vertical direction and, therefore, the critical propagation will be in
the horizontal direction.

ERIKSSON et al.: TOWARD ARCHITECTURE-BASED TEST-VECTOR GENERATION FOR TIMING VERIFICATION OF FAST PARALLEL MULTIPLIERS

the subsequent columns, the number of ones needs to be an even

number, after all input carries have arrived, to propagate an incoming carry bit. Otherwise, the incoming carry bit is killed or
a new carry is generated in this column; either way the carry
propagation path is broken.
and to enable carry
As a consequence, when selecting
propagation, there are only two possibilities; either set both to
zero or set both to one. If both are set to one, we face the exact
same situation again to enable a continued carry propagation:
either set both and to zero or both to one. However, if both
and are set to zero, there will be an odd number of ones
in the next column, and we have to choose between
and
or
and
to enable a continued carry
propagation.
bits of vectors
This selection process continues until all
and , respectively, have been determined. Then all partialproduct bits at the right-hand side of the partial-product triangle
have also been determined, and we can check how far into the
right-hand side of the triangle the carry bit propagates. Each
complete vector corresponds to one path from the root to a leaf
in the search tree. All leaves are exhaustively searched for the
longest overall carry propagation path.
The search algorithm is expressed as pseudocode in
Algorithm 1. It is basically a depth-first traversal of the
search tree, in which partial-product and carry bits are set
according to traversed branches. In each leaf of the search tree,
the propagation length stimulated by the present vectors is
compared with the previously best vectors.

depth01 = 0 then
adepth+1 ; ppdepth+1;0 ( 1
bdepth+1 ; pp0;depth+1 ( 1

if

vr

else

depth+1 ; ppdepth+1;0 ( 0
bdepth+1 ; pp0;depth+1 ( 0
vldepth01 ( 1

end if
end if
if depth

02
( ^
( b(1 2)
< N

ppi;j
noc

ci;j

(1

2 f0

a i ; bi

;i

; i; j

ci;j

vr

depth01

(
( max

if

repeat
< N

( depth + 1

if odddepth+1 = 1 then
if

depth01 = 0 then
adepth+1 ; ppdepth+1;0 ( 0
bdepth+1 ; pp0;depth+1 ( 1

vr

else

depth+1 ; ppdepth+1;0 ( 1
bdepth+1 ; pp0;depth+1 ( 0
vldepth01 ( 1

end if
else

0 depth+2

c ;

0 2 then
( ^ + 
( b(1 2) ( + )c (
+
+ 
(1 +

0 ( 0 1) +
ai

bj ; i

nock

j; i

ppi;j

ci;j

;k

;i

>

N; i

nock

02

ci;N

(ppi;j
m;

oddi

018i < N

8 ) (
^ carry 8 [
ci;j ; k
i;

+j

i N; m]

max then
lmax ( l
amax ( a
bmax ( b

l > l

depth

ppi;j

if (vrdepth = 0 _ vldepth = 0) ^ depth

then

(1

if depth =

oddk

c ;

ci;j ); i

noc

else

carryN +i

+j =

end if

;i

(ppi;j

;i

1

end if

length of input operands;

ppi;j

carrydepth+1

0 1g
( 1 2 f 0 1g
( 1 2 f 0 1g
( 0 + 2 f 0 1 2g
02 ( 1
odd0 carry0 carry1 ( 1
odd1 odd2 ( 0
depth ( 0

+ j = depth + 2; i

odddepth+2
depth + 1

;N

;i

= depth+2; i; j

(ppi;j + ci;j )

ci;j

i; j

then

bj ; i + j

ai

depth + 1

Algorithm 1: Full Search

Require:

373

end if
depth

( depth 0 1

end if
until depth =

01

Independent of how the compressor cells in the reduction

tree are interconnected, the aforementioned derivation is valid.
The same number of carry bits have to be produced to the next
column and the way the sum bits are compressed has no effect. This means that the derived critical vectors will cause the
same long carry propagation regardless of underlying multiplier
scheme: e.g., array, Dadda, or TDM.
C. Complexity of New Method
As can be deduced from Fig. 2, the number of vectors that
. This growth rate is conhave to be evaluated grows as

374

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 14, NO. 4, APRIL 2006

TABLE I
TEST-VECTOR GENERATION TIME FOR DIFFERENT WORD LENGTHS

TABLE II
FOUND CRITICAL VECTORS a AND b FOR DIFFERENT WORD LENGTHS (WLS),
FOR A FULL SEARCH. PROPAGATION LENGTH (PL) AND THE QUALITY METRIC
(QM) IS ALSO STATED FOR EACH PAIR OF VECTORS

firmed by the scaling of the test-vector generation time on a

three-year-old conventional desktop PC (AMD
MB RAM) for a program producing critical vectors. The generation times can be seen in Table I (full search), where each
specific generation time is roughly twice the time of the previous one. Since we target to derive timing-critical vectors up
to a word length of 54 bits, the growth rate implies a generation time for the 54-bit case of at least 1900 years, which is
infeasible.
As a consequence, with the hardware at our disposal at the
present time, a full search is only feasible for word lengths up
to roughly 32 bits. For larger word lengths (preferably up to
54 bits), we have to reduce the search space considerably, i.e.,
to sacrifice some of the quality of the vectors in favor of shorter
run-time. The best partial-search heuristic we have found is to
prune one of the branches, when we have an odd number of ones
and
and
in the present column, i.e., not try both
and
, but always choose
and
.
The run-time of this partial-search heuristic is also presented in
Table I, and here we see that a specific generation time is the
sum of the two previous ones, i.e., a growth rate according to
. This growth rate makes it
the Fibonacci sequence [17],
possible to derive vectors up to 54 bits.
D. Quality Metric for Timing-Critical Vectors
In order to assess the quality of the vectors found by our fullsearch and partial-search methods, a quality metric is needed.
Since the vectors have been derived with carry propagation in
mind, the quality metric is defined to be

Here, PL is the propagation length, i.e., the number of stages the

is the maximum number of
carry propagates through, and
stages for a specific word length . Consequently, e.g., vectors
that stimulate a carry propagation through the entire multiplier
, which from our point of view is indicative
will get
of the perfect vector.
E. Obtained Timing-Critical Vectors
The obtained timing-critical vectors are presented in Table II
for the full search and in Table III for the partial search. The
quality metric for the vectors derived by the full search is larger
than 90 (and increasing) for all vectors with a word length larger
than 18, whereas for the partial search the quality metric is always between 80 and 85.

F. Application of New Method To Signed Multipliers

The method, as it is presented here, only works for unsigned
multipliers, where partial-product bits are generated by AND
gates. A transformation of the method to suit, e.g., Booth multipliers is out of the scope of this paper. Furthermore, this transformation is far from trivial, but not impossible. The feature of
the signed multiplier that makes carry propagation mechanisms
different from the unsigned case is found in the complex way
that the partial products are formed. For example, the recoding
logic of the modified Booth multiplier makes it harder to select
appropriate input vector bits corresponding to partial-product
and carry bits which stimulate carry propagation.

ERIKSSON et al.: TOWARD ARCHITECTURE-BASED TEST-VECTOR GENERATION FOR TIMING VERIFICATION OF FAST PARALLEL MULTIPLIERS

TABLE III
FOUND CRITICAL VECTORS a AND b FOR DIFFERENT WORD LENGTHS (WLS)
FOR A PARTIAL SEARCH. PROPAGATION LENGTH (PL) AND THE QUALITY
METRIC (QM) IS ALSO STATED FOR EACH PAIR OF VECTORS

IV. EVALUATION OF THE CRITICAL TEST VECTORS

Six multiplier schemes with different properties will be analyzed in five different cases. This approach was selected in
order to thoroughly evaluate the quality of the critical test vectors, i.e., quantify how well the delay obtained from a simulation using the proposed timing-critical vectors describes the true
worst case delay. The five cases are:
1) exhaustive HSpice simulations on all six schemes at 5-bit
word length;
2) exhaustive HSpice simulations on all six schemes at 6-bit
word length;
3) exhaustive HSpice simulations on TDM and Wallace
schemes at 8-bit word length;
4) ad hoc event-driven simulation of the TDM scheme for 8to 13-bit word lengths;
5) STA/PathMill analyses versus HSpice simulations for all
six schemes at 8-, 16-, and 32-bit word lengths.
To conform to the principle behind the test-vector derivation, we
have in all five cases restricted the vector transitions so that input
vectors initially are zero. Also, the final adder used in cases 14
is fairly slow for two reasons. First, in these cases the multipliers
are small, so only a limited speed improvement can be obtained
by using a logarithmic final adder. Second, the use of a conventional ripple-carry final adder in the multiplier makes it easier
to verify the carry-propagation caused by the critical vectors.
A. Multiplier Schemes
Six different schemes have been chosen based on their diverging characteristics and popularity among designers. They
range from slow and straightforward array multipliers to fast
and complex reduction-tree multipliers. There are two primary
inputs to these unsigned multipliers, input and .
RCA Multiplier: This is the straightforward way of implementing an array multiplier and its similarity with the
paper-and-pencil-way of multiplication is obvious [14]. The
RCA multiplier has a regular placement of cells and a trivial

375

wiring scheme at the cost of a critical path delay that is the

longest among the six schemes used in our evaluation.
CSA Multiplier: An increased performance compared to the
RCA multiplier can be obtained by replacing the RCAs with
CSAs. A final carry-merge or carry-propagate adder is needed
to form the final product [14].
Overturned-Stairs (OTS) Multiplier: This is a straight-forward implementation of the multiplier presented by Mou [18].
It uses the suggested branches and connectors, and achieves a
.
worst case path of
Dadda (DAD) Multiplier: In the Dadda (DAD) multiplier [7],
the key is to reduce the number of rows in the partial-product
from
matrix following the series
higher to lower values. This produces a reduction tree with a
.
worst case path of
Wallace (WAL) Multiplier: In the Wallace (WAL) multiplier
[6], the partial-product bit matrix is divided into parts containing
three rows each. Possible leftover rows are not consumed until
the next step of the algorithm. The other parts are compressed
from three rows down to two by using HAs and FAs. This continues until there are only two rows left, for which a fast-final
adder can be used.
TDM Multiplier: Oklobdzija et al. [10] presented a heuristic
for a multiplier, where the input to output delays of the compressors are carefully tabulated and used to steer the interconnection
of compressors in a globally delay-optimal way. The TDM multiplier always yields optimal or near optimal delays [19]. The
TDM is the only one of the selected schemes where the interconnect structure is dependent on the compressor delays.
B. Exhaustive Hspice Simulations on Small Multipliers
To evaluate our timing-critical test vectors, all 1024 vector
combinations4 for a 5-bit multiplier have been simulated on all
six multiplier schemes in HSpice using parameters provided for
a commercially available standard 0.13- m process, at a supply
voltage of 1.2 V. Only one threshold voltage was available.
The gates were sized to compensate for mobility differences
and stacked transistors. Only one driving strength was provided
for each gate type. A capacitance depending on estimated wire
length was back-annotated in the generated netlists.
As stated several times already, we have assumed that the
multiplier starts from zeroed inputs and then makes a transition
to the two input vectors that are presently evaluated. To be able
to study the correlation between delay and power dissipation,
the power dissipation for the vectors was also captured during
the simulations. The resulting power-delay plots are shown in
Fig. 3. The encircled points correspond to the critical test vectors and being applied to either and , or to and . The
point marked by a triangle represents the application of vectors
containing only ones to and . It has occasionally been assumed, e.g., in [20], that the vectors with only ones are the
delay-critical vectors but the plots indicate that, regardless of
scheme, those vectors only enable carry propagation through
roughly half of the multiplier. However, we also note that in
most of the multipliers the vectors containing only ones are
associated with the largest power dissipation. This property is
4 Multiplier inputs, x and y , are each forced to make a transition from 0 to
any of 2 values.

376

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 14, NO. 4, APRIL 2006

Fig. 3. Average power (W) versus delay (s) for 1024 vectors for 5-bit multipliers. A uniform scaling of the axes is used to expose the differences between the
multiplier schemes: (a) RCA, (b) CSA, (c) overturned-stairs multiplier (OTS), (d) DAD, (e) WAL, (f) TDM.

natural, since many input bits have to be one to produce partial-product bits that are one in the reduction tree. One single
zero bit in the input vector immediately forces partial-product
bits to zero.
From Fig. 5, we can see that the proposed timing-critical test
vectors and actually correspond to the category of vectors
that exercise the longest paths for all the multipliers. For WAL
and TDM, the proposed vectors are identical to the worst case
vectors and regardless of multiplier scheme the critical vectors
are among the top 10% of vectors with the longest delay. There
is a strong reason to believe that this ratio will become even
smaller for large logarithmic multipliers. In large logarithmic
multipliers, the horizontal delays will dominate the vertical delays, since columns experience increasingly compressed logic
depth.
To see how well the delay of the critical vectors matches the
worst case delay as the multiplier size increases, exhaustive simulations were carried out for a 6-bit case, involving all six multipliers, and an 8-bit case, involving only the TDM and WAL
multipliers.5 As before, the term exhaustive refers to all vector
transitions starting with zeroed inputs. The results from the simulations are summarized in Table IV. Note that V1 represents the
case when the timing-critical vectors and of Table II are
5The run-time of circuit simulations attempting to use, in some sense, exhaustive test vector sequences, quickly grows with factor word length. Even after
restricting the vector transitions to start from zero, the run-time for an 8-bit simulation, distributed on seven Linux and UNIX machines (Two Sun Blade 1000,
one Sun Blade 100, two Sun Ultra 10, and two PCs Intel 2.0 GHz), exceeded
one week per multiplier scheme.

TABLE IV
QUALITY OF CRITICAL VECTORS FOR DIFFERENT WORD LENGTHS (WLS)

applied to inputs and of the multiplier, whereas V2 represents the swapped case, when is used for input and is used
for input .
For each of the six multiplier schemes, the table entries are
organized so that the top row represents how many of the simulated vectors exhibit a longer delay than the evaluated critical
vectors and do ( and will change with word length only).
In the bottom row, the delay caused by the critical vector pair
is related to the true worst case delay. Hence, e.g., 0% in the
top row means that the critical vectors are identical to the worst
case vectors.

ERIKSSON et al.: TOWARD ARCHITECTURE-BASED TEST-VECTOR GENERATION FOR TIMING VERIFICATION OF FAST PARALLEL MULTIPLIERS

377

Fig. 5. Delay values (s) from the event-driven simulator (Y axis) versus those
obtained from HSpice (X axis) for an 8-bit TDM multiplier. (A perfect match
would have meant a straight 45 line).

and actually are identical for 5 and 6 bits (see Table II). In
the 6-bit case there is an increasing number of vectors that exhibit longer delay, thus decreasing the delay prediction quality.
We can see that the delay for the critical vectors approximately
belong to the top 30% for the array multipliers, and to the top
10% for the other faster schemes. Fig. 4 shows the delay and
power values for 5-, 6-, and 8-bit TDM multipliers for all 1024,
4096, and 65 536 vectors. Note the explosion of different delay
and power values located after roughly one third of the multiplier length.
C. Ad Hoc Event-Driven Simulation of the TDM Multiplier

Fig. 4. Impact of vectors on delay (s) and average power (W) in the TDM
multiplier for increasing word lengths: 5, 6, and 8 bits. The timing-critical vectors are as before encircled and the one vectors are marked with a triangle.
(a) 5-bit TDM. (b) 6-TDM. (c) 8-TDM.

We see that the delay prediction quality of the proposed critical test vectors is decreasing when analyzing 6-bit instead of
5-bit multipliers. This is due to the fact that the critical vectors

Since the number of vectors increases exponentially with

word length, it is impossible to use HSpice to simulate all
vectors for a multiplier with an
larger than 8 bits (despite
the restriction on zeroed inputs). Therefore, a simplified ad hoc
event-driven simulator was developed to make it possible to
simulate all vectors for larger multipliers. Among the properties that simplify the ad hoc event-driven simulator are that all
multiplier nodes are reset at start-up and that all fan-outs in the
multiplier are one.
In Fig. 5, the delay values from the HSpice simulations of
the 8-bit TDM multiplier are plotted against the corresponding
delay values from the event-driven simulator. We see that the
agreement is fairly good for most of the vectors, but for some
(quite many) there are much larger delays obtained from the
event-driven simulator. The reason for this discrepancy is that
in the HSpice simulations glitches can overlap transitions in
such way that glitches at the output vanish. This is not possible in the event-driven simulator. It assumes ideal input and
output signals, i.e., rise and fall times are infinitesimal. As a
consequence, all input transitions will potentially cause output
transitions. Thus, glitches may propagate long distances in the
event-driven simulator. The critical vectors are, as in previous
figures, encircled in Fig. 5.

378

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 14, NO. 4, APRIL 2006

TABLE V
PERCENTAGE OF VECTORS THAT HAVE A LONGER DELAY THAN THE CRITICAL
VECTORSCHECKED WITH THE EVENT-DRIVEN SIMULATOR

Despite the delay inaccuracies of the event-driven simulator

for many vectors, we believe that the results can serve as pessimistic bounds for evaluation of critical vectors at larger word
lengths.
In Table V, the percentage of vectors that have a longer delay
than the critical vectors are presented. Still, the TDM multiplier
is used as the test vehicle. We see that for all simulated word
lengths, the critical vectors belong to the 2% of vectors having
the longest delay.
D. HSpice Simulations Versus STA Analyses
We now feel fairly confident to continue and compare HSpice
delay simulations using the proposed timing-critical test vectors
with results from a commercial STA tool (in our case PathMill).
As explained in Section II-B, different adder types should be
selected for different parts of the output delay profile of the reduction tree in order to obtain optimal performance. For this
comparison, we have complemented the previous multipliers,
which until now have been equipped with a slow final RCA, with
one set of multipliers that uses a KoggeStone parallel-prefix
adder [21] as a final adder. This choice will give an unnecessarily long delay in the least significant bits, but the worst case
delay will be correctly analyzed and simulated. KoggeStone
was selected since it is straightforward to implement, i.e., it
is one of the tree adders with the least complex interconnect
structure.
PathMill uses the same netlists and parameters (BSIM3 and
BSIM4 models) that were used for the HSpice simulations.
PathMill eliminates false paths but, unfortunately, it cannot
output the vectors that cause the critical delay; it only outputs
information about which transistors are being traversed from
primary inputs to primary outputs. As all STA tools, it has one
very important feature, it will traverse a much larger search
space than was possible in Section III when we derived the
critical vectors.
The results from the HSpice simulations as well as the PathMill analyses are presented in Table VI. Both a slow (ripplecarry) and a fast (KoggeStone) final adder have been evaluated
in the simulations. Since it does not make any sense to employ
a fast final adder in the RCA multiplier, that case was omitted
from the comparison.
First, we summarize some general observations on the performances of the multipliers per se. For a 32-bit multiplication,
the logarithmic TDM, WAL, and DAD schemes (with fast final
adder) are outstanding, having delays that are more than 75%
shorter than that of an RCA array scheme. The OTS has slightly

longer delays than the logarithmic ones, but is far from poor as
the array multiplier. For a small multiplier (8 bit), delay differences between the multipliers are small, and employing a fast
final adder only pays off slightly.
The first observation about the delay values in Table VI is
that the values from HSpice always are shorter than the ones
from PathMill. This is good (and expected), since PathMill is
designed to be truly pessimistic. We also know, from the evaluations earlier in the article, that our vectors may not be the worst
case ones, since we have restricted our method to test vector
transitions that start from zero.
We also observe that regardless of word length, the agreement
is the best for the logarithmic multipliers. For the array multipliers, on the other hand, the agreement is quite poor. This is expected, since array multipliers contain propagation paths in the
sum direction that traverse an equal or greater number of gates
than the paths in the carry direction. Because the sum delay of
adder cells often is in excess of twice the carry delay, array multipliers will not experience the longest delays for the vectors we
propose.
Finally, we must once more bear in mind that due to simplifications in algorithm and models, the critical paths that are
identified by an STA tool may not be the true ones. In fact, for
one of the 5-bit multiplier schemes, we made an effort to manually derive6 the vector transition that caused what we supposed
was the worst case delay. We then used this STA-generated
vector transition for delay simulation in HSpice. When comparing the STA-generated vector transition with the vector from
our method, the STA-generated vector gave a shorter delay.
V. CONCLUSION
Although far from perfect, we believe that the presented critical vectors can be a stepping stone on the way toward architecture-based test-vector generation for timing verification of
logarithmic multipliers. The carry-propagation path is the most
critical one in logarithmic multipliers, since the sum paths are
compressed, and our critical vectors have been derived with this
fact in mind.
In this work, we have made the restriction that a vector transition always starts from zeroed inputs. Even if we, in some
situations, have found that the proposed critical vectors match
exactly the actual worst case vectors, the restricted transition
is a fundamental weakness, since the worst case vector transition often starts with a pair of nonzero vectors. We are currently considering methods to manipulate the initial vectors,
while keeping the carry propagation behavior.
A possible extension of this work may be found in test-vector
generation for functional verification. Since many long paths
are exercised by the critical test vectors proposed here, they can
be suitable for an initial functional sanity check of a multiplier
design; the reason being that when many paths are exercised,
there is a good chance to detect misrouted wires and faulty gates.
ACKNOWLEDGMENT
The authors would like to thank Dr. L. J Svensson, who
provided many insightful comments that improved the content
6We had guidance from the outputs and a few of the inputs provided by PathMill.

ERIKSSON et al.: TOWARD ARCHITECTURE-BASED TEST-VECTOR GENERATION FOR TIMING VERIFICATION OF FAST PARALLEL MULTIPLIERS

379

TABLE VI

DELAY VALUES.t

= HSPICE SIMULATIONS USING THE CRITICAL VECTORS. t = DELAY VALUES FROM PATHMILL

of this paper. They would also like to thank the anonymous reviewers for their valuable comments.
REFERENCES
[1] T. Thiel, Have I really met timing?Validating primetime timing reports with spice, in Proc. Des., Automat. Test Eur. Conf. Exhibition,
2004, pp. 114119.
[2] K.-T. Cheng, The confluence of manufacturing test and design validation, in Proc. Int. Test Conf., 2003, pp. 12931293.
[3] L. McMurchie, WTAWaveform-based timing analysis for deep
submicron circuits, in Proc. Int. Conf. [Link] Des., 2002,
pp. 625631.
[4] H.-Y. Song, Timing analysis for full-custom circuits using symbolic
DC formulations, in Proc. Int. Workshop Logic Synthesis, 2002, pp.
203208.
[5] A. Agarwal, Statistical timing analysis using bounds and selective
enumeration, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst.,
vol. 22, no. 9, pp. 12431260, Sep. 2003.
[6] C. S. Wallace, A suggestion for a fast multiplier, IEEE Trans. Electron. Comput., vol. 13, pp. 1417, Feb. 1964.
[7] L. Dadda, Some schemes for parallel adders, Alta Frequenza, vol. 34,
no. 5, pp. 349356, May 1965.
[8] A. D. Booth, A signed binary multiplication technique, Q. J. Mech.
Appl. Math., vol. 4, pp. 236240, 1951.
[9] W.-C. Yeh and C.-W. Jen, High-speed booth encoded parallel multiplier design, IEEE Trans. Comput., vol. 49, no. 7, pp. 692701, Jul.
2000.
[10] V. G. Oklobdzija, D. Villeger, and S. S. Liu, A method for speed optimized partial product reduction and generation of fast parallel multipliers using an algorithmic approach, IEEE Trans. Comput., vol. 45,
no. 3, pp. 294306, Mar. 1996.
[11] E. E. Swartzlander Jr., Parallel counters, IEEE Trans. Comput., vol.
C-22, no. 11, pp. 10211024, Nov. 1973.
[12] W. J. Stenzel, W. J. Kubitz, and G. H. Garcia, A compact high-speed
parallel multiplication scheme, IEEE Trans. Computers, vol. C-26, no.
10, pp. 948957, Oct. 1977.
[13] P. J. Song and G. De Micheli, Circuit and architecture trade-offs for
high-speed multiplication, IEEE J. Solid-State Circuits, vol. 26, no. 9,
pp. 11841198, Sep. 1991.
[14] J. M. Rabaey, A. Chandrakasan, and B. Nikolic, Digital Integrated Circuits, A Design Perspective, 2nd ed. Upper Saddle River, NJ: Prentice-Hall, 2003.
[15] Z. Wang, G. A. Jullien, and W. C. Miller, A new design technique for
column compression multipliers, IEEE Trans. Comput., vol. 44, no. 8,
pp. 962970, Aug. 1995.
[16] W. Rulling, A remark on carry-free binary multiplication, IEEE J.
Solid-State Circuits, vol. 38, no. 1, pp. 159160, Jan. 2003.
[17] L. P. Fibonacci, Liber Abaci, 1202 ed. New York: Springer-Verlag,
2002.
[18] Z.-J. Mou and F. Jutand, Overturned-stairs adder trees and multiplier
design, IEEE Trans. Comput., vol. 41, no. 8, pp. 940948, Aug. 1992.
[19] P. F. Stelling, C. U. Martel, V G. Oklobdzija, and R. Ravi, Optimal
circuits for parallel multipliers, IEEE Trans. Comput., vol. 47, no. 3,
pp. 273285, Mar. 1998.

[20] J.-N. Ohban, Multiplier energy reduction through bypassing of partial

products, in Proc. Asia-Pacific Conf. Circuits Syst., 2002, pp. 1317.
[21] P. M. Kogge and H. S. Stone, A parallel algorithm for the efficient
solution of a general class of recurrence equations, IEEE Trans.
Comput., vol. C-22, no. 8, pp. 786793, Aug. 1973.
Henrik Eriksson (S00M04) was born in 1974
and grew up in Fellingsbro, Sweden. He received
the [Link]. degree in electrical engineering from
Linkping University, Linkping, Sweden, in 1998,
and the Ph.D. degree in computer engineering from
Chalmers University of Technology, Gothenburg,
Sweden, in 2003, where his main focus was on
efficient implementation of CMOS arithmetic circuits, primarily adders and multipliers, as well as
techniques for power consumption estimation.
Since 2004, he has been working at SP Swedish
Testing and Research Institute, Boras, Sweden, where he focuses on research
dependable embedded systems with an emphasis on dependable integrated and
distributed computer systems for avionics and automotive electronics.

Per Larsson-Edefors (M05) received the [Link].

degree in electrical engineering and engineering
physics and the Ph.D. degree in electronic devices
from Linkping University, Linkping, Sweden, in
1991 and 1995, respectively.
He was a Visiting Scientist at National Microelectronics Research Center, Ireland, in 1996/1997 and a
Visiting Professor at Intel Corporations Circuit Research Lab in 2000. He holds the Chair of Computer
Engineering at Chalmers University of Technology,
Gothenburg, Sweden. His research activities are focused on low-power high-performance digital circuits and microarchitectures,
as well as circuit and interconnect macromodeling for efficient performance and
power estimation.

Daniel Eckerbert (S00M04) was born in Visby,

Sweden in 1973. He received the [Link]. degree in
electrical engineering from Linkping University,
Linkping, Sweden, in 1998, and the Ph.D. degree
in computer engineering from Chalmers University
of Technology, Gothenburg, Sweden, in 2003. His
thesis focused on high-speed low-power clock
generation circuits and methods for estimation of
power dissipation at the RT level.
In 20002001, he had an internship at Intel Corporations Circuit Research Lab, where he worked
on high-speed clock generation circuits. Since 2004, he has been with Imego,
Gothenburg, Sweden, where he works on sensor readout ASICs (mainly MEMS
gyros and accelerometers) and the electronics of the systems containing the
sensor and readout circuits.