IE4756 Computer Architecture Tutorial Questions

Tutorial 7

1. Suppose a cache is 10 times as fast as the main memory, and suppose that the cache can
be used 90% of the time. How much speedup do we gain by using the cache?

2. (a) Assume we have a machine where the CPI is 2.0 when all memory accesses hit the
cache. The only data accesses are loads and stores, and these total 40% of the
instructions. If the miss penalty is 25 clock cycles and the miss rate is 2%, how much
faster would the machine be if all instructions were cache hits?

(b) What happens if we don’t have the cache at all?

(c) If the CPI is 1.0 and we still want keep the same speedup, what is the required miss
penalty by keeping the same miss rate?

3. (a) State some reasons why memory references exhibit spatial locality.
(b) State some reasons why memory references exhibit temporal locality.

1
 IE4756 Computer Architecture Tutorial Questions

Tutorial 8

1. Your latest computer has 4GB of byte-addressable main memory. It has a 32-bit address
bus. For each of the following cache organizations, answer the following design
questions:
a. How many blocks (lines) are in the cache?
b. How many sets are in the cache?
c. How many address bits are used for block offset?
d. How many address bits are used for index?
e. How many address bits are used for tag?
f. How many additional memories (in bits) are needed for storing all Tags?
g. How many XOR gates are needed for comparing the tag bits?

h. (i) A direct-mapped cache with total data size of 512KB. Use 8-word (32 bytes)
blocks in the cache.

i. (ii) A 2-way set-associative cache using block size of 2-word (8 bytes),

with a total data size of 256KB?

2. Consider a program in which 20% of the instructions are memory load or store
instructions. Assume that there is a main memory access time of 50 ns, a 500 MHz
processor clock rate, and a CPI of 2 for a machine with a perfect cache (i.e., the data and
instructions are always found in the first level cache). For a machine with an instruction
cache miss rate of 3% and a data cache miss rate of 10%, what is the effective CPI of this
machine?

3. Answer the following questions about cache parameters.

a. For a 1MB, 8-way set-associative cache, with 128-byte blocks, find the number of
bits needed for the cache tag, index, and offset.
b. Consider a direct-mapped cache, with 32 blocks, and a 21-bit tag. What is the
block size (in bytes), and the capacity of the cache?
c. For a 256 byte cache with a 28-bit tag and 4-word blocks, find the number bits in
the index and then compute the associativity.

2
 IE4756 Computer Architecture Tutorial Questions

Tutorial 9
1. Suppose you have a 12-bit machine with a 16-block direct-mapped cache. Each cache
block can hold 16 bytes of data. A program is run on this machine that makes the
following memory accesses in hexadecimal (each memory address addresses a byte of
data):

3FE, 4FE, 4FD, 4F2, 111, 111, 2F1, 4FE, 2F7, 448, 2F9, 2A2

a. How many bits wide is the cache's tag field?

b. Assuming the cache is initially empty, what are the final contents of the cache
after the program runs? Draw a diagram of the cache showing all its fields, but
fill in the tag fields only!

c. Suppose a cache hit takes 5 ns, a cache miss takes 100 ns, and a memory
access without a cache takes 95 ns. How much time is saved by this cache on
this program over an equivalent cacheless machine running this program?

d. Give an example each of spatial and temporal memory access locality

exhibited by this program.

2. Assume that the CPI of a CPU with a perfect cache is 2.0 and the clock cycle time is 2
ns, that there are 1.3 memory references per instruction. Now consider two cache
systems. Assume that the size of both caches is 64 KB and both have a block size of
32 bytes. One cache is direct mapped and the other is two-way set associative.
Assume the CPU clock cycle time must be stretched 1.10 times to accommodate the
selection multiplexer of the set associative cache. The cache miss penalty is 70 ns for
either cache organization.

First calculate the average memory access time, and then CPU performance. Assume
the hit time is one clock cycle. Assume that the miss rate of direct-mapped 64-KB
cache is 1.4%, and the miss rate for a two-way set-associative cache of the same size
is 1.0%.

What is the impact of two different cache organizations on the performance of a

CPU?

3
 IE4756 Computer Architecture Tutorial Questions

3. The Corleone2004 processor has two levels of data caches, with the characteristics
shown below. You can also assume that it takes 50 clock cycles to request and
complete a 32-byte transfer between main memory and the L2 cache.

Find the average memory access time (AMAT) for both the L2 and L1 cache.

Assume the ideal CPI is 2.0 and if 25% of the instructions are loads or stores, what is
the average memory stall cycles per instruction? What is the overall CPI?

4
 IE4756 Computer Architecture Tutorial Questions

Tutorial 10

Q1. (i) Given a task that can be divided into m sub-tasks, each requiring 1 unit of
time, how much time is required for an m-stage pipeline to process n tasks?

(ii) How many widgets must the pipelined widget-assembly machine of Figure
1 assemble in order to achieve a speedup of 3 over the sequential machine? Justify
your answer.

A B C W W
AA B CC W W W W W
2 1 5 4 3 2 1

Sequential machine Pipelined machine

Figure 1

