The Third Laboratory ("Lab 3")

Setup

The start-up script has created the directory smd137/lab3 and placed the files "mips_pipe.xml" and "mips_pipe_extended.xml" there. The mips_pipe.xml defines a simple pipelined MIPS architecture, while the mips_pipe_extended.xml further adds exception/interrupt handling in the coprocessor 0 (CP0). You should copy the file lab1.s to this directory

	cd smd137/lab3
	cp ../lab1/lab1.s ./lab3.s
and modify your code to run on the pipelined mips (mips_pipe.xml). Compile using:
	sde-as -mcpu=r3k -O0 lab3.s -o test.o
	sde-ld -T linker_script test.o -o a.out
	sde-objdump -h -z -s -d -t a.out > mips_pipe_program.objdump
	rm a.out test.o
or simply by using make:
	make pipe

When exposing your code to interrupts (using mips_pipe_extended.xml) you should compile your modified code (lab3.s) together with the files "init.s" and "int_handler.s" that have been placed in this directory by the start-up script.

	sde-as -mcpu=r3k -O0 init.s lab3.s int_handler.s -o test.o
	sde-ld -T linker_script test.o -o a.out
	sde-objdump -h -z -s -d -t a.out > mips_pipe_extended_program.objdump
	rm a.out test.o
or
	make pipe_ext
Group specific information which you will need later is found under lab3underlag.

General information on lab 3.

You will turn in three parts: The first part,
       DT_LABNUMMER     3
       DT_LABDEL        1
will be MIPS assembler code based on the file you submitted for Lab One, Part One. We will take your source code, and load it into the SyncSim simulator in "Mips Pipe Extended" mode (mips_pipe_extended.xml), and watch it run. The second part,
       DT_LABNUMMER     3
       DT_LABDEL        2
will be based on the group-specific underlag part A in which you will answer some questions and provide some summary information, to be described later. The third part,
       DT_LABNUMMER     3
       DT_LABDEL        3
is your "Mips Pipe" code, based on group-specific underlag part B. You MAY use MIPS pseudo-ops in Part Three.
You will submit your lab by electronic mail as usual, the details are found here.

What the Lab is About.

This lab is mainly about arithmetic. But before we get into that, there are a few other "side" things that we take care of here too. The first two parts of the lab are warm-up, easy stuff, before getting to the last part, which take us all the way into floating-point arithmetic.

One of the "side" issues of the lab is to demonstrate that there is a trade-off and interaction between hardware and software when one wants to make a hardware/software codesign run faster. In this case we consider a pipelined the MIPS model. Our pipelined variant is called "mips_pipe.xml". It is not exactly like the one discussed in the book. In fact the SyncSim "Mips Pipe" model is much closer to the true MIPS processor. Your job is to understand this new model, how and why it works, and what changes become visible to the programmer. In particular are the problems of delayed branch, and delayed memory loads. In this lab you will see "delay slots". You must understand (by studying the executing SyncSim model) why these occur. Then, you must alter your code from Lab One to run in the Mips Pipe model, in such a way that you avoid "wasting" the delay slots. This involves moving your instructions around, possibly changing their order, and adding "nop" instructions as a last resort. You will have to understand which reorderings are safe, and which are not. Obviously the compiler has to know how to cooperate with the hardware. In this lab, you are making the reordering instead of the compiler.

The second "side" thing will be to take the very first steps toward working with interrupts and exceptions. For this you should use the "Mips Pipe Extended" model (mips_pipe_extended.xml) that have a CoProcessor (used to handle interrupts), MMU (Memory Management Unit), IO (Input/Output) and Timer (generates timer interrupts). You will modify your Lab One program and compile it together with a init program and a small "interrupt handler", and you will run your program at the same time that interrupts are being allowed to "hit" at unpredictable times. If you have written your program properly, it will not be affected by these "hits." But if you have been sloppy working with the stack for example, you may find that your program no longer works, or fails at random times. Now you have to go back and try to make your code robust for working in an interrupt environment.

