Comput

erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

Chapt
er–5
Pi
pel
i
neandVect
orPr
ocessi
ng
Pi
pel
i
ning
 Pi peli
ningi sat echni queofdecomposi ngasequent ialpr ocessi nto
suboper ations,wi th each subpr ocess bei ng executed in a speci al
dedicatedsegmentt hatoper atesconcur rentlywit
hallothersegment s.
 Theov er l
appi ngofcomput ationi smadepossi bl
ebyassoci at ngar
i egist
er
witheachsegmenti nt hepipel ine.
 Ther egister spr ov ideisolationbet weeneachsegmentsot hateachcan
operateondi stinctdat asimul taneousl y .
 Per hapst hesi mpl estwayofv i
ewi ngt hepi peli
nestr
ucturei stoi magine
thateach segmentconsi sts ofan i nputr egi
ster followed by a
combi nationalci rcuit.
o Ther egisterhol dst hedat a.
o Thecombi nationalci rcui tper for mst hesuboperationi nt he
particularsegment .
 A cl ocki sappl iedt oal lregi stersaf terenought i
mehasel apsedt o
perform all segmentact iv
ity.
 Thepi pelineor gani zationwi llbedemonst ratedbymeansofasi mple
exampl e.
o Toper formt hecombi nedmul tiplyandaddoper ationswi tha
str
eam ofnumber s
Ai*Bi+Cif ori =1, 2,3, …, 7
 Eachsuboper ationi st obei mpl ement edi nasegmentwi thina
pipeli
ne.R1 Ai, R2 BiI nputAiandBi
R3 R1*R2, R4 CiMul tiplyandi nputCi
R5 R3+R4 AddCit opr oduct
 Eachsegmenthasoneort wor egister
sandacombi nati
onal circuitas
showni nFig.9- 2.
 Thef i
ver egi ster sar eloadedwi thnewdat aev erycl
ockpul se.Theef f
ect
ofeachcl ocki sshowni nTabl e4- 1.

Ref
erence:
W.St
all
i
ngs 1
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

Fi
g4-
1:Exampl
eofpi
pel
i
nepr
ocessi
ng

Tabl
e4-
1:Cont
entofRegi
ster
sinPi
pel
i
neExampl
e

Gener
alConsiderat ions
 Anyoper ationt hatcanbedecomposedi ntoasequenceof
suboperationsofaboutt hesamecompl exit
ycanbeimplementedby
apipel
inepr ocessor.
 Thegener al struct
ureofaf our-
segmentpipeli
nei
sill
ust
ratedi
nFig.4-
2.
 Wedef neat
i askast hetot
aloperat
ionperfor
medgoingthrough
al
lthesegment sinthepipeli
ne.
 Thebehav iorofapi pel
inecanbeill
ustr
atedwithaspace-t
imediagr
am.
o Itshowst hesegmentut i
li
zati
onasaf unct
ionofti
me.

Ref
erence:
W.St
all
i
ngs 2
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

Fi
g4-
2:FourSegmentPi
pel
i
ne

 Thespace-timedi agram ofaf our-

segmentpipelineisdemonst ratedinFig.4-3.
 Wher eak-segmentpi pelinewi thaclockcy cl
etimet pisu sedt
oe xecuten t
as ks.
o Thef irsttaskT1r equiresat i
meequal tokt pt
ocompl et
eitsoperation.
o Ther emai ningn-1t askswi l
lbecompl etedafterat i
meequal t
o(n-1)tp
o Ther efore, t
ocompl etent asksusingak- segmentpi pel
inerequir
es
k+(
n-1)cl ockcy cles.
 Consideranonpi pel i
neuni tthatperformsthesameoper ati
onand
takesatimeequal totntocompl et
eeacht ask.
o Thet ot altimer equiredf orntasksisntn.

Fi
g4-
3:Space-
ti
medi
agr
am f
orpi
pel
i
ne

 Thespeedupofapi pel
inepr ocessi ngov eranequi valentnon-pi
peli
ne
processi ngi sdef i
nedbyt her ato S=nt
i n/(k+n-1)tp.
 Ifnbecomesmuchl argert hank- 1, thespeedupbecomes S=tn/t
p.
 Ifweassumet hatt het imei ttakest opr ocessat askisthesamei nt he
pipelineandnon- pipeli
neci rcuits,i .
e.,tn =k tp,thespeedupr educest o
S=kt p/tp=k.
 Thisshowst hatt het heoret i
cal maxi mum speedupt hatapi pel
inecanpr ovi
dei
s
k,wher eki st henumberofsegment sint hepi peline.
 To dupl icatet het heoret icalspeedadv ant ageofapi peli
nepr ocessby
meansofmul t
iplef unct i
onaluni ts,itisnecessar yt oconstructkidentical
unitst hatwi llbeoper atingi npar allel.
 Thisi si l
lustrated i n Fig.4- 4,wher ef ouri dent icalcircuit
s are
connect edi npar allel.
 Insteadofoper atingwi tht hei nputdat ai nsequenceasi napi peli
ne,the
paral l
elci rcuitsacceptf ouri nputdat ai emssi
t mul taneouslyandper form
fourt asksatt hesamet ime.

Ref
erence:
W.St
all
i
ngs 3
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

