Homework 4: Introducing ULNAv2-A

This homework is due on Thursday, April 23, at 11:59:59 PM (Eastern daylight time). You must use submit to turn in your homework like so:
submit cs411_jtang hw4 hw4.c multu16.S hw4.circ
 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.

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 unsigned multiplication algorithm written in assembly.

In this assignment, you will implement a disassembler, in C, for the ULNAv2-A instruction set. You will then use that disassembler to partially decode a ULNAv2-A program, displaying control signals that would be generated for each instruction. Finally, you will add a decoder into your Logisim file to decode those control signals.

Part 0.0: ULNAv2-A Instruction Set

ULNAv2-A (UMBC's Limited Nifty Architecture, version 2 bugfix A) is the 16-bit RISC architecture that you will implement for this class's final project. In ULNAv2-A, all instructions are 16 bits and all data registers hold 16 bits. The data format is big-endian.

There are 8 general purpose registers, each 16-bit wide, referred to as R0 through R7. There is also a 16-bit program counter (PC). All registers are initialized to 0 after reset.

In ULNAv2-A, there are two memory systems: Instruction Memory and Data Memory. Both memories have 16-bit addresses and 16-bit data widths. The data memory is initialized at zero at processor startup and is writable, while instruction memory is preloaded with the program to execute and is considered read-only.

All instructions are 16 bits, where the top 5 bits (towards MSB) give the instruction number. The top 2 bits (bits 15 and 14) specify the instruction class, the next three bits are instruction subtype, and remaining bits are operands:

Instruction Class 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
A 0 0 subtype Reg W Reg A Reg B X X
B 0 1 subtype Reg W Reg A Imm 5
C 1 0 subtype Reg W Imm 8
D 1 1 subtype Imm 11

There are 29 instructions defined in ULNAv2-A. Instructions numbers 6, 17, and 19 are undefined. Use the following links to obtain the full instruction set:

In ULNAv2-A RTN, the notation R[n] means general purpose register n. MemWord[n] means the 16-bit value within data memory at address n. All additions and subtractions treat operands as two's complement signed integer values. When executed, only some of these instructions update the ALU's condition codes Z, C, N, and V, as specified by the column Updates Cond Codes; these instructions' names also end with a dot.

Here are further details for some of the instructions:

and., andi., or., ori.
These instructions update the condition codes Z and N based upon the result of the logic operation. The condition codes C and V are set to Don't Cares; Z and N are based upon the result of the operation.
ash
This normally performs an arithmetic shift right, by a number of bit positions equal to the immediate, towards the LSB. If the immediate is negative, then shift left instead.
br
The B and W register values are Don't Cares.
brl
This "branch to register and link" first saves the program counter to a register, before jumping to the address within a register. W and A can refer to the same register, in which case the PC is first saved prior to the jump.
cmp., cmpi.
These instruction do not modify any registers nor data memory; they simply set the ALU's condition codes.
halt
This instruction explicitly sets the PC to itself, preventing the program from executing further. The imm11 value is a Don't Care.
lsh
This normally performs a logical shift right, by a number of bit positions equal to the immediate, towards the LSB. If the immediate is negative, then shift left instead.
movis
This replaces the upper eight bits of a register with the 8-bit immediate value. (This instruction moves an immediate that has been shifted to the left by eight bit positions.)
rot
This normally rolls a register's value to the right, by a number of bit positions equal to the immediate, towards the LSB. If the immediate is negative, then rotate left instead.

Study ULNAv2-A carefully. Post on the Blackboard forum questions you have about this instruction set.

Part 0.1: ULNAv2-A Assembler and Emulator

Your friendly instruction has written several useful ULNAv2-A tools. Create in your hame directory a subdirectory named ulnav2-a, add then fetch the following files via wget:

http://www.csee.umbc.edu/~jtang/cs411.s20/homework/ulnav2-a/ulnav2a-as.c
Assembler for ULNAv2-A.
http://www.csee.umbc.edu/~jtang/cs411.s20/homework/ulnav2-a/ulnav2a-as.h
Common header file used by the assembler.
http://www.csee.umbc.edu/~jtang/cs411.s20/homework/ulnav2-a/ulnav2a-lexer.l
Flex file that "tokenizes" an input stream.
http://www.csee.umbc.edu/~jtang/cs411.s20/homework/ulnav2-a/ulnav2a-parser.y
Bison file that parses tokens into an "abstract syntax tree".
http://www.csee.umbc.edu/~jtang/cs411.s20/homework/ulnav2-a/ulnav2a-emu.cpp
Software emulator for the ULNAv2-A instruction set, controllable using a GDB-like interface.
http://www.csee.umbc.edu/~jtang/cs411.s20/homework/ulnav2-a/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.

In addition, you need to install the flex and bison utilities: 

    sudo apt-get install flex bison libreadline-dev

After you have downloaded all of the files, run make. You will use the resulting tools ulnav2a-as and ulnav2a-emu for both this assignment and the final project. You may find these files interesting to read through, if you are interested in compiler theory.

Part 1: ULNAv2-A Disassembler

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

http://www.csee.umbc.edu/~jtang/cs411.s20/homework/hw4/hw4.c
Skeleton C code for this assignment.
http://www.csee.umbc.edu/~jtang/cs411.s20/homework/hw4/multu16.S
Skeleton assembly code for this assignment.
http://www.csee.umbc.edu/~jtang/cs411.s20/homework/hw4/adder.S
Demonstration ULNAv2-A program, that adds two values and stores the result into main memory. Do not submit this file with your work.
http://www.csee.umbc.edu/~jtang/cs411.s20/homework/hw4/bsort.S
Another demonstration ULNAv2-A program, that bubble sorts an array of 4 values. Do not submit this file with your work.
http://www.csee.umbc.edu/~jtang/cs411.s20/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.
Furthermore, duplicate your hw3.circ, and rename that copy as hw4.circ. You will edit hw4.circ in Part 4.

Now run make to build the disassembler and demonstration ULNAv2-A programs.

Examine the files adder.S and bsort.S. The ULNAv2-A assembly syntax is similar to ARMv8-A syntax. Minor differences between ULNAv2-A and ARMv8-A syntax are:

Now 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 ulnav2a-as is run with the -g flag, additional debugging information are added as comments.

Returning to this homework, the first part of this assignment involves building your ULNAv2-A Disassembler. Run hw4, passing in an image filename on the command line. For each instruction within the image file, the disassembler displays the raw 16-bit value and its instruction class. You are to further decode the instruction. Based upon the instruction number, display the instruction name. For example, given the instruction c7ee, which is a branch instruction, display this: 

    c7ee: instruction class "D"
          this is: b

Part 2: Control Signals Decoder

In the final project, you will use Logisim to implement ULNAv2-A as a single-cycle datapath. This will take a while to do. In preparation, your next task is to analyze the ULNAv2-A instruction set and determine how to set control signals for each decoded instruction. For this part, concentrate on these signals:

ALUOp (5 bits)
Specifies which operation the ALU should perform. Not all combination of bits are valid.
CondUpdate (1 bit)
This signal is 1 if the Condition Codes register should be modified.
MemRead (1 bit)
This signal is 1 when reading from data memory.
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.

Then update your hw4.c. After displaying the instruction's name, display its control signal values.

Hint: You should build yourself a spreadsheet to analyze ULNAv2-A. Using the supplied spreadsheet as a basis, insert columns for each control signal. For each instruction, determine what value needs to be written to each control signal. Use an X if the control signal is set to a Don't Care.

Note: Your final implementation of ULNAv2-A will require many more signals. For this homework, you only need to generate the above signals.

Part 3: Implement Unsigned Multiplication

In this next part, you will write your own ULNAv2-A assembly code. Examine the skeleton file multu16.S. This assembly code is to implement unsigned 16-bit integer multiplication, based upon the ARMv8-A code you wrote in HW3. Like the previous assignment, four registers will be set prior to executing your algorithm: register R0 has the multiplicand, R1 the multiplier, R2 the address in memory to store the upper half of the product, and R3 the address in memory to store lower half.

Run make to assemble your code into the image file multu16.img. In the final project, you will execute that image within Logisim. For this assignment, you will instead execute the image using the ULNAv2-A emulator ulta2a-emu. Start the emulator like so: 

    $ ~/ulnav2-a/ulnav2a-emu multu16.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 run continuously until a halt instruction with the command c.

Upon program completion, defined as execution of a halt instruction, your algorithm is to have written the 32-bit product into instruction memory. Warning: the grader will use different values for R0, R1, R2, and R3 during grading.

Part 4: Instruction Decoder

In this part of the assignment, you will expand your Logisim file from the third homework.

Create a new subcircuit, Decoder. It has exactly one input, the 16-bit instruction Inst. Its outputs are the five control signals from the Part 2, plus these three:

ASel (3 bits)
Selects a register to read from the register file.
BSel (3 bits)
Selects a register to read from the register file.
WSel (3 bits)
Selects a register to read/write from the register file.

Using the input Inst, generate all eight output signals. To get you started, here is one part of the decoder:

Next, update your Main circuit. Insert the Instruction Memory (a RAM device), configured with one asynchronous load/store port. Then connect the PC's output to the Instruction Memory's address port. Route the Instruction Memory's output into a 16-bit tunnel Inst. Then rewire the clock, so that the Program Counter, Register File, and Condition Codes are updated on the clock's falling edge.


Add your Instruction Decoder to Main. Route Inst into it, then route its outputs to the rest of your circuit.

Note: Control signals MemRead and MemWrite do not go anywhere in this assignment, but you will need them for the final project.

Test your circuit by right-clicking Instruction Memory, select "Load Image...", then choose an ULNAv2-A image file. Manually poke the clock line. Ensure that all control signals generated by your Instruction Decoder match your ULNAv2-A disassembler.

Part 5: Required Documentation

Add a comment block to the top of hw4.c file that answers these questions:

  1. ARMv8-A has the mov instruction to copy the value from one register to another register, but ULNAv2-A lacks that instruction. Give four different ways that mov can be simulated, using only a single ULNAv2-A instruction.
  2. ARMv8-A has the sub (immediate) instruction, to subtract a constant from a register and store the difference in a register. How can sub be simulated in ULNAv2-A, using only a single instruction?

Sample Output

Here is a sample output from running the instruction decoder. The grader will use different image files when testing your decoder. This sample does not show all of the required control signals, and it only shows the disassembly of the last three instructions from bsort.img 

$ ./hw4 bsort.img
<snip>
c7f6: instruction class "D"
      this is: b
      CondUpdate: 0
      MemRead: 0
      RegWrite: 0

4921: instruction class "B"
      this is: addi.
      CondUpdate: 1
      MemRead: 0
      RegWrite: 1

c7ef: instruction class "D"
      this is: b
      CondUpdate: 0
      MemRead: 0
      RegWrite: 0

Here is a sample output from running the multiplication algorithm through the ULNAv2-A emulator: 

$ ~/ulnav2-a/ulnav2a-emu multu16.img
ULNAv2-A emulator. Enter '?' to display list of commands.

PC 0x0000: MOVI r0, 0x10 > (User enters c)
VM halted!
-- Cycle = 328, PC = 0x0028 --
Register File:
    0: 0x010c    1: 0xa310    2: 0x0020    3: 0x0021
    4: 0x4110    5: 0x0000    6: 0x8000    7: 0x0000
Condition Codes:
  C: t  N: f  V: f  Z: t
Data Memory:
  0x0000:  0000 0000 0000 0000 0000 0000 0000 0000
    ...
  0x0020:  010c a310 0000 0000 0000 0000 0000 0000
  0x0028:  0000 0000 0000 0000 0000 0000 0000 0000
    ...
  0xfff8:  0000 0000 0000 0000 0000 0000 0000 ffff

Other Hints and Notes

Extra Credit

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