Computer Integer Arithmetic.

We begin with basic integer arithmetic for the unsigned, and two's-complement signed integer systems. Year after year we have observed that our students do not really understand the differences between (for example) the SLT and SLTU instructions, nor the difference between the ADD and ADDU instructions, nor the difference between "overflow" and "carry", nor how (in general) to detect integer arithmetic errors for: signed addition, signed subtraction, unsigned addition, and unsigned subtraction; nor if we were to give you a three-bit word length, that you couldn't write down which bit pattern corresponds to which integer in both the unsigned and two's-complement signed systems; and many many other such things. Part Two of this lab (part of the "warm-up") includes a few simple exercises in integer addition, subtraction, and comparison. It also includes an exercise in writing a little piece of code that will teach you quite a lot about comparing signed integers. You must debug that code in SyncSim (mips.xml) before including it with the rest of your Part Two submission.

Floating Point Package.

In group-specific underlag part B you will begin to code a sequence of subroutines. Use the following precoded rutines; lab3_code.txt. Each subroutine involves some new arithmetic method. You will learn the relationship between multiplying, division and shifting; you will write subroutines to perform fixed-point fraction multiplication and division, and gain insight into how this could more efficiently be implemented in hardware. You will then begin to work with such fixed-point fractions: adding, subtracting, multiplying and dividing them. You will see the sign-and-magnitude method of representing signed quantities. Then, the excess-code method of representing integers. Finally, all these subroutines are combined to form a full floating-point package for addition, subtraction, multiplication and division of floating-point numbers represented in an almost-standard floating-point representation. You will turn in your code as Part Three.

How to Begin, for the First Two Parts:

To do this lab, the members of your (present) group MUST (both) HAVE COMPLETED LAB ONE SUCCESSFULLY. This applies even if you were not in the same group when you did Lab One.
LAB THREE WILL BE RETURNED AUTOMATICALLY IF THE MEMBER(S) OF THE PRESENT GROUP STILL HAVE A PENDING LAB ONE.
Use your code for Lab One as the starting point. If you have joined a (different) group since then, then use the code which was turned in having the same "group number" as the one you have now.

You may not use any pseudo-instructions in your Lab Three program, that is, in your modified-for-pipeline Lab One program. That means you will have to expand all your Lab One pseudo-instructions out. First test that your program still works properly under mips.xml. Make sure that you correclty treat "seed" as a global variable before continuing! Note how many cycles your program now takes to finish under mips.xml. (Think about it, did the number of cycles change to Lab One, if so, why?)

Now, first of all in order to run in pipelined mode you should add some code to the main function from your Lab One so that it looks like this:

	.text
	.set noreorder
main:   li	$s0, ...

...	bal	   decode	# outer call to recursive "decode"
	nop
end:    b       end             # infinite loop; plaintext now in "plain".
	nop
It is only the bold text that should be added.

Now compile your Lab Three program for mips_pipe.xml.

Now try to execute the program in "Mips Pipe" (mips_pipe.xml), and compare the results against those of the "No Pipe" (mips.xml) execution. Does the unmodified program work? Does it reach the infinite loop in the end of the main function? How many characters are successfully decrypted? Try to locate where things first "go wrong".

