Homework 4: ULNAv2-C Memory Access

This homework is due on Wednesday, April 24, at 11:59:59 PM (Eastern daylight time). You must use submit to turn in your homework like so:
submit cs411_jtang hw4 hw4_asm.S hw4.circ hw4.txt [image1...] The grader will use the supplied Makefile to compile your work. In addition, each submitted source code file must have a file header comment, as described on the coding conventions page. For the Logisim file, place your name and assignment number in a text label on the main circuit. For image files, ensure your name and assignment number appear somewhere in the image.

This assignment builds upon the logic components you created in the third homework, and thus you must have completed that homework before attempting this assignment. Furthermore, you must have a working is_divisible_by_assembly implementation from HW2.

In this assignment, you will port ARMv8-A assembly code into ULNAv2-C. You will then implement additional control signals so that your Logisim circuit can start executing code.

Part 0.1: ULNAv2-C Compiler Tools

As a reminder, the first project introduced the ULNAv2-C instruction set. Use the following links to obtain the full instruction set:

See HW3 for detailed explanations of the RTN.

Your friendly instructor has written several useful ULNAv2-C tools. Create in your home directory a subdirectory named ulnav2-c, add then fetch the following files into that directory:

http://www.csee.umbc.edu/~jtang/cs411.s24/homework/ulnav2-c/ulnav2-c-as.c: Assembler for ULNAv2-C.
http://www.csee.umbc.edu/~jtang/cs411.s24/homework/ulnav2-c/ulnav2-c-as.h: Common header file used by the assembler.
http://www.csee.umbc.edu/~jtang/cs411.s24/homework/ulnav2-c/ulnav2-c-lexer.l: Flex file that "tokenizes" an input stream.
http://www.csee.umbc.edu/~jtang/cs411.s24/homework/ulnav2-c/ulnav2-c-parser.y: Bison file that parses tokens into an "abstract syntax tree".
http://www.csee.umbc.edu/~jtang/cs411.s24/homework/ulnav2-c/ulnav2-c-emu.cpp: Software emulator for the ULNAv2-C instruction set, controllable using a GDB-like interface.
http://www.csee.umbc.edu/~jtang/cs411.s24/homework/ulnav2-c/adder.S: Demonstration ULNAv2-C program, that adds two values and stores the result into data memory.
http://www.csee.umbc.edu/~jtang/cs411.s24/homework/ulnav2-c/bsort.S: Another demonstration ULNAv2-C program, that bubble sorts an array of 4 values.
http://www.csee.umbc.edu/~jtang/cs411.s24/homework/ulnav2-c/Makefile: Builds the above tools, by simply running make. Also included is a clean target to remove all built objects.

You do not need to modify any of the above files, nor should you submit them with your work.

After you have downloaded all of the files, run make. You will use the resulting tools ulnav2-c-as and ulnav2-c-emu for both this assignment and the final project. Read these files' source code if you are interested in compiler theory.

Part 0.2: ULNAv2-C Assembly Syntax

Ensure you have already built ulnav2-c-as and ulnav2-c-emu. Examine the files adder.S and bsort.S. The ULNAv2-C assembly syntax is similar to ARMv8-A syntax. The minor differences between ULNAv2-C and ARMv8-A syntax are:

ARMv8-A requires immediate values to be preceded by #, but in ULNAv2-C it is optional. The value after the # may be prefixed by 0x to indicate a hexadecimal value. Otherwise it is treated as a signed decimal.
Unlike ARMv8-A, ULNAv2-C does not support pre-indexed nor post-indexed addressing modes.
Whereas ARMv8-A can refer to the same register using an X or W notation, ULNAv2-C registers are always 16-bits, and are always referenced by an R.

Examine the generated files adder.img and bsort.img. These are Logisim memory image files. Every line after the first represents a 16-bit value to be stored in instructional memory. When ulnav2-c-as is run with the -g flag, additional debugging information are added as comments.

Part 0.3: ULNAv2-C Procedure Call Convention

