CS152 Computer Architecture and Engineering

Lab 1 is due Tuesday, September 5th.  Your lab report must be submitted by 11:59 PM on Tuesday night, using the submit program. To submit the Lab 1 final report:

1. Log into the Windows Terminal Server iserver2.eecs.berkeley.edu, using RDC (see Resources page) or via other means.
2. Once logged into iserver2, copy the file m:\bin\submit-fall2006.exe to your desktop (which is on the C: drive).
3. Execute the copied file on your desktop and follow the instructions.

This lab is to be done individually. Get started early! Also, remember to put your name on the lab report! The required format for lab reports is shown on the handouts page.

What happens if I miss the Lab 1 submission deadline? Assume we grade your lab report and its numerical score is X. If you miss the Tuesday night deadline, the Lab 1 score we will use in calculating your CS 152 final grade will be 0.8*X. If the Lab 1 report has still not been submitted by 11:59 PM Weds Sept 6th, the score we will use for your final grade calculation will be 0.4*X. If the Lab 1 report has still not been submitted by 11:59 PM Thursday Sept 7th, the score we will use for your final grade calculation will be 0.

The software for this assignment is located in m:\bin and m:\lab1. The broken version of spim is called spim_broken. The good version is called spim.

Problem 1: Introduction to SPIM

This problem will give you a chance to get familiar with the MIPS instruction set, SPIM (a MIPS simulator) and the MIPS calling convention. You will learn SPIM's basic functionalities by simulating a MIPS assembly program at calculates the factorial of 5. You should read Chapter 2 and Appendix A (on the CD ROM) of P&H to prepare for this assignment. An on-line manual for SPIM can be found on the resources web-page.

Copy m:\lab1\fact.s to your home directory for this assignment. This program uses recursion to evaluate the factorial of 5 (f(N) = N * f (N - 1), f (0) = 1). Type spim (or m:\bin\spim) to start the windows version of the SPIM program. Load the assembly program fact.s by pressing the open button, typing the file name in the dialogue box, and clicking on 'open'. Observe that the instructions for your main program now appear in the Text Segments pane (Hint: you can go to the "Windows" drop down menu to select which pane you want to display). You are using the default mode of SPIM which supports the extended instruction set and has no delayed jumps or delayed loads.

Copy the questions below into your lab report, and follow each question with your answer to it.

1a) The program does not look exactly the same as in the fact.s file, because the some of the instructions are macros and SPIM translates them to bare machine instructions (the original codes are displayed as comments). For example, consider the pseudoinstructions "li" and "la" that appear in the program. What do the instructions "li" and "la" mean? How are "li" and "la" translated to bare machine instructions?

1b) What is the starting address of the 'main' routine of 'fact'? Single-step the code from start until it reaches the first instruction of 'main'. Note that R31 has been modified. Which is the instruction that modified R31? What is the purpose of having this instruction modify R31 in this way?

1c) Set a breakpoint at the first instruction of the 'fact' routine. Continue tracing through the program execution by using single-stepping and breakpoints. What are the registers sp and fp used for? What are the values on the stack when the first instruction of the fact procedure is about to be executed for the fourth time?

1d) Now it is time to switch from the virtual machine to the bare hardware. To run the bare machine, check the "bare machine" option in "Simulator->Settings". Then restart spim. This turns off the assembly language translations and imposes delayed jumps and branches.

Convert fact.s to use only the bare machine by translating the non-native instructions and by inserting NOPs after the jumps, branches, and loads. You will need to convert the call in main to fact back into a simple JAL. You might also need to take special actions to start executing the 'main' of 'fact'. Turn in this version along with program output that shows how it works.

(Note that this version of SPIM does not implement delayed loads, and so not adding NOPs before loads will not produce incorrect results; however, some of your labs will use delayed loads, and so we included it in this exercise)

If you are working on the sections of Problem 1 out of order, be sure to turn off "bare machine" mode after completing this section.

Problem 2: Writing diagnostic programs

Here is a list of things you should check for:

1. Register zero always has the value zero.
2. All the branch and jump instructions should jump to the right address under the right condition.
3. All the branch and jump instructions with link should put the correct return address into the right register.
4. SLT(I) and STLU(I) must work properly with bit patterns representing negative two's complement integers or large natural numbers.
5. All the arithmetic and logical instructions with immediate field should extend it properly.
6. Make sure a load that follows a store to the same address reads the appropriate data.
7. Jump and branch instruction should have a delay slot.
8. Overflow should be detected correctly in arithmetic and logical instructions.
9. Shifting instructions work correctly and extend the MSB appropriately.

You should make sure that the fundamental things work before you test some other things that depend on them. Once you have verified that simple compares and branches work, you can build longer programs with a sequence of tests. After each test, you can use a compare followed by a branch to either go to the next test, or to a "failure label" which will put in an identifier for the failed test in a register. As long as there are no failures, it will sequence through all the tests. You can easily look at the "failure register" at the end of execution to determine which (if any) of the tests failed. Your test code should look something like the following:

test case a
beq caseA_result, expected_Result, go_to_caseB
jump to failure A

caseB:
test case b
...
...

failure A:
addiu $t0, $0, 1
j endOfTest

failure B:
addiu $t0, $0, 2
j endOfTest

...
...
endOfTest:

Writing diagnostic programs can deepen your understanding of the instruction sets. The main purpose of this assignment, however, is not only to learn MIPS and understand the diagnostic process, but to teach you how to create programs that can be used to validate your design later in the semester. Since the final project only requires you to implement only a subset of the MIPS instruction set, the diagnostic programs in this assignment will only be useful later in the semester if they are written using this limited set of instructions. Hence, you must write the diagnostics using only the MIPS instructions below:

arithmetic: addu, subu, addiu
logical: and, or, xor, andi, ori, xori, lui
shift: sll, sra, srl
compare: slt, slti, sltu, sltiu
control: beq, bne, j, jr, jal
data transfer: lw, sw

Helpful Hints

The 5 bugs were introduced by modifying a simulator, not by modifying hardware. Thus, do not think in terms of "I think one shift opcode has a bug, and therefore the other shift opcodes must have a bug too". Instead, you should think in terms of hunting for 5 independent bugs.

From our experience in previous years, some of you will find 6 or 7 opcodes with bugs, and you will feel certain that all of these bugs exist. In actuality, what is happening is that one of the instructions you think is correct is in fact buggy, and that bug is deceiving you into thinking that correct instructions are buggy.

Problem 2: What to Turn In

For Problem 2, turn in all of your diagnostic programs. Describe the testing methodology that motivated the program suite. Tell us how your programs systematically test the processor, and explain why these tests were able to find the bugs you found.

Also, turn in a description of the specific errors that you found, and note which test program excited each error.

Point out the machine language instruction sequences in your diagnostic suite that tests each of the "things you should check for" listed earlier in this section. Points will be taken off if you did not test for all of these items, even if you found all of the bugs! We want to see that you can design systematic tests for an ISA.

In previous semesters, many students did poorly in this lab because they missed several of the 5 bugs due to lack of testing. In particular, students ignored the list of "things you should check for", and just wrote tests for whatever ideas came to mind. Don't repeat their mistakes!