You may have heard of reversible logic... well, the idea there is to build gates in a way that makes them thermodynamically reversible (aka, adiabatic), so it can take a miniscule amount of power to perform the logic functions. Reversible instruction sets are essentially taking that idea up a level, trying to make the instruction set literally allow execution both forward and backward. You know, kind of like this. Ok, I lied. It's really nothing like that.
Probably the first reversible instruction set design was Pendulum, and there's also Bob (coincidentally done the same year as the video linked above), but there really haven't been many (instruction set designs, that is... there are other palindrome vidoes like this and and even this). The motivation for those instruction sets seems to be just taking adiabatic logic up a level. However, honestly, there isn't any need for the instruction set to be reversible in order to use adiabatic gates for the implementation. So, does anybody know a better reason to make the instruction set reversible?
Well, in the high-performance-computing world, there are actually at least a couple of great reasons to want this. One is the general desirability of something called checkpointing -- the ability to save the state of a program so that, if an error occurs, the program can be resumed from the most recent checkpoint rather than restarted. The other has to do with inter-process communication and synchronization via shared memory. Using semaphores to ensure exclusive access to objects in shared memory can impose a significant overhead even when no other processor wants to access those objects at that moment; to avoid that overhead, transactional memory allows you to simply make the accesses assuming no contention, but have the hardware detect contention and undo and repeat any incomplete transaction. In sum, these are concepts closely related to the high-level language concepts that you try to execute some code and catch any failure of it. That's the kind of behavior our reversible instruction set, AXA, is designed to implement. In that sense, AXA is actually more like this movie than the palindromic things linked above, because it allows repeating your actions until you get it right. Best of all, we think that, by the end of the semester, the entire class may be able to be authors on a publishable research paper about it....
First off, let's get the name out of the way. Of course, AXA is a palindrome. In fact, it is also visually palindromic: the left and right sides of the name are literally mirror images of each other. It's also somewhat mnemonic, standing for "Ahead X About-face" where "X" is meant to symbolize an error. In other words, it's an instruction set that reverses execution when an error is encountered.
This detailed description of AXA tells you what this strange instruction set looks like. Actually, you'll probably find it is disturbingly normal-looking despite supporting reversible execution. In truth, that's partly because it doesn't really support an arbitrary amount of reverse execution, but just a modest, yet useful, amount constrained by the size of a hardware undo stack. AXA's undo stack is a lot like the garbage stacks in earlier reversible machines, but it is explicitly finite and, unlike garbage stacks, you can actually read values from the undo stack. Yup, they're not garbage. In other words, you get to use the undo stack partly as a low-cost place to spill register values to when you run out of registers. AXA is also different in that reverse execution is merely a side-effect of encountering an error; it's really a mechanism for recovery of consistent state rather than a "reverse execution mode" lacking a clear purpose.
The key thing you need to know for the current project is that none of the reverse execution stuff has anything to do with how you build the assembler for AXA. The assembler is absolutely normal. In fact, you will not be dealing with the reversibility stuff until the semester's final project.
So, for this project, you're given the assembly language and functional design of AXA. Your job is simply to determine a way to encode each instruction in a single 16-bit words and the build an assembler implementing that encoding. Each student must devise their own encoding of the instructions implement their own assembler using AIK: the Assembler Interpreter from Kentucky (which is also discussed here).
AXA is a completely 16-bit machine. Everything is 16 bits wide: instruction words, addresses, data, and each of the 16 registers. It isn't even byte-addressed for memory... and, incidentally, it has separate memories for code and data. No fancy arithmetic operations in AXA either.
It's really quite straightforward (why is "straightforward" so much more complex a word than "complex"? -- nevermind). Your AIK assembler must recognize all the instructions described in the detailed description of AXA. Incidentally, your assembler does not need to generate errors messages for illegal instructions; for example, bz $5,$6 would not be a legal instruction, but you might find it naturally would generate the same word-length bit pattern as jz $5,$6bz $5,$6 in the first place... so boo on them. The output should be .VMEM-format .text and .data segments suitable for loading into memory in a Verilog simulation.
The regular assembly-language pseudo-operations supported by AIK are sufficient, so you don't need to worry about things like renaming .equate. However, don't forget to define the two segments and define the register names using .const.
There's just one curve ball I'm throwing you: I want you to implement an optimized l16 instruction. What does l16 do? Well, it loads a 16-bit immediate value in the cheapest way possible. You should pick the cheapest of the following three methods to implement l16 $d,i:
lhi $d,(i>>8) llo $d,i lhi $d,(i>>8) xlo $d,i
These instruction sequences cannot be written-out in the above way. AIK can output either 16 or 32 bits from a single pattern match (as required), but you can't reference the other instruction patterns by name. You must list the individual field values just as if you were defining how a "real" instruction would be encoded.
Your project is simply to design the instruction set encoding and implement an assembler using AIK. Here's a simple test case:
.text
start:
add $1, $2
add $1, 2
add $1, @$2
add $1, 2$
and $1, $2
and $1, 2
and $1, @$2
and $1, 2$
bn $1, 2
bnn $1, 2
bnz $1, 2
bz $1, 2
com
dup $1, $2
dup $1, 2$
dup $1, 2
dup $1, @$2
ex $1, $2
ex $1, 2
ex $1, @$2
ex $1, 2$
fail 0b0110
jerr $1, 0x0011
jn $1, $2
jn $1, 2$
jn $1, @$2
jnn $1, $2
jnn $1, @$2
jnn $1, 2$
jnz $1, $2
jnz $1, @$2
jnz $1, 2$
jz $1, $2
jz $1, 2$
jz $1, @$2
.data ; switch to data segment
.origin 0x0000
.word 42
l16 $1, 0x0034
l16 $1, 0x1200
l16 $1, 0x5678
l16 $1, -1
.text ; back to text segment
land
lhi $1, 2
llo $1, 2
or $1, $2
or $1, 2$
or $1, 2
or $1, @$2
rol $1, $2
rol $1, 2$
rol $1, 2
rol $1, @$2
shr $1, 2
shr $1, $2
shr $1, @$2
shr $1, 2$
sub $1, $2
sub $1, 2$
sub $1, 2
sub $1, @$2
sys
xhi $1, 2
xlo $1, 2
xor $1, $2
xor $1, 2$
xor $1, 2
xor $1, @$2
No, the above isn't a useful program. Worse still, I obviously can't show you sample output without giving-away how I've encoded the instructions....
The recommended due date for this assignment is before class, Wednesday, September 25, 2019. This submission window will close when class begins on Friday, September 27, 2019. You may submit as many times as you wish, but only the last submission that you make before class begins on Friday, September 27, 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!)
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 AIK source file axa.aik.
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).
Advanced Computer Architecture.