Now modify your program to run under "Mips Pipe" (don't worry about interrupts yet, we will do that afterwards, below...) The changes MUST BE small, "local" transformations, not a big sweeping rewrite! There are only two special types of instructions that cause "trouble." The "name of the game" is to AVOID USING "NOP" instructions (or any other instruction that does no useful work). Instead, "reschedule" (re-order) your instructions a little bit, wherever possible, to make best use of the pipeline.

Once it looks like you've got it working for "Mips Pipe", and without pseudo-instructions, then run your program under "Mips Pipe" and record the number of cycles it takes to complete (put a breakpoint at the infinite loop in the main function), it must properly decode your string.

Exposing your Code to Interrupts

Now recompile the code for "mips_pipe_extended.xml". Take this new modified program, and load it into SyncSim "Mips Pipe Extended" (mips_pipe_extended.xml). Put a breakpoint in the interrupt routine in the code view. Press "Play" and your program should break at the interrupt routine (for each timer interrupt, approaximately every 1000 cycles). If your code does not work, check your stack management. (How many cycles did your program take to finish?....)

Open a New Input Window by right-clicking the IO component. Now, while your program is free-running, click in the input window with the mouse and strike a key on the keyboard which will print the key in the input window if it can be represented. If your program is working correctly, nothing strange should happen, i.e it should branch to the interrupt routine and stop at your breakpoint, when you press play it should finish the interrupt routine, jump back to your program and continue executing. Keep testing keystrikes like this for about a minute.

Now reset the program and set a breakpoint in the infinite loop in the main function. Start the program and try to run the keystrike interrupt test on it. When your program reaches the breakpoint, record how many cycles were required total. You should also verify that your program has decoded its string properly. Your program still has to work correctly !

Submitting Parts One and Two:

Part One must be your MIPS assembler code file from Lab One, complete with comments and pseudocode, modified so that it contains the changes described above and so that it contains NO pseudo-instructions in your code, and so that it can run correctly in SyncSim "Mips Pipe Extended" mode. It has to work, even under the interrupt test.

Part Two is the group-specific underlag, part A file for your group, which you have modified according to the instructions found there, answering all questions please.

How to Begin, Part Three:

Review the course text on floating point arithmetic. Then get a copy of your group-specific underlag part B, and start to code the subroutines in the order shown. Use the subroutine calling convention that you learned in Lab One. The subroutines must have the exact names as shown. We have coded all rountines except four. We may have taken certain "liberties" in the code which we wrote. But YOU must follow the standard calling conventions.

What you are coding is called a software floating point package, that is, software which implements basic floating-point operations. Once you can perform the basic arithmetic operations, then it is possible to build other subroutines which call them, to perform other complex floating-point calculations. For eample, we have provided you with a primitive routine which can take the natural logarithm of small positive floating-point values.

You should debug each subroutine carefully before moving to the next subroutine. When all are complete, you should then execute the main program which is provided in the underlag. It will test floating addition, subtraction, multiplication and division, in that order, and repeat that sequence a total of five times. After this it will call the logarithm subroutine once. To execute your program,

When it stops, the first entries in the data memory display will show your results. For readability we present the example below in four columns. From left to right these are: first operand ("A"), second operand ("B"), the "correct" result (computed in C on a Sun workstation with hardware floating-point) and the fourth column is the value that you computed. You should compare the third and fourth columns, they should be almost identical (allowing for small errors). For example, here are some of my results. They took about 41000 cycles total to compute the whole thing:
00 +  5.19644e-11  1.24881e-11  6.44525e-11  6.44525e-11
10 -  0.026717674  0.000641741  0.026075933  0.026075933
20 *  2.410685e13  2118202496.  5.106319e22  5.106319e22
30 /  3.90302e-15  0.002211778  1.76465e-12  1.76465e-12
40 +  0.000676339  1.73150146   1.732177854  1.732177734 **
50 -  3.12215e-12  8.61221e-09  -8.6091e-09  -8.6091e-09
60 *  1.29128e10   0.00065208   8420175.     8420175.
70 /  1.37244e-14  1.07808e-13  0.127304226  0.127304211 **
80 +  3.298334e13  5.594143e10  3.303928e13  3.303928e13
90 -  7.21709919   102.1479416  -94.9308395  -94.9308395
A0 *  0.029066296  1.667559e27  4.846976e25  4.846976e25
B0 /  0.026228737  4.73909e-09  5534551.5    5534550.5   **
Not too bad. The first six significant digits are the same.

How We Will Grade Part Three:

We will take your Lab Three Part Three, and then

Do NOT erase your lab after you turn it in !

Last modified 2005-11-24 by pln