Fig4- 4:Multi
plef uncti
onalunitsinpar al
lel
 Therearev ari
ousreasonswhyt hepipeli
necannotoper ateatit
s
maximum t heoreti
cal r
ate.
o Differentsegment smayt akedi f
fer
entt i
mest ocompl et
e
theirsuboper ation.
o Itisnotal wayscor recttoassumet hatanonpi pecir
cuithast
he
samet imedel ayast hatofanequi valentpipel
i
necircuit
.
 Therearetwoar easofcomput erdesignwher et hepi
peli
ne
organi
zati
oni sapplicable.
o Arithmet i
cpipeline
o Instructi
onpipel i
ne

Par
all
elProcessing
 Par all
elprocessi ngi sat erm usedt odenot eal argecl assoft echni ques
thatar eusedt opr ov i
desi mul taneousdat a-pr ocessi ngt asksf ort he
purposeofi ncr easi ngt hecomput ati
onal speedofacomput ersy stem.
 The pur pose ofpar al
lelpr ocessi ng i st o speed up t he comput er
processingcapabi li
tyandi ncr easei tst hroughput ,thati s,
t heamountof
processingt hatcanbeaccompl i
sheddur ingagi venint erval ofti
me.
 Theamountofhar dwar eincr easeswi thpar allelprocessi ng,andwi thit
,
thecostoft hesy stem incr eases.
 Par all
elprocessi ngcanbev iewedf r
om v ariousl evelsofcompl exity.
o Att hel owestl evel ,
wedi stingui shbet weenpar allelandser i
al
oper at ionsbyt het ypeofr egist ersused.e. g.shi f
tregi stersand
regist erswi thpar allelload
o Atahi gherl ev el,itcanbeachi ev edbyhav ingamul t i
plicit
yof
funct ional unitst hatper f
ormi dent ical ordi ffer
entoper ati
ons
simul taneousl y.
 Fi g.4-
5showsonepossi blewayofsepar atingt heexecut i
onuni tinto
eightfunctional uni tsoper atingi npar all
el.
o Amul tifunct i
onal organi zationi susual lyassoci atedwi thacompl ex
cont rol uni ttocoor dinat eal lt
heact i
vities amongt he v ari
ous
component s.

Ref
erence:
W.St
all
i
ngs 4
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

Fi
g4-
5:Pr
ocessorwi
thmul
ti
plef
unct
ional
uni
ts

 Therear eav arietyofway sthatparallelprocessingcanbecl assi

fied.
o I nternalor ganizat i
onoft hepr ocessor s
o I nterconnect ionst ructurebetweenpr ocessor s
o Thef lowofi nfor mationthrought hesy stem
 M.J.Fl ynnconsi der stheor ganizationofacomput ersy stem byt he
numberofi nstr
uct i
onsanddat aitemst hataremani pulated
simultaneously.
o Si ngleinst ructi
onst r
eam, singledat ast r
eam ( SI
SD)
o Si ngleinst ructi
onst r
eam, mul ti
pledat astream ( SIMD)
o Mul ti
pleinst ructionst r
eam, singledat astream (MI SD)
o Mul ti
pleinst ructionst r
eam, mul t
ipledat astream ( MIMD)
SI
SD
 Represent stheor ganizationofasi nglecomput ercont ainingacont rol
unit,
apr ocessoruni t,andamemor yunit.
 Instr
uctionsar eexecut edsequent iall
yandt hesy st
em mayormay
nothav einternal parallelprocessingcapabi li
ties.
 parall
elprocessi ngmaybeachi evedbymeansofmul ti
plef uncti
onalunit
sorby
pipel
inepr ocessing.

SI
MD
 Representsanor ganizati
onthati
ncludesmanypr ocessingunits
undert hesupervisi
onofacommoncont r
olunit.
 Allprocessorsreceivethesameinstruct
ionfrom thecontroluni
tbut
operateondi f
ferentit
emsofdat a.
 Theshar edmemor yunitmustcontainmulti
plemodul esso
thati
tcancommuni catewit
halltheprocessorssimultaneousl
y.

Ref
erence:
W.St
all
i
ngs 5
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

MI
SD&MI MD
 MI SDst ructur ei sonl yoft heoreticalinterestsi ncenopr act i
cal system
hasbeenconst ruct edusi ngthisor ganization.
 MI MDor ganizat i
onr ef erst oacomput ersy st
em capabl eofpr ocessi ng
sev er
al progr amsatt hesamet i
me.e. g.mul t
iprocessorand
mul ti
comput ersy stem
 Flynn’sclassi ficat iondependsont hedi st
inctionbet weent he
performanceoft hecont r
ol unitandt hedat a-
pr ocessinguni t
.
 Itemphasi zest hebehav i
or alchar acterist
icsoft hecomput ersy st
em
ratherthani tsoper ational andst r ucturalinterconnect i
ons.
 Onet ypeofpar allel processi ngt hatdoesnotf i
tFl y
nn’s
classif
icationi spi pel ining.
 Weconsi derpar allel processi ngundert hef oll
owi ngmai ntopics:
o Pi pelinepr ocesssi ng
 I sani mpl ement ationt echni quewher ear i
