Assignment 4: Reversible Pipelined AXA

In this project, your team is going to build a pipelined implementation of AXA that, unlike your previous project, fully supports reverse execution.

How Reverse Execution Works

Reverse execution in other reversible instruction sets is, honestly, a bit of a curiosity -- it doesn't really have a great reason for being there. In AXA, reverse execution is all about error handling. The key concept involves a 4-bit mask that is used to specify error conditions. Each bit position in the mask refers to a different type of error that can occur in forward execution. The bit definitions are:

0x1

Illegal instruction: SIGILL. This error condition is normally raised when an illegal instruction is executed. I don't expect you to necessarily detect all types of illegal instructions, but you must at least detect when the exchange instruction, ex is attempted with a src that isn't of the form @$s. It also can be explicitly raised using fail.

0x2

Transactional memory violation: SIGTMV. This error condition is normally raised when the data cache detects a potential conflict between two (or more) processors access the same memory locations. If your team is doing project 4, you don't have to worry about how the memory system would detect this, because your memory system will not detect it -- that's what the teams doing project 5 have to deal with. However, your implementation still has to handle it properly when the exception is explicitly raised using fail.

0x4

Checkpoint: SIGCHK. In many programs, it is useful to be able to save a consistent state before doing some computation that might fail. For example, one might have code that attempts to compute a value by some heuristic and then checks to see if the value was good enough. If the value wasn't good enough, you want to undo the execution back to the point where you began the heuristic computation, and then proceed with a (presumably more expensive) way to compute the value. This exception is what programmers should use for general exception handling, and should only be explicitly raised using fail.

0x8

Loop exit: SIGLEX. Although I hate this style of programming, it is common that in languages like Java programmers are encouraged to rely on things like array subscript bounds checks to exit ordinary for loops. That's what SIGLEX is intended to be used for -- undoing the current iteration of a loop body, and cleanly exiting the loop, when something like an out-of-bounds subscript reference is detected. This exception should only be explicitly raised using fail.

If your team is doing project 4, you only need to worry about automatically triggering SIGILL. Of course, any combination of the above can be explicitly raised by a fail instruction. For example, fail SIGTMV+SIGCHK could raise both the transactional memory violation and checkpoint exceptions.

How does the hardware really raise an exception? Well, if you look at the AXA instruction set specification, the answer is that you don't always do anything. Only exceptions that are present in the current check mask actually get raised, and that's done by something like errors|=(mask&check);. Whenever errors isn't 0, you are in reverse execution mode.

Ok, clear enough? Well, maybe not. So let's talk about what each of the relevant instructions do:

jerr $d, mask

Think of jerr as being a lot like the UNIX signal() system call; it essentially establishes what to do when the specified signals happen. In forward execution, jerr is entirely about the mask. It simply adds the mask to the set of exception conditions it is currently checking for. In other words, check|=mask;. In reverse execution, you essentially keep going backwards until there are no more errors remaining. This particular jerr handles mask, so we stop checking for those conditions: check&=~mask;. We also turn off the errors this jerr handles: errors&=~mask;. Thus, if there are no errors left, this is the jerr that caught the last of them, and hence we go into forward execution at the address in $d. If there are still errors left, we just keep going backward....

com

Commit basically says "I trust everything up to this point" -- and thus you can stop checking for any signals. (In retrospect, I probably should have had it take a mask saying which signals to no longer check... but I didn't, although I wouldn't object to you doing that.) In forward execution, it simply makes check=0;. In reverse execution, it also makes errors=0;, and then resumes forward exection. If some sense, com is the opposite of jerr; it disables any signal handlers set-up by jerrs.

fail mask

This is essentially a lot like the UNIX kill() call, although the only process you can send a signal to is yourself. Although the meaning of failing as raising exceptions is probably clear from the above discussion, the specification of fail in the AXA instruction set specification is slightly imprecise: what does it mean to raise an exception for which no handler is active? Well, it means you die. So, if mask&~check isn't 0, fail should essentially become a sys instruction and halt the machine. Otherwise, errors=(mask&check); and reverse execution begins. If we're already executing in reverse, fail does nothing... which is also what fail 0 should do in forward execution.

Well, that wasn't too bad, was it?

One last note. Your previous project only needed 16 entries in the undo buffer. Here, your undo buffer should have 256 entries. That will not only allow deeper reverse execution, but will continue to have i4$ references correctly handled despite backing-up as many as 256-16=240 undo buffer entries....

Stuff You Can Use/Reuse

As with the previous assignment, reusing knowledge and even some code can make this project easier. You are not allowed to use anything from another Assignment 4 team nor from an Assignment 3 team that none of your Assignment 4 team members were on. The wierd thing here is you are encouraged to discuss things with any/all of the Assignment 5 teams! Why? Well, the goal is to eventually integrate the best of the Assignment 4 results with the best of the Assignment 5 results... so a little coordination is a good thing.

Remember, if you find other materials, for example solutions posted from previous semesters, useful, you may borrow ideas from them, but should generally not literally copy code and you must cite the sources you borrowed ideas from in your Implementor's Notes.

Testing

Again, the test coverage plan and testbench from Assignment 3 are probably very close to what you want. However, you do need to seriously think about coverage again. Why? You are not testing the same Verilog code, so there may be some paths that didn't exist before -- and they might not be covered with a testbench that covered your old version. In particular, you will need to test reverse execution of the various constructs, and that will require a somewhat different test.

Due Dates

The recommended due date is Friday, December 13, 2019. By that time, you should definitely have at least submitted something that includes the assembler specification (axa.aik), and Implementor's Notes including an overview of the structure of your intended design. That overview could be in the form of a diagram, or it could be a list of top-level modules, but it is important in that it ensures you are on the right track. Final submissions will be accepted up to just before the final exam at 8AM on Thursday, December 19, 2019.

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). Be sure to make it obvious which files are which; for example, if the Verilog source file isn't axa.v or the AIK file isn't axa.aik, you should be saying where these things are in your implementor's notes.

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).