CS 341L Computer Architecture, Spring 2019

Please get started on the lab as soon as possible. In general, in this class you will have about 3 weeks from the lab release date until the due date.

You will submit your work by pushing it to your repository on LoboGit. Details about how to access your repository are found on the course webpage.

First, install some tools. You will need to do this on your class VM (or another Linux machine/VM where you sudo permissions). Details about how to access your class VM are found on the course webpage.

sudo apt-get install qemu
sudo apt-get install gcc-arm-linux-gnueabi
sudo apt-get install gcc-mips-linux-gnu
sudo apt-get install gdb-multiarch

This part of the lab is about learning the semantics of the most important MIPS instructions, by thinking about how a machine would actually execute these instructions.

The course textbook provides a very useful MIPS Cheat Sheet. You can also check out the other MIPS Assembly Reference which shows the syntax of the MIPS assembly language instructions (the order of the arguments can sometimes be a bit confusing). In this part of the lab, you will utilize the cheat sheet to build a MIPS simulator, i.e., a program that simulates the execution of a MIPS assembly-language program.

• You can use C, C++, Java, or Python for this part of the lab.
• Implement the registers by using a 32-element array of 32-bit integers.
• Implement the main memory by using a 512-element array of 32-bit integers.
• Your simulator only needs to handle the following 18 instructions: add, addi, sub, mult, mfhi, mflo, and, or, nor, sll, srl, lw, sw, slt, bne, beq, j, nop.
• Your simulator should be able to read a MIPS assembly file such as the following (note that you also need to handle an optional label on each line):

add $t0, $t1, $t2
j end
label: sub $t1, $t2, $t3
end: nop

• Note that mult (integer multiplication) can produce a 64-bit result (since it multiplies two 32-bit integers), and this result is stored in a pair of registers called Hi and Lo - the only way you can access these two registers is by using the mfhi and mflo to move their contents into a normal register.
• Note that nop is a pseudo-instruction, i.e., it is not actually implemented in a MIPS CPU. You can treat a nop instruction as a shorthand for sll $zero, $zero, $zero (an instruction that uses a single clock cycle and does not change the state of the CPU).
• We should be able to build your simulator by typing make sim.
• We should be able to run your simulator by typing ./simulator somefile.s, where somefile.s is a MIPS assembly program.
• After executing the program, your simulator should print the contents of all the registers, and then exit.
• Make sure to test your simulator by writing some basic MIPS assembly programs.

Here's a simple MIPS assembly program you can use to test your simulator. Note that your simulator should simply ignore any lines starting with # (a comment) or . (an assembler directive). Your simulator should also ignore any blank lines.

# this program computes $t1 * $t2 and places the result in $t0

.globl c_entry
c_entry: nop
# initialize registers
addi $t1, $zero, 5
addi $t2, $zero, 4
addi $t0, $zero, 0

loop: beq $t2, $zero, done
add $t0, $t0, $t1
addi $t2, $t2, -1
j loop

.globl done
done: nop

This part of the lab is about converting assembly-language instructions into machine instructions, i.e., binary numbers that are readable by the CPU.

Build a simple assembler for the above 18 instructions. In other words, your assembler will convert each instruction in a MIPS assembly language program, and encode it into a 32-bit word that can be executed on the CPU. Remember that the above cheat sheet also contains all the details you will need to do this.

• You can use C, C++, Java, or Python for this part of the lab.
• You will need to compute the address of labels. The address will be the number of bytes from the beginning of the program (remember that all addresses will be multiples of 4).
• We should be able to build your assembler by typing make asm.
• We should be able to run your assembler by typing ./assembler somefile.s, where somefile.s is a MIPS assembly program
• Your assembler should print the correct list of machine instructions (as 32-bit binary numbers, one on each line), and then exit

The following table shows the machine instruction (32-bit word) for each assembly-language instruction in the example code from Part 1 of the lab. In your code, you should assume that the first instruction is at address 0x0.

This part of the lab is about using the QEMU framework to emulate a MIPS architecture. We will also learn how to use GDB (GNU Debugger) to interact with a running MIPS assembly language program.

Save the following as simple.s

.globl c_entry
c_entry: nop
#######################################################################
## YOUR MIPS CODE SHOULD APPEAR AFTER THE FOLLOWING TWO INSTRUCTIONS ##
#######################################################################
addi $t1, $zero, 13
addi $t2, $zero, 3
##############################
j done

.globl done
done: nop
nop

Now compile using the MIPS cross-compiler, and run in QEMU:

mips-linux-gnu-gcc -g --entry c_entry -nostdlib simple.s -o simple 
qemu-mips -g 1234 ./simple &

Now, start the debugger:

gdb-multiarch simple