Q2. We have a single stage, non-pipelined machine and a pipelined machine with 5
pipeline stages. The cycle time of the former is 5 ns and the latter is 1ns.

(i) Assuming no stalls, what is the speedup of the pipelined machine over the single
stage machine?
(ii) Given the pipeline stalls 1 cycle for 40% of the instructions, what is the speed up
now?
(iii) Now consider a 4 stage pipeline machine with a cycle time of 1.1ns. Again
assuming no stalls, is this implementation faster or slower than the original 5 stage
pipeline? Explain your answer.

5
 IE4756 Computer Architecture Tutorial Questions

Q3. Suppose the time for an ALU operation can be shortened by 25% compared to the
illustration in the following figure:

(a) Will it affect the speedup obtained from pipelining? If yes, by how much? If not, why
not?

(b) What if the ALU operation now takes 25% more time?

Q4. (a) An instruction requires four stages to execute: stage 1 (instruction fetch) requires 30
ns, stage 2 (instruction decode) = 9 ns, stage 3 (instruction execute) = 20 ns and stage
4 (store results) = 10 ns. An instruction must proceed through the stages in sequence.
What is the minimum asynchronous time for any single instruction to complete?

(b) We want to set this up as a pipelined operation. How many stages should we
have and at what rate should we clock the pipeline?

(c) For the pipeline, how frequently can we initiate the execution of a new instruction,
and what is the latency?

(d) What is the speedup of the pipeline?

6
 IE4756 Computer Architecture Tutorial Questions

Tutorial 11

Q1. Describe the following classes of hazard in the context of a standard DLX pipeline. For
each class, provide a small DLX code fragment that generates such a hazard. Explain
how the machine copes with each condition.

(i) Structural hazards

(ii) Data hazards

Q2. Show the data dependencies and indicate the hazards in the following code sequence:

LW R2, 20(R1)
AND R4, R2, R5
OR R8, R2, R6
ADD R9, R4, R2

Q3. For each of the following, identify the type of hazard and explain how the basic DLX
pipeline (IF ID ALU MEM WB) deals with that hazard. For instruction sequences,
remember that the first instruction will only be one stage ahead of the second in the
pipeline.

a) The instruction sequence

ADD R2, R3, R4
ADDI R5, R2, #-10

b) The instruction sequence

SW 8(R3), R2
ADDI R3, R4, #-10

c) The instruction sequence

LW R2, 8(R3)
ADDI R4, R2, #8

d) The instruction sequence

ADD R2, R3, R4
ADDI R2, R3, #-12

Q4. Suppose you have two RISC machines, M1 and M2. M1 has a 50 nsec cycle time.
Fifteen percent of its instructions are load and stores, and half of these instructions waste
a delay slot by a NO-OP. M2 has a 40 nsec cycle time and thirty percent of its
instructions are load and stores. Each of these requires two delay slots and only sixty
percent of these can fill the delay slots with useful instructions. Which machine is faster
and by how much? Explain your answer. (You should assume that executing a NO-OP
instruction in a delay slot amounts to executing no useful instruction at all.)

7
 IE4756 Computer Architecture Tutorial Questions

Tutorial 12

Q1. For an R4000-style pipeline, it takes three pipeline stages before the branch target
address is known and an additional cycle before the branch condition is evaluated,
assuming no stalls on the registers in the conditional comparison. This leads to the
branch penalties for the three simplest prediction schemes listed in the following table.

Branch scheme Penalty uncond. Penalty untaken Penalty taken

Flush pipeline 2.0 3 3

Predict taken 2.0 3 2
Predict untaken 2.0 0 3

Find the effective addition to the CPI arising from branches for this pipeline, using the
data from the SPEC benchmark in which the frequencies for the unconditional branches,
conditional untaken branches and conditional taken branches are 4%, 6% and 10%
respectively.

Q2. PowerPC 601 is a pipelined machine and it has six pipeline stages: Fetch,
diSpatch, Decode, Execute, Cache access, and Write. In this machine the result of a
branch is decided in the Execute stage and the target of any jump or conditional
branch is available at the end of the Decode stage. CPU detects the branch/jump
instruction at the fetch stage. Researchers are going to do a performance test by using
a set of benchmark programs. 20% of the instructions are conditional branches, 5% of
instructions are jumps or calls in this benchmark. And we also know that 60% of
conditional branches are going to be taken.

a) What is the expected CPI on this machine for the given benchmark programs?
Assuming that CPU is going to stall the pipeline until it finds out what the result of
branch is.

b) Do you think that adding two-slot Delayed Branch capability for unconditional
branches to CPU improves the performance? If 60% of these delay slots are filled
with useful instructions by the compiler, what will be the new CPI? Assume that for
conditional branches, CPU continues to fetch the instructions from the following
instructions (Predict Branch Not Taken strategy).

Q3. Assume that delayed branching is implemented, so that the instruction after the branch is
always executed before branching. Reorder the following code to make better use of the
branch delay slot. Assume R3 is initialised to integer 8 before the loop starts. You may
also need to slightly modify the code.

Loop: LW R2, 100(R3)

SW 200(R3), R2
SUBI R3, R3, #4
BNEZ R3, Loop
NOP ; Branch Delay Slot