Consider the following ISA for a Harvard
architecture processor:
• There are 16 general purpose registers, 16 bits each,
named R0..R15.
• There is a 16 bit Program Counter (PC) register.
• There is a maximum of 1K (1024 words) of code space.
• There is a maximum of 1K (1024 words) of data space.
• Each word is 2 bytes (16 bits) in length.
• The processor has no stack.
• Instructions are all 16 bits long.
• All data are integer values. Both integer and hexadecimal
(e.g., 0xFFFF) literals are allowed.
• There are the following 2-operand integer arithmetic
instructions: ADD, SUB, AND, OR, XOR. The left operand
must be a register, while the right operand can be a
register or a literal. The result is placed in the left
operand’s register.
• There is a MOVE instruction for transferring data. It
supports the following address modes:
o MOVE Rx,{Literal,[Ry]}. Copy into Rx a literal
value, or the contents of the memory whose address
is contained in Ry.
o MOVE [Rx],{Ry,Literal}. Copy into the memory
whose address is contained in Rx the contents
of Ry or a literal value.
• There are the following 1-operand instructions:
o SRL Rx. Shifts the contents of Rx one bit to the left,
filling with a 0 bit on the right.
o SRR Rx. Shifts the contents of Rx one bit to the
right, filling with a 0 bit on the left.
o JR Rx. Jumps to the address contained in Rx.
• The following branch instructions compare the values in
the given register with the contents of R0 to determine if
the branch should occur. All branches take a PC-relative
address for the jump location. There will be reasonable
jump ranges (i.e., the number of bits required for the
address location) given the current code space size and
the potential for future extensions.
o BEQ Rx,location. Branch if equal to R0.
o BNE Rx,location. Branch if not equal to R0.
o BLT Rx,location. Branch if less than R0.
o BGT Rx,location. Branch if greater than R0.
o BLE Rx,location. Branch if less than or equal
to R0.
o BGE Rx,location. Branch if greater than or equal
to R0.
An assembler for this ISA has been created that you can use to
assemble some sample programs (the .dat files are for loading
memory). The assembler will generate machine code that can
be loaded into a processor that supports the ISA (for example,
for an input named test.asm the assembler will
generate test.o as an object file and print the machine code
in ASCII to standard output). You cannot make any changes
to the assembler or sample programs, but you’re free (and
encouraged) to create your own test programs.
Questions
Question 1
Implement a simulator for the ISA described above.
The simulator will bootstrap (i.e., start itself up into a state) by
loading a passed object file into the code area and a passed
file’s contents into the data area. Your simulator will accept
two parameters, the first is the object file and the second is the
data file. In addition to the interface described above, your
implementation should do the following:
• All registers are initialized to 0x0000 at startup.
• Make sure all negative values are correctly sign extended.
• The program counter (PC) is incremented after the
execution of an instruction.
• Your simulator should always complete. To handle
infinite loops, define some (large) maximum loop
count. Clearly document this.
• All operations and data accesses are word aligned. Be
careful, since everything involves 2 bytes, not 1 (which
leads to the next point…)
• All values (data, etc) are big endian. Note that this
doesn’t mean everything has to be big endian internally;
you just have to make sure you deal with memory such
that it is big endian (especially when displayed).
• Make sure you interpret the machine instructions
carefully, the bit ordering is very important (see machine
code below).
• Your data area should be initialized to contain all 0xFFs
prior to loading the passed data file.
• The data file is an ASCII file of hex digits. The code to
load the data has been written for you (see void
insert_data( string line );).
• Your simulator must accurately reflect the instruction
execution cycle discussed in our review. Take a look at
the control unit state machine, and use start.cpp to start
your implementation.
The simulation begins by executing the instruction found at
location 0x0000. It will continue executing instructions until it
reaches an invalid instruction (defined as not being contained
in the machine language definition). Note that the best way to
do this is to initialize your code area to fully contain invalid
instructions prior to loading the program. To be clear: this
means that programs in this simulator will never exit
gracefully, programs will always crash to terminate.
Upon completion, the simulator will print out the invalid
instruction and its address (as an error indication – in real
systems you would get an illegal operation trap). If any other
error is detected, an appropriate error message should be
printed (e.g., possible infinite loop detection). Following this it
will print the contents of the data area. Use the same
formatting used in the assembler. For example:
Illegal instruction ffff detected at address 0010
00000000 00 00 00 01 00 01 00 02 00 03 00 05 00 08
00 0d |................|
00000010 00 15 00 22 00 37 00 59 00 90 00 e9 01 79
02 62 |...".7.Y.....y.b|
00000020 03 db 06 3d 0a 18 10 55 1a 6d 2a c2 45 2f
6f f1 |...=...U.m*.E/o.|
00000030 b5 20 25 11 da 31 ff 42 d9 73 ff ff ff ff
ff ff |..%..1.B.s......|
00000040 ff ff ff ff ff ff ff ff ff ff ff ff ff ff
ff ff |................|
...
Grading for question 1
There are a total of 20 points for question 1:
• 5 points for output of memory contents and failure
condition per input .asm/.dat pair (10 × 0.5):
o 0 points: no output or very wrong output.
o 0.5 points: output that’s correct and matches the
sample.
• 5 points for code quality and design:
o 0 points: the code is very poor quality (e.g., no
comments at all, no functions, poor naming
conventions for variables, etc). Code structures to
represent parts or state of the CPU are not used at
all.
o 1–3 points: the code is low quality, while some
coding standards are applied, their use is
inconsistent (e.g., inconsistent use of
comments, some functions but functions might do
too much, code is repeated that should be in a
function, etc). Code structures to represent parts or
state of the CPU may not be used.
o 4–5 points: the code is high quality, coding
standards are applied consistently throughout the
code base. Appropriate code structures are used to
represent different parts or state of the CPU
(e.g., struct, enum, etc).
• 10 points for implementation (5 × 2):
o 0 points: no implementation is submitted, the
implementation is vastly incomplete, or the code
crashes when executed (this specifically means
that your code crashes with, for example,
a Segmentation fault or Bus error, the assembly
code is expected to crash as an exit condition).
o 1–2 points: implementation is significantly
incomplete. Many instruction cycles are
unimplemented or implemented incorrectly. May
store processor state in variables outside of
registers. Data is not moved appripriately between
processor components within a cycle.
o 3–4 points: implementation is mostly complete.
May not implement all instruction cycles or
instruction cycles may be implemented incorrectly.
May store processor state in variables outside of
registers. Data may not be moved appropriately
between processor components within a cycle.
o 5 points: implementation is complete. Instruction
cycles (each phase of the state diagram) are
implemented correctly. The state of the processor is
stored only in the specified registers, no additional
variables are used to maintain state. Data is moved
appropriately between processor components (e.g.,
registers, ALU, memory, etc) within a cycle.
Notes:
• If your code does not compile
on rodents.cs.umanitoba.ca with a single invocation
of make (that is, the grader will change into the
appropriate directory and issue the command make with
no arguments), you will receive a score of 0 for this
assignment. If your submission does not have
a Makefile, that’s effectively the same as submitting
code that does not compile.
o Forget how to make a Makefile? Never knew how
to make a Makefile? Thankfully, you can go
to https://makefiletutorial.com and find some very
easy to use basic examples.
o You can use g++ or clang++, there are no
restrictions on which compiler you use.
• While we’re not checking for warnings or DbC, both are
your friends.
Question 2
Test your simulator with the sample programs and
corresponding data files. These are the programs that the
graders will use to evaluate your simulator.
In a Markdown-formatted file, describe what each of the 7
assembly programs do. Some of the programs
(test2.asm and test6.asm) have multiple input memory
states. For these two programs, explain why each one ends
differently based on the initial state of memory.
Organize your file with headings named for the program name
and the memory input name, for example:
`test1.asm` + `test1.dat`
=========================
`test1.asm` is a program that ...
`test2.asm`
===========
`test2.asm` is a program that ...
`test2-1.dat`
-------------
`test2.asm` terminates with output ... with input
`test2-1.dat` because ...
`test2-2.dat`
-------------
`test2.asm` terminates with output ... with input
`test2-1.dat` because ...
Grading for question 2
1 point for each program and memory input pair
(e.g., test1.asm + test1.dat, test2.asm + test2-
1.dat, test2.asm + test2-2.dat, …) for a total of 10 points.
Notes:
• If your code from question 1 does not compile
on rodents.cs.umanitoba.ca, you will earn a score of 0
for this question, even if you have submitted something.
• If your file is not a Markdown-formatted file, your score
will be reduced by 3 points down to a minimum of 0
points.
Handing in
You should hand in your assignment
with handin on rodents.cs.umanitoba.ca. See man
handin after you’ve connected to rodents for information on
how to use handin.
Appendices
Machine code
All opcodes are 6 bits, with the first 3 bits identifying the
opcode family and the last 3 bits identifying the specific
operation.
Registers are encoded in 4 bits,
with R0 being 0000 and R15 being 1111 (and normal
incrementing between them).
Standard format: [opcode][operand 1][operand 2].
Operand 1 is always 4 bits. Operand 2, when present, can be
up to 6 bits in length (for literal values ranging from -31 to 31).
Any unused bits will be filled with zeros (for either an unused
operand or unused bits).
Operations
In all of the formats indicated below, the underscore (_) is
used to identify a single bit. If there are 4 bits together, then a
register number is to be placed in the operand. If there are 6
bits, then a literal value is to be placed in the operand.
An x (or a grouping) is used to indicate a selection from the
relevant list.
Arithmetic
The first 3 bits of the opcode identify the operation. The
remaining 3 bits are used to indicate the addressing mode of
the second operand: 000 indicates a literal while 001 indicates
a register. Literals are a maximum of 6 bits.
Each operation will have the following formats:
xxx 000 _ _ _ _ _ _ _ _ _ _
xxx 001 _ _ _ _ _ _ _ _ 0 0
The 3 bit operation value assignments are:
• 000: ADD
• 001: SUB
• 010: AND
• 011: OR
• 100: XOR
MOVE
101 indicates that the opcode is for a MOVE operation. The next
3 bits indicate the addressing mode (note that they are
selected such that they can be grouped according to source
and/or destination). The middle bit is set if any other
combination is detected (i.e., memory to memory or register to
register).
• 000: literal to register with format:
101 000 _ _ _ _ _ _ _ _ _ _
• 001: memory to register with format:
101 001 _ _ _ _ _ _ _ _ 0 0
• 100: literal to memory with format:
101 100 _ _ _ _ _ _ _ _ _ _
• 101: register to memory with format:
101 101 _ _ _ _ _ _ _ _ 0 0
Shift
110 is used to identify a shift operation. The remaining 3 bits
are used to identify direction, with 000 indicating right
and 001 indicating left.
The operation has the format:
110 00x _ _ _ _ 0 0 0 0 0 0
Branch
111 is used to identify branch operations (identified as
changing the flow of execution). The remaining 3 bits are used
to identify the type of branch. The remaining 6 bits of the
branch operation store the offset and defines the maximum
branch range as 31 words from the current instruction.
Each operation will have the following format:
111 xxx _ _ _ _ _ _ _ _ _ _
The operation value assignments are:
• 000: JR (note that operand 2 will contain all zeros)
• 001: BEQ
• 010: BNE
• 011: BLT
• 100: BGT
• 101: BLE
• 110: BGE
Control unit state machine