Description
Learning Objectives
Here are the learning objectives of this assignment, which will be examined in this week’s quiz.
They are a subset of the unit learning objectives listed on Slide 2 of Unit 1b.
After completing this assignment you should be able to:
1. identify and describe the basic components of a machine instruction;
2. outline the steps a RISC machine performs to do arithmetic on numbers stored in memory;
3. distinguish static and dynamic computation for access to global scalars and arrays in C;
and
4. translate between C and assembly language for access to global scalars and arrays.
Goal
With this assignment we begin exploring assembly language, its connection to C and to the
processor that implements it.
You’ll begin by examining the Java/C/assembly code snippets we discuss in class this week.
They show the allocation of and access to a global int and a global array of int’s. Then, using
this assembly code as a template, you’ll write a couple of very small bits of assembly code. In
each case, you’ll execute this code in the reference-implementation version of the simulator (i.e.,
the solution) and examine carefully how its execution affects the register file and main memory.
Then, you will dig into the implementation of the processor. You will implement a significant
subset of the SM213 ISA we are developing in class: the memory-access and arithmetic
instructions that are listed below. You will test your implementation using the test program
provided with the assignment.
By implementing these instructions in the simulator you will see what is required to build them in
hardware and you will deepen your understanding of what a global variable is, what memory is,
and what role the compiler and hardware play in implementing them.
A key thing to think about while doing this is: “what does the compiler know about these
variables?” and so what can the compiler hard-code in the machine code it generates. For global
variables, recall that the compiler knows their address. And so the address of a global variable is
hard-coded in the instructions that access it. But, the compiler does not know the address of a
dynamic array and so, even though it knows the address of the variable that stores the array
reference, it must generate code to read the array’s address from memory when the program runs.
Examine and Write Assembly
The SM213 distribution you downloaded for Assignment 1 contains the reference implementation
(i.e., solution) of the machine simulator you will build over the next few assignments. You can
execute this version by double-clicking on the file SimpleMachine213.jar on your
machine, or from the command line by typing:
java -jar SimpleMachine213.jar
The file www.students.cs.ubc.ca/~cs-213/cur/assignments/a2/code.zip contains two code
snippets: S1-global-static and S2-global-dyn-array discussed in class. Your first
task is to examine these files (there are C, Java and sm213-assembly versions of each of them)
and to run the assembly versions in the simulator.
To run them, click “Show Animations” to turn animation on and then click “Run Slowly” to
begin the execution. The line for the next instruction to execute is coloured green. When an
instruction reads a register or memory location it turns blue and when it writes one of these it
turns red. You can pause the animation by clicking “Pause” and you and restart it at any
instruction by double clicking on that instruction’s address. More details on how to use the
simulator are provided below on the “Some tips for using the Simulator” Section.
Note that if you are starting this assignment early, you might want to do just the first snippet now,
and save the other one until Wednesday. You can proceed to the first question without examining
this second snippet.
Questions 1–3: Write Assembly [50% of the total marks]
1. [15%] Using S1-global-static.s as a guide, implement the following C program in
assembly and place the code in a file named swap.s. Note: just as in the snippet, ignore
the procedure declaration (we will come to this later in the course). Your program should
thus just do two things: (1) allocate the global variables and (2) swap the two array
elements. If you’d like, you can avoid using memory for the variable t by just using a
register in place of the variable. Load your program into the simulator. Assign different
values to the two elements of array and run the program to confirm that it works.
int t;
int array[2];
void swap() {
t = array[0];
array[0] = array[1];
array[1] = t;
}
2. [15%] Now let’s bring in the math instructions. You’ll find a complete list of the ISA in
the Companion and below (for the math and memory instructions). Implement the
following C program in assembly, using your previous work as a guide. Place your code
in a file named math.s. Again, skip the procedure itself; just show the code inside of the
procedure. Write, run, and test your program. Note: both a and b must be global variables
in memory and the variable a must store the correct value when the execution completes;
that’s what we’ll check to determine if your code works.
int a, b;
void math() {
a = ((((b + 1) + 4) / 2) & b) << 2; } 3. [20%] Finally, let’s put it all together. Implement the following C program in assembly, again using your previous work as a guide. Place your code in a file named calc.s. Again, skip the procedure itself; just show the code inside of the procedure. Write, run, and test your program. Note: data, i, x, and y must all be global variables. int data[4]; int i, x, y; void calc() { y = data[i] + data[i+1]; x = y & 0xff; } Some tips for using the Simulator You’ll get help using the simulator in the labs, but here are a few quick things that you will find helpful. 1. You can edit instructions and data values directly in the simulator (including adding new lines or deleting them). 2. The simulator allows you to place “labels” on code and data lines. This label can then be used as a substitute for the address of those lines. For example, the variable’s a and b are at addresses 0x1000 and 0x2000 respectively, but can just be referred to using the labels a and b. Keep in mind, however, that this is just a simulator/assembly-code trick, the machine instructions still have the address hardcoded in them. You can see the machine code of each instruction to the left of the instructions in the memory image portion of the instruction pane. 3. You can change the program counter (i.e., pc) value by double-clicking on an instruction. And so, if you want to execute a particular instruction, double click it and then press the “Step” button. The instruction pointed to by the pc is coloured green. 4. Memory locations and registers read by the execution of an instruction are coloured blue and those written are coloured red. With each step of the machine the colours from previous steps fade so that you can see locations read/written by the past few instructions while distinguishing the cycle in which they were accessed. 5. Instruction execution can be animated by clicking on the “Show Animation” button and then single stepping or running slowing. Implement SM213 Memory and Math Instructions The file www.students.cs.ubc.ca/~cs-213/cur/assignments/a2/code.zip contains the files Memory.java and CPU.java. The first is a complete implementation of the sm213 machine’s main memory; i.e., the solution to Assignment 1. You can use this file or your version from Assignment 1. The second is the starting point for the CPU implementation. It contains the implementation of some instructions and leaves to you the implementation of others. Copy these files into your IntelliJ environment to replace CPU.java and Memory.java that are there now in the arch.sm213.machine.student package. Here is a description of the memory and math instructions for your convenience. These instructions are described in more detail, including examples, in the 213 Companion. Memory-Access Instructions (and load immediate) ALU Instructions Instruction Assembly Format Semantics load immediate ld $v, rd 0d– vvvvvvvv r[d] ← v load base + offset ld o(rs), rd 1psd r[d] ← m[o=p*4+r[s]] load indexed ld (rs,ri,4), rd 2sid r[d] ← m[r[s]+r[i]*4] store base + offset st rs, o(rd) 3spd m[o=p*4+r[d]] ← r[s] store indexed st rs, (rd,ri,4) 4sdi m[r[d]+r[i]*4] ← r[s] Instruction Assembly Format Semantics rr move mov rs, rd 60sd r[d] ← r[s] add add rs, rd 61sd r[d] ← r[d] + r[s] and and rs, rd 62sd r[d] ← r[d] & r[s] inc inc rd 63-d r[d] ← r[d] + 1 inc addr inca rd 64-d r[d] ← r[d] + 4 dec dec rd 65-d r[d] ← r[d] – 1 dec addr deca rd 66-d r[d] ← r[d] – 4 not not rd 67-d r[d] ← ~r[d] Question 4: Implement and Test the Remaining Instructions [50%] Modify the execute() method in CPU.java to replace every “TODO” flag with the appropriate code. Each step of the processor (i.e,. cycle) has two stages: fetch and execute. The first stage fetches the next instruction from memory and loads it into the special-purpose register named ins. The second stage executes the instruction. For convenience the fetch stage places the various parts of the instruction into the following special-purpose registers insOpCode, insOp0, insOp1, insOpImm, and insOpExt and the execute stage uses these values plus the general-purpose register file, reg, and main memory, mem, to perform the instruction’s specified computation. To test your implementation of an instruction you need to execute some code in the simulator that uses that instruction and then manually examine the register and/or memory contents to ensure that it worked. You can set breakpoints in the Java to examine Java variables. You can use the lower left panel of the simulator to see the value of the CPU’s special-purpose registers. And you can set breakpoints in the assembly by clicking the little box next to an instruction, turning it red. The provided code includes a file named test.s that you can use to test the instructions you implement. Each test starts with a label that identifies the instruction it tests and ends with a halt instruction that stops the simulation. To test an instruction, click on its label in the simulator and then click “Run” or “Step”. We recommend that you implement one instruction at a time and test each one before moving on. You will likely find that implementing and debugging the first instruction is the hardest. Once you have one working, you will see that adding others will follow a pattern. Use the instructions that are already implemented as your guide. What to Hand In Use the handin program to hand in the following in a directory named a2. Please do not hand in anything that isn’t listed below. In particular, do not hand in your entire IntelliJ workspace nor the entire source tree for the simulator and do not hand in any class files. 1. swap.s – that contains your code for Question 1. 2. math.s – that contains your code for Question 2. shift shl $v, rd shr $v, rd 7dss (ss > 0)
7dss (ss < 0) r[d] ← r[d] << v=ss r[d] ← r[d] >> v=-ss
halt halt f000 throw halt exception
nop nop ff00 do nothing (nop)
Instruction Assembly Format Semantics
3. calc.s – that contains your code for Question 3.
4. CPU.java – that contains your implementation for Question 3. Be sure you don’t turn in
the .class file.
OPTIONAL – Testing Using the Command Line
The simulator has a command-line (i.e., non-GUI) interface. This would allow you, for example,
to build a test script to automate regression testing.
To invoke the command-line version of the simulator you need to locate three items in your file
system: your implementations of MainMemory.class and CPU.class and
SimpleMachineStudent213.jar that you downloaded for this assignment (or Assignment
1). Lets say that all three are in the same directory and you have “cd”ed into that directory (i.e.,
if you type ls you see these three files) and thus the directory is called “.”. To invoke the
command-line simulator you type:
java -cp .:SimpleMachineStudent213jar SimpleMachine -i cli -a sm213 -v student
Then type help to see a list of commands. Note that register names are distinguished from label
names by adding a percent sign to the register name; e.g., %r0 is the name for register 0.
To run test the load instruction you might type the following (what you type is in bold):
% java -cp .:SimpleMachineStudent213jar SimpleMachine -i cli
-a sm213 -v student
Simple Machine (SM213-Student)
(sm) l test.s
(sm) %r0=0
(sm) %r7=0
(sm) s
(sm) s
(sm) i reg
%r0: 0x11223344 287454020
%r1: 0x0 0
%r2: 0x0 0
%r3: 0x0 0
%r4: 0x0 0
%r5: 0x0 0
%r6: 0x0 0
%r7: 0x11223344 287454020
If you want to run it again, or when you have several tests and you want to go to a specific one,
you can use the goto command with the label associated with the first instruction of that test.
And, if you place a halt instruction after each test, you can use the run command instead of
stepping. For example, in this case:
(sm) g ldi
(sm) r
Note that if you step past the end of the the loaded file you will get an address out of bounds
exception.
Note also that if you want to run the reference implementation from the command line you leave
off the “-a” and “-v” command line flags and type the following instead.
java -jar SimpleMachine213.jar -i cli
You can use the assert command to streamline the testing to look something like this.
% java -cp .:SimpleMachineStudent213jar SimpleMachine -i cli
-a sm213 -v student
Simple Machine (SM213-Student)
(sm) l test.s
(sm) %r0=0
(sm) %r7=0
(sm) g ldi
(sm) r
(sm) a “ld imm”
(sm) a %r0==0x11223344
(sm) a %r1==0
(sm) a %r7==0x11223344
If an assertion succeeds, then it prints nothing. If it fails it prints something like this:
XXX ASSERTION FAILURE (ld imm): %r0 == 0x11223344 != 0x0
You could use this approach to run the entire test in a script and then scan its output for lines that
indicate an assertion failure.
The script is simply a file that contains the commands to execute in sequence, for example, the
file named test-script might look like this:
l test.s
%r0=0
%r1=0
g ldi
r
a “ld imm”
a %r0==0x11223344
a %r1==0
a %r2==0x11223344
You can then use the unix shell “<“ operator to run the simulator with this as input.
java -cp… -v student < test-script
And you can then process the output to look for assertion failures by using a similar trick to pipe
the output to a unix command called grep using the “|” operator like this.
java -cp… -v student < test-script | grep XXX
The resulting output is a list of the tests that failed.
All of this is entirely optional and it will take some work to setup, so don’t worry about trying this
if you aren’t up for the challenge. We’ll help you if you do want to try. The advantage of
investing time on the setup is that testing will run a bit more smoothly for you.
