Homework 2- Memory, Pipeline, Pipeline Hazard
Deadline: April 12, 2024
Q1: On the Motorola 68020 microprocessor, cache access takes two clock cycles. Data access from the
main memory over the bus to the processor takes three clock cycles in the case of no wait state insertion;
the data are delivered to the processor in parallel with delivery to the cache.
a) Calculate the effective length of a memory cycle given a hit ratio of 0.9. (i.e., one clock cycle
equals 60 ns.)
b) Repeat the calculation assuming insertion of two wait states of one cycle each per memory cycle.
What conclusion can you draw from the result in terms of performance and average access time?
a) One clock cycle equals 60 ns, so a cache access takes 120 ns and a main memory access takes 180
ns. The effective length of a memory cycle is:
(0.9 x120) + (0.1x180) = 126 ns.
b) The calculation is now (0.9 x120) + (0.1 x 300) = 138 ns. Clearly the performance degrades. However,
note that although the memory access time increases by 120 ns, the average access time increases by
only 12 ns.
Q2: Consider a single-level cache with an access time of 2.5 ns, a block size of 64 bytes, and a hit ratio
of H = 0.95. Main memory uses a block transfer capability that has a first word (4 bytes) access time of
50 ns and an access time of 5 ns for each word thereafter.
a. What is the access time when there is a cache miss? Assume that the cache waits until the line has
been fetched from main memory and then re-executes for a hit.
b. What is the average memory access time?
c. Suppose that increasing the line size to 128 bytes increases the H to 0.97. Does this reduce the
average memory access time?
a) First, 2.5 ns are needed to determine that a cache miss occurs. Then, the required line is read into the
cache. Then an additional 2.5ns are needed to read the requested word.
Tmiss = 2.5 + 50 + (15 x 5) + 2.5 = 130 ns
b) The average access time = (0.95 x 2.5) + (0.05 x 130) = 8.875 ns
c) Tmiss = 2.5 + 50 + (31 x 5) + 2.5 = 210 ns
and the new average access time = (0.97 x 2.5) + (0.03 x 210) = 8.725ns
Yes, it reduces the access time.
Q3: Consider a fully- associative cache with 8 cache blocks (numbered from 0 to 7) and the following
sequence of memory block requests:
4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7
If LRU replacement policy is used, which cache block will have memory block 7.
4 3 25 8 19 6 25 8 16 35 45 22 8 3 16 25 7
4 4 4 4 4 4 4 4 4 4 45 45 45 45 45 45 45
3 3 3 3 3 3 3 3 3 3 22 22 22 22 22 22
25 25 25 25 25 25 25 25 25 25 25 25 25 25 25
8 8 8 8 8 8 8 8 8 8 8 8 8 8
19 19 19 19 19 19 19 19 19 3 3 3 3
6 6 6 6 6 6 6 6 6 6 6 77
16 16 16 16 16 16 16 16 16
35 35 35 35 35 35 35 35
m m m m m m h h m m m m h m h h m
Therefore, cache block 5 will have memory block 7.
Q4: Assume a pipeline with Four stages:
1. FI: Fetch instruction
2. DA: Decode instruction and calculate addresses
3. FO: Fetch operand
4. EX: Execute
Draw a diagram similar to the following Figure for a sequence of 7 instructions to show how many
time units are now needed.
Figure A: Timing Diagram for Instruction Pipeline Operation.
Q5: In Figure A, consider the effects of the conditional branch. Assume that instruction 2 is a
conditional branch to instruction 7. If the branch is taken:
a) What will happen to the pipeline and instruction execution?
Instruction 3 through 6 would be skipped resulting in a pipeline stall.
b) What would be the completion time for 9 instructions?
14
Q6: Consider the 5-stage pipeline discussed in class. For the following pairs of instructions (in parts A,
B, C, D, E, F), how many stalls will the 2nd instruction experience with bypassing approach?
Part A)
Add R6, R5, R4
LW R7, 5(R6)
No. of stalls: 0, since 2nd instruction reads R6 after the R6 is calculated in 1st instruction. In other words, point of
production for R6 is 3rd stage, point of consumption for R6 is 4th stage, since the p.o.c is after the p.o.p, we are
good to proceed with no stalls.
Part B)
LW R3, 5(R4)
LW R6, 5(R3)
No. of stalls: 1, since 2nd instruction reads R3 one stage before the value is written in R3 in the 1st instruction. It
means that p.o.p for R3 is stage 4th, and p.o.c for R3 is happening before the p.o.p. So, it doesn’t work. We need
1 stall.
Part C)
LW R2, 5(R3)
SW R2, 5(R4)
No. of stalls: 0, since 2nd instruction needs R2 after the 1st instruction has modified the value of R2. Producing
instruction is going to produce R2 in the stage 4, the store instruction is going to use R2 in DM stage which
is after the p.o.p. No stall is required.
Part D)
Add R6, R5, R4
Add R8, R6, R7
No. of stalls: 0, since 2nd instruction needs R6 after the 1st instruction has modified the value of R2.
Part E)
LW R6 ß (R1)
Add R4 ß R6+R3
No. of stalls: 1, P.O.P for R6 is è stage 4th, point of consumption of R6 is è 3rd stage. We need 1 stall.
Part F)
LW R4 ß (R1)
SW R3 à (R4)
No. of stalls: 1, P.O.P for R4 is è stage 4th, point of consumption of R4 is è 3rd stage. We need 1 stall.