thmet i
c
suboper ationsort hephasesofacomput erinstructioncycle
ov erlapi nexecut ion.
o Vect orpr ocessi ng
 Deal swi thcomput at i
onsi nv olv
ingl argevectorsandmat rices.
o Ar raypr ocessi ng
 Per for m comput ationsonl argear r
aysofdat a.

Ar
it
hmeti
cPipeline
 Pipel
i
near i
thmet icunitsareusual l
yf oundi nv er
yhighspeedcomput er
s
o Float ing–poi ntoperat
ions, mul t
ipli
cationoff i
xed-
point
number s,andsi mil
arcomput ationsinscientifi
cproblem
 Fl
oating–poi ntoper ati
onsareeasi lydecomposedi ntosuboperat
ions.
 Anex ampl eofapi peli
neunitforf l
oating-pointadditi
onand
subtr
actioni sshowedi nthefollowing:
o Thei nput stothefloati
ng- poi
ntadderpi pel
inearetwo
normal izedf l
oati
ng-pointbinar ynumber
XA2a
YB2b
o AandBar et wof r
acti
onst hatrepresentthemantissas
o aandbar et heexponent s
 Thefl
oati
ng-
pointaddi ti
onandsubt racti
oncanbeper f
ormed
i
nfoursegments,asshowni nFig.4-6.
 Thesuboper
ati
onst hatareper f
ormedi nthef oursegmentsare:
o Compar etheexponent s
 Thel argerex ponentischosenast heexponentofther
esult
.
o Al i
gnthemant issas
 Theexponentdi ff
erencedet er
mineshowmanyt i
mest he
mant issaassoci atedwi t
ht hesmal l
erexponentmustbe
shif
tedt otheright.
o Addorsubt ractt hemant issas

Ref
erence:
W.St
all
i
ngs 6
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
o Nor
mal
i
zet
her
esul
t pr
ocessi
ng

Ref
erence:
W.St
all
i
ngs 7
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

 Whenanov erf
low occur s,t hemant i
ssaoft hesum or
differencei sshiftedr i
ghtandt heex ponenti ncr ement ed
byone.
 I fanunder fl
owoccur s, thenumberofl eadi ngz erosint he
mant i
ssa det ermines t he numberofl eftshi ftsi nt he
mant i
ssaandt henumbert hatmustbesubt ractedf rom
theexponent .
 Thef oll
owi ngnumer i
cal exampl emaycl arif
ythesuboper at i
ons
perfor medi neachsegment .
 Thecompar ator ,shift,adder ,
subt r
act or,increment er,and
decr ement erint hef loating-pointpipelinear ei
mpl ement edwi th
combi national circuits.
 Supposet hatt het i
medel aysoft hef oursegment saret 1=60ns,
t2=70ns, t3= 100ns, t4= 80ns, andt heinterf aceregistershav ea
delayoft =10ns
r
o Pi pel inef l
oat ing-pointarithmet i
cdel ay:t
p=t3+t=110ns
r
o Nonpi pel i
nef loating-pointarit
hmet i
cdelay: t
n=t1+t2+ t
3+ t4+t
r=320ns
oSpeedup: 320/ 110=2. 9

Fi
g4-
6:Pi
pel
i
nef
orf
loat
ingpoi
ntaddi
ti
onandsubt
ract
ion

I
nst
ructi
onPi pel
ine
 Pi peli
neprocessingcanoccurnotonlyinthedatastream butinthe
i
nst r
ucti
onaswel l.
 Consi deracomput erwithaninst
ruct
ionfetchunitandan
i
nst r
ucti
onexecut i
onunitdesi
gnedtoprovideatwo-segment
pipel
ine.
 Comput erswit
hcompl exinstr
ucti
onsrequireot
herphasesi n
additi
ontoabov ephasestoprocessaninstruct
ioncompletely.
 I nthemostgener alcase,t
hecomputerneedst oprocesseach
Ref
erence:
W.St
all
i
ngs 8
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
i
nst
ruct
ionwi
ththefoll
owingsequpe
r
on
cc
eeo
ssf
ist
ngeps.
o Fetcht
heinstructi
onfrom memor y
.
o Decodetheinstruct
ion.

Ref
erence:
W.St
all
i
ngs 9
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

o Cal culatetheef fectiveaddr ess.

o Fet cht heoper andsf rom memor y .
o Ex ecutet heinstruct i
on.
o Stor ether esultinthepr operpl ace.
 Ther
ear ecer tai
ndi f
ficulti
est hatwi l
l prev enttheinstructi
onpipeli
ne
fr
om oper ati
ngati tsmax imum r ate.
o Differentsegment smayt akedi fferenttimest ooper at
e
ont heincomi ngi nformation.
o Somesegment sareski ppedf orcer tai
noper ati
ons.
o Twoormor esegment smayr equi rememor yaccessatt hesame
ti
me, causingonesegmentt owai tunti
l anotherisfi
nishedwit
h
thememor y.

Exampl
e:Four-SegmentI nst ructionPi pel i
ne
 Assumet hat:
o Thedecodi ngoft hei nstructi
oncanbecombi nedwi ththe
calculat
ionoft heef fect i
veaddr essi ntoonesegment .
o Thei nstructionexecut ionandst oringoft her esultcanbe
combi nedi ntoonesegment .
 Fig4- 7showshowt hei nstruct i
