Description

I. Pipelining

The slides contain five examples. Study them first:

Example 1 (no pipeline): slides 5d-31b and 31c.

Example 2 (full pipeline): also on slides 5d-31b and 31c.

Example 3 (different-length steps): slide 31e.

Example 4 (second copy of one step, and it doubles the speed): slide 31f.

Example 5 (second copy of one step, but it doesn’t double the speed): slide 31g.

Then study the restaurant analogy provided on Blackboard.

1. Answer the following questions:
2. a) In example 5 (slide 5d-31g), why does duplicating the execution hardware not double the speed of the system?
3. b) Is it possible that duplicating the execution hardware wouldn’t change the speed of the system at all? Why or why not?
4. c) Is is possible that duplicating the execution hardware would make the system slower? Why or why not?

Finally, work the following problems.

This table gives three instruction types with the times for each step of a five‑step fetch/execute pipeline.

1. a) If pipelining is not supported, how many cycles does it take to process one instruction?
2. b) If pipelining is supported and the pipeline is kept full, how often is an instruction completed?
3. c) If there are two parallel copies of the execution step and the pipeline is kept full, how often is an instruction completed?

II. Stack machines

The slides discuss three types of machine architecture, accumulator, GPR and stack machines.

In an accumulator machine, the result of an operation is always in the accumulator. There can be at most one other operand, expressing the value that we are going to add to (or subtract from, etc.) the accumulator. MARIE is an accumulator machine.

The IBM mainframe is a GPR machine, so you have already studied those too. It is a memory-memory machine since it allows memory-memory instructions, namely the SS and SI instructions. If we eliminated those instructions, we would have a register-memory machine. If we also eliminated all the RX and RS instructions except for load and store instructions, we would have a load-store machine.

So the only type of architecture we have not studied is the stack architecture. In this problem we will write some code for an imaginary stack machine. Here are the instructions:

PUSH X          push contents of memory address X on stack

STORE X        store contents of top of stack in m(X) (does not pop stack)

POP                 pop stack

ADD                add contents of top two stack cells, pop them, push result on stack

MULT             multiply (details same as ADD)

SUB                subtract (details same as ADD)

DIV                 divide (details same as ADD)

For all of the arithmetic operations, the operator on top of the stack (i.e., the one that was pushed second) is the second operand of the expression.

After you store the final result, make sure to pop the stack. (Otherwise the stack will continue to grow and grow as your program runs.)

Start by studing the example on slide 5c‑15. (You may find the slides before and after helpful also.)

6. Consider these two programs:

PUSH X                                                          PUSH Y

PUSH Y                                                          PUSH X

DIV                                                                 DIV

STORE Z                                                        STORE W

POP                                                                 POP

1. a) Write an equation for Z in reverse Polish.
2. b) Write an equation for Z in conventional (infix) notation.
3. c) Write an equation for W in reverse Polish.
4. d) Write an equation for W in conventional (infix) notation.
5. e) Does Z = W? Why or why not?
6. Convert each of the following to postfix notation.
7. a) A + B + C + D e., ((A + B) + C) + D
8. b) A + (B + C + D) e., A + ((B + C) + D)
9. c) A + (B + (C + D))
10. Now write code for each of the expressions below. Remember that they are written in standard mathematical notation, i.e. multiplication and division precede addition and subtraction.

Note that you will have to convert the expressions to postfix (reverse Polish) notation first.

Do not reorder the calculations. If the problem asks for A + B, do not use the commutative law to replace that with B + A. Remember that A + B + C means (A + B) + C, not A + (B + C). There are two reasons you should evaluate the expressions as written. First, you are trying to emulate the compiler. Second, although these pairs of expressions are equal for the small integers we are practicing with, that is not necessarily true for complex floating point calculations.

1. a) X = A + B/C
2. b) Y = (A + B)/C
3. c) Do parts a) and b) calculate the same value, i.e., does X = Y? Why or why not?
4. d) X = (A + B) * (C – D)
5. e) X = A * (B + C / D)