Similar to ARMv8-A's Procedure Call Standard, ULNAv2-C has the following calling convention:

Register	Usage	Who Is Responsible?
R0	First parameter into function, and holds return value from function	Caller
R1	Second parameter into function	Caller
R2, R3, R4, and R5	Temporary storage	Callee
R6	Stack Pointer	Callee
R7	Link Register	Callee

When an assembly function is called, R0 will hold the first function parameter while R1 holds the second parameter. The function stores the return value in R0, and it then jumps to the address in R7 to return to the caller. If the function needs to modify registers R2, R3, R4, or R5, or if it needs to call a subfunction (and therefore change R7), do the following:

Decrement the stack pointer (i.e., update R6). Then preserve registers on the stack (i.e., by using stwi instruction).
If the function needs to call a subfunction, copy the link register (i.e., R7) to the stack. Set R0 and R1 to the subfunction's parameters. Then call the subfunction with bl.
Prior to returning from the function (i.e, by using br instruction), restore all callee-saved registers. Increment the stack pointer (i.e., update R6) to what it was when the function first began. Set R0 to the function's return value. Then unconditionally jump to the return address (i.e., br R7).

Part 1: ULNAv2-C Assembly Code

Create another directory for this assignment. Download the following additional files:

http://www.csee.umbc.edu/~jtang/cs411.s24/homework/hw4/hw4_asm.S: Skeleton ULNAv2-C assembly code for this assignment.
http://www.csee.umbc.edu/~jtang/cs411.s24/homework/hw4/memtest.S: Test code for your Logisim implementation. You do not need to modify this file.
http://www.csee.umbc.edu/~jtang/cs411.s24/homework/hw4/Makefile: Builds all of the code for this assignment, by simply running make. Also included is a clean target to remove all built objects.

The first part of this assignment involves converting ARMv8-A code into ULNAv2-C. Edit hw4_asm.S. The given code first sets register R0 with the dividend, and then sets R1 with the divisor. It also initializes the stack pointer (R6). The code calls into is_divisible_by_assembly to determine if the dividend is evenly divisible of the divider. The function's return value is stored into memory, and then the program halts.

Like from HW2, you must implement is_divisible_by_assembly without using multiplication, division, or module division operators. As per the ULNAv2-C calling convention, if your function uses callee-saved registers (R2, R3, R4, R5, or R7), be sure to save their previous values to the stack (R6), then restore their values prior to returning from the function. As a hint, study how bsort.S saves callee-saved registers in the function prologue, then restores those registers in the epilogue.

Run make to assemble your code. Then execute the resulting image using the ULNAv2-C emulator, like so:

    $ ~/ulnav2-c/ulnav2-c-emu hw4_asm.img

The emulator takes you to a command prompt. Enter ? to view a list of commands. You can simulate one CPU cycle at a time by entering s, or c to continuously run up to the halt instruction.

Note: the grader will use different values for R0 and R1 during grading. The grader will also check that R6 is properly restored by the callee.

You have your choice on how to write is_divisible_by_assembly. You can write it iteratively or recursively.

Part 2: Karnaugh Maps for More Control Signals

In HW3 you first constructed Karnaugh Maps and then implemented the ALUOp control signal. In this assignment you will work with these signals:

CondUpdate (1 bit): This signal is 1 if the Condition Codes register should be modified.
MemWrite (1 bit): This signal is 1 when writing to data memory.
RegWrite (1 bit): This signal is 1 when the register file should be written with the contents of the W Bus.

Compare this list to the signals shown in the single-cycle datapath from lecture 13.

Like with the previous assignment, create a file hw4.txt. List all instructions, not just those that are Class A, B, or C. For each instruction, decide how that instruction should set the above control signals. Observe how halt is a Class D instruction that writes to memory. CondUpdate is already given for you.

Construct Karnaugh Maps for these three signals. Calculate sum of products for the signals. For consistency in grading, the MSB is input E. Add to your hw4.txt three Sum of Products, corresponding to the three signals. Alternatively, draw your K-Maps and Sum of Products on a piece of paper, take a snapshot of the page, then upload the image with the rest of your assignment.