oncy cl
ei nt heCPUcanbepr ocessed
withaf our -
segmentpi peli
ne.
o Thus up t of oursuboper ati
ons i nt he inst ructi
on cy cl
e can
overlapandupt of ourdi ffer
entinst ructi
onscanbei npr ogr
essof
beingpr ocessedatt hesamet i
me.
 Ani nstructionint hesequencemaybecausesabr anchoutof
normal sequence.
o I nthatcaset hependi ngoper ati
onsi nthelastt wosegment sare
compl etedandal linfor mationstor edi nthei nstructionbufferi
s
deleted.
o Si milarl
y,an i nterruptr equestwi l
lcause t he pipeli
ne to
empt yandst artagai nf rom anewaddr essv alue.

Ref
erence:
W.St
all
i
ngs 10
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

Fi
g4-
7:Four
-segmentCPUpi
pel
i
ne

 Fi
g.9-
8showst
heoper
ati
onoft
hei
nst
ruct
ionpi
pel
i
ne.

Fi
g4-
8:Ti
mingofI
nst
ruct
ionPi
pel
i
ne

o FI:
thesegmentthatfetchesani nst
ruct
ion
o DA:thesegmentthatdecodest heinstr
uct
ionand
cal
culat
etheeff
ectiveaddress
o FO:thesegmentthatfetchestheoperand
o EX:thesegmentthatexecutestheinstr
ucti
on

Pi
pel
i
neConfli
cts
 I
ngeneral
,therearethreemajordi
ffi
cul
ti
esthatcausethei
nst
ruct
ion
pi
peli
netodeviatefr
om itsnormaloper
ati
on.
o Resour ceconf l
i
ctscausedbyaccesstomemor ybytwo
segment satthesamet i
me.

Ref
erence:
W.St
all
i
ngs 11
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

 Canber esolvedbyusi ngsepar atei

nst r
uctionand
dat amemor ies
o Dat adependencyconf l
ict
sar i
sewhenani nstructi
ondependson
ther esul tofapr ev i
ousi nstr
uction,butt hisr esultisnotyet
avail
abl e.
o Br anchdi ffi
cultiesar i
sefrom br anchandot herinstruct
ionst
hat
changet hev alueofPC.
 A diff
icul
tyt hatmaycauseadegr adat i
onofper formancei nan
i
nstructi
onpi pel i
neisduet opossi blecolli
sionofdat aoraddr ess.
o Adat adependencyoccur swhenani nstr
uctionneedsdat at
hat
arenoty etav ail
able.
o Anaddr essdependencymayoccurwhenanoper andaddress
cannotbecal culatedbecauset hei nf
ormat i
onneededbyt he
addressi ngmodei snotav ail
able.
 Pipel
ined comput er s deal wi th such conf li
cts bet ween dat a
dependenciesi nav arietyofway s.

Dat
aDependencySol uti
ons
 Hardwarei nterl
ocks:an i nterlock i s a ci rcuitt hatdetect
si nst r
ucti
ons
whosesour ceoper andsar edest inationsofi nstruct
ionsfart
herupi nthe
pipel
i
ne.
o Thi sappr oachmai ntainst hepr ogr am sequencebyusi nghar dware
toinserttherequireddel ay s.
 Operandf orwarding:usesspeci alhar dwar et odet ectaconf li
ctandt hen
avoiditby r outi
ng t he dat at hrough speci alpat hs bet
ween pi peli
ne
segment s.
o Thi s met hod r equi res addi tional har dware pat hs t hrough
mul t
ipl
exersaswel last heci rcuitt hatdet ectstheconfl
ict.
 Delayedload:thecompi l
erf orsuchcomput ersi sdesignedtodet ectadata
confl
ictandr eordert heinst ructi
onsasnecessar ytodelaythel oadingof
theconfli
ctingdatabyi nsertingno- oper ationinstructi
ons.

Handl
i
ngofBr anchI nstructi
ons
 Oneoft hemaj orpr oblemsi n operati
ng an i nstr
ucti
on pipel i
nei st he
occurrenceofbr anchi nstructions.
o Anuncondi ti
onalbr anchalway salterst hesequentialpr ogram f l
ow
byl oadingt hepr ogram count erwiththet argetaddress.
o I nacondi t
ionalbr anch,t hecont r
olsel ectsthetargeti nstructi
oni f
thecondi ti
oni ssat i
sfi
edort henextsequent i
alinstructioni fthe
condi t
ioni snotsat isfied.
 Pi peli
nedcomput ersempl oyv ari
oushardwar et echni
quest omi nimi z
et he
perfor
mancedegr adat i
oncausedbyi nstr
uctionbr anchi
ng.
 Pr efetcht argetinst r
uct i
on:Topr efet
chthet argetinstr
ucti
oni naddi ti
ont o
theinstruct i
onf ollowingt hebr anch.Bothar esav eduntilt
hebr anchi s
executed.
 Br ancht argetbuf fer
(BTB) : TheBTBi sanassoci ati
vememor yincludedi n
thefetchsegmentoft hepi peli
ne.

