Assignment 3 CS 365 Spring 2002

GEORGE MASON UNIVERSITY

Computer Science Department

CS 365 - Computer Architecture Spring 2002

Assignment 3 (Instruction Set Design or RISC vs CISC)

DUE DATE - March 6

The goal of this project is to give you an idea about the tradeoffs involved in instruction set design.

Exercise 1 (30 pts)

In this exercise you have to obtain the CPI for the program sort.s from Assignment 2. The first step is to obtain a count of how often each instruction in this program is executed. (Remember, this requires you to use the profiling technique discussed in class; brute force counting is not allowed) Then, based on your analysis, complete the table shown below:

Instruction category	MIPS examples	CPI	Instruction Count
Arithmetic 1	Add,sub,addi	1.0
Arithmetic 2	mult, multu	5.0
Arithmetic 3	div, divu	7.0
Data Transfer	lw, sw, lui	2.0
Conditional Branch	beq, bne, slt, slti	1.5
Jump	j, jr, jal	1.2
Others	syscall, mflo, mfhi	1.0

Based on the CPI and the frequencies for each category in the table above compute the CPI for the program sort.s. (The correct counts for the Table above are available on the class web page. Please compare your answers to the answers on the web site to see if you have done this exercise correctly.)

Exercise 2 (30 pts)

Suppose that someone suggested to you that it would be a good idea to have a SWAP instruction. The idea is that a SWAP instruction would replace some of the work that is done in the swap procedure in the program sort.s.

So the sequence of instructions similar to:

        lw      $15,0($2)

        lw      $16,4($2)

        sw      $16,0($2)

        sw      $15,4($2)

would be replaced by

        swap   0($2), 4($2)

Assume that the new instruction swap has a CPI of 3 but that the introduction of this instruction causes the CPU cycle time to increase by 20%. First of all, complete the table below for the program sort.s in which the new instruction is used in place of the sequence of instructions shown above:

Instruction category	MIPS examples	CPI	Instruction Count
Arithmetic 1	add,sub,addi	1.0
Arithmetic 2	mult, multu	5.0
Arithmetic 3	div, divu	7.0
Data Transfer 1	lw, sw, lui	2.0
Data Transfer 2	Swap	3.0
Conditional Branch	beq, bne, slt, slti	1.5
Jump	j, jr, jal	1.2
Others	syscall, mflo, mfhi	1.0

Find the CPI for the new program based on the table above. What is the difference in the execution time of the old version of sort.s and the new version of sort.s? Remember you have to use cycle time, instruction count, and CPI in this calculation.

Based on the calculations above, is it a good idea to introduce this new instruction? Explain your answer.

NOTES:

You have to submit:

1. A listing of the program sort.s showing the basic blocks in the program.

2. The modified program sort.s with the code for counting and printing the number of basic blocks.

3. The output generated by your modified program.

4. The tables you have to complete for Exercises 1 and 2 above.

5. Your calculations for CPI and execution time using these tables.

6. The answers to any questions in the writeup for exercises 1 and 2.

Exercise 3 (40 pts)

Repeat the steps above (i.e. Exercise 1 and 2) for the program matrix.s that you wrote for Assignment 2.