Reducing branch delay to zero in pipelined processors

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