Ref
erence:
W.St
all
i
ngs 12
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
o EachentryintheBTBconsists
po
rf
ot
ch
ee
ssa
id
ndr
g essofaprevi
ously
executedbranchi
nstruct
ionandthet argeti
nstr
ucti
onforthat
branch.
o Ital
sostoresthenextfewinst
ructi
onsaf tert
hebranchtar
getinst
ruct
ion.

Ref
erence:
W.St
all
i
ngs 13
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

 Loopbuf fer:Thi sisasmal lv eryhi ghspeedr egisterfi

lemaintainedbythe
i
nstructi
onf etchsegmentoft hepi peline.
 Branchpr ediction:Api peli
newi thbr anchpr edicti
onusessomeaddi ti
onal
l
ogict oguesst heout comeofacondi t
ionalbranchi nstr
ucti
onbef or
eitis
executed.
 Delayed br anch:i nt his pr ocedur e,t he compi lerdet ect
st he branch
i
nstructi
ons and r earranges t he machi ne language code sequence by
i
nserting usef ulinstructi
ons t hatkeep t he pipeline operat
ing wit
hout
i
nterrupti
ons.
o Apr ocedur eempl oyedi nmostRI SCprocessor s.
o e. g.no-oper at
ioninstruction

RI
SCPi
peline
 Touseanef ficientinst r uct ionpi pel i
ne
o Toi mpl ementani nst r
uctionpi pelineusi ngasmal lnumberof
suboper ati
ons, wi theachbei ngexecut edi nonecl ockcy cle.
o Becauseoft hef ixed- l
engt hi nstr
uct i
onf or mat ,t hedecodi ngof
theoper ati
oncanoccuratt hesamet imeast her egi ster
sel ect i
on.
o Ther efor e,thei nst ructionpi peli
necanbei mpl ement edwi tht wo
ort hr eesegment s.
 Onesegmentf etchest hei nst ructionf r om pr ogram memor y
 Theot hersegmentexecut est hei nst ruct ioni nt heALU
 Thi r
dsegmentmaybeusedt ost oret her esul toft he
ALUoper at i
oni nadest i
nat i
onr egi ster
 Thedat at ransf erinstr uct ionsi nRI SCar el imi tedt oloadand
st
or einstruct ions.
o Thesei nst ructionsuser egi sterindi rectaddr essi ng.Theyusual ly
needt hr eeorf ourst agesi nt hepi pel ine.
o To pr ev entconf lict s between a memor yaccess t of etch an
inst ruct ionandt ol oadorst oreanoper and, mostRI SCmachi nes
uset wosepar at ebuseswi tht womemor ies.
o Cachememor y: oper ateatt hesamespeedast heCPUcl ock
 One oft he maj oradv ant ages ofRI SC i si ts abi lityt o execut e
i
nstructionsatt herateofonepercl ockcy cle.
o I nef fect ,itist ost ar teachi nstr
uct ionwi theachcl ockcy cleand
to pi pelinet hepr ocessort o achi ev et hegoalofsi ngle-cy cle
inst ruct ionex ecut ion.
o RI SCcanachi ev epi peli
nesegment s, requi ri
ngj ustonecl ockcy cl
e.
 Compi ler suppor t
ed t hat t ransl ates t he hi gh-lev ell anguage
program i ntomachi nel anguagepr ogram.
o I nst ead of desi gni ng har dwar e t o handl e t he di fficulti
es
associ at edwi thdat aconf lictsandbr anchpenal ti
es.
o RI SCpr ocessor sr elyont heef f
iciencyoft hecompi l
ert odet ect
andmi nimi zet hedel aysencount er edwi tht hesepr oblems.

Exampl
e:Thr
ee-
SegmentI
nst
ruct
ionPi
pel
i
ne

Ref
erence:
W.St
all
i
ngs 14
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
 Theear
ethreety
pesofi
nst
ructi
ons:processi
ng
o Thedatamani
pul
ati
oninstr
ucti
ons: oper
ateondat
ainpr
ocessorr
egi
ster
s

Ref
erence:
W.St
all
i
ngs 15
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

o Thedat atransf eri nstr uct ions:

o Thepr ogr am cont rol inst r uct i
ons:
 Thecont rolsect i
onf et chest hei nst ruct i
onf rom pr ogr am memor y
i
ntoani nst r
uct ionr egist er.
o Thei nst ruct ioni sdecodedatt hesamet imet hatt her egi sters
neededf ort heexecut ionoft hei nst r
uct ionar esel ected.
 Thepr ocessoruni tconsi st sofanumberofr egi stersandanar ithmet ic
l
ogi cuni t(ALU) .
 Adat amemor yi susedt ol oadorst or et hedat af r
om asel ected
registerint her egi sterf i
le.
 Thei nstruct i
oncy clecanbedi v idedi ntot hreesuboper ati
onsand
i
mpl ement edi nt hr eesegment s:
o I :Instruct i
onf et ch
 Fet chest hei nst r uct ionf rom pr ogr am memor y
o A: ALUoper ation
 Thei nstruct ioni sdecodedandanALUoper ati
oni sper for med.
 I tper formsanoper at ionf oradat amani pulationi nst ruction.
 I tev aluat est heef fect i
v eaddr essf oral oadorst or einst r
uct i
on.
 I tcal culat est hebr anchaddr essf orapr ogr am cont r
