Assignment 0: Rise up!

Remember alignment? When allocating a 32-bit word in a byte-address machine, you really want the word to be allocated on an address that aligns with the word-wide datapath -- in this case, the next free address that is a multiple of 4. Well, there's a similar issue when allocating a larger data structure: you don't want it starting in the middle of a cache line because that would mean a cache miss at the start of the data structure would pull-in less than a full line's worth of useful data. How do we fix this? Well, with a cache line size of 32 bytes, you want the address to rise up (not gonna waste my cache) to the next multiple of 32.

It's pretty easy to do this. Given an address, if it isn't already a multiple of 32, keep incrementing it until it is. Here's a little Verilog module that "rises up" each possible 16-bit value to be a multiple of 32:

module demoriseup;
reg [15:0] a, b;
initial begin
    a = 0;
    repeat (65536) begin
        b = a;
        while (b % 32 != 0) b = b + 1;
        $display(a, b);
        #1 a = a + 1;
    end
end
endmodule

While the above code is a pretty obvious implementation, it really isn't very fast -- heck, there's a while loop in each computation. It also isn't synthesizable Verilog. In this project, I want you to design a synthesizable, purely combinatorial, circuit to align a 16-bit value to a multiple of 32 by making it "rise up" to the next multiple of 32 if it isn't already a multiple of 32. You must do this without using Verilog word-level operators like + for addition. You also must exhaustively test your design.

So, let's talk about alignment. The alignment factor we're talking about here is 32, which is a power of 2 -- a bit position. A multiple of 32 has 0 in each of the five least-significant bits. If any of those bits isn't 0, then the bottom five bits must replaced by all 0s and 32 is added to the result. That's really all there is to it; no looping needed. Of course, that doesn't really help much here because you're not allowed to use the Verilog + operator in making your combinatorial circuit. It is worth noting that I would allow you to use >> (shift) and | (bitwise OR, including the unary OR reduction operator) because they are bitwise operators, not really word-level arithmetic operations.

The basic point is, it's up to you what algorithm you use... and that choice will determine what other modules you might need to create as helpers.

One last point: demoriseup, and any versions you create, will get 31 values "wrong." Huh? Well, when 65505 gets aligned to the next multiple of 32, the value wraps back to 0. Don't worry about that. All the methods will generate the same theoretically-wrong-but-we'll-call-it-right answer for the 31 largest 16-bity values: 0.

Your Project

Your project is about writing a Verilog module called riseup, but there are actually two other chunks of Verilog code you need in order to test it. The three required modules of Verilog code are:

1. The definition of a module that starts with module refriseup(b, a); and makes b the 16-bit result of upward-aligning the value of a. This module MUST use at least one of Verilog's word-level operators that you're not allowed to use in your synthesizable design (e.g., demoriseup uses + and %). Use as straightforward an implementation as possible, perhaps derived from the algorithm used in demoriseup above. This refriseup module will serve as your oracle to deliver known correct answers.
2. The definition of a module that starts with module riseup(b, a); and makes b the 16-bit result of upward-aligning the value of a, but is fully synthesizable and uses only bitwise or gate-level operations. Of course, it may instantiate other combinatorial logic modules to implement its functionality, e.g., you might start with defining a 16-bit adder circuit and then instantiate that in your riseup. Alternatively, you might begin by building a one-bit full adder and then a 16-bit ripple cary adder from that. You have a free choice of algorithm for how you implement riseup. However, this module MUST be Verilog code that you author using synthesizable, purely combinatorial, logic -- it is NOT permitted to use word-level Verilog operators (as noted above) in itself nor in anything it instantiates.
3. The definition of a non-synthesizable module that starts with module testbench; and instantiates a riseup which it exhaustively tests for correctness. Note that it is not sufficient to just print what happens for all 65,536 possible input values; I don't want just a stimulus module. Who would want to manually check 65,536 lines of output? Your testbench must not only try each possible input value, but also must check that the answer from your riseup matches the answer from refriseup in each case. Your testbench should only output the combinations of inputs for which the answer from riseup was wrong. Further, it should count how many input combinations were correct and how many failed. The last line of text output should be generated by Verilog code like:

   $display("All cases tested; %d correct, %d failed", correct, failed);
   

Place all your verilog code for the above in one file called riseup.v. That's the file you need to submit.

Naturally, I also expect you to run that file through a Verilog compiler either using our CGI interface or Icarus Verilog directly:

iverilog -o riseup riseup.v

And to run the simulation to test it:

vvp riseup

Which will hopefully result in it printing just:

All cases tested; 65536 correct, 0 failed

If not, and you can't figure-out how to fix it, as Ricky Ricardo would say, you got some splainin to do. ;-)

Details For The Implementor's Notes

You should be submitting an implementor's notes document with your project. Just a couple of quick comments about that....

Your implementor's notes certainly should describe the logic used to implement your riseup module. That can be done as text. I am not requiring you to provide a schematic of your riseup module... it's rather simple and the schematic wouldn't really be very useful. However, practice creating schematics is certainly a good thing (i.e., a skill you will appreciate in this course) and it wouldn't hurt to include a schematic.

Although I would encourage you to think about generating a VCD file and using gtkwave to visualize it, I don't think there's much point in doing that for a simple combinatorial circuit like riseup. If you do find it useful, you may include a screen grab from gtkwave in your implementor's notes.

Due Dates

The recommended due date for this assignment is before class, Friday, September 13, 2019. This submission window will close when class begins on Monday, September 16, 2019. You may submit as many times as you wish, but only the last submission that you make before class begins on Monday, September 16, 2019 will be counted toward your course grade.

Note that you can ensure that you get at least half credit for this project by simply submitting a tar of an "implementor's notes" document explaining that your project doesn't work because you have not done it yet. Given that, perhaps you should start by immediately making and submitting your implementor's notes document? (I would!)

Submission Procedure

For each project, you will be submitting a tarball (i.e., a file with the name ending in .tar or .tgz) that contains all things relevant to your work on the project. Minimally, each project tarball includes the source code for the project and a semi-formal "implementors notes" document as a PDF named notes.pdf. It also may include test cases, sample output, a make file, etc., but should not include any files that are built by your Makefile (e.g., no binary executables). For this particular project, name the Verilog source file riseup.v.

Submit your tarball below. The file can be either an ordinary .tar file created using tar cvf file.tar yourprojectfiles or a compressed .tgz file file created using tar zcvf file.tgz yourprojectfiles. Be careful about using * as a shorthand in listing yourprojectfiles on the command line, because if the output tar file is listed in the expansion, the result can be an infinite file (which is not ok).