Department of Electrical and Computer Engineering

The University of Texas at Austin

EE 360N, Spring 2003
Problem Set 4
Due: 24 March 2003, before class
Yale N. Patt, Instructor
Hyesoon Kim, Moinuddin Qureshi, Onur Mutlu, Santhosh Srinath, TAs

Instructions:
You are encouraged to work on the problem set in groups and turn in one problem set for the entire group. Remember to put all your names on the solution sheet. Also remember to put the name of the TA in whose discussion section you would like the problem set returned to you.

1. Explain the differences between exceptions and interrupts. Be concise in your explanations.

Explain the similarities of exceptions and interrupts. Clearly describe the steps required to handle an exception or an interrupt.

2. In class, we discussed two types of busses: "pending bus" and "split transaction bus". What is the advantage of a split-transaction bus over a pending bus?

3. In class, we discussed the asynchronous finite state machine for the device controller of an input-output device within the context of a priority arbitration system. Draw the state diagram for this device controller (as drawn in lecture), identify the input and output signals, and briefly explain the function of each input and output signal.

As mentioned in class, the finite state machine has some race conditions. Identify the race conditions and show what simple modifications can be made to eliminate them.

4. A group of students have decided to build a computer system using the LC-3b. The system will have one LC-3b processor connected to physical memory and several disk units via a shared bus. The disk units have the ability to transfer data directly to and from memory via the Direct Memory Access controller.

Every time a disk unit finishes a transfer, the LC-3b is interrupted, and the disk unit is given another transfer operation. The unit of transfer between the disk and the memory is a 212 B page and the disk units are capable of maintaining a transfer rate of 218 B/s. The bus itself is the fastest technology and is able to keep up with the transfer rate of the disk units (i.e., the bus does not slow down the transfer between disk and memory).

After a few experiments, the students found that the average disk transfer consisted of 2 pages of data. The disk interrupt handler on the LC-3b was known to take 5 ms of processing time per interrupt. The goal of their experiment was to figure out how many disk units could be connected to the system and fully utilized. Help them out.

5. Given the following code:
```MUL R3, R1, R2
MUL R7, R8, R9
MUL R10, R5, R6
```
Note: Each instruction is specified with destination register first.

Calculate the number of cycles it takes to execute the given code on the following models:

1. A non-pipelined machine.
2. A pipelined machine with scoreboarding with one multiplier and one adder.
3. Tomasulo's algorithm with one multiplier and one adder.

Show the state of the reservation stations (node tables) and the register file (with the valid bits and the tags) for part (3) after 5 clock cycles. Show it after 10 clock cycles. Assume that the adder and the multiplier both have 4 entries in their associated reservation stations. Use symbolic tags for renaming as Professor Patt did in class. The structure of the reservation stations and register file (register alias table) should be the same as explained in lecture.

Note: For all machine models, use the basic instruction cycle as follows:

Fetch (one clock cycle)
Decode (one clock cycle)
Execute (MUL takes 4, ADD takes 2 clock cycles)
Write-back (one clock cycle)

Do not forget to list any assumptions you make about the pipeline structure (e.g., data forwarding between pipeline stages).