ol instructi
on.
o E: Execut ei nst ruct ion
 Di rect st heout putoft heALUt ooneoft hr ee
dest inat i
ons, dependi ngont hedecodedi nstruction.
 I tt ransf er st her esul toft heALUoper ationi nt oa
dest inat i
onr egi st eri nt her egi sterf il
e.
 I tt ransf er st heef f ect iveaddr esst oadat amemor yf or
l
oadi ngorst oring.
 I tt ransf er st hebr anchaddr esst ot hepr ogr am count er.
Del
ayedLoad
 Consi dert heoper at ionoft hef ollowi ngf ouri nst ructions:
o LOAD:R1 M[ addr ess1]
o LOAD:R2 M[ addr ess2]
o ADD: R3 R1+R2
o STORE: M[ addr ess3] R3
 Ther ewi llbeadat aconf li
cti ni nst ruct ion3becauset heoper andi nR2i s
noty etav ailablei nt heAsegment .
 Thi scanbeseenf rom t het i
mi ngoft hepi pelineshowni nFi g.4- 9(a) .
o TheEsegmenti ncl ockcy cl e4i si napr ocessofpl acingt he
memor ydat ai nt oR2.
o TheAsegmenti ncl ockcy cle4i susi ngt hedat af r
om R2.
 Itisupt ot hecompi lert omakesur et hatt hei nst ructionf ollowi ng
theloadi nstruct i
onusest hedat af etchedf rom memor y.
 Thi sconceptofdel ay ingt heuseoft hedat aloadedf rom memor yisr eferredtoas
delayedl oad.

Ref
erence:
W.St
all
i
ngs 16
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

Fi
g4-
9(a)
:Thr
eesegmentpi
pel
i
net
imi
ng-Pi
pel
i
net
imi
ngwi
thdat
aconf
li
ct

 Fig.4-
9(b)showsthesamepr
ogr
am wi
thano-
opi
nst
ruct
ioni
nser
tedaf
ter
theloadtoR2inst
ruct
ion.

Fi
g4-
9(b)
:Thr
eesegmentpi
pel
i
net
imi
ng-Pi
pel
i
net
imi
ngwi
thdel
ayedl
oad

 Thustheno-opinst
ruct
ionisusedtoadvanceoneclockcy
cleinorderto
compensateforthedat
aconf l
icti
nthepi
peli
ne.
 Theadv ant
ageofthedelay
edloadapproachist
hatthedatadependencyis
takencareofbythecompilerr
athert
hanthehardware.

Del
ayedBranch
 Themet hodusedi
nmostRISCpr
ocessorsistorel hecompi
yont l
ertoredefi
ne
t
hebranchessothatt
heyt
akeeff
ectattheproper i
nthepi
peli
ne.This
t
ime

met hodisref
err oasdel
edt ayedbranch.
 Thecompi lerisdesignedtoanalyzetheinstruct
ionsbef
oreandafterthe
branch and r earr
ange t he program sequence by i nser
ti
ng usef ul
i
nstructi
onsinthedelaysteps.
 I
tisupt othecompilertofi
ndusefulinst
ruct
ionsto putaft
erthebranch

i
nst
ruction.Faili
ngthat,
thecompil
ercani tno-
nser opinstr
uct
ions.
AnExampl
eofDel ayedBranch
 Thepr ogram f ort
hisexampleconsi
stsoffi
veinst
ruct
ions.
o Loadf r
om memor ytoR1
o I ncrementR2
o AddR3t oR4
o Subt ractR5from R6
Ref
erence:
W.St
all
i
ngs 17
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
o Br
ancht
oaddr
essX pr
ocessi
ng

Ref
erence:
W.St
all
i
ngs 18
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

 I
nFi
g.4-
10(
a)thecompil
eri
nser
tstwono-opi
nst
ruct
ionsaf
tert
hebr
anch.
o Thebr
anchaddressXist
ransf
err
edtoPCincl
ockcycle7.

Fi
g4-
10(
a):
Usi
ngnooper
ati
oni
nst
ruct
ion

 Theprogr
am inFi
g.4-
10(b)isr
earrangedbyplaci
ngtheaddand
subt
racti
nst
ructonsaf
i t
erthebranchinst
ruct
ion.
o PCisupdatedtotheval
ueofXi nclockcycl
e5.

Fi
g4-
10(
b):
Rear
rangi
ngt
hei
nst
ruct
ions

VectorProcessi ng
 I nmanysci enceandengi neer ingappli
cati
ons,t
heproblemscanbe
for
mul atedint ermsofv ect orsandmat ri
cesthatl
endthemsel
vest
o
vect
orpr ocessi ng.
 Comput erswi t
hv ectorprocessi ngcapabil
it
iesarei
ndemandi n
speci
alizedappl i
cations.e.g.
o Long- rangeweat herf orecast
ing
o Pet roleum expl or
ations
o Sei smi cdat aanal ysis
o Medi cal diagnosis
o Ar ti
ficialintel
ligenceandexper tsy
stems
o I magepr ocessi ng

Ref
erence:
W.St
all
i
ngs 19
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
o Mappi
ngt
hehumangenome pr
ocessi
ng

