IEEE TRANSACTIONS
ON
COMPUTERS,
VOL.
42,
NO.
3.
MARCH
1993
363
Reducing B anch Delay
o
Ze o in Pipelined P ocesso s
An onio M. Gonzalez and Jose
M.
Llabe ia
Abs ac -A mechanism o educe he cos o b anches in pipelined
p ocesso s is desc ibed and e alua ed. I is based on he use o mul iple
p e e ch, ea ly compu a ion o he a ge add ess, delayed b anch, and
pa allel execu ion
o
b anches. The implemen a ion
o
his mechanism
using a B anch Ta ge Ins uc ion Memo y is desc ibed.
An
analy ical
model o he pe o mance
o
his implemen a ion is p esen ed, which
allows
us
o
measu e he
e iciency
o he mechanism wi h a e y low
compu a ional cos . The model is used o de e mine he size o cache lines
ha maximizes he p ocesso pe o mance, o compa e he pe o mance
o he mechanism wi h o he schemes, and o analyze he pe o mance o
he mechanism wi h wo al e na i e cache o ganiza ions.
Index Te ms-B anch ins uc ions, b anch a ge ins uc ion memo y,
compu e a chi ec u e, ins uc ion cache memo y, ins uc ion dependen-
cies, pe o mance e alua ion, pipelined p ocesso s.
I.
INTRODUCTION
Pipelining is a echnique equen ly used in he design o p ocesso s
in o de o inc ease hei pe o mance by execu ing se e al ins uc-
ions simul aneously. Howe e , he e iciency b ough by pipelining
may be signi ican ly educed by haza ds caused by ins uc ion depen-
dencies. Those due o b anches, also known as con ol dependencies,
may ha e a se e e impac
on
he p ocesso pe o mance since hese
ins uc ions accoun o a high pe cen age o execu ed ins uc ions.
The p esen wo k ocuses
on
he design and e alua ion o mech-
anisms o educing he nega i e e ec due o haza ds p oduced by
b anch ins uc ions in pipelined p ocesso s. We p esen and e alua e a
mechanism called COBRA (Cos Op imiza ion o BRAnches) which
elimina es mos o he haza ds caused by b anches and allows he
p ocesso o execu e b anches in pa allel wi h he es
o
ins uc ions.
In
his way, he cos o mos b anches can be educed o ze o. To
e alua e he pe o mance o his mechanism, a ma hema ical model
o COBRA
is
de eloped and used o une he design.
The es o his pape is o ganized as ollows. Sec ion I1 is a
e iew o p e ious wo k on educing he cos o b anches. Sec ion 111
desc ibes he COBRA mechanism. A ma hema ical model o COBRA
is p esen ed in Sec ion
IV.
Sec ion
V
discusses he pe o mance o
COBRA and compa es i wi h o he schemes.
11. REDUCING
THE
COST
OF
BRANCHES
Se e al mechanisms ha e been p oposed in he li e a u e in o de
o educe he cos o b anches [14], [15]. They make use o ei he
one
o
se e al o he i e echniques desc ibed b ie ly below.
u)
Deluyed b unch.
A delayed b anch wi h leng h equal o
n
is
a b anch ins uc ion ha akes e ec a e he execu ion o he
n
ins uc ions below i . The compile is esponsible o bene i ing om
his mechanism because i is in cha ge o inding he ins uc ions ha
mus be scheduled in he
n
delay slo s. Among o he s, he mechanism
is used by he MIPS R3000 [16].
I he p ocesso is p o ided wi h he possibili y o nulli ying he
execu ion o he ins uc ions in he delay slo s, he numbe o delay
Manusc ip ecei ed June
15,
1990; e ised Ma ch 15, 1992. This wo k was
suppo ed in pa by he Comision In e minis e ial de Ciencia
y
Technologia
(CICYT) unde g an TIC89/0300.
The au ho s a e wi h he Depa men
o
Compu e A chi ec u e, Uni e si a
Poli Ccnica de Ca alunya, Ba celona, Spain.
IEEE
Log
Numbe 9202843.
slo s ha can be p o i ably used inc eases. This mechanism is called
delayed b unch wi h squashing.
This is he case o he SPARC [4].
b) Ea ly execu ion o b anches.
Haza ds caused by a b anch can be
educed by execu ing some o i s ope a ions in ad ance. Fo example,
he Mo o ola 68040 [3] has an addi ional adde o compu e he a ge
add ess as
soon
as a b anch is e ched.
c)
B unch p edic ion.
Ano he way o ad ancing he possible esul
o a b anch is o p edic i . As an example we could men ion he
In el 8096CLNex Gene a ion
[ll].
In his p ocesso , each b anch
ins uc ion includes a bi ha is used by he compile o p edic he
mos likely esul o he b anch.
d) Mul iple p e e ch.
I is based on p e e ching a e each b anch
some o he ins uc ions a he beginning o each possible pa h. In
his way, when he esul o he b anch is known, he e ch s age has
been al eady pe o med, ega dless o he aken pa h. This echnique
is implemen ed in he In el i486 [2].
e) Pa allel execu ion
o
b unches.
The p eceding echniques y o
educe he nega i e e ec caused by con ol dependencies. A g ea e
inc ease in pe o mance can be achie ed i he execu ion o b anches
is comple ely o e lapped wi h he execu ion
o
he es o ins uc ions.
This is he case o he IBM RS/6000 [9].
In
many p ocesso s we ind ha se e al echniques om hose ypes
lis ed abo e a e combined in o de o build a pa icula mechanism
o educe he cos o b anches. This is he case o he COBRA
mechanism.
111. COBRA MECHANISM
In his sec ion we p esen he COBRA mechanism. I was de ised
o pipelined p ocesso s wi h any numbe o s ages and wi h condi ion
codes. A p elimina y s udy o he COBRA mechanism was p esen ed
in [7], [8], and [6].
The COBRA mechanism combines se e al echniques o allow he
p ocesso o execu e b anches in pa allel wi h he es o ins uc ions.
These echniques a e: Ea ly compu a ion o he a ge add ess, mul-
iple p e e ch, delayed b anch and pa allel execu ion o b anches. A
he ime COBRA was is p oposed [7], wha was no el abou i in
ela ion o o he mechanisms was he app oach used o implemen he
pa allel execu ion o b anches, which is based
on
ea ly compu a ion o
he a ge add ess and p e e ching he
wo
pa hs o b anches. Besides,
i was he i s mechanism (as a as we know) ha combined all
hese ou ypes o echniques in o de o educe he b anch cos o
ze o. A e ha , a ew ecen comme cial p ocesso such as he IBM
RS/6000 [9], implemen also a mechanism based
on
he combina ion
o hese ou ypes o echniques The same concep has di e en
implemen a ions ha lead o di e en pe o mance le els,
so,
he
o he con ibu ion o COBRA is he way i is implemen ed. COBRA
can be implemen ed using ei he a con en ional ins uc ion cache
o
a b anch a ge ins uc ion memo y (bo h e ms a e de ined la e ). We
show in his pape ha he implemen a ion using he la e memo y
o ganiza ion has a be e pe o mance in e ms o cos -e ec i eness.
To explain he unc ioning o COBRA, we dis inguish wo main
uni s in he p ocesso : he Ins uc ion Uni
(IU),
which is espon-
sible o e ching and sequencing ins uc ions, and he Execu ion
Uni
(EU),
which execu es only da a manipula ion ins uc ions (all
ins uc ions excep con ol ans e ins uc ions). The a ge add ess
is compu ed in ad ance by he use o p e e ching echniques. When
he IU inds a b anch (usually some cycles be o e i mus ake
e ec ), i compu es i s a ge add ess and p e e ches some o he i s
ins uc ions o he wo possible pa hs (mul iple p e e ch). When he
0018-9340/93$03.00
0
1993 IEEE
364 IEEE
TRANSACTIONS
ON
COMPUTERS,
VOL.
42,
NO.
3,
MARCH
1993
)
me
nex
b anch
Ins uc ion is e ched
(")
ins ucliom
om
bo h
aken and no aken pa h
a e
e ched
)
Cmdi ion codes a e compu ed and depending
on
hei
due,
al
he
end
o
he
cycle
he
p ocesso chooses
be ween he
wo
possible
paihs.
bem
and n hei especli e i s ins uc ions.
IF
Ins uc ion e ch
0:
Decode
OF
ope ands e ch
ALU:
ALU
opwa kn
WR:
WMe
esul
inlo des ina ion egis e
Fig.
1.
Execu ion
o
a b anch ins uc ion using he
COBRA
mechanism.
esul o he b anch condi ion is known, one o he wo p e e ched
lows o ins uc ions is chosen.
In
his way, he delay in oduced
by b anches is dec eased by one uni (in gene al, i is dec eased by
he same amoun o uni s as a e ch ope a ion akes). The emaining
delay slo s a e u ilized by means o he delayed b anch echnique.
All he ope a ions equi ed by b anch ins uc ions a e pe o med by
he IU in pa allel wi h he EU ac i i y, ha is, wi h he execu ion
o
ins uc ions di e en om b anches. In his way, he ime cos o
many b anches can be educed o ze o.
The scheme p oposed by Ka e enis in
[13]
is used o codi y he
a ge add ess o PC- ela i e b anches. The basic idea o his app oach
is ha he ins uc ion con ains he leas -signi ican bi s o he a ge
add ess, a he han i s o se . This scheme allows he IU o
pe o m
he p e e ch in cache memo y o he ins uc ions a he a ge add ess
in he cycle nex o he e ch o he b anch ins uc ion, in pa allel
wi h he compu a ion o he mos -signi ican bi s o he a ge add ess.
In his way, he delay cycle cause by he addi ion ope a ion in he
con en ional scheme is a oided.
Fig.
1
shows a possible execu ion o a b anch using he COBRA
mechanism o a sample pipeline.
In
his example he
IU
inds a
b anch in cycle
n.
A e ha , i con inues e ching ins uc ions ha
ollow in sequence and also some ins uc ions om he aken pa h.
When he ins uc ion ha se s he condi ion codes inishes i s ALU
s age (cycle
n
+
3)
he
IU
decides which pa h mus be selec ed and
sends he co esponding i s ins uc ion o he EU. F om hen on,
he IU e ches ins uc ions om he selec ed pa h un il a new b anch
is ound. The delay in oduced by compu ing he condi ion codes
( wo cycles in his example) is used by means o he delayed b anch
echnique [lo]. I he ALU is he N h s age o he pipeline, wi h his
scheme each b anch will ha e
N
-
2
delay slo s.
A.
Memo y O ganiza ion
'ho
di e en cache memo y o ganiza ions ha e been conside ed
o he implemen a ion o COBRA. We call hese o ganiza ions
con en ional ins uc ion cache memo y
and
b anch a ge ins uc ions
memo y
(BTIM).
In a con en ional ins uc ion cache memo y he mapping uni
is a ixed size
block.
Fo a b anch a ge ins uc ion memo y, he
mapping uni consis s o he ins uc ions be ween
wo
consecu i e
aken b anches (including he la e b anch).
In
his case, he mapping
uni has a a iable size and is de ined a execu ion ime. This uni
will be called
sequence.
To educe he complexi y ha he managemen o in o ma ion uni s
wi h a a iable size implies, a usual app oach o implemen a BTIM
consis s in limi ing o a ixed amoun he numbe o ins uc ions o
a sequence ha a e s o ed in cache memo y. I a sequence is g ea e
han his size, he emaining ins uc ions a e ob ained om he nex
le el
o
he memo y hie a chy. I i is smalle , he line is illed up
wi h he ins uc ions ha ollow in sequence.
An
implemen a ion like
his is used in he Am29000 p ocesso [12].
Each en y o he cache memo y will be called a
line.
A line s o es
a block in he case o a con en ional cache
o
pa o a sequence in
he case o a BTIM.
To access he nex le el o memo y, a
bu s -mode p o ocol
is
used. Wi h his p o ocol, ansac ions a e no ixed in leng h. A e
sending he ins uc ions co esponding o a gi en line, he memo y
can con inue sending he ins uc ions o he ollowing lines, one
ins uc ion pe cycle, wi hou any delay un il he p ocesso o memo y
decides o e mina e he ansac ion.
In
his way, he la ency
o
he
ex e nal memo y is expe ienced jus once as long as he eques ed
ins uc ions a e a consecu i e add esses.
Each ime a cache miss occu s, an en i e new line is loaded in o
cache memo y. The ins uc ions o he line a i e a he a e o one
pe cycle, in he o de hey a e s o ed in he line.
As
soon
as he
ins uc ion ha caused he miss is a ailable, i is passed o he
IU
and begins execu ion. I a new cache memo y access is equi ed while
a line is being loaded ( o ins ance, when he line con ains a aken
b anch), he o me line mus be comple ely loaded be o e beginning
he new cache access.
B.
Design
o
he Ins uc ion Uni
The main componen s o he ins uc ion uni ha implemen s he
COBRA mechanism a e shown in Figs. 2 and
3.
The IU is composed
o a BTIM and he ha dwa e necessa y o selec ing he ins uc ion
ha mus eed he EU in each cycle, de ec ing b anch ins uc ions in
ad ance and elimina ing hem om he low o ins uc ions sen o
he EU. The implemen a ion using a con en ional ins uc ion cache
can be ound in
[8].
The IU uses he BTIM o p e e ch he i s line om he aken pa h
o b anches. Since he BTIM p o ides a comple e line jus in one
cycle, he p e e ch o he aken line can be pos poned un il he same
cycle in which he condi ion codes o he b anch a e se . Accessing
he BTIM ea lie does no p o ide any addi ional bene i excep o
he case when he eques ed line is no in he BTIM.
In
his case, a
u he an icipa ion could be used o p e e ch he line om ex e nal
memo y bu , since he IU has jus one pa h o ex e nal memo y, his
implies suspending he e ching o ins uc ions ha ollow in sequence
be o e he ou come o he b anch is known.
In
[5]
we demons a ed
ha his al e na i e does no p o ide any addi ional bene i .
In
consequence, he IU mus only analyze in each cycle he
ins uc ion ha ollows in sequence o he one ha is in he i s s age
o he EU pipeline. I he analyzed ins uc ion is a b anch, he BTIM
is accessed o ob ain (i hi ) he aken line.
In
he same cycle, he
ins uc ion ha se s he condi ion codes will be in he ALU s age.
In
his way, a he end o his cycle, he BTIM line
(o
he co esponding
miss) will be selec ed
o
disca ded, depending
on
he condi ion codes.
The IU has a egis e o s o e he line ob ained om he BTIM
in case o hi . The i s ins uc ion o his line does no need o be
s o ed because i mus immedia ely be sen o he EU.
XI
is a mul iplexe ha selec s he ins uc ion o be sen o he EU.
The
X2
mul iplexe selec s he ins uc ion nex o he one selec ed
by
XI.
This ins uc ion is examined by he ea ly b anch de ec ion
ci cui o check i i is a b anch (in a RISC a chi ec u e i could be
as simple as es ing jus one
o
e y ew bi s o he op-code). The
ci cui ha gene a es he con ol signals o hese wo mul iplexe s
(no shown in Fig.
2)
is basically a coun e wi h he possibili y o
being inc emen ed by one
o
wo
uni s depending on he esul o
,
IEEE
TRANSACTIONS
ON
COMPUTERS,
VOL.
42,
NO.
3, MARCH 1993
365
MSB:
Mos
signi ican bi s
LSB:
Less
signi ican bi s
Ti:
Ta @
ad&
s:
Sign
bi .
Used
o
compu e
he
MSB
o
he
W'gC
dd ps
c:
Cany
bi .
Used
o
compu e
he
MSB
o
he
lage
a& .ss
b :
Indica es
whe he
he
b auch
is
a
canpuled
bd
o
no .
I
TAC
I
Ta ge Add ess Compu a ion ci cui (see
ig.
3).
B anch de ec ion ci cui .
Fig.
2.
Block diag am o he Ins uc ion Uni .
L+K
(line
size)
4-1
Ta+lii
size
Compu ed
b anch
( om
EU
o -
MSWa
+
pL7
C+S
LSBC a)
b
MSB: Mos
aigni ica il
bi s
LSB
Legs
siglli ican
bils
Ta:
Ta ge
add ss
s:
Sign
bi .
Used
o
compu e
he
MSB
o
he
lage
dd ps
c:
Ca y
bi .
Used
o
compu e
he
MSB
o
he
a ge
dd eps
b :
Indica s
whe he
he
b anch
is
a
compu ed
bd
o
w .
Fig.
3.
Block diag am
o
he
Ta ge Add ess Compu a ion ci cui (TAC in Fig.
2).
he b anch de ec ion ci cui . When a b anch is aken, his coun e is
ese o ze o.
The ins uc ions supplied by he ex e nal memo y should a i e a
he IU one cycle be o e he EU can s a i s execu ion in o de o be
analyzed by he b anch de ec ion ci cui and p ocessed by he IU i
hey a e eally b anches. A u he an icipa ion, as explained abo e,
does no p o ide any addi ional bene i . I o any eason, like a BTIM
miss, hey a i e la e , some bubbles will occu in he EU pipeline,
causing a deg ada ion in he p ocesso pe o mance. Du ing he cycle
ha an ins uc ion supplied by he ex e nal memo y is p ocessed by
he IU, i is held in he Delay egis e .
When a b anch is de ec ed, he BTIM is sea ched o he a ge line
while he ins uc ion ha se s he condi ion codes
is
in he ALU s age.
A he end o his cycle, he condi ion codes de e mine whe he he
b anch is o be aken.
I
he b anch is aken, he PC block is loaded
wi h he a ge add ess and
X,
selec s he add ess ha is sen o
ex e nal memo y. I he access
o
he BTIM p oduced a cache miss
he selec ed add ess is he b anch a ge add ess. O he wise, i is he
b anch a ge add ess plus he cache line size
(S
=
L
+
K).
No e
ha he bu s ansac ion ini ia ed o he las aken b anch is no ye
suspended and, he e o e, i can
be
con inued i he b anch is no
aken.
The a ge add ess
o
compu ed b anches is calcula ed by he EU
and sen o he IU. Call and Re u n ins uc ions a e also a pa icula
kind o b anches. Call ins uc ions can be sen o he execu ion uni ,
like an a i hme ic ins uc ion, wi h he sole objec i e o s o ing he
e u n add ess ( he a ge s add ess is compu ed by he
IU).
Re u n
ins uc ions a e also sen o he EU and a e ea ed like compu ed
366
IEEE
TRANSACITONS
ON
COMPUTERS,
VOL.
42,
NO.
3,
MARCH
1993
TABLE
I
NOTATION
FOR
THE
MODELS
F om
he
amlica ions:
B:
P obabili y ha an ins uc ion is a b anch
T:
P obabili y ha a b anch is aken
D(d):
P obabili y densi y unc ion o he dis ance
be ween wo consecu i e aken b anches
(leng h
o
sequences)
F(d): P obabili y dellsi y unc ion o he dis ance
be ween wo consecu i e b anch
ins uc ions.
b anches ha ob ain he a ge add ess om he place whe e he
co esponding call ins uc ion s o ed i . The d awback o his solu ion
is ha Call and Re u n ins uc ions, unlike he es o b anches, spend
one cycle in he EU, and, he e o e, canno be comple ely execu ed
in pa allel. A mo e e icien solu ion, also mo e expensi e, consis s
in adding a ha dwa e s ack o he IU, whe e he IU will s o e he
e u n add ess o Call ins uc ions in pa allel wi h he EU ac i i y. In
his case, when he IU inds a Re u n ins uc ion, he a ge add ess
is ob ained om he op o his s ack, also comple ely in pa allel
wi h he EU ac i i y. In his way, Call and Re u n ins uc ions can
be execu ed wi h ze o ime cos . The esul s p esen ed in he nex
sec ion assume ha he IU has a ailable his ha dwa e s ack.
IV.
MODELING COBRA
A ma hema ical model o COBRA o he implemen a ion ha
uses a BTIM is de eloped in his sec ion. The model has some
inpu pa ame e s lis ed in Table I. These inpu pa ame e s can be
classi ied in h ee ypes: a) Those ha depend
on
he applica ions
(B,T,
D(d),
F(d)),
b) hose ha depend
on
he implemen a ion
(L
and
S),
and
c)
hose ha depend on bo h he applica ions and
he implemen a ions
(H).
This model will be used. o compu e he
pe o mance o he p ocesso o di e en sys em con igu a ions.
In addi ion, an analy ical model o he Delayed B anch scheme is
p esen ed. I s objec i e is o compa e COBRA wi h Delayed B anch
in o de o show he ex a pe o mance o COBRA in ela ion o i s
ha dwa e cos (shown in he p e ious sec ion).
A. Pipeline
The e iciency o COBRA and Delayed B anch depend
on
he
leng h o he pipeline. In his pape we concen a e
on
a pipeline in
which he ALU s age is he second one.
Fo
his, pipeline, he Delayed
B anch scheme has one delay slo pe b anch whe eas COBRA does
no need any delay slo and, in addi ion, b anches a e execu ed in
pa allel wi h o he ins uc ions. A deepe pipeline will imply an
inc ease in he numbe o delay slo s o bo h schemes.
B. Analy ical Model
o
COBRA
The peak pe o mance
o
he p ocesso using COBRA is ze o
cycles o b anches and one cycle o any o he ins uc ion. Howe e ,
o achie e his peak pe o mance se e al condi ions mus hold:
The a ge line
o
each aken b anch should be in he BTIM. The
a io o lines ha a e ac ually ound in he BTIM depends
on
he numbe o lines o he BTIM, he BTIM o ganiza ion, and
he empo al locali y o he p og am.
Each cycle, he EU should begin he execu ion o a nonb anch
ins uc ion and, in pa allel, he IU should deal wi h he ins uc-
ion ha ollows in sequence. E en when e e y a ge line we e
in he BTIM, he e would be no gua an ee ha his condi ion
is me , since he IU elies
on
he ex e nal memo y o pa
o
hose sequences whose size is g ea e han a BTIM line.
So
F om he implemen a ion:
L:
La ency o ex e nal memo y
S:
Size o
BTIM
lines
F om bo h he amlica ions and imDlemen a ioK
H:
BTlM
a ge hi a io, which is compu ed
as
he numbe o aken b anches whose a ge
sequence
is ound in
he
BTIM
di ided by
he
o al numbe o aken b anches
he line size and he ex e nal memo y la ency also a ec he
pe o mance o he p ocesso .
In he de elopmen o he analy ical model we assume ha
wo
b anches ne e occu wi hou a leas one ins uc ion be ween hem.
This hypo hesis simpli ies he model by in oducing a negligible e o ,
since in p ac ice his ac happens e y a ely.
The p ocesso pe o mance
(P)
is compu ed as he a e age numbe
o use ul ins uc ions execu ed pe cycle. Use ul ins uc ions a e hose
ins uc ions p ocessed by he EU (all ins uc ions bu b anches). In
his way,
P
=
(1
-
B)/(
1
-
B
+
D),
whe e
D
is he a e age numbe
o los cycles pe ins uc ion (including b anches). To compu e
D,
he
di e en sou ces p penaliza ion will be cha ac e ized. Los cycles
a e due o i e di e en causes:
1)
Memo y la ency due o BTIM
misses,
2)
Comple e eplacemen o lines,
3)
Memo y la ency o
BTIM hi s,
4)
Lack o an icipa ion due o BTIM misses, and
5)
Loss
o an icipa ion due o
no
aken b anches. Then,
D
=
D1
+
02
+
03
+
04
+
05,
whe e
Di
ep esen s he a e age numbe o los
cycles pe ins uc ion due o cause
i.
Nex , exp essions o each
Di
a e de eloped.
1)
Memo y La ency Due o BTIM Misses:
This happens when a
b anch is aken and a cache miss occu s when he IU accesses he
BTIM o e ch he nex sequence. The cos o his cache miss is
L
cycles. The p obabili y ha his e en happens is
BT(
1
-
H
),
and,
he e o e, he a e age numbe o los cycles pe ins uc ion due o
his cause is
D1
=
LBT(1
-
H).
2)
Complz e Replacemen
o
Lines:
This happens when he IU is
dealing wi h a b anch ha u ns ou o be aken, a BTIM miss occu ed
in he p e ious aken b anch and he dis ance be ween hese wo
b anches (he e called
d)
is less ha
S
-
1.
In his case, he IU mus
inish he eplacemen o he o me line be o e beginning o sea ch
he BTIM o he new line. The addi ional cycles needed o comple e
he eplacemen a e
S
-
1
-
d,
and he a e age numbe o los cycles
pe ins uc ion due o his cause is
$--2
~-
02
=
BT(l
-
H)
E
D(d)(S
-
1
-
d).
d=2
3)
Memo y La ency
o
BTIM Hi s:
This happens when he cu en
sequence was ound in he BTIM bu i is la ge han a line, and
he e o e, only he i s ins uc ions a e in he BTIM; he emaining
ins uc ions a e p o ided by he ex e nal memo y. I he ex e nal
memo y la ency
(L)
is g ea e han he line size
(S),
hen
L
-
S
cycles will be los o each one o hose sequences. The a e age
numbe o los cycles pe ins uc ion due o his cause is
4)
Lack
o
An icipa ion Due o a BTIM Miss:
This happens o any
b anch when a BTIM miss occu ed in he p e ious aken b anch.
In his case, all he ins uc ions be ween he las aken b anch and
he nex aken one a e p o ided by he ex e nal memo y a he a e
IEEE
TRANSACTIONS
ON
COMPUTERS,
VOL.
42,
NO.
3,
MARCH
1993
361
o one pe cycle and he e o e b anches cos one cycle since hey
a e no de ec ed ea ly enough o o e lap i s execu ion wi h some
p e ious ins uc ion. In his way, while he IU is dealing wi h he
b anch a NOP is sen o he EU. The a e age numbe o los cycles
pe ins uc ion due o his cause is
04
=
B(l
-
H).
5)
Loss
o
An icipa ion Due o
no
Taken B anches:
This happens
o sequences ha a e ound in he BTIM and a e la ge han a line.
Le
assume ha
Y
is he size o he sequence and i con ains
X
b anches. The numbe o cycles needed o ead he comple e sequence
om memo y is
Y
-
S
+
L
and he numbe o use ul ins uc ions in
he block is
Y
-
X.
Then, he numbe o cycles ha he EU will be
idle is
(I’
-
S
+
L)
-
(Y
-
X)
=
X
-
(S
-
L).
When
S
<
L,
om
his amoun we mus sub ac he
L
-
S
cycles ha ha e al eady been
aken in o accoun in cause
3.
In
conclusion, we mus coun a los
cycle o each b anch ha is p eceded by a leas
S
-
L
no aken
b anches, assuming ha i
S
-
L
<
0
he p e ious sen ence mus be
in e p e ed as p eceded by a leas ze o no aken b anches ( his holds
o any b anch). The a e age numbe o los cycles pe ins uc ion
due o his cause is (see equa ion a bo om o page)
whe e
N
and
I
a e andom a iables.
N
ep esen s he numbe o
no aken b anches be ween he cu en b anch and he p e ious aken
b anch and
I
ep esen s he numbe o ins uc ions o he sequence
o which he b anch being analyzed belongs.
Compu ing
P (N
2
K):
We assume ha he p obabili y ha a
b anch is aken is independen o wha happened in he b anches
execu ed be o e, which implies ha he andom a iable
N
ollows
a geome ic law. No e ha in his case, he p e ious b anches
co espond o no aken b anches and he e o e
all
he p e ious
b anches and he one analyzed a e di e en ins uc ions. Then, i is
easonable o assume ha each b anch ins uc ion is independen o
he o he s, al hough his is no necessa ily ue. This in oduces some
negligible e o in ou analysis, bu no enough o a ec he esul as
he alida ion o he model (nex sec ion) will p o e. The e o e,
00
P (N
2
IC)
=
~(1-
T),
=
(1
-
TI*.
,=K
Compu ing P ob(I
>
SIN
2
K):
To compu e his p obabili y,
we will i s calcula e P (I
>
S).
To do ha , we de ine
By
as
he a e age numbe o b anch ins uc ions
in
a sequence wi h Y
ins uc ions. We ha e ha
P (I=Y)=
oo
ByD(Y)
+
P ob(1
>
Y)
c
BAA
3=2
,=2
By
can be compu ed using he exp ession
Y
BY
=
j
A,
C,
(Y)
,=1
whe e
A,
is he p obabili y ha a sequence is composed o
j
b anches
and
C,
(Y)
ep esen s he p obabili y ha a sequence wi h
j
b anches
has a leng h equal o
Y.
Because o he hypo hesis made be o e, he alue o
A,
is gi en
by he p obabili y densi y unc ion o a geome ic law, which means
ha
A,
=
T(1
-
Ty-1.
C,(Y)
depends on
F(d)
and can be compu ed using he ollowing
exp essions.
Cl(Y)
=
F(Y)
c,(Y)
=
F(Y
-
k)~,-l(k)
i
j
>
1.
Y
-1
le=,
-
1
The e alua ion o P (I
>
SIN
2
K)
is simila o he calcula ion
o P (I
>
S)
wi h he di e ence ha only hose sequences wi h
mo e han
K
b anches mus be conside ed, and he con ibu ion o
he is
K
b anches mus no be aken in o accoun o compu ing
his p obabili y.
Thus,
we ha e ha
k=2
whe e
hl~
(k)
ep esen s he a e age numbe o b anches le (no
including he i s
K
b anches) in a sequence wi h
k
ins uc ions and
assuming ha he sequence has a leas
K
+
1
b anch ins uc ions.
I s alue is equal o
L.
whe e
A,
and
C3
(k)
a e he unc ions abo e de ined.
6)
Valida ion o he Model:
The co ec ness o he analy ical model
was alida ed by compa ing i s esul s wi h he ones ob ained by sim-
ula ion o he execu ion o ou benchma k p og ams: LEX, NROFF,
PCC,
and
YACC’
(9,
12, 21,
and
42
million o execu ed ins uc ions,
espec i ely). These p og ams w i en in
C
language we e compiled
o RISC-I1 Assembly language
[13]
and hei execu ion was simula ed
using he app oach p esen ed in
[l].
F om his simula ion, in addi ion
o he
COBRA
pe o mance, he inpu pa ame e s o he model (see
Table
I)
we e also ob ained. The simula ion was ca ied ou o
se e al alues o he cache size, line size, and ex e nal memo y
la ency. In his way, he p ocesso pe o mance was ob ained o
31.
se s o di e en alues o hese h ee pa ame e s. The p ocesso
pe o mance p edic ed by he model and he pe o mance ob ained
by simula ion was always less han
3.76%
di e en and he a e age
di e ence o he
31
simula ions was
1.36%.
C.
Analy ical Model
o
Delayed B anch
Fo he memo y o ganiza ion ha we call a BTIM, a line size
equal o he ex e nal memo y la ency
(S
=
L)
is enough o ob ain
he maximum bene i om he delayed b anch mechanism in e ms
o ins uc ion execu ion a e.
A
u he inc ease
in
he line size
would educe he ex e nal memo y a ic bu would no p o ide any
addi ional gain
ih
e ms o execu ion a e since hese ex a ins uc ions
can be supplied by he ex e nal memo y wi hou any pe o mance
deg ada ion. In consequence, he ollowing model assumes ha
S
is
equal
o
L.
The a e age numbe o los cycles pe ins uc ion is he
sum o he ollowing ou e ms:
a) Execu ion o b anch ins uc ions:
B
Unix u ili ies Unix is a adema k
o
AT&T
Bell
Labs.
BHP (N
2
(S-
L)nI>
S)
=
BHP (I>
SIN
2
(S
-
L))P (N
2
(S
-
L))
BHP (N
2
On1
>
S)
=
BIIP (I>
SIN
2
O)P (N
>_
0)
i
S
2
L
i S
<
L
D5={

IEEE
TRANSACTIONS
ON
COMPUTERS,
VOL.
42,
NO.
3,
MARCH
1993
,
BTlM
M
a60
No op imiza ion o he delay slo :
B(l
-
Po).
The alue o
Po
o each benchma k was ob ained by he simula ion o i s
execu ion.
BTIM miss o a aken b anch:
BT(1
-
H)
A aken b anch occu s be o e concluding he eplacemen o he
line co esponding o he p e ious BTIM miss:
BT(
1
-
H)Nc,
whe e
Nc
is
he a e age numbe o en ies in he cache line ha
ha e no ye been illed. I can be calcula ed by he ollowing
exp ession:
L-2
Nc
=
D(d)(L
-
1
-
d).
d=2
Then, he p ocesso pe o mance compu ed as he a e age numbe
o use ul ins uc ions execu ed pe cycle is equal
o
1-B
1+B(1- Po+T(l-H)+T(l-H)Nc)'
P=
The di e ence be ween he p ocesso pe o mance es ima ed by
means o his model and he esul s ob ained by simula ion o he
ou benchma ks o
15
di e en se s o pa ame e s was always less
han
0.22%,
and he mean alue o he di e ence was
0.05%.
V. PERFORMANCE MEASURES
In his sec ion, he e iciency o he COBRA mechanism is an-
alyzed. Fi s , we in es iga e which is he BTIM line size ha
maximizes he pe o mance o COBRA. Nex , he imp o emen
achie ed by COBRA in ela ion o he delayed b anch mechanism
is shown. Finally, he pe o mance
o
COBRA wi h wo al e na i e
cache memo y o ganiza ions a e compa ed.
A.
Size
o
he Cache Line
The i s applica ion o he ma hema ical model was o de e mine
he op imum size o BTIM lines o COBRA mechanism. A ypical
alue o he ex e nal memo y la ency ( h ee cycles) was assumed o
his analysis. In his sec ion we show ha , o he assumed ex e nal
memo y la ency, he bes adeo be ween cos and pe o mance is
p o ided by a cache line equal o ou ins uc ions.
The pe o mance o he p ocesso was ob ained o a BTIM line
size anging om
1
o
6
ins uc ions and a hi a io anAing om
0
o
1
(no e ha he hi a io, as i is de ined in Table I,
only
depends on
he numbe o lines, no on he line size). The o he inpu pa ame e s
o he model
(B,
T,
F(d),
and
D(d),
see Table
I),
which depend
on he applica ions, we e assumed o be equal o he a e age o he
alues ob ained o he ou benchma ks. The esul s a e shown in
Fig.
4.
The main conclusion ha can be d awn om Fig.
4
is ha o a
gi en hi a io, he p ocesso pe o mance is imp o ed when he line
size augmen s, bu only un il a gi en size. A u he inc ease in he
line size p oduces a dec ease in he p ocesso pe o mance due o
he cos o loading a new line on cache misses.
In
his igu e we can
also see ha he highe he hi a io, he g ea e he size om which
he pe o mance begins o dec ease. A he le end o he g aphs
(hi
=
0)
pe o mance dec eases as he line size inc eases whe eas a
he igh end, pe o mance augmen s as he line size ge s la ge .
When he line size is lowe han he ex e nal memo y la ency
(1
o
2
ins uc ions) he pe o mance o he sys em is a he low. I we
compa e line size o h ee wi h line size o ou in Fig.
4,
we can
obse e ha he pe o mance o he la e
is
be e om low alues o
hi a io on (hi
2
0.4),
and he di e ence be ween hem is subs an ial
o ypical alues o he a ge hi a io
(0.7-0.9).
A
u he inc emen
in he line size
(5
ins uc ions) is use ul only i he hi a io is g ea e
han
0.7
and, in his case, he inc ease in pe o mance is
so
low
0.8
1
p
-4
I
--
5
Fig.
4.
P ocesso pe o mance
o
di e en alues o he
BTIM
hi a io and
line
size,
assuming
an ex e nal memo y la ency
o
h ee cycles.
ha i does no jus i y he addi ional occupied chip a ea.
So,
we can
conclude ha he bes adeo be ween cos and e iciency is a line
size o ou ins uc ions.
B. COBRA Ve sus Delayed B anch
In his sec ion we show he bene i s b ough by COBRA. We
ha e al eady seen he ha dwa e cos needed o implemen i . He e
we compa e he pe o mance o COBRA agains he delayed b anch
mechanism. Since his la e mechanism does no use any addi ional
ha dwa e, we can ha e an idea o he ex a pe o mance in ela ion
o he addi ional ha dwa e o COBRA.
Fig.
5
shows he pe o mance o COBRA and delayed b anch
mechanisms. In bo h cases, he same cache memo y o ganiza ion has
been assumed, ha is, a BTIM wi h di ec mapping and
32,64,128,
o
256
lines. The line size is equal o he memo y la ency
(3
ins uc ions)
o he delayed b anch scheme and equal
o
he la ency plus one
uni
(4
ins uc ions) o he COBRA mechanism. The line size o
COBRA is jus i ied in he p e ious sec ion whe eas he choice o
delayed b anch, as explained in Sec ion IV-C, is due o he ac ha
ha ing a line g ea e han he ex e nal memo y la ency does no
p o ide any addi ional inc ease in he ins uc ion execu ion a e. In
consequence, o a ou ins uc ion line size, he pe o mance igu es
(use ul ins uc ion pe cycle) o he delayed b anch mechanism wi h
a BTIM will be he same
as
he ones depic ed in Fig.
5.
The o he
inpu pa ame e s
o
he analy ical models
(H,
B,
T,
F(d),
D(d),
see Table
I)
we e ob ained om he simula ion o he execu ion o
each benchma k.
The e iciency o he COBRA mechanism is be ween
36%
(BTIM
wi h
32
lines) and
40%
(BTIM wi h
256
lines) highe han he
delayed b anch o
LEX;
be ween
6
and
21%
o NROFF; be ween
12
and
21%
o PCC and be ween
24
and
26%
o YACC. The highe
he cache hi a io, he g ea e he di e ence be ween hem.
C. BTZM Ve sus Con en ional Ins uc ion Cache
I is also in e es ing
o
compa e he e iciency o COBRA o
di e en cache o ganiza ions. Fig.
6
shows he pe o mance o he
COBRA mechanism wi h a BTIM and wi h a con en ional ins uc ion
cache. In bo h cases we assume he same numbe o cache lines, he
same size o lines
(4
ins uc ions), a di ec mapping and a h ee-cycle
ex e nal memo y la ency. The pe o mance igu es o a con en ional
cache we e ob ained using he app oach p esen ed in
[SI.
Fig.
6
shows ha , o he cache pa ame e s e alua ed, a con en-
ional ins uc ion cache and a BTIM ha e a simila pe o mance o
IEEE TRANSACTIONS ON COMPUTERS,
VOL.
42,
NO.
3,
MARCH
1993
usMho.lw!E
LEX
0.9
0.8
-
1
0.9
0.8
0.7
0.6
0.5
0.a
-
32
84
128
254
0.7
-
0.6
-
dlnl3.lLW
PCC
0.9
1
BTlMlineS
0.5
32
64
128
256
1
0.9
0.8
0.7
0.6
0.5
BnM
li m
32
64
128 256
u lu(inU.l yds
YACC
BTIM
lins
369
Fig.
5.
COBRA
e sus
delayed
b anch.
LEX and YACC (a li le be e o a con en ional cache) whe eas o
NROFF and PCC, he pe o mance o a BTIM is conside ably be e
han a con en ional cache. The imp o emen o he BTIM in ela ion
o he con en ional cache anges om
-1
o
-3%
o LEX,
29
o
2%
o NROFF,
18
o
12%
o
PCC,
and
4
o
-5%
o YACC. The
main di e ence be ween LEX, YACC and PCC, NROFF is ha he
o me wo p og ams exhibi a highe empo al locali y. We can also
obse e in Fig.
6
ha he imp o emen o a BTIM in ela ion o a
con en ional cache inc eases as he numbe o lines (and he e o e
he hi a io) inc eases.
So
he conclusion jus ega ding e iciency
is ha bo h schemes p o ide abou he same e iciency when he
cache hi a io is e y close o
1
and he pe o mance o he BTIM
is conside ably be e when he hi a io is no
so
high.
On he o he hand, he BTIM gene a es much mo e a ic han
a con en ional cache. Fo LEX he BTIM a ic is be ween
424
and
5220%
highe han he con en ional cache a ic;
28-234%
o
NROFF;
46-104%
o PCC;
422-5956%
o YACC. The eason is
ha , in a BTIM, he e a e many ins uc ions ha mus always be
supplied by he ex emal memo y, ega dless o he numbe o lines
o he cache and he cache hi a io. These ins uc ions a e due o
sequences g ea e han a cache line. In his case, he BTIM only
s o es he i s ins uc ions o he sequence (jus a line) and he es
o ins uc ions a e supplied by ex e nal memo y e en when a BTIM
hi occu s o ha sequence. No e ha his ex a a ic does no mean
any penaliza ion in he p ocesso speed since he access o ex emal
memo y
is
o e lapped wi h he execu ion o ins uc ions p o ided by
he BTIM.
Finally, ega ding ha dwa e cos , he implemen a ion o he IU
equi es a simple ha dwa e o a BTIM. The design o he
IU
o a
con en ional cache can be ound in
[8].
In
conclusion, a BTIM o e s
a be e cos -e iciency pe o mance han a con en ional cache since
he o me simpli ies he implemen a ion o he
IU
and in addi ion i
p o ides in many cases an e iciency qui e highe han a con en ional
cache.
VI.
CONCLUSIONS
We ha e p esen ed and e alua ed a mechanism (COBRA) o
educing he cos o b anches in pipelined p ocesso s. The mechanism
is based
on
he ollowing echniques: a) ea ly compu a ion o he
a ge add ess, b) mul iple p e e ch, c) delayed b anch, and d) pa allel
execu ion o b anch ins uc ions.
370
LEX
___
BTIM
Con en ional cache
___-_--
-
IEEE TRANSACTIONS
ON
COMPUTERS,
VOL.
42,
NO.
3,
MARCH
1993
NROFF
dho.lWd8
db./Wd8
PCC
1
0.9
0.8
0.7
BnH
bnl
0
A
32
64
128
250
32
64
128
256
uuhlhlb./clde
YACC
1
04
0.E
0.1
0.6
0.5
0.4
32
64
128
256
Fig. 6. COBRA wi h a
BTIM
e sus COBRA wi h a con en ional ins uc ion cache.
An
implemen a ion o he mechanism using a B anch Ta ge
Ins uc ion Memo y (BTIM) is p oposed. The beha io o he sys em
has been cha ac e ized by means o an analy ical model. This model
has been used o selec he mos adequa e size o BTIM lines which,
o a ex e nal memo y wi h la ency equal o h ee cycles, esul ed o
be equal o he la ency plus one uni .
The e iciency
o
he COBRA mechanism is in a e age abou
25%
highe han he Delayed B anch and he addi ional ha dwa e
needed o implemen COBRA is qui e simple. We ha e also compa ed
wo
implemen a ions
o
he COBRA mechanism, each one using
a di e en cache o ganiza ion. The conclusion was ha , in e ms
o
cos -e ec i eness, he BTIM has a be e pe o mance han a
con en ional ins uc ion cache al hough he o me gene a es a highe
memo y a ic.
This
ex a a ic does no mean any penaliza ion
in he p ocesso speed since i is o e lapped wi h he execu ion
o
ins uc ions p o ided by he BTIM.
ACKNOWLEDGMENT
We would like o hank T. Lang and he anonymous e e ees o
many sugges ions ha imp o ed he quali y
o
his pape .
REFERENCES
[
11
J. Co adella and
J.
M.
Llabe ia, “Low cos e alua ion me hodology o
new a chi ec u es,” in
P oc. USTED In . Symp. Appl. In o ma ics,
Feb.
[2] J.H. C aw o d, “The i486 CPU: Execu ing ins uc ion in one clock
cycle,”
IEEE
Mic o,
ol.
10,
no. 1, pp. 27-36, Feb. 1990.
[3] R.
W.
Eden ield, “The 68040 P ocesso . Pa
1,
Design and implemen-
a ion,”
IEEEMic o,
ol.
10,
no.
1,
pp. 66-78, Feb. 1990.
[4]
R.
B. Game
e
al.,
“The scalable p ocesso a chi ec u e (SPARC),” in
P oc. 33 d.
IEEE
In . Compu . SOC.
Con$,
COMPCON’88, Feb 1988,
[5] A. Gonzilez, “Designing an ins uc ion cache o educing he cos o
b anches,” Rese. Rep. UPCDAC RR-91/02, Compu . A chi ec u e Dep.,
Poly hecnic Uni . o Ca alonia, Ba celona, Jan.
1991.
[6] A. Gonzilez and
J.M.
Llabe ia, “Ins uc ion e ch uni o pa allel
execu ion o b anch ins uc ions,” in
P oc. 3 d In?.
Con$
Supe compu .,
ACM
SIGARCH
ICs-89,
June 1989, pp. 417-426.
[7] A. Gonzilez,
J.
M.
Llabe ia, and J. Co adella, “Ze o-delay cos b anches
in RISC a chi ec u es,” in
P oc.
LASTED
In . Symp. Appl. In o ma ics,
Feb. 1988, pp. 24-27.
[8]
-,
“A mechanism o educing he cos o b anches in RISC a chi-
ec u es,”
Mic op ocessing and Mic op og amming,
ol. 24, no. 1-5,
1987, pp. 192-195.
pp. 278-283.
pp. 565-572, Aug. 1988.
IEEE
TRANSACTIONS
ON
COMPUTERS, VOL.
42,
NO.
3,
MARCH
1993
371
[9] G. F. G ohoski, “Machine o ganiza ion
o
he IBM RISC
Sys em/6000
P ocesso ,”
IBMJ. Res. De elop.,
ol. 34,
no.
1,
pp. 37-58, Jan. 1990.
[lo] T. R. G oss
and
J.
L. Hennessy, “Op imizing delayed b anches,” in
P oc.
15 h Annu. Wo kshop Mic op og amming, ACM SIGMICRO,
Oc . 1982,
[ll] G. Hin on, “80960
-
Nex
gene a ion,” in
P oc 34 h.
IEEE
Compu .
Socie y
Con$
COMPCON’89,
Feb. 1989, pp. 13-17.
[12]
M. Johnson, “Sys em conside a ions in he design
o
he Am29000,”
IEEE
Mic o,
ol.
7,
no.
4, pp. 29-41, Aug. 1987.
[13] M.
G.
H. Ka e enis,
Reduced Ins uc ion Se Compu e A chi ec u e o
VLSI.
Camb idge, MA, MIT P ess, 1985.
[14]
D.
L.
Lilja, “Reducing he b anch penal y in pipelined p ocesso s,”IEEE
Compu . Mag.,
ol. 21,
no.
7, pp. 47-55, July 1988.
[15]
S.
McFa ling and
J.
Hennessy, “Reducing he
cos
o
b anches,”
in
P oc.
13 h
In .
Symp. Compu . A chi ec u e,
1986, pp. 396-403.
1161
T. Rio dan
e
a[.,
“Sys em design using
he
MIPS R3000/3010
RISC
Chipse ,” in
P oc. 34 h
IEEE
Compu . SOC.
Con ,
COMPCON’89,
Feb.
pp. 114-120.
1989, pp. 494-498.
Cons an Geome y Fas Fou ie
T ans o ms
on
A ay P ocesso s
Geo ge Miel
Abs ac -Ma ix algeb a is used
o
design and alida e pa allel algo-
i hms
o
la ge cons an geome y
FFT’s
on
ixed-size a ay p ocesso s.
The N-poin adix 2 case o a linea a ay p ocesso wi h
N/2
cells is
iden ical o he usual p ocedu e co esponding o he ma ix ac o iza ion
o
M.
C. Pease. The algo i hms a e engende ed by ma ix ac o iza ions,
which hemsel es depend
on
a basic ac o iza ion o he pe ec shu le.
The esul ing da a mo emen
is
ealized in pa allel as ela i ely small
pe ec shu les inside each local memo y and along each ow and column
o he a ay p ocesso , wi hou equi ing ha he comple e a ay i sel
ha e he shu le-exchange ne wo k.
Index Te ms-A ay p ocessing, as Fou ie ans o ms, pa allel al-
go i hms.
I.
INTRODUCTION
The ma ix app oach, as a means o design and alida e algo i hms
o
pa allel a chi ec u es, was used and ad oca ed by Pease
[9]
in his modi ica ion o he Cooley-Tukey p ocedu e. The esul ing
algo i hm is o en called a cons an geome y FFT because i s
communica ion pa e n, namely, he add essing o ope ands o he
bu e ly ope a ions, is kep he same om s age
o
s age. Fo he
N-poin adix
2
case, he algo i hm consis s o log,
N
s ages each
p eceded by a pe ec shu le o he da a. The mos na u al mapping
o
his algo i hm is on o a linea a ay a chi ec u e wi h N/2 cells and a
shu le-exchange in e connec ion ne wo k
[2],
[
141,
[
151. Thompson
[16] has shown ha he VLSI design o his a chi ec u e achie es
a ea* ime2 pe o mance o
R(N2
log:
N),
which is he op imum
heo e ical limi o he N-elemen Fou ie ans o m es ablished by
Vuillemin [17].
The ma ix ac o iza ion
o
he Fou ie ans o m gi en
by
Pease is
in aluable in he s udy o pa allel FIT’S. The p oblem o pa allelizing
Manusc ip ecei ed June 15, 1990; e ised Ma ch 15, 1992. This wo k was
done a and suppo ed by
Hughes
Resea ch Labo a o ies, Malibu, CA 90265.
The au ho is wi h he Depa men
o
Ma hema ical Sciences, Uni e si y
o
Ne ada, Las Vegas,
NV
89154.
IEEE
Log
Numbe 9202844.
an
FFT is essen ially ha
o
scheduling on o a a ge ed a chi ec u e
he asks engende ed by he ma ix ac o s
in
he co esponding
ac o iza ion. This app oach was used by No on and Silbe ge
[8]
in
he pa alleliza ion and pe o mance p edic ion
o
FFT algo i hms o
MIMD sha ed-memo y a chi ec u es. Recen ly, Whelchel and o he s
[18] used he Pease ac o iza ion o desc ibe a pipeline a chi ec-
u e, based
on
ma ix ac o s called sys olic phase o a ions, which
elimina es delay commu a o swi ches used in he Pu dy McClellan
p ocesso .
Ou aim is o decompose he Pease ac o iza ion in o de
o
map la ge cons an geome y FFT’s on o ixed-size ec angula a ay
p ocesso s. Sec ion
I1
shows ha ou esul s depend undamen ally
on
a ac o iza ion o he pe ec shu le pe mu a ion. The esul ing da a
mo emen is ealized in pa allel as ela i ely small pe ec shu les
inside each local memo y and along each ow and column o he
a ay p ocesso , wi hou equi ing ha he comple e a ay i sel ha e
he shu le-exchange in e connec ion ne wo k. Sec ion I11 uses hese
esul s o alida e pa allel algo i hms o ec angula a ay p ocesso s.
The e ec i eness o a mapping
o
a cons an geome y FFT on o
an a ay p ocesso depends p ima ily
on
wo i ems. The i s i em is
he e iciency wi h which he in e connec ion ne wo k o he a ay
p ocesso ealizes he da a mo emen equi ed by he algo i hm. The
second i em in ol es a di ide-and-conque s a egy o he SIMD
e alua ion o specialized ma ix- ec o p oduc s. Suppose ha a
p oduc
Dz,
whe e
D
is he di ec sum
N-1
D=@A
Z=O
wi h each
A,
o
dimension
M
x
M
and
2
is
an hlN- ec o , is o
be compu ed
on
an a ay p ocesso wi h
N
cells. The ec o is i s
di ided in o N M- uples
2
=
(209
21,
’
’’
7
ZN-1
I ,
22
=
(Z A-4..
’ ’
7
z(%+l)A4-1)$
each cell compu es in pa allel a p oduc
A,ZI,
and he sub ec o s
a e hen conca ena ed o ge he esul . Whe eas he i s i em deals
wi h he communica ion complexi y o he mapping, he second i em
pe ains
o
i s pa allel a i hme ic complexi y.
11. MATRIX FACTORIZATIONS
A
pe ec
shu le
is a pe mu a ion ha ans o ms he 2m- ec o
=
(0,1,....m
-
1,m.m
+
1,...,2m
-
o
he ec o
~,~z
=
(O,m,l,m+
l,...,i.m+i,...,m
-
1,2m
-
li .
(2)
Componen s ha we e
m
apa become adjacen as a esul o he
pe ec shu le. Fo simplici y, we hence o h call
(2)
he
shu pe
o
z.
Pe mu a ions by cu ing and shu ling we e s udied by Golomb
[3]. Compu a ional applica ions o he shu le we e concei ed by
Ba che
[l]
o bi onic so ing and by Single on [13] and Pease
[9] o he as Fou ie ans o m.
In
pa icula , Pease p esen ed a
ma ix ac o iza ion o he ans o m,
(4)-(5)
below, sui able o
pa allel implemen a ion. The ele ance
o
he shu le pe mu a ion
in pa allel p ocessing was u he es ablished by S one [14]. The
shu le-exchange in e connec ion ne wo k in a mul ip ocesso sys em
p o ides use ul capabili ies [2]. Fo ins ance, Wu and Feng [19] ha e
shown ha a shu le-exchange ne wo k o size
N
can ealize an
a bi a y pe mu a ion in 31og,
N
-
1
passes.
001&9340/93$03.00
0
1993 IEEE