Project 10

In this project we work on multiplication.

Software multiplication

In project 7 you wrote an assembler program Mult.asm with the following specification:

This program computes the value R0*R1 and stores the result in R2. We assume that R0>=0, R1>=0, and R0*R1<32768. Your program need not test these conditions, but rather assume that they hold.

At that time we didn't care about the running time of the program. Let us measure it now: use the CPUEmulator to run the script MultTime.tst. It will load your Mult.asm file, run it on a few inputs, and measure it's running time. You'll get an output like the following:

|  RAM[0]  |  RAM[1]  |  RAM[2]  | time  |
|       2  |       3  |       6  | 28    |
|      17  |     123  |    2091  | 1016  |
|     197  |     137  |   26989  | 2116  |
|      13  |    2333  |   30329  | 20784 |
|    2333  |      13  |   30329  | 20892 |
|    8888  |       3  |   26664  | 20920 |
|       3  |    8888  |   26664  | 92028 |
The last column time indicates the running time of your program, counted in clock cycles. (Note that it is cumulative, so the last multiplication used \(92028 - 20920 = 71108\) cycles.)

Rewrite your program to make multiplication as fast as you can, and use MultTime.tst to measure its running time. For comparison, here is my own implementation's timing:

|  RAM[0]  |  RAM[1]  |  RAM[2]  | time  |
|       2  |       3  |       6  | 34    |
|      17  |     123  |    2091  | 120   |
|     197  |     137  |   26989  | 262   |
|      13  |    2333  |   30329  | 336   |
|    2333  |      13  |   30329  | 550   |
|    8888  |       3  |   26664  | 796   |
|       3  |    8888  |   26664  | 834   |

Upload mult.asm to our submission server.

Hardware multiplication

Even the best multiplication code still needs more than 100 clock cycles. If we want to multiply faster, we need to do it in hardware.

Implement a chip that can multiply two 8-bit numbers and produces a 16-bit result. (We interpret both input and output as unsigned numbers.)

A template HDL file and test script is in pp10.zip.

Use only built-in parts of our HardwareSimulator. Don't worry about wasting Nand-gates: To add two 8-bit numbers, just use an Add16 chip and leave the unused input pins unconnected.

Upload Mult16.hdl to our submission server.