Part 3: Instruction Decoder

You will continue expanding upon your ULNAv2-C Logisim file. First duplicate your hw3.circ, and rename that copy as hw4.circ. Open your newly created hw4.circ. You may safely remove the main subcircuit. Examine hw4_main. Observe how it adds a 64 kibibyte ROM to hold instructions, and a 64 kibibyte RAM to hold data. Also observe how Program Counter and Instruction Register are now registers.

Update your Instr_decoder. Using your Sum of Products from Part 2, implement the control signals CondUpdate, RegWrite, and MemWrite.

Then take a look at Win_selector. This subcircuit controls which value will be written back to the register file. For now, only the ALU's output can be stored. You do not need to modify it for this assignment.

Test your implementation thus far. Go to hw4_main. Right-click Instruction_Memory, then load memtest.img. Step through the first five instructions. If your MemWrite K-Map is correct, MemWrite should be 0 for the first three instructions, and then 1 for the last two. Then examine your register file. R0 should hold 0x0011, R1 should hold 0x0021, and then R2 should hold 0x0032.

Part 4: Program Control Unit

During lectures we discussed the Instruction Fetch Unit and Branch Control Unit. In this assignment we combine both functionality into a single Logisim subcircuit, the Program_Control_Unit (PCU). Because it is complex, only part of it will be implemented here.

For HW4, you will work with these signals:

PC (16 bit): The current program counter.
BrReq (1 bit): This signal is 1 to take a branch. Otherwise when it is 0, simply increment the PC by one.
ExtSel (2 bits): When a branch is taken, this selects how to compute the new address. This signal is ignored when BrReq is 0.

The output of this subcircuit is Next_PC. This is the 16-bit address to be stored back into the PC.

For now, the only branching instruction to implement is halt. Update both Program_Control_Unit and Instr_decoder, such that halt sets the PC to itself, while every other instruction increments PC.

Test your implementation via memtest.img. This time instead of poking the clock signal, enable Auto-Tick. You should see the PC stop at 0x0007 when your CPU executes halt.

Sample Output

Here is a sample output from running a completed hw4_asm.img through the ULNAv2-C emulator:

$ ~/ulnav2-c/ulnav2-c-emu -v hw4_asm.img
ULNAv2-C emulator. Enter '?' to display list of commands.

PC 0x0000: MOVI r0, 0x41 > status
-- Cycle = 0, PC = 0x0000 --
Register File:
    0: 0x0000    1: 0x0000    2: 0x0000    3: 0x0000
    4: 0x0000    5: 0x0000    6: 0x0000    7: 0x0000
Condition Codes:
  C: f  N: f  V: f  Z: f
Data Memory:
  0x0000:  0000 0000 0000 0000 0000 0000 0000 0000
    ...
  0xfff8:  0000 0000 0000 0000 0000 0000 0000 0000
PC 0x0000: MOVI r0, 0x41 > c
<snip>
VM halted!
-- Cycle = 37, PC = 0x0005 --
Register File:
    0: 0x0001    1: 0x000d    2: 0x0000    3: 0x0000
    4: 0x0000    5: 0x0000    6: 0xe000    7: 0x0005
Condition Codes:
  C: f  N: t  V: f  Z: f
Data Memory:
  0x0000:  0000 0000 0000 0000 0000 0000 0000 0000
    ...
  0xfff8:  0000 0000 0000 0000 0000 0000 0000 ffff

Other Hints and Notes

Ask plenty of questions on the Blackboard discussion board.
At the top of your submitted files, list any help you received as well as web pages you consulted. Please do not use any URL shorteners, such as goo.gl or TinyURL. Also, do not cite shared data services, such as Pastebin, Dropbox, or Google Drive.
You are not writing any ARMv8-A assembly for this assignment, but rather ULNAv2-C assembly.

Extra Credit

Sorry, there is no extra credit available for this assignment.

CMSC 411:

Computer Architecture