Ref
erence:
W.St
all
i
ngs 20
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

 Toachievetherequir
edl evelofhi
ghper f
ormancei
tisnecessar
ytoutil
i
ze
thefastestandmostr el
iabl
ehar dwareandapplyi
nnovati
veprocedur
es
from v
ectorandparal
lelprocessi
ngtechni
ques.

Vect
orOper ations
 Manysci ent i
fi
cpr oblemsr equi rearithmet i
coper ationsonl arge
arraysofnumber s.
 Av ectori sanor der edsetofaone- dimensi onal arrayofdat ai t
ems.
 Av ectorVofl engt hni sr epr esent edasar owv ect orbyV=[ v1,v2,
…,Vn].
 Toexami nethedi ffer
encebet weenaconv ent i
onal scalarpr ocessorand
av ectorpr ocessor ,consi dert hef ollowingFor tranDOl oop:
DO20I=1, 100
20 C( I)=B( I)+A( I)
 Thisi simpl ement edinmachi nel anguagebyt hef ollowing
sequenceofoper ations.
Initi
alizeI =0
20 ReadA( I)
ReadB( I
)
Stor eC( I)=A( I)+B( I
)
IncrementI=I+1
IfI<=100got o
20Cont i
nue
 Acomput ercapabl eofv ectorpr ocessingel i
mi natest heov er head
associ atedwi tht het i
mei tt akest ofetchandexecut ethei nst r
ucti
onsin
thepr ogram l oop.
C(1:100)=A( 1: 100)+B( 1:100)
 Apossi bleinstruct i
onf ormatf orav ectorinst r
uct i
oni sshowni nFig.4-
11.
o Thi sassumest hatthev ectoroper andsr esideinmemor y.
 Iti
sal sopossi blet odesi gnt hepr ocessorwi t
hal argenumberof
registersandst oreal l operandsi nregisterspr iortot headdi ti
on
oper ati
on.
o Thebaseaddr essandl engt hinthev ectorinst r
uctionspeci fya
groupofCPUr egister s.

Fi
g4-
11:
Inst
ructi
onf or
matf
orv
ect
or
processor

Mat
ri
xMulti
pli
cati
on
 Themul t
ipl
icat
ionoft
wonxnmat
ri
cesconsi
stsofn2 pr
oducsorn3
t
innemulti
ply-
addoper
ati
ons.

o Consider,forex ample,themul ti
pli
cat
ionoftwo3x3mat ri
cesAandB.
oc11=a11b11+a 12b21+a13b31
o Thisrequirest hreemultipli
cat
ionand( af
teri
nit
ial
i
zingc11t
o0)
threeadditions.
Ref
erence:
W.St
all
i
ngs 21
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
 I
ngeneral
,thei
nnerpr
oductconsistso
pf
r
oct
he
ess
su
i
ngm ofkpr
oductter
msof
t
hefor
m C=A1B1+A2B2+A3B3+…+AkBk.
o Inat ypi
cal
appli
cati
onkmaybeequal t
o100orev en1000.

Ref
erence:
W.St
all
i
ngs 22
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

 Theinnerpr
oductcal
cul
ati
ononapi
pel
i
nev
ect
orpr
ocessori
sshowni
nFi
g.
4-12.
CA1B1A5B5A9B9A13B13
A2B2A6B6A10B10A14B14
A3B3A7B7A11B11A15B15
A4B4A8B8A12B12A16B16

Fi
g4-
12:
Pipel
i
nef
orcal
cul
ati
ngani
nnerpr
oduct

Memor
yI nterl
eaving
 Pipeline and v ectorpr ocessor s oft
en r equire si
mul taneous access to
memor yfrom t woormor esour ces.
o Ani nstructi
onpi pelinemayr equirethef etchingofani nstruct
ion
andanoper andatt hesamet i
mef r
om t wodi f
ferentsegment s.
o Anar it
hmet icpipelineusual l
yr equirestwoormor eoperandsto
enterthepi pelineatt hesamet ime.
 Insteadofusi ngt womemor ybusesforsi mul t
aneousaccess,t hememor y
canbepar t
it
ionedi ntoanumberofmodul esconnect edt oacommon
memor yaddr essanddat abuses.
o A memor ymodul ei sa memor yar r
ayt ogetherwi thitsown
addressanddat aregisters.
 Fig.4-13showsamemor yuni twit
hfourmodul es.

Fi
g4-
13:
Multi
plemodulememor
y
or
ganizat
ion

Ref
erence:
W.St
all
i
ngs 23
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

 Theadv antageofamodul armemoryisthati

tallowstheuseofatechni
quecal
l
ed
i
nterl
eav i
ng.
 I
nani nt
erl
eavedmemor y,dif
fer
entset
sofaddr essesar
eassignedt
o
dif
ferentmemor ymodules.
 Bystaggeringthememor yaccess,t
heeffect
ivememor ycycl
etimecanbe
reducedbyaf actorcl
osetothenumberofmodul es.

Super
comput er s
 Acommer cial comput erwi thv ectori nstructi
onsandpi pelinedf loat i
ng
-pointar ithmet icoper at ionsi sr ef
erredt oasasuper comput er .
o Tospeedupt heoper ation,thecomponent sar epackedt ight l
y
toget hert omi nimi zet hedi stancet hattheel ectronicsi gnal shav e
tot rav el
.
 Thisi saugment edbyi nst r
