Eli Intriligator and Max Behrendt
Date: Nov 23 2021
TA help acknowledgements: Alex, Ann-Marie, Liana, Alan, Tina, Igor, Gustavo, Mary-Joy
In this assignment, we wrote the software implementation of a virtual machine, complete with 14 machine instructions that result in a Turing-complete system.
We believe we have implemented all features correctly.
In our design, we planned to store each segment in a sequence. However, we switched to using UArrays to store each segment since this approach involves less pointer-following, making it faster and simpler to program. In addition, using UArrays means that we did not have to manage memory as much.
The program is composed of two modules and a file um-main.c, which contains main. The first module, segment.h, implements the segmented memory abstraction, allowing the user to map and unmap segments of memory and receive 32-bit identifiers for the allocated segments. This module knows the secrets of where memory is stored and how segment identifiers are managed. To create the initial segment, segment.h receives a UArray of the input instructions from main. The second module, instructions.h, implements the UM's instruction set abstraction. It keeps the registers, instruction codes, and information about the bit representation of instructions hidden from the other modules. This module depends on um-main.c to feed it instruction words, and it depends on segment.h to handle segmented functions. Lastly, um-main.c reads instructions from the .um file and contains the main execution loop for UM programs. um-main.c keeps the file I/O hidden from the other modules. It interacts with segment.h to initialize the UM and to free all segments at the end of execution, and it interacts with instruction.h to execute UM instructions.
How long does it take our program to execute 50 million instructions? We know that midmark.um executes 85070522 instructions (we counted the instructions and printed the result), and we also know that it took our program 8.305 seconds to run midmark.um. That means, on average, our program takes 9.76248859e-8 seconds to execute one instruction. Based on this, it would take our program 4881.244 seconds to execute 50 million instructions.
add
: Tests add by loading the ascii value B into one register and
the value 1 into another, then calling add on them to get an
expected output of 'C'.
conditional move
: Tests first by putting the values 80 and 90 into
two registers and calling conditional move with the condition 0. We
then print the first register to see that it is still 80. The same then
occurs with the condition 1, in which case we print the first register
and see the value 80 has changed to 90.
divide
: Loads the values 640 and 10 into two registers, then calls
the divide instruction with the first being divided by the second.
We use output to print the result, which is the 64th ascii char.
halt
: Calls halt immediately; the program should stop.
halt verbose
: Similarly to halt, the program should stop, but if it
does not the word 'bad' will be printed.
load_prog_full
: This tests whether load program successfully switches
to a new segment. It checks this by first mapping a new segment that
will be switched to, then loading 80 into register 7 using
multiplication and addition to construct two new instructions βΒ an
output instruction that prints the contents of register 7 and a halt
instruction. These two new instructions are loaded into the new segment
using segmented store, then the test calls load program and switches to
the new segment. The test will then print 80 (i.e. 'P') if load program
is implemented correctly.
load_prog_pointer
: Loads the values A, B, C, and D into 4 registers,
prints the first 2, then calls load_program with m[0], such that
it just moves the program pointer to the 10th instruction, skipping
the print of C. Thus the correct output is ABD.
map_segment
: Uses map segment to make a new segment of size 7, which
places the index of the new segment into a register. We then take that
register and add 80 to it, then output it. If correct, the test should
output the 81st ascii char.
multiply
: Multiplys 8 by 8 and then prints the result. Should print the
64th ascii char.
nand
: Calls nand on the values 5 and 10, then adds 80 to the result
so that we can output a printable ascii. Then does the same with the
values 5 and 5. The correct output is 'OJ'.
output
: Loads and then outputs every ascii char.
seg_store_load
: Tests both seg_store and seg_load by mapping a new
segment, using seg store to store the value 80 in that segment,
using seg load to load that value into a register, then using
output to print the value.
unmap_segment
: Maps a segment of size 8, then immidiately unmaps it.
We then map a new segment, which should be at the same index as the
first segment, and place values in it. We then print those values
to make sure that the segment was properly mapped to the index
that the original was unmapped from.
Time spent analyzing problems posed in the assignment: 5 hours
Time spent preparing our design: 7 hours
Time spent solving the problems after our analysis: 18 hours