Int
ern
at
i
onal
Journ
al of Ele
ctrical
an
d
Co
mput
er
En
gin
eeri
ng
(IJ
E
C
E)
Vo
l.
10
,
No.
4
,
A
ugus
t
2020
,
pp.
3476
~
34
82
IS
S
N:
20
88
-
8708
,
DOI: 10
.11
591/
ijece
.
v
10
i
4
.
pp3476
-
34
82
347
6
Journ
al h
om
e
page
:
http:
//
ij
ece.i
aesc
or
e.c
om/i
nd
ex
.ph
p/IJ
ECE
Hybrid
b
ra
nch
predicti
on
for pipelin
ed MIPS
process
or
Ali S
.
Al
-
K
h
alid, S
afa
a
S
.
O
mran
Middle
Te
chn
ica
l
Univer
si
t
y
,
Ele
ct
ri
ca
l
Eng
ine
er
i
ng
Techni
c
al Co
ll
eg
e, I
raq
Art
ic
le
In
f
o
ABSTR
A
CT
Art
ic
le
history:
Re
cei
ved
Ma
y
10
, 201
9
Re
vised
N
ov 15
,
2019
Accepte
d
Ja
n
11
, 2
020
In
the
m
oder
n
m
ic
roproc
essors
tha
t
design
ed
with
pipe
l
i
ne
stage
s,
the
per
form
anc
e
of
the
se
t
y
pes
of
proc
essors
will
be
aff
ec
t
ed
whe
n
execut
in
g
bra
nch
instru
ct
i
ons,
bec
ause
in
thi
s
ca
se
the
re
will
be
sta
ll
s
in
the
pip
el
in
e
.
In
turn
thi
s
c
ause
s
in
r
educing
the
C
y
c
le
Per
Instruc
ti
o
n
(CPI)
of
the
proc
essor.
I
n
the
c
ase
of
e
x
ec
ut
ing
a
bra
n
ch
instruction,
t
he
proc
essor
nee
ds
an
ext
r
a
c
l
ocks
to
know
if
tha
t
bra
n
ch
will
happe
n
(T
ake
n)
or
not
(Not
Ta
ken)
and
al
s
o
it
req
uire
s
calc
ul
at
ing
the
ne
w
addr
ess
in
t
he
ca
se
of
the
bra
n
ch
is
T
a
ken.
Th
e
pre
d
ic
t
ion
tha
t
the
br
an
ch
is
T
/
NT
is
a
n
important
stage
in
enha
n
cing
the
proc
essor
per
form
anc
e.
In
thi
s
rese
arc
h
m
ore
tha
n
one
m
et
hod
of
bra
n
ch
pre
d
ic
t
ion
(h
y
brid)
is
used
a
nd
the
d
esigne
d
ci
r
cui
t
wil
l
choose
diffe
r
ent
t
y
pes
of
pre
di
ct
ion
a
lg
orit
m
s
depe
nding
on
t
he
t
y
p
e
of
the
bra
n
ch.
Som
e
o
f
the
se
m
et
h
ods
were
used
are
stat
i
c
while
t
he
othe
r
ar
e
d
y
nami
c.
All
c
irc
uit
s
wer
e
buil
t
pra
ct
i
call
y
a
nd
exa
m
ine
d
b
y
app
l
y
ing
diffe
ren
t
progr
ams
on
the
d
esigne
d
pr
edict
or
al
gor
it
h
m
t
o
compute
the
p
erf
orm
anc
e
of
the process
or.
Ke
yw
or
d
s
:
Dynam
ic
b
ran
c
h
pr
e
dicti
on
Hybr
i
d br
a
nc
h pr
e
dictor
Stat
ic
b
ra
nch predict
io
n
The hazar
ds
Copyright
©
202
0
Instit
ut
e
o
f Ad
vanc
ed
Engi
n
ee
r
ing
and
S
cienc
e
.
Al
l
rights re
serv
ed
.
Corres
pond
in
g
Aut
h
or
:
Safaa
S
.
Om
ran
,
Mi
dd
le
Tec
hnic
al
U
ni
ver
sit
y
,
Ele
ct
rical
En
gi
neer
i
ng
Tec
hn
i
cal
Colle
ge,
Ir
a
q
.
Em
a
il
:
O
m
ran
_s
afaa
@ym
ail.co
m
1.
INTROD
U
CTION
Branc
h
pre
dictors
now
c
onsidere
d
on
e
of
t
he
ba
sic
unit
s
in
the
m
od
er
n
m
ic
ro
process
or
s
t
hat
use
pip
el
ine
sta
ges
in
t
heir
desi
gn.
T
his
un
it
(BP
)
m
akes
a
pr
e
di
ct
ion
f
or
the
branc
h
i
ns
tr
uctions
that
if
t
he
br
a
nc
h
will
be
Take
n
or
N
ot
Ta
ken.
Pr
e
viously
w
hen
pro
cess
ors
wer
e
desig
ne
d
with
out
br
a
nch
pr
e
dicti
on
un
it
,
the
proces
sor
r
equ
i
res
m
or
e
cl
ock
cy
cl
es
by
m
aking
a
dela
y
in
the
pip
el
i
ne
sta
ges
i
n
ea
ch
com
ing
of
br
a
nc
h
instru
ct
io
n
in
order
to
know
if
that
br
anc
h
is
Taken
or
N
ot
Taken
an
d
al
so
to
cal
culat
e
the
ta
rg
et
address
i
n
the case
of Ta
ke
n [1,
2].
In
g
e
ner
al
2
0%
out
of
the
i
ns
tr
uctions
in
a pr
ogram
is
br
anc
h
inst
ru
ct
io
ns
; t
his
m
eans
that
is
in
eve
ry
5
inst
ru
ct
io
ns
there
is
one
br
a
nc
h
inst
r
uction
[
3].
H
ence,
pr
e
dicti
ng
t
he
beh
a
vi
our
of
the
br
a
nc
h
(which
is
T
ake
n
or
N
ot
Take
n)
is
ve
ry
im
p
or
ta
nt
an
d
a
ff
e
ct
s
the
pe
rfo
r
m
ance
of
the
proces
sor.
T
he
pen
al
t
y
associat
ed
with
m
ispred
ic
te
d
br
a
nc
hes
i
n
m
od
ern
pip
el
i
ned
proc
esso
rs
has
a
great
e
ff
ect
on
pe
rform
ance.
The
pe
rfor
m
an
ce
pen
al
ty
is
i
ncr
ease
d
as
th
e
pip
el
ines
de
epen
a
nd
t
he
num
ber
of
m
ispred
ic
te
d
in
struc
ti
on
s
increases
.
F
or
exam
ple,
the
AMD
Athl
on
process
or
ha
s
10
sta
ges
in
th
e
intege
r
pip
el
i
ne
[4
]
,
w
hile
the
In
te
l
NetB
urst
m
ic
r
oar
c
hitec
ture
us
e
d
in
t
he
P
entium
4
proc
essor
is
hyper
-
pi
pelined
wit
h
a
20
-
sta
ge
br
a
nc
h
pr
e
dicti
on
pe
na
lt
y
[5
]
.
The
r
est
of
t
his
w
or
k
will
be
as
f
ol
lows
;
in
t
he
ne
xt
sect
ion
a
t
heoreti
cal
rev
i
ew
f
or
so
m
e
ty
pes
of
sta
ti
c
and
dynam
ic
br
anc
h
pr
e
dicti
on
m
eth
ods.
T
hen
a
sect
ion
will
pr
esents
th
e
des
ign
e
d
br
a
nc
h pr
e
dicti
on circ
uit an
d
t
he follo
wi
ng s
ect
ion
s
will
pr
esents
resu
lt
s a
nd conclu
sio
ns res
pecti
vely
.
2.
THE
ORETI
C
AL BA
CKRO
UN
Ther
e
a
re
tw
o
kinds
of
bran
ch
predict
io
n,
on
e
cal
le
d
sta
t
ic
wh
il
e
the
ot
her
is
dy
nam
i
c,
an
d
he
re
a brie
f
e
xp
la
na
ti
on
for
s
om
e t
ypes
of
branc
h pr
e
dicti
on m
eth
ods.
Evaluation Warning : The document was created with Spire.PDF for Python.
In
t J
Elec
&
C
om
p
En
g
IS
S
N:
20
88
-
8708
Hyb
ri
d br
an
c
h pre
dicti
on for
pip
el
ine
d
M
IP
S proce
ssor
(
A
li
S
. Al
-
k
hali
d
)
3477
2.1.
St
ati
c br
an
c
h
predic
tio
n
If
the
te
ch
nique
of
th
e
us
e
d
br
an
ch
pre
dicti
on
ci
rcu
it
gi
ves
the
sam
e
pr
e
dicti
on
f
or
al
l
t
ypes
of
br
a
nc
hes
is
kn
own
as
sta
ti
c
branc
h
pre
dicti
on
[
6
,
7
]
.
Wh
il
e
if
the
pr
e
dicti
on
c
ha
ng
es
with
the
r
unni
ng
t
i
m
e,
this
is
cal
le
d
a
dynam
ic
br
a
nch
predict
io
n.
For
e
xam
ple
the
proce
ssor
i486
us
ed
sta
ti
c
br
anc
h
pr
e
dicti
on
al
gorithm
,
in
wh
ic
h
at
each
com
ing
br
a
nc
h
the
predict
io
n
is
al
ways
N
ot
Take
n
[
8
]
.
But
m
os
t
of
t
he
br
anch
e
s
are
ta
ken
es
pe
ci
al
ly
the
br
a
nc
hes
of
ki
nd
Lo
op,
w
her
e
t
he
branc
h
is
ta
ken
for
al
l
the
nu
m
ber
of
the
lo
op
excep
t t
he
la
st on
e the
br
a
nc
h i
s N
ot Tak
en
. A
s an
exa
m
ple
f
or
a lo
op
of
100
cy
cl
es, 99
of them
are
ta
ken
and
on
ly
the
la
st
one
is
not
ta
ke
n.
Hen
ce
,
a
no
t
her
te
c
hn
i
qu
e
of
sta
ti
c
branc
h
pre
dicti
on
is
us
e
d
in
Pe
ntium
4
pro
cess
or
w
hich
is
Ba
ck
ward
Take
n/F
orw
ard
No
t
Ta
ke
n
(BTFNT).
Th
is
is
do
ne
by
countin
g
the
va
lue
of
the
new
a
ddres
s
if
it
is
le
ss
than
the
curre
nt
address
the
n
th
e
pr
edict
io
n
is
Ba
ckw
a
rd
Ta
ke
n
an
d
if
the
address
is
gr
eat
er
t
han
the
cu
rr
e
nt
ad
dress
the
n
the
pr
edict
io
n
is
F
orwa
rd
N
ot
Tak
en
[
9
,
10
].
The
adv
a
ntag
e
of
us
in
g
sta
ti
c
br
anc
h
predict
io
n
al
gor
it
h
m
s
is
that
they
are
ve
ry
eas
y
to
i
m
ple
m
ent
an
d
nee
ds
sim
ple
ha
rdwa
re
c
ircuit
to b
e
adde
d
t
o t
he
de
sig
ned pr
ocess
or.
2.2.
Dyna
mi
c
br
anch predi
c
tion
This
ty
pe
of
br
a
nc
h
pr
e
dicti
on
te
c
hniq
ue
will
ta
ke
t
he
ad
van
ta
ge
of
the
a
vaila
ble
inf
or
m
at
ion
thr
ough
the
r
un
tim
e
of
br
a
nc
h
be
ha
vio
r
.
T
he
m
ai
n
idea
i
n
dy
nam
ic
br
a
nch
pr
e
dicti
on
is
to
ta
ke
into
account
the
sta
te
of
the
bra
nch
as
the
ti
m
e
is
run
w
hich
giv
es
bette
r
pr
ed
ic
ti
on
f
rom
the
sta
ti
c
br
a
nc
h
pr
e
dicti
on
[
11,
12
].
O
ne
of
the
earli
est
m
et
hods
us
e
d
a
s
a
dynam
ic
br
a
nc
h
pr
e
dict
ion
i
s
the
al
gorithm
pr
ese
nted
by
[13
]
(als
o
known
as
Bi
m
od
al
Pr
e
dictor
),
wh
ic
h
is
s
ho
wn
in
Fig
ur
e
1.
I
n
t
his
al
gorith
m
the
predict
io
n
con
sist
s
f
r
om
ta
ble
recordi
ng
eac
h
pr
e
vi
ou
s
predict
io
n
wh
e
re
it
was
ta
ken
o
r
not
ta
ken
.
It
is
sh
own
i
n
Figure
1
t
hat
the
ci
rcu
it
of
th
e
br
a
nch
pr
e
di
ct
ion
co
ns
ist
s
from
a
gr
oup
of
2
m
cou
nte
rs
wh
e
re
each
one
of
th
e
m
reco
r
ding
the
previ
ous
sta
te
of
the
br
a
nc
h.
Si
nce
th
ere
are
2
m
counter
s
(en
trie
s
)
the
addres
s
of the
br
a
nc
h
i
ns
tr
uction (
PC)
shou
l
d be
has
hed do
wn to m
b
it
s.
S
a
t
u
r
a
t
i
n
g
c
o
u
n
t
e
r
I
n
c
r
e
m
e
n
t
/
D
e
c
r
e
m
e
n
t
B
r
a
n
c
h
a
d
d
r
e
s
s
B
r
a
n
c
h
o
u
t
c
o
m
e
B
r
a
n
c
h
p
r
e
d
i
c
t
i
o
n
M
o
s
t
s
i
g
n
i
f
i
c
a
n
t
b
i
t
U
p
d
a
t
e
d
c
o
u
n
t
e
r
v
a
l
u
e
2
m
2
-
b
i
t
s
c
o
u
n
t
e
r
s
m
/
Figure
1.
A
rch
i
te
ct
ur
e
of
basic
d
ynam
ic
b
ra
nc
h pr
e
dictor
al
gorithm
The
siz
e
of
t
he
us
e
d
c
ounte
r
in
t
his
te
ch
ni
qu
e
co
ns
ist
s
of
2
-
bits,
wh
ic
h
is
be
st
f
ro
m
us
in
g
1
-
bit.
The
MSB
of
th
e
counter
in
dicat
es
the
pr
edict
ion
sta
te
wh
il
e
the
LSB
of
th
e
counter
in
dicat
es
the
past
branch
sta
te
.
In
t
he
ca
se
of
inc
reasin
g
the
num
ber
of
co
unte
r
bits
to
3,
the
im
pr
ov
em
ent
in
the
pr
e
dictor
al
gor
it
h
m
is
ver
y
sm
al
l,
so
that
it
is
alw
ay
s
pr
e
fers
to
us
e
2
-
bits
counter
with
le
ss
hard
war
e
from
us
ing
a
la
rg
e
r
counter
[
1,
14
].
So
m
e
of
the
research
e
rs
us
e
d
the
two
-
le
ve
l
pr
edict
or,
w
hich
us
e
s
a
histo
ry
for
the
m
os
t
br
an
c
h
ou
tc
om
es.
The
se
outc
om
es
are
sto
red
in
a
Branc
h
History
Re
gister
(B
HR)
wh
ic
h
is
a
sh
ift
reg
ist
er
wh
e
re
the
ou
tc
om
e
f
or
eac
h
br
a
nc
h
is
sh
ifte
d
in
side
the
sh
ift
r
egiste
r
an
d
the
old
est
ou
tc
om
e
is
sh
ifte
d
ou
t
an
d
discar
ded
[
13,
15,
16
]
.
Fig
ure
2
s
hows
t
he
struct
ur
e
f
or
the
tw
o
-
le
vel
br
a
nc
h
pr
e
dic
ti
on
al
go
rithm
s
with
global hist
or
y.
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2088
-
8708
In
t J
Elec
&
C
om
p
En
g,
V
ol.
10
, No
.
4
,
A
ugus
t
2020
:
3476
-
3482
3478
It
is
cl
ear
fro
m
Figu
re
2
th
at
le
vel
on
e
c
on
sist
s
from
t
he
ci
rc
uit
of
t
he
Gl
ob
al
His
tory
Re
giste
r
(GHR)
w
hile
le
vel
tw
o
is
t
he
ci
rcu
it
of
the
t
able
w
hic
h
c
on
sist
s
from
the
s
at
ur
at
ed
co
unte
rs.
This
ta
ble
cal
le
d
the
Patt
ern
Hi
story
Table
(PHT)
.
The
pred
ic
ti
on
in
this
al
gorithm
us
ing
the
ou
tc
om
e
of
a
4
m
os
t
recent
br
a
nc
hes
with
2
-
bits
from
the
br
a
nch
a
ddres
s
to
com
po
se
a
6
-
bit
w
hich
is
the
ind
e
x
to
on
e
of
the
64
co
unte
rs
from
the
PH
T.
Also
the
re
exis
ts
ano
the
r
ty
pe
of
the
tw
o
-
le
ve
l
pr
edict
or,
w
hich
is
know
n
as
the
Local
H
ist
or
y
two
-
le
vel
pr
e
di
ct
or
[17
-
19]
s
how
n
i
n
Fi
gure
3.
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
1
.
.
.
.
0
1
0
1
0
0
0
1
0
1
0
1
0
1
0
1
1
0
0
1
0
1
1
1
.
.
.
.
.
1
1
1
1
1
0
1
1
1
1
1
1
P
H
T
P
C
=
0
1
0
1
1
0
1
0
0
1
0
1
0
1
0
1
1
0
B
H
R
0
1
0
1
1
0
1
B
r
a
n
c
h
p
r
e
d
i
c
t
i
o
n
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
1
1
.
.
.
.
0
1
0
1
1
0
0
0
1
0
1
1
0
1
0
1
0
1
1
1
0
0
1
0
1
1
1
1
.
.
.
.
0
1
1
1
1
1
0
0
1
1
1
1
1
1
P
C
=
0
1
0
1
1
0
1
0
0
1
0
1
0
1
0
1
0
1
1
1
0
P
H
T
B
H
T
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
0
1
0
B
r
a
n
c
h
p
r
e
d
i
c
t
i
o
n
Figure
2. Tw
o
-
le
vel predict
or
with
global his
tory
Figure
3. Tw
o
-
le
vel predict
or
with local
hist
or
y
This
m
e
tho
d
i
s
done
by
rep
l
aci
ng
the
Bra
nc
h
Histo
ry
Re
gister
(BHR
)
by
a
set
of
cou
nte
rs
w
hich
known
a
s
Bra
nch
Histo
ry
T
able
(B
HT).
T
he
bra
nch
ad
dress
is
us
e
d
to
sel
ect
on
e
of
the
e
nt
ries
of
t
he
BH
T
and
acco
rd
i
ng
to
the
sel
ect
ed
nu
m
ber
of
t
he
se
entries
as
s
how
n
in
Fig
ure
3.
T
his
a
ddr
ess
will
sel
ect
on
e
of
the
existi
ng
en
trie
s
(BHR)
i
n
the
BHT
,
in
wh
ic
h
it
will
giv
e
th
e
local
histor
y.
The
c
on
te
nts
of
the
chose
n
BHR wil
l be
c
om
bin
ed
with t
he
PC
to
i
nd
e
x t
o on
e
of t
he
c
ounters
in
t
he PHT.
2.3.
Hy
brid
Bra
nc
h Predicti
on
Be
cause
the
re
are
di
ff
e
ren
t
ty
pes
of
bra
nch
e
s
exists
i
n
the
pro
gr
am
s,
m
ay
be
these
ty
pes
are
correla
te
d
wit
h
dif
fer
e
nt
ty
pe
s
of
histor
y.
Hen
ce
s
om
e
of
the
branc
hes
m
ay
b
e
is
bet
te
r
to
us
e
the
global
histor
y
al
go
rithm
wh
il
e
oth
e
r
branc
hes
a
re
bette
r
to
us
e
with
it
the
loc
al
histor
y
or
a
ny
oth
e
r
al
go
r
it
h
m
correla
te
d
wit
h
local
histo
ry
al
go
rit
hm
.
This
diff
e
ren
ce
i
n
the
ty
pe
of
pr
e
dicti
on
al
gorithm
s
le
ads
so
m
e
of
the
researc
hers
to
us
e
a
Hy
bri
d
Branc
h
Pr
e
dicti
o
n
(
HBP
)
[20
-
25
]
.
On
e
of
the
earli
est
res
earche
rs
w
ho
us
e
d
the
HBP
is
[17
]
wh
o
sug
gests
wh
at
is
cal
le
d
the
Tourn
am
ent
Pr
edict
or
as
sh
own
in
Fi
gure
4.
It
is
cl
ear
fr
om
this
fig
ure
th
at
the
Me
ta
pr
e
di
ct
or
(M)
c
ons
ist
s
from
a
ta
ble
of
2
-
bit
co
unte
rs
w
hich
in
dex
e
d
t
o
it
by
us
in
g
the
tw
o
lo
wer
order
bits
f
r
om
the
bra
nch
a
ddress
.
Accor
din
g
to
the
co
nte
nt
of
these
co
unte
rs
t
he
m
ultip
le
xe
r
will
sel
ect
the
pr
e
dictor
P
0
in
the
case
of
the
MSB
=0,
and
choosin
g
the
pr
e
dictor
P
1
i
n
the
case
of
MSB
=1
.
The
Me
ta
pr
e
di
ct
or
works to
pr
e
dict f
or whi
ch
al
go
rithm
p
red
ic
ti
on m
et
ho
d P
0
or P
1
is c
orrect.
Wh
e
n
t
he
br
a
nch
outc
om
e
is
avail
able,
t
he
pr
e
dicto
rs
P
0
and
P
1
a
re
updated
acco
r
ding
to
their
resp
ect
ive
up
da
te
ru
le
s.
Wh
il
e
the
Me
ta
pr
e
dictor
i
s
updat
ed
acco
r
ding
to
di
ff
e
ren
t
ru
le
s.
The
2
-
bit
co
un
te
rs
will
be
us
e
d
i
n
the
pre
dictor
s
are
finite
sta
te
m
achines
(
FSMs),
w
he
re
the
i
nputs
a
re
ty
pical
ly
the
br
a
nc
h
ou
tc
om
e
and
the
pre
vious
st
at
e
of
the
FS
M.
For
the
Me
ta
pr
e
dictor
,
th
e
inputs
are
C
0
,
C
1
a
nd
the
previo
us
FSM stat
e,
where C
i
is
one if
P
i
predict
e
d
c
orrectl
y. Ta
ble 1 li
sts t
he
sta
te
tran
sit
io
ns
.
Wh
e
n
P
1
'
s
predict
ion
was
correct
and
P
0
m
iss
pr
edict
ed,
the
co
rr
es
pondin
g
co
un
t
er
in
M
is
increm
ented,
sat
ur
at
in
g
at
a
m
axi
m
u
m
value
of
3.
Wh
il
e,
wh
e
n
P
1
m
iss
pr
edict
s
an
d
P
0
pr
e
dicts
correct
ly
,
the
co
unte
r
is
decr
em
ented,
s
at
ur
at
in
g
at
zer
o.
If
both
pr
e
di
ct
or
s
a
re
c
orre
ct
,
or
both
m
iss
pr
e
dict
,
the
c
ounter
in
M
is
unm
od
ifie
d.
T
he
pr
e
di
ct
ion
lo
okups
on
P
0
an
d
P
1
with
the
sta
te
f
or
M
a
re
al
l
pe
rfor
m
ed
in
pa
rall
el
.
Wh
e
n
the
pr
e
di
ct
ion
operati
ons
f
or
t
he
three
pr
e
dictors
a
re
done,
t
he
Me
ta
pr
e
dictor
is
us
ed
to
ch
oose
one
of
the
m
ulti
plexer
li
nes
P
0
or
P
1
.
T
he
pr
oces
so
r
Com
paq
Alpha
21264
[
26,
27
]
us
ed
the
HBP
al
gori
thm
as
sh
ow
n
in
Fi
gur
e
5.
Evaluation Warning : The document was created with Spire.PDF for Python.
In
t J
Elec
&
C
om
p
En
g
IS
S
N:
20
88
-
8708
Hyb
ri
d br
an
c
h pre
dicti
on for
pip
el
ine
d
M
IP
S proce
ssor
(
A
li
S
. Al
-
k
hali
d
)
3479
P
0
P
1
B
r
a
n
c
h
a
d
d
r
e
s
s
M
M
e
t
a
-
p
r
e
d
i
c
t
i
o
n
B
r
a
n
c
h
p
r
e
d
i
c
t
i
o
n
Figure
4.
The
tour
nam
ent sele
ct
ion
m
echan
is
m
Table
1.
T
our
nam
ent
Me
ta
predict
or up
date
ru
le
s
C
0
(P
0
co
rr
ect)
C
1
(P
1
co
rr
ect)
m
o
d
if
icatio
n
toM
0
0
d
o
no
th
i
n
g
0
1
satu
rating
incre
m
e
n
t
1
0
satu
rating
decre
m
e
n
t
1
1
d
o
no
th
i
n
g
B
r
a
n
c
h
a
d
d
r
e
s
s
B
r
a
n
c
h
P
r
e
d
i
c
t
i
o
n
M
g
s
h
a
r
e
P
A
p
Figure
5.
To
ur
nam
ent
hybr
i
d for c
om
paq
alp
ha
21264
3.
SY
STE
M DESIGN
AN
D
I
MPLEME
NT
ATIO
N
In
t
his
resea
r
ch
the
hybri
d
pr
e
dicti
on
m
et
hod
is
us
e
d
in
the
de
sig
n
of
the
us
e
d
pr
ocess
or
.
The
pr
ocess
or
is a MIPS (
Mi
croprocess
or wi
tho
ut
In
te
rl
oc
ked
Pipeli
ne
d St
ages)
pip
el
in
ed
proc
esso
r w
it
h
five
pip
el
ine
sta
ge
s
.
The
desig
n
of
this
ty
pe
of
pr
ocess
or
is
a
pa
rt
from
the
wo
r
k
in
the
s
ubj
ect
adv
a
nce
d
com
pu
te
r
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2088
-
8708
In
t J
Elec
&
C
om
p
En
g,
V
ol.
10
, No
.
4
,
A
ugus
t
2020
:
3476
-
3482
3480
te
chnolo
gy
f
or
the
MSc
co
urse
stu
dy.
T
his
desig
ne
d
al
gorithm
was
synthesiz
ed
usi
ng
the
Xili
nx
ISE
(Integ
rated
Sof
tware
E
nvir
onm
ent)
desi
gn
s
uite
14.
7,
a
nd
us
in
g
th
e
Ve
rt
ex
-
4
Kit
with
op
e
rati
ng
f
re
quenc
y
of
50
M
Hz.
The
branc
h pr
e
dicti
on alg
ori
thm
is d
esi
gne
d
f
or th
e MIPS
Proces
so
r
to be a
s fol
lows
:
-
In
t
he
case
of
Un
c
onditi
onal
br
a
nc
h
an
d
Ca
ll
/R
et
ur
n,
a
sta
ti
c
al
go
rithm
of
Al
ways
Ta
ke
n
is
use
d.
T
his
is
because
of
it
s s
i
m
ple d
esi
gn a
nd also
for i
ts l
ess
m
iss pr
edic
ti
on
pen
al
ty
.
-
In
cas
e
of
the
br
a
nc
h
is
Co
nd
it
io
nal,
a
dynam
ic
al
go
rith
m
wh
ic
h
is
t
he
Tw
o
-
Le
vel
al
g
ori
thm
is
us
ed
as sho
wn in Fi
gure
2
.
-
Finall
y
in
the
case
of
br
a
nc
h
of
ty
pe
Lo
op,
the
predic
tor
will
be
dy
nam
ic
br
anc
h
pr
e
dictor
o
f
t
ype
Bim
od
al
as s
how
n
i
n
Fi
gure
1
.
-
Fo
r
the tw
o
ty
pes
(t
wo
le
vel
and
bim
od
al
)
of d
y
nam
ic
b
ranch pre
dicti
on
a
1
02
4
2
-
bits co
un
te
rs
we
re
use
d,
wh
ic
h
is
in
this
case
approxi
m
at
ely
the
eff
e
ct
of
al
ia
sing
not
exists.
At
st
art
al
l
the
2
-
bit
counters
will
be
sat
ur
at
ed
(its
va
l
ue
is
11)
.
F
or
the
t
wo
-
le
vel
pr
e
dicto
r
a
32
Branc
h
History
Re
gister
is
use
d
in
t
he
Bra
nc
h
History
Table.
-
A
sel
ect
or
is
use
d
t
o
sel
ect
th
e
ty
pe
of
t
he
predict
io
n
al
go
r
it
h
m
fr
om
the
three
desi
gn
e
d
al
gorithm
s
P
0
,
P
1
,
and P
2
acc
ordi
ng to Ta
ble
2.
Table
2.
Pr
e
dic
ti
on
ty
pe se
le
ct
ion
Selecto
r
o
/p
Predicto
r
00
P
0
01
P
1
10
P
2
The
Pr
e
dicti
on
Ty
pe
Ci
rcu
it
(P
TC)
s
how
n
in
Fig
ur
e
6
is
us
e
d
to
decide
the
ty
pe
of
the
pr
edict
i
on
al
gorithm
acc
ordin
g
to
the
ex
ecuti
ng
bran
ch
inst
ru
ct
io
n.
Fig
ur
e
6
s
ho
ws
the
desi
gned
hybr
i
d
al
gorithm
.
As
s
hown
fro
m
Figu
re
6,
th
e
input
to
the
Pr
e
dicti
on
Ty
pe
Ci
rcu
it
is
bits
0:5
a
nd
bits
26
:
31
from
the
br
a
nc
h
address
,
this
gro
up
of
bits
known
as
fun
ct
ion
an
d
O
p
Cod
e
re
sp
ect
ively
.
The
P
re
dicti
on
Ty
pe
Ci
rcu
it
exam
ines
these
two
set
s
of
bit
s
and
decides
t
he
ty
pe
of
br
a
nch
in
str
uction,
and
he
nce
th
e
ou
tp
ut
de
pe
nds
on
the ty
pe of
the
br
a
nc
h,
t
hen th
e sele
ct
or
sel
ect
s one
of
t
he pr
edict
or
s
acc
ord
ing
t
o
Ta
ble
2.
Figure
6.
Str
uc
ture of
the
desi
gn
e
d b
ran
c
h pre
dicti
on
al
gorithm
4.
RESU
LT
S
In
orde
r
to
te
s
t
the
desi
gned
hybri
d
branc
h
pr
e
dictor
al
gorithm
and
t
o
c
om
par
e
it
with
diff
e
re
nt
br
a
nc
h
pre
dicti
on
al
gorithm
s,
three
dif
fer
e
nt
pro
gr
am
s
were
wr
it
te
n
a
nd
e
xecu
te
d
us
in
g
the
MIPS
pi
pe
li
ned
process
or w
it
h
the foll
owin
g
c
ases:
-
Wi
t
hout
us
in
g
a
ny
BP al
gor
it
h
m
.
Evaluation Warning : The document was created with Spire.PDF for Python.
In
t J
Elec
&
C
om
p
En
g
IS
S
N:
20
88
-
8708
Hyb
ri
d br
an
c
h pre
dicti
on for
pip
el
ine
d
M
IP
S proce
ssor
(
A
li
S
. Al
-
k
hali
d
)
3481
-
U
sin
g
the
d
e
s
ign
e
d HBP al
gorithm
.
-
U
sin
g
sta
ti
c
BP h
a
rdwa
re a
lgorit
hm
that al
ways NT
.
-
U
sin
g
the
Bi
m
od
al
d
ynam
i
c BP alg
or
it
hm
w
it
h 1
024 2
-
bi
ts co
un
te
r
s.
Table
3
s
how
s
the
dif
fer
e
nt
rec
orded
res
ults.
It
is
cl
ear
f
r
om
T
able
3
that
t
he
hy
br
i
d
Bra
nc
h
Pr
e
dicti
on
al
gorithm
giv
es
be
st
resu
lt
s
an
d
this
is
becau
s
e
of
us
in
g
m
or
e
than
one
al
gorithm
,
wh
er
e
each
al
gorithm
is
su
it
able
for
ce
rtai
n
ty
pes
of
bra
nch
instr
uctio
ns.
Als
o
it
is
cl
ear
that
us
in
g
BP
al
gorithm
of
a
ny
ty
pe
(stat
ic
or
dynam
ic
)
giv
e
s
b
et
te
r res
ults than
not
us
in
g b
ran
c
h pr
e
dicti
on alg
ori
thm
Table
3.
E
xec
ut
ion
ti
m
e fo
r di
ff
e
ren
t B
P
alg
ori
thm
s
Prog
ra
m
Execu
tio
n
Ti
m
e
No
Branch
Predictio
n
Static Not
Taken
Dy
n
a
m
i
c
Bi
m
o
d
al
Hy
b
rid BP
Test pro
g
ra
m
1
2
7
3
ns
2
5
0
ns
2
1
8
ns
2
0
2
ns
Test
p
rog
ra
m
2
3
6
6
ns
3
1
4
ns
2
9
7
ns
2
7
2
ns
Test pro
g
ra
m
3
5
0
7
ns
4
7
1
ns
4
3
2
ns
4
1
1
ns
5.
CONCL
US
I
O
N
Ther
e
are
diff
e
ren
t
kinds
of
branc
h
i
ns
tr
uctions,
s
o
that,
t
he
re
is
a
certai
n
al
gorithm
s
we
re
s
uitable
for
so
m
e
ty
pes
for
bra
nch
es
wh
il
e
ot
her
ki
nd
s
of
bra
nch
e
s
are
s
uitable
f
or
oth
e
r
ty
pes
of
B
ran
c
h
P
re
dicti
on
Algorithm
s.
Hen
ce,
th
ree
dif
f
eren
t
pre
dictor
s
wer
e
use
d
in
this
work
in
t
he
sa
m
e
structure
wh
ic
h
is
kn
own
as
a
Hyb
rid
Bra
nc
h
P
re
dictor.
This
pr
e
dictor
is
te
ste
d
by
usi
ng
a
de
sig
ned
32
-
bits
pi
peline
d
MIP
S
pro
cesso
r
us
in
g
the
Xili
nx
ver
te
x
-
4
kit.
Diff
e
re
nt
te
st
program
s
wer
e
wr
it
te
n
t
o
te
st
the
des
ign
e
d
hy
br
i
d
br
a
nc
h
pr
e
dictor
al
gorithm
with
the
MIPS
proce
sso
r
a
nd
the
resu
lt
s
c
om
par
ed
with
oth
e
r
ty
pes
of
pr
e
dicti
on
al
gorithm
s an
d i
t i
s f
ou
nd that
the
HBP
ga
ve t
he
be
st res
ults.
REFERE
NCE
S
[1]
L.
Henne
ss
y
an
d
D.
Patt
erson,
“
Co
m
pute
r
Archi
t
ec
tur
e:
A
Quanti
t
at
iv
e
Approac
h,
”
Cambr
idge
,
MA:
Morgan
Kaufmann
Publi
shers
,
2019
.
[2]
S.
Mitt
a
l,
“
A
surve
y
of
va
lue
pr
e
dic
ti
on
techniqu
es
for
le
v
era
g
in
g
val
ue
localit
y
,
”
Concurrenc
y
a
nd
Computati
on
:
Pract
i
ce
and
E
x
perie
nc
e
,
vol. 29
,
no
.
21
,
Sept
ember
2017.
[3]
S.
P.
Dand
amudi,
“
Fundam
ent
al
s
of
computer
org
ani
z
at
ion
and
de
sign,
”
Spring
er
-
Ve
rlag N
ew Y
ork
,
2003
.
[4]
Me
y
e
r
D
.
,
"A
MD
-
k7
te
chno
log
y
pr
ese
nt
at
ion
,
"
Micropr
oce
ss
or F
oru
m
,
Oct
ober
1998.
[5]
Hinton,
Glenn,
Dave
S,
Mike
U,
Darre
l
B,
Doug K,
Alan
K,
and
Patri
c
e
R,
" T
he m
ic
roa
rch
i
tectur
e
of
the
Penti
um
4
proc
essor,"
Int
el
Technol
ogy
jour
nal
Q1
,
pp.
1
-
13
,
2001
.
[6]
D.
C.
Burger
a
nd
T.
M.
Aus
tin,
“
The
Sim
p
le
Scalar
tool
se
t
,
ver
sion
2.
0
,
”
in
ACM
SIGAR
CH
Computer
Archi
t
ec
ture
Ne
ws
,
vol. 25, no.
3,
pp
.
13
-
25
,
Jan
uar
y
2002.
[7]
M.
Kam
pe,
P.
Stenstrom,
and
M.
Dubois,
“
The
FA
B
pre
dic
tor:
Us
ing
Fourier
ana
l
y
s
is
to
pre
di
c
t
the
out
come
of
condi
ti
on
al
bra
nche
s,”
in
Proce
ed
ings
Ei
ght
h
Inte
rnational
Sympo
sium
o
n
High
Pe
rform
ance
Compute
r
Archi
t
ec
ture
,
C
a
m
bridge
,
MA
,
U
SA
,
pp.
223
–
232
,
2002
.
[8]
Corpora
ti
on
,
I
.
,
“
Embedde
d
Intel
486
Proc
essor Hardwa
re
Refe
r
en
ce
Manu
al,”
Intel
Corpor
ati
on
,
1
997.
[9]
Corpora
ti
on
,
I
.
,
“
Inte
l®
Arch
it
e
c
tur
e
Opt
imiza
t
io
n
Refe
r
ence
Ma
nual
,
”
In
te
l
Corpor
ati
on
,
2003
.
[10]
P.
-
Y.
Chang,
E
.
Hao,
T
.
-
Y.
Y
e
h,
and
Y
.
Pat
t,
“
Branc
h
class
ifica
t
ion:
a
new
m
ec
hani
sm
for
improving
bra
nc
h
pre
dictor
p
erf
or
m
anc
e,”
in
MIC
RO
,
pp
.
22
–
31
,
1994.
[11]
P.
-
Y.
Chang,
M.
Eve
rs,
and
Y.
N.
Patt.,
"Im
proving
bra
nch
pre
dic
ti
on
accurac
y
b
y
r
educing
pa
t
t
ern
histor
y
ta
b
l
e
int
erf
ere
n
ce
,
"
Proce
ed
ings
of
th
e
1996
Confe
renc
e
on
Parallel
Archi
t
ec
tures
and
Compilat
ion
Tec
hnique
,
Bosto
n
,
MA
,
US
A,
pp.
4
8
-
57,
1996
.
[12]
J.
Bonanno,
A.
Coll
ura
,
D.
Lipetz,
U.
M
a
y
er
,
B.
Prask
y
,
an
d
A.
Sapori
to,
“
Tw
o
le
vel
bul
k
pre
lo
ad
bra
n
c
h
pre
diction,”
201
3
IEE
E
19th
In
te
rnational
Sym
posium
on
High
Pe
rform
ance
Computer
Architecture
(
HPCA)
,
Shenzhe
n,
pp.
7
1
-
82,
2013
.
[13]
E.
S.
Jam
es,
“
A
stud
y
of
br
an
ch
pre
di
ct
ion
st
rat
eg
ie
s,
in
25
y
e
ars
of
th
e
interna
t
iona
l
s
y
m
p
osia
on
Com
pute
r
arc
hi
te
c
ture
(sel
ec
t
ed
p
ape
rs),
”
ISCA
'98:
25
y
ears
of
th
e
int
e
rnational
sympo
sia
on
Comput
er
architec
tur
e
(
sele
ct
ed
papers)
,
pp.
202
-
215
,
Augus
t
1998.
[14]
M.
Al
-
Otoom
,
E
.
Forbes,
and
E.
Rote
nber
g
,
“
EX
ACT:
Exp
li
c
it
D
y
nami
c
-
Branc
h
Predic
ti
on
with
Acti
ve
Updat
es,
”
CF
'10:
Proceed
ings o
f the
7th A
CM
internationa
l
con
fe
renc
e
on
Computing
front
ie
rs
,
pp
.
165
-
17
6,
Ma
y
2010
.
[15]
A.
F.
Jos
eph,
a
nd
M.
F.
St
efan,
“
Predic
t
ing
c
ondit
ional
br
anch
direct
ions
fro
m
pre
vious
runs
of
a
progr
am,
”
ASP
LO
S
V:
Pro
ce
ed
ings
of
th
e
f
if
th
in
te
rnat
iona
l
conference
on
Archi
t
ec
tural
su
pport
for
progr
a
mm
ing
languages
and
operati
ng
sy
stems,
pp.
85
-
95,
Septe
m
ber
1992
.
[16]
Y.
Ma,
H.
Gao,
and
H.
Zhou,
“
U
sing
inde
xing
func
ti
ons
to
red
uc
e
conf
lict
al
i
asin
g
in
bra
nch
pre
dic
ti
on
t
abl
es
,
”
in
IEE
E
Tr
a
nsacti
o
ns on
Computers
,
vol
.
55
,
no
.
8
,
p
p.
1057
-
1061
,
A
ug.
2006
.
[17]
S.McFarl
ing,
“
Com
bini
ng
Branch Predi
c
tors,
”
W
este
rn R
ese
arch
Labor
atory
,
250
Univer
sit
y
Aven
ue,
June
1993
.
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2088
-
8708
In
t J
Elec
&
C
om
p
En
g,
V
ol.
10
, No
.
4
,
A
ugus
t
2020
:
3476
-
3482
3482
[18]
G.
H.
Loh
,
“
Sim
ula
ti
on
diffe
r
e
nce
s
bet
wee
n
a
ca
demia
and
in
dustr
y
:
A
bra
nc
h
pre
dic
t
ion
cas
e
stud
y
,
”
IEEE
Inte
rnational
Sy
mpos
ium
on
Pe
rform
ance
Analysis
of
Syste
ms
and
Soft
ware,
2
005.
ISPA
SS
20
05
,
Aus
ti
n,
TX,
pp.
21
-
31
,
2005
.
[19]
M.Srila
th
a,
K.
Artur,
and
G.
Dirk,
“
Bran
ch
Predic
ti
on
Us
in
g
Sele
ct
iv
e
Bra
nch
Inve
rsion,
”
1999
Inte
rnational
Confe
renc
e
on
Parall
el
Architect
ures
and
Co
mpilat
ion
Techni
que
s
(
Cat.
No.
PR
00
425)
,
Newport
B
ea
ch
,
CA,
US
A,
pp.
48
-
56
,
1999
.
[20]
Go
y
al
and
J.
Sin
gh,
"Two
-
le
v
el
a
ll
o
y
ed
br
anc
h
pr
edi
c
tor
base
d
on
gene
tic
a
lgori
th
m
for
dee
p
pipe
l
ini
ng
proc
essor,"
in
Int
ernati
onal
Journal
of
Mode
rn E
ducation
an
d
Computer
Sc
ience
,
vol
.
9
,
no
.
5
,
pp
.
27
-
33
,
Ma
y
2017.
[21]
P.
-
Y
.
Chang,
E.
Hao,
and
Y.
N.
Patt
,
“
Alte
rn
ativ
e
implementatio
ns of
h
y
brid
br
a
nch
pre
di
ct
ors
,”
Proce
e
d
ings o
f
t
he
28th
Annua
l
Int
e
rnational
S
ymposium on
Mic
roar
chi
t
ec
ture
,
Ann
Arbor,
MI,
US
A,
pp
.
252
-
257
,
1
995.
[22]
A.
Baniasadi
an
d
A.
Mos
hovos,
“
SEP
A
S:
A
high
l
y
a
cc
ur
at
e
en
er
g
y
-
e
fficie
nt
bra
n
ch
pre
d
ic
to
r,
”
Pr
oce
ed
ings
of
the
2004
Inte
rnation
al
Symposium
o
n
Low
Powe
r
El
ec
troni
cs
and
D
esign
(
IEE
E
Cat.
No.
04TH
8758)
,
Newport
Bea
ch,
CA,
US
A,
pp.
3
8
-
43,
2004
.
[23]
A.
Falc
on
,
J.
St
ark
,
A.
Ramire
z
,
K.
L
ai,
and
M.
Val
ero
,
“
Prophet/critic
h
y
br
id
bra
nch
pr
edi
c
ti
o
n,
”
Proce
ed
ings.
31st
Annual Int
e
rnational
S
ymposium on
Comput
er
Architecture,
2004
,
Munch
en,
Germ
an
y
,
pp.
25
0
-
261,
2004
.
[24]
M.
Eve
r
s,
P.
-
Y.
Chang,
and
Y.
N.
Patt
,
“
Us
ing
hy
brid
br
anc
h
pre
dic
tors
to
improve
bra
nch
pre
d
iction
accurac
y
i
n
the
pr
ese
nc
e
of
c
onte
xt
sw
it
che
s
,
”
in
ISCA
,
pp
.
3
–
11,
1996
[25]
M.
Eve
rs,
“
Im
pr
oving
bra
nch
pre
diction
b
y
unde
rstandi
ng
bra
nch
beha
vior,”
Ph.D.
disserta
ti
on
,
The
Univer
sit
y
o
f
Michi
gan
,
2000
.
[26]
R.
E
.
Kess
ler,
“
The
Alph
a
2126
4
Micropr
oc
essor,”
in
I
EE
E
Mi
cro
,
vol
.
19
,
no
.
2
,
pp.
24
-
36
,
Mar
c
h
-
April
1999.
[27]
A.
Sezn
ec
,
S.
Feli
x,
V.
Krish
nan,
and
Y
.
Sa
ze
id
es
,
“
Design
tra
d
eof
fs
for
t
he
Alpha
EV8
condi
ti
on
al
bra
n
ch
pre
dictor,
”
in
IS
CA
,
pp
.
295
–
306
,
2002
.
BIOGR
AP
H
I
ES
OF
A
UTH
ORS
Ali
S
.
Al
-
K
halid
was
born
in
B
aghda
d,
Ira
q
in
1958.
He
rec
ei
v
ed
his
BS
c
and
MS
c
in
el
ec
trica
l
engi
ne
eri
ng
in
1980
and
1983
respe
ct
iv
ely
fr
om
the
Univer
sit
y
of
B
aghda
d
.
He
is
now
a
n
assistant
profe
ss
or
working
at
the
Coll
eg
e
of
El
e
ct
ri
ca
l
Engi
n
ee
ring
T
ec
hn
ic
a
l
Coll
eg
e,
th
e
m
iddl
e
te
chnica
l
unive
rsit
y
,
B
aghda
d,
Ira
q
.
His
m
ai
n
int
ere
st
is
in
instrumenta
ti
on
and
m
ea
surem
ent
in
power
li
n
e. He
i
s a
lso i
n
te
r
este
d
in
th
e
fi
el
d
of cr
y
pt
anal
y
sis
.
Safaa
S
.
Omr
an
was
born
in
Ir
aq.
I
gra
duated
f
rom
Univer
sit
y
of
Baghda
d
in
1978,
a
nd
the
n
I
got
th
e
MS
c
fro
m
the
sam
e
Uni
ver
sit
y
in
1984
.
Now
I
am
worki
ng
in
the
Elec
tr
i
ca
l
Engi
n
ee
r
ing
Coll
ege
/
Middle
Techni
c
al
Univ
ersity
as
an
assistant
prof.
M
y
intere
st
working
re
sea
rch
es
in
th
e
fie
ld
of
m
icrop
roc
essor
design
for
embedde
d
s
y
stems
,
Im
age
proc
essing
an
d
cr
y
ptogra
ph
y
s
y
stem de
sign
.
Evaluation Warning : The document was created with Spire.PDF for Python.