uct i
onst hatpr ocessv ect orsand
combi nat i
onsofscal arsandv ectors.
 A super comput er i s a comput er sy stem best known f or i ts high
comput ationalspeed,f astandl argememor ysy st ems,andt heext ensive
useofpar al lelpr ocessi ng.
o I ti sequi ppedwi thmul tiplefunct i
onaluni t
sandeachuni thasi tsown
pipel i
neconf igur at i
on.
 Iti
sspeci ficallyopt imi zedf ort het ypeofnumer ical cal
culat ions
involvingv ect orsandmat r
icesoff l
oat ing-pointnumber s.
 Theyar el imi tedi nt hei ruset oanumberofsci entifi
cappl icat ions,
suchasnumer icalweat herf orecast ing, seismicwav eanaly sis,and
spacer esear ch.
 Ameasur eusedt oev aluat ecomput ersint heirabil
itytoper for m agi ven
numberoff l
oat ing-poi ntoper at i
onspersecondi sr eferredt oasf lops.
 At ypical super comput erhasabasi ccy clet i
meof4t o20ns.
 Theexampl esofsuper comput er:
 Cray -
1:i tusesv ectorpr ocessi ngwi th12di sti
nctf unct i
onaluni tsi nparal
lel
;
alar genumberofr egi st ers(ov er150) ;mul ti
processorconf i
gur ation(Cray
X-MPandCr ayY- MP)
o Fuj itsuVP- 200: 83v ectorinst ructionsand195scal ar
i
nst ruct i
ons; 300megaf l
ops

Ar
rayProcessing
 Anar r
ayprocessori sapr ocessort hatper f
ormscomput at
ionsonlar
ge
arr
aysofdat a.
 Thetermi susedt orefertot wodi f
ferentt y
pesofpr ocessors.
o At t
achedar rayprocessor :
 I sanauxiliaryprocessor .
 I tisi
ntendedt oimprov etheper f
ormanceoft hehost
comput erinspeci f
icnumer i
calcomput ati
ontasks.
o SIMDar rayprocessor :
 Hasasi ngle-instr
uctionmul ti
ple-dat
aor gani
zati
on.
 I tmanipulatesv ectorinst
r uct
ionsbymeansofmul ti
ple

Ref
erence:
W.St
all
i
ngs 24
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
f
unct
ional
uni
tsr
espond
pi
n
ogt
r oa
cessicommoni
ng nst
ruct
ion.

Ref
erence:
W.St
all
i
ngs 25
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

At
tachedAr r
ayPr ocessor
 I t
spur poseist oenhancet heper
formanceoft hecomputerbyprovi
ding
vectorprocessingf orcompl exscienti
fi
capplicati
ons.
o Par all
el pr
ocessi ngwi t
hmul ti
plefuncti
onaluni
ts
 Fi g.4-
14showst heinterconnect
ionofanat t
achedarraypr
ocessortoa
hostcomput er.
 Forexampl e, whenat t
achedt oaVAX11comput er
,th FSP-164/MAXf r
om

Fl
oat
ing-
PointSy
stems i
ncr
eases t
he comput
ing powerof t
he VAX t
o
100megaf
lops.

 Theobject
iveoftheat
tachedar
rayprocessori
stoprov
idevect
or
manipul
ati
oncapabil
it
iestoaconvent
ionalcomput
eratafr
acti
onoft
he
costofsupercomput
er.

Fi
g9-
14:
Att
achedar
raypr
ocessorwi
thhostcomput
er

SI
MDArrayProcessor
 AnSI MDar raypr ocessori sacomput erwi thmul ti
plepr ocessi
ngunits
operati
ngi npar allel.
 Agener alblockdi agr am ofanar rayprocessori sshowni nFig.9-15.
o I tcont ainsasetofi dent icalprocessi ngelement s( PEs)
,each
havingal ocal memor yM.
o EachPEi ncl udesanALU, af l
oating-pointarithmeticunit
,and
wor kingr egi sters.
o Vect ori nstr uct i
onsar ebr oadcastt oallPEssi mult
aneously.
 Maskingschemesar eusedt ocont rolthest at
usofeachPEdur i
ngthe
executi
onofv ect ori nstruct i
ons.
o EachPEhasaf lagt hatissetwhent hePEi sactiveandresetwhen
thePEi si nact i
ve.
 Forexampl e, t
heI LLI ACI Vcomput erdev el
opedatt heUni ver
sit
yofIll
inoi
s
andmanuf act uredbyt heBur roughsCor p.
o Ar ehi ghlyspeci alizedcomput ers.
o Theyar esui tedpr imar ilyfornumer i
cal problemst hatcanbe
expr essedi nv ectorormat ri
xform.

Ref
erence:
W.St
all
i
ngs 26
|
Comput
erOr
gani
zat
ionandAr
chi
tect
ure Chapt
er5:Pi
pel
i
neandVect
or
pr
ocessi
ng

Fi
g4-
15:
SIMDar
raypr
ocessoror
gani
zat
ion

Ref
erence:
W.St
all
i
ngs 27
|