CS
465
Final
Review
Fall
2015
Prof.
Daniel
Menasce
Ques?ons
What
are
the
types
of
hazards
in
a
datapath
and
how
each
of
them
can
be
mi?gated?
State
and
explain
some
of
the
methods
used
to
deal
with
branch
predic?on.
Answer
What
are
the
types
of
hazards
in
a
datapath
and
how
each
of
them
can
be
mi?gated?
Data
hazard
(forwarding)
Structural
hazard
(more
func?onal
units;
e.g.,
separate
instruc?on
and
data
caches)
Control
hazard
(branch
predic?on,
determining
branch
outcome
at
the
ID
stage).
State
and
explain
some
of
the
methods
used
to
deal
with
branch
predic?on.
Sta?c
(assume
taken
not
taken)
and
dynamic
(1-bit,
2-
bit)
Does the following code sequence must stall,
can avoid stalls using forwarding only, or can
execute without stalling or forwarding?
lw $t0, 0($t0)
add $t1, $t0, $t0
Does the following code sequence must stall,
can avoid stalls using forwarding only, or can
execute without stalling or forwarding?
lw $t0, 0($t0)
add $t1, $t0, $t0
$t0 available
must stall
$t0 needed
Explain
This
Ques?on
Which
of
these
elements
inuence
the
execu?on
?me
of
a
program?
The
level
1
cache
hit
rate
The
hit
rate
to
the
TLB
The
number
of
instruc?ons
handled
per
stage
The
page
fault
rate
The
ISA
The
clock
cycle
dura?on
Answer
Which
of
these
elements
inuence
the
execu?on
?me
of
a
program?
The
level
1
cache
hit
rate
The
hit
rate
to
the
TLB
The
number
of
instruc?ons
handled
per
stage
The
page
fault
rate
The
ISA
The
clock
cycle
dura?on
ALL
Ques?on
What
are
all
the
levels
of
a
memory
system
hierarchy?
How
do
size,
access
?me,
and
cost/bit
vary
along
the
hierarchy?
What
property
of
programs
is
important
for
the
performance
of
the
memory
system
hierarchy?
Answer
What
are
all
the
levels
of
a
memory
system
hierarchy?
caches,
main
memory,
secondary
storage
How
do
size,
access
?me,
and
cost/bit
vary
along
the
hierarchy?
Size
and
access
?me
increase
going
down
and
cost/bit
decreases
going
down
What
property
of
programs
is
important
for
the
performance
of
the
memory
system
hierarchy?
Space
and
temporal
locality
Ques?on
What
are
the
types
of
cache
organiza?on?
Explain
for
each:
block
search,
block
placement,
block
replacement?
Explain
the
two
cache
hit
on
write
policies:
write-through
and
write
back
(includes
write
buer)
Explain
approaches
used
for
cache
miss
on
write
policies
Answer
What
are
the
types
of
cache
organiza?on?
Direct
mapped,
set
associa?ve,
fully
associa?ve
Explain
for
each:
block
search,
block
placement,
block
replacement?
DM:
search
one
cache
entry
only;
SA:
search
all
entries
in
a
set;
FA:
search
all
cache
entries
DM:
at
a
specic
cache
entry;
SA:
any
empty
loca?on
in
a
set;
FA:
any
empty
loca?on
in
the
cache
DM:
only
one
op?on;
SA:
LRU/Random
within
set;
FA:
LRU/
Random
within
the
cache
Explain
the
two
cache
hit
on
write
policies:
write-through
and
write
back
(includes
write
buer)
Explain
approaches
used
for
cache
miss
on
write
policies
Allocate
on
miss
(fetch
block
and
overwrite
por?on
of
block)
and
write-around
(do
not
fetch
block)
Ques?on
Which
of
the
following
are
true?
A.
All
cores
share
a
single
L1
cache
B.
All
cores
share
a
single
L2
cache
C.
Each
core
has
its
own
page
table
register
D.
All
cores
share
a
single
L3
cache
E.
The
TLB
is
stored
in
main
memory
F.
The
page
table
needs
to
be
accessed
for
every
memory
access
Answer:
C
and
D
Which
of
the
following
are
true?
A.
All
cores
share
a
single
L1
cache
B.
All
cores
share
a
single
L2
cache
C.
Each
core
has
its
own
page
table
register
D.
All
cores
share
a
single
L3
cache
E.
The
TLB
is
stored
in
main
memory
F.
The
page
table
needs
to
be
accessed
for
every
memory
access
Explain
This
Explain
This
Explain
This
Explain
This
Ques?on
Consider
a
4-way
set
associa?ve
cache
with
blocks
of
4
words
of
4
bytes
each.
The
cache
size
is
256
K
bytes.
How
many
bits
in
the
address
are
used
for
the
tag,
cache
index,
and
block/word/
byte?
Answer
Consider
a
4-way
set
associa?ve
cache
with
blocks
of
4
words
of
4
bytes
each.
The
cache
size
is
256
K
bytes.
How
many
bits
in
the
address
are
used
for
the
tag,
cache
index,
and
block/
word/byte?
Each
block
has
16
bytes.
Each
set
has
4
blocks.
So,
each
set
has
64
bytes
The
number
of
sets
in
the
cache
is
the
size
of
the
cache
divided
by
the
size
of
a
set
=>
2^8
*
2^10
/2^6
=
2^12
Thus,
we
need
12
bits
to
index
a
set
a
the
cache
Index=
12
bits
Block
has
16
bytes:
need
4
bits
to
address
a
byte
in
a
block
Tag
=
32
(12+4)
=
16
bits
Ques?on
A
machine
supports
virtual
memory
and
page
sizes
are
4
Kbytes
long.
A
physical
address
is
32
bits
long.
How
many
page
frames
are
there
in
main
memory?
Suppose
that
a
virtual
address
is
34
bits
long.
What
is
size
of
the
virtual
address
space
in
pages?
How
many
entries
are
there
in
the
page
table?
Es?mate
the
size
of
the
page
table
in
MB.
Answer
A
machine
supports
virtual
memory
and
page
sizes
are
4
Kbytes
long.
A
physical
address
is
32
bits
long.
How
many
page
frames
are
there
in
main
memory?
2^32
/
2^12
=
2^20
=
1024
*
1024
page
frames
Suppose
that
a
virtual
address
is
34
bits
long.
What
is
size
of
the
virtual
address
space
in
pages?
2^34
/
2^12
=
2^22
virtual
pages
How
many
entries
are
there
in
the
page
table?
2^22
Es?mate
the
size
of
the
page
table
in
MB.
(2^22
*
(20
+
1
+
1
+
1))
bits
=
2^22
*
(23/8)
/
2^20
MB
=
11.5
MB
Explain
This
Ques?on
Consider
the
following
table.
Access
.me
Hit
rate
Miss
Penalty
Memory
element
L1
Cache
1
cycle
85%
5
cycles
L2
cache
5
cycles
99%
100
cycles
Memory
100
cycles
100%
Compute
the
Average
Memory
Access
Time
in
cycles
Answer
Consider
the
following
table.
Access
.me
Hit
rate
Miss
Penalty
Memory
element
L1
Cache
1
cycle
85%
5
cycles
L2
cache
5
cycles
99%
100
cycles
Memory
100
cycles
100%
Compute
the
Average
Memory
Access
Time
in
cycles
0.85
*
1
+
0.15
*(0.99
*5
+
0.01
*
100)
=
1.724
cycles
Ques?on
How
is
write
on
hit
handled
in
virtual
memory
(write-through
or
write-back)
and
why?
What
is
the
typical
page
replacement
policy
used
in
virtual
memory
and
how
it
is
implemented?
Answer
How
is
write
on
hit
handled
in
virtual
memory
(write-through
or
write-back)
and
why?
Write
back
because
it
takes
too
long
to
write
to
disk
(approximately
one
million
cycles)
What
is
the
typical
page
replacement
policy
used
in
virtual
memory
and
how
it
is
implemented?
LRU,
approximated
by
a
reference
bit
that
is
reset
regularly
for
all
pages
and
set
at
every
reference
to
a
page.
