Computer Science and Engineering 477



14:332:331

Midterm Examination #2

Spring 2005

Name: __________________________________________

S.S.#: _______________________________

|1 |35 | |

|2 |25 | |

|3 |40 | |

|Total |100 | |

Instructions:

This exam contains 3 questions. It is closed book and notes. Calculators are NOT allowed. Do all of your work on the attached sheets.

Please make sure that you finish all the questions.

(35 pts) 1. Short Answer

A. (3 pt)What decimal number does this two’s complement binary number represent: 1111 1111 1111 1111 1111 1111 1110 1111

B. (4 pt) Describe the four situations in which an overflow can occur.

A. -

B. -

C. -

D. -

C. (3 pt) ALU has three output signals: result, zero, and carry out. Which output signifies whether the condition for beq is true or not?

D. (12 pt) You are asked to perform the following multipy operation 01010101 X 01111110 using (1) the normal multiply algorithm, and (2) the Booth algorithm (looking at the current bit and the previous bit at the same time). Please show your work in detail.

And explain how many add and shift operations will be needed in both cases.

Then show your work for 01010101 X 01111110 using the same two algorithms, and explain how many add and shift operations will be needed in both cases.

From these two exercises, can you comment when the Booth algorithm will do better than the normal algorithm?

E. (6pt) Please refer to the ALU figure below to fill the following table ( I have filled the first entry as an example):

|ALU control (Ainvert+Binvert+operation) |Operation |

|0000 |A and B |

|0001 | |

|0010 | |

|0100 | |

|0101 | |

|0110 | |

|1000 | |

[pic]

F. (7 pt) A 32-bit ALU is shown below. Please note that this ALU doesn’t support slt instruction. In order to support slt instruction, what should be the values for the less signals? Note that you need to specify each of the following signals: less0, less1, … less31.

(25 pts) 2. CPU Performance

A. (10 pt) A program has 3000 instructions. It has the following instruction types:

• R type (70%) which takes 6 ns to execute on a dedicated datapath

• lw (10%) which takes 8 ns to execute on a dedicated datapath

• sw (10%) which takes 5 ns to execute on a dedicated datapath

• beq (8%) which takes 7 ns to execute on a dedicated datapath

• j (2%) which takes 2 ns to execute on a dedicated datapath

If we run this program on a single-cycle datapath, what is the smallest execution time for this program?

B. (15 pt) We are interersted in two implementations of a machine, one with and one without special floating point hardware. Consider a program, P, with the following mix of operations:

Floating-point multiply 10%

Floating-point add 15%

Floating-point divide 5%

Integer instructions 70%

Machine MFP (Machine with Floating Point) has floating-point hardware and can therefore implement the floating point operations directly. It requires the following number of clock cycles for each instruction class:

Floating-point multiply 6

Floating-point add 4

Floating-point divide 20

Integer instructions 2

Machine MNFP (Machine with No Floating Point) has no floating-point hardware and so must emulate the floating point operations. The integer instructions all take 2 clock cycles. The number of integer instructions needed to implement each of the floating-point operations is as follows:

Floating-point multiply 30

Floating-point add 20

Floating-point divide 50

Both machines have a clock rate of 1000MHz. If the machine MFP needs 300 million instructions for this program, how many integer instructions does the machine MNFP requrie for the same program?

What is the execution time (in seconds) for the program to run on MFP and MNFP?

(40 pts) 3. Single Cycle Datapath Design

A. (9pt) A single stuck-at-1 fault (i.e. regardless of what it should be, the signal is always 1) can affect the instruction executions in single-cycle datapath. Which instructions, if any, will NOT work correctly?

Consider each of the following faults separately:

• RegWrite = 1

• ALUOp0 = 1

• ALUOp1 = 1

• Branch = 1

• MemRead = 1

• MemWrite = 1

• RegDest = 1

• MemtoReg = 1

• ALUSrc = 1

B. (11pt) Assuming the following delays for the components in the single cycle datapath

PC read access 1 ns

memory read access 3 ns

memory write access 4 ns

register file read 2 ns

Main control logic delay 3 ns

ALU control logic delay 2 ns

ALU delay 4 ns

Add delay 6 ns

what is the fastest clock speed (i.e., clock cycle time measured from active clock edge to next active clock edge) for the single cycle machine when executing a R type instruction (you may assume that the Sign Extend logic, Shift left 2 logic, PC writes, register file writes, register set up, register hold, mux, and wire delays are all zero)?

what is the fastest clock speed for the single cycle machine when executing a lw instruction?

what is the fastest clock speed for the single cycle machine when executing a sw instruction?

what is the fastest clock speed for the single cycle machine when executing a beq instruction?

what is the fastest clock speed for the single cycle machine when executing a j instruction?

C. (20pt) Your next task is to add the instruction lui (load upper immediate) to the single-cycle datapath. Remember that lui sets the upper 16 bits of a constant in a register.

The machine language version of lui $t0, 255 #$t0 = 8

|001111 |0000 |01000 |0000 0000 1111 1111 |

Contents of register $t0 after executing lui $t0, 255:

|0000 0000 1111 1111 |0000 0000 0000 0000 |

Add any necessary datapaths and control signals to the single-cycle datapath shown on next page. You may use additional 2-to-1 multiplexors, additional shift logic (if you need a shift logic to perform left shift n bits, just name it as “shift left n”), additional control signals, and additional interconnects. Mark a line that is no longer connected with an X somewhere along its length where the disconnect should occur.

What new control signal(s) did you need to add and explain their basic function.

Give the setting for all the control signals (both previously existing and the one(s) you added) to execute a lui

|Control Signal |lui | |Control Signal |lui |

|RegDst | | |MemWrite | |

|Jump | | |ALUSrc | |

|Branch | | |RegWrite | |

|MemRead | | | | |

|MemtoReg | | | | |

|ALUOp1 | | | | |

|ALUOp0 | | | | |

[pic]

-----------------------

Less31

less1

. . .

result31

B31

A31

+

less0

result0

B0

A0

+

result1

[pic]

+

A1

[pic]

[pic]

B1

................
................

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

Google Online Preview   Download