Pipelining Design Techniques - Fundamentals of Computer Organization and Architecture - page 214

3. A computer system has a four-stage pipeline consisting of an instruction fetch
unit (F), an instruction decode unit (D), an instruction execution unit (E), and a
write unit (W). Compute the speed-up time P(4), throughput U(4), and the effi-
ciency

(4) of the pipeline in executing a code segment consisting of 20 instruc-
tions, given that branch instructions occur as follows: I 3 , I 9 , I 10 , I 15 , I 20 .Assume
that when a branch instruction is fetched, the pipeline stalls until the next
instruction to fetch is known. Determine the time required to execute those
same 20 instructions using two-way interleaved memory if the functions
performed by the F, E, and W units require the use of the memory. What is
the average number of cycles per instruction in both cases? Use the following
space-time chart to compute the number of time units.
4. Consider the integer multiplication of two 16-bit numbers M and Q to produce
a product P. Show that this operation can be represented as

z

P ¼ P

15

0 P i i ¼

where P i ¼ M * Q i * 2 i represents a 32-bit partial product.
Design a pipeline unit to perform the above operation using the minimum
number of carry-save adders and one carry-look-ahead adder. Show also the
design of a pipeline for performing floating-point addition subtraction.

/

Give numerical examples to support your design.
5. A computer system has a three-stage pipeline consisting of a Fetch unit (F), a
Decode unit (D), and an Execute (E) unit. Determine (using the space-time
chart) the time required to execute 20 sequential instructions using two-
way interleaved memory if all three units require the use of the memory
simultaneously.
6. What is the average instruction processing time of a five-stage instruc-
tion pipeline for 36 instructions if conditional branch instructions occur as
follows: I 5 , I 7 , I 10 , I 25 , I 27 . Use both the space-time chart and the analytical
model.
7. A computer has a five-stage instruction pipeline of one cycle each. The
five stages are: Instruction Fetch (IF), Instruction Decode (ID), Operand
Fetch (OF), Instruction Execution (IE), and Operand Store (OS). Consider
the following code sequence, which is to be run on this computer.

Load 1, R1; R1 2 1;

2

Load 5, R2; R2 5;

Again: Sub R2, 1, R2 R2 R2 2 1;

Add R1, R2, R3; R3 R1 þ R2;

Bnn Again; branch to Again if result is N ot N egative;

Add R4, R5, R6; R6 R4 þ R5;

Add R6, R4, R7; R7 R4 þ R6;