CSE141 Chien Quiz #1



April 30, 1999

Instructions

The midterm exam is closed book -- no notes or books are allowed. You should solve these problems using only pencil and paper. No calculators are permitted.

You will have 50 minutes to complete the exam; the problems vary widely in both their topical area and difficulty; please arrange manage your time so that you will have an opportunity to attempt all of the questions. Show your work, so it is possible for us to give partial credit. Please draw a box around your final answers to facilitate grading.

|Part |Max Points |Points |

|I |30 | |

|II |35 | |

|III | 20 | |

|IV |30 | |

|V |35 | |

|VI |50 | |

|Total |200 | |

1. Performance (30 points)

a. Alyssa P. Hacker and Joe Hacker decide to compare computers from the Binary Computer Corporation (BCC) and the Supercomputers Incorporated (SI). To do this, they each take their a chess playing program, written in C, and compile it on their respective machines and then calculate the instruction processing rate. The BCC machine executes at twice the instruction processing rate at the SI machine, so they conclude its twice as fast. Give two reasons why this performance comparison is flawed.

Answer

← Instruction count can vary with compiler and machine

← Programs may be different

b. Consider a two computer systems A and B which implement identical instruction sets. Given the following execution times for 4 programs in our benchmark suite, give a performance summary and a precise performance statement comparing one system to the other. If necessary, you can express your answer in unreduced fractions.

System Bmark #1 Bmark #2 Bmark #3 Bmark #4

A 10 15 22 13 Total 60

B 13 10 12 10 Total 45

System B is 4/3 times faster than System A.

c. Consider a multi-cycle implementation of the MIPS instruction set in which the mix across instruction classes is as shown below:

Instruction Dynamic Frequency (by count)

R-class (arithmetic/logic) 70% 4 ----2.8

Memory (load/store) 20% 8----1.6

Branch (branch and jump) 10% 3----0.3

If R-class instructions on average take 4 cycle, memory instructions 8 cycles, and branch instructions 3 cycles, compute the CPI (cycles per instruction) for this machine.

CPI=4.7

d. Based on Amdahl's law, what is the maximum performance improvement achievable for the system described in part (c) possible by improving the performance of memory instructions?

Answer: Best performance increase means memory instruction contribution to CPI(0.

According to Amdahl’s Law

speedup=4.7/3.1=1.5 times

2. Instruction Set Design (35 points) The MIPS instruction set we have been studying has three basic instruction classes, dividing the basic arithmetic and logic operations, memory operations, and control transfer instructions. In this question, we will explore your understanding of the capabilities and limitations of that instruction set design.

a. Consider the following sequence of assembly code which loads a variable from memory, computes on it, and then stores the modified value back into the memory. First, count the number of bits spent on operation code, register specifiers and offsets (and indicate the numbers) used in the actual operations.

Lui $t0, Aupper

Addi $t0, $t0, Alower

Lw $t1, 0($t0)

Addi $t1, $t1, 23

Sw $t1, 16(4t0)

Total opcode bits Total Register Specifier Bits Total Offset/Constant bits

6*5=30 9*5=45 5*16=80

b. Some of the bits in the instructions are not used directly as operands, to specify operands, or to specify control. In this program fragment, how many such wasted bits are there?

5 bits in Lui

c. Based on the actual program example, smaller offsets could have been used for memory addressing. If this code example were really typical, how many of the offset bits could have been saved?

0,16 as offsets

max. bits saved 26 bits

max. bits saved with a fixed constant field size is 22 bits

d. Joe Hacker suggests that a good way to reduce the number of bits wasted is to use a custom instruction encoding for memory and immediate instructions with 8-bit constants. These instructions use a 24-bit format. Give two reasons why this might not be a good idea.

← Makes instruction fetch difficult

← Changes alignment of offset field within the instruction

3. Instruction Set Implementation (single cycle), (20 points) Consider the single cycle implementation of the MIPS instruction set, including both the datapath and control issues.

a. For the following instruction, indicate the multiplexor and other control signal settings to implement the following instruction on the picture on the next page:

beq $t0, $t1, target

You should indicate the multiplexor on the figure we gave, which is the one control by ALUSrc

Specify the Control Signal settings

RegDst X (doesn’t care)

ALUSrc 1

MemtoReg X (doesn’t care)

Regwrite 0

MemRead 0

MemWrite 0

Branch 1

(this control signal is describe in Fig 5.18 of the Textbook)

(In the mid-term, we let Branch be PCSrc, in this case, the setting depends on Zero ( i.e., the value of $t0 & $t1) )

b. Identify the longest path in the datapath that instruction and data signals must flow along to complete this instruction. Write down a list of the elements along that path. For simplicity in identifying the longest path, you can assume that each element in the picture (memory, ALU, multiplexor, etc.) except the wires has an equal delay of one unit.

Correct answers:

PC---instruction mem---Reg file---ALUSrc---ALU---PCSrc mux---PC

Or

PC---instruction mem---Sext---SL---ADD---PCSrc mux---PC

NOTE: this question asks about the longest path of BEQ, hence, though the following is a longer path than above, it isn’t the answer for this question

PC---instruction mem---Reg file---ALUSrc---ALU---DataMem---MemtoReg----Regfile

4. Multiple Cycle CPU (30 points) A multiple cycle implementation of a CPU breaks the execution of a single instruction into multiple clock periods. Breaking the instruction into equal size pieces is important because it enables the shortest clock period (fastest clock). In this question, we will explore the control required for a multiple cycle implementation for the MIPS instruction set.

a. Write down the execution in cycles for the R-class, memory, and Branch instructions. Indicate the number of cycles for each instruction and the actions performed at each cycle of the instruction in RTL language as shown for the R-class instruction.

R-class 1: ir ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download