At the GDB prompt, type the following

target remote localhost:1234
break done

(this will connect GDB to the running MIPS program, and set a breakpoint on the done label).

GDB has a nice set of commands that allow you to execute and monitor the MIPS program. The main ones we care about are the following:

• Task A: write a simple MIPS program to compute the power of a number. You should compute the result $t1 to the $t2 power, and store the result into $t0.
• Task B: save your program as power.s, and compile it using the GCC cross-compiler as shown above, run it using QEMU, and list the final register contents (save this as power-qemu.txt).
• Task C: run the program in your simulator and list the final register contents (save this as power-sim.txt).

Writing more efficient algorithms in a high-level language such as C can have a huge effect on the performance of the program. This part of the lab investigates how algorithm design influences the size and structure of the generated assembly code.

First, add a function to your GDB installation. Create a new file in your home directory (~) with the name .gdbinit, and place the following in it:

define do_count
set pagination off
set $count=0
while ($pc != $arg0)
stepi
set $count=$count+1
end
print $count
end

This is instruction-counting functionality, courtesy of StackOverflow.

• Task A: Write a basic bubble-sort algorithm in C (sort1.c). You can hard-code an array of unsorted integers, and your C program should simply sort the numbers in ascending order, using doubly-nested for loops. Do not include any header files or use any libraries in your C program. Your program should have the following basic structure:

void done() {}

int main(int argc, char **argv) {
    int a[16];
    a[0] = 13;
    a[1] = 3;
    a[2] = 8;
    // ...
    // sort algorithm goes here
    done();
    return 0;
}

• Task B: Make a modified version of your bubble-sort C program (sort2.c) in which the inner for loop doesn't go through all of the elements. In other words, you should now have a bubble-sort implementation, and another more efficient implementation.
• Task C: Compile both C programs into MIPS assembly code:

mips-linux-gnu-gcc -nostdlib -S sort1.c -o sort1.s
mips-linux-gnu-gcc -nostdlib -S sort2.c -o sort2.s

• Task D: Similar to what you did in Part 3, compile sort1.s into a MIPS binary, and load it using QEMU.

mips-linux-gnu-gcc -g --entry main -nostdlib sort1.s -o sort1 
qemu-mips -g 1234 ./sort1 &

Now, start the debugger:

gdb-multiarch sort1

At the GDB prompt, type the following

target remote localhost:1234

(this will connect GDB to the running MIPS program). Now, we need to get the address of the done label:

x/i done

which will show you the address in hexadecimal, e.g., 0x123456. Now, using this address (say it is 0x123456), you can type

do_count 0x123456

This will run the program until it hits the done label, and will keep track of the number of executed instructions up until that point.

• Task E: Compare the number of instructions executed for sort1 versus sort2, and save this information in sort-comparison.txt.

This part of the lab is about learning how to read basic assembly-language programs. In general, being able to reverse-engineer software in this way can be a valuable skill to have.

Consider the following MIPS code, and assume that c_entry is where execution begins. Your task is to modify the code at the marked location, so that the program always reaches the "win" state (and not the "lose" state). You are not allowed to use any type of branching instructions (e.g., j win would be a trivial solution). You are only allowed to add code at the marked location. Save your modified code as win.s.

.globl c_entry
c_entry: nop
##############################################
##      ADD NON-BRANCHING CODE HERE         ##
## (YOU SHOULD NOT MAKE ANY ASSUMPTIONS     ##
##  ABOUT THE INITIAL VALUES OF REGISTERS)  ##
##############################################

addu $t2, $t3, $16
slt	$t2, $17, $t2
beq	$t2, $0, L5
nop
j L6
nop

L7: nop
addu $t3, $t3, $t3
addiu $16, $16, -1

L6: nop
slt $t4, $zero, $16
bne $t4, $zero, L7

nop
sll	$t2, $17, 1
slt	$t2, $t2, $t3
beq	$t2, $0, L8
nop
j win
nop
j L10
nop

L8: nop
j lose
nop
j L10
nop

L5: j lose
nop

L10: j done
nop

win: nop
addi $t0, $zero, 0xAB
j L10

lose: nop
addi $t0, $zero, 0xCD
j L10

.globl done
done: nop

Clearly document (using source-code comments) all of your work. Also fill in the README.md file (preferably using Markdown syntax) with a brief writeup about the design choices you made in your code.

Make sure that you have named your source code files exactly as requested in the lab assignment! (If for some reason you need to use a different naming convention, make sure to carefully explain the mapping between your source code files and the requirements in the lab assignment).

Providing adequate documentation helps us see that you understand the code you've written.

We will automatically grab a snapshot of the master branch of your Lab 1 repository at the deadline.

Make sure you push all of your work before the deadline!