Instruction set design is hard. Prof. Dietz has designed dozens of instruction sets in the three decades he's been a professor, and it still isn't easy for him to get things right. Thus, rather than giving you complete freedom to design your own instruction set, we're going to walk through the design logic for a reasonably well-crafted one that he built specifically for Fall 2016 EE480. However, this design is not complete -- each student must devise their own encoding of the instructions implement their own assembler.
What the heck is loQ Don? It means "slightly parallel" (if you don't believe me, ask a Klingon... who also would tell you it's pronounced somewhat like "L-oh-Q D-oh-N"). It's what our target machine will be for Fall 2016 EE480. The idea is simple enough: it is a SWAR (SIMD Within A Register) instruction set where every operation is slightly parallel. The machine has 32-bit registers and datapaths, but can operate on data as either a single 32-bit value or a four-element vector of 8-bit values. Thus, data memory (i.e., the .data segment) looks like an array of 32-bit data objects in which adding 1 to an address gets you the next 32-bit data object. Instruction memory (i.e., the .text segment) is different; each instruction is 16 bits long and adding one to an instruction address gets you the next 16-bit instruction. For simulation purposes, you should assume each of the .data and .text segments can hold 65536 of their size "words."
This instruction set is complete enough that I'll be giving you a compiler (including full C source code) that translates programs written in a significant subset of C into loQ Don code. It's not a particularly smart compiler (ok, it's really dumb), but it will show you how loQ Don can be used for complete programs.
Enough with the platitudes about this great loQ Don instruction set. Here's the instruction set assembly language syntax, with instruction names listed in alphabetical order.
| Instruction | Description | Functionality |
|---|---|---|
| add $d, $s, $t | ADD 32-bit integers | $d = $s + $t |
| addv $d, $s, $t | ADD vector of 8-bit integers | $d[3] = $s[3] + $t[3];
$d[2] = $s[2] + $t[2]; $d[1] = $s[1] + $t[1]; $d[0] = $s[0] + $t[0]; |
| and $d, $s, $t | bitwise AND 32-bit integers | $d = $s & $t |
| any $d, $s | bitwise ANY reduction | $d = ($s ? 1 : 0) |
| anyv $d, $s | bitwise ANY Vector reduction | $d[3] = ($s[3]? 1 : 0);
$d[2] = ($s[2]? 1 : 0); $d[1] = ($s[1]? 1 : 0); $d[0] = ($s[0]? 1 : 0); |
| ld $d, $s | LoaD | $d = memory[$s] |
| li $d, immed8 | Load Immediate 8-bit signed value | $d = ((immed8 & 0x80) ? 0xffffff00 : 0) | (immed8 & 0xff) |
| jnz $c, $a | Jump if Non-Zero | if ($c != 0) goto $a |
| jz $c, $a | Jump if Zero | if ($c == 0) goto $a |
| morei $d, immed8 | MORE Immediate | $d = ($d << 8) | (immed8 & 0xff) |
| neg $d, $s | NEGate 32-bit integers | $d = -$s |
| negv $d, $s | NEGate Vector of 8-bit integers | $d[3] = -$s[3];
$d[2] = -$s[2]; $d[1] = -$s[1]; $d[1] = -$s[0]; |
| nop | Null OPeration; do nothing | |
| or $d, $s, $t | bitwise OR 32-bit integers | $d = $s | $t |
| pack $d[p], $s | PACK into byte positions p | $d[3] = ((p & 0b1000) ? $s[0] : $d[3]);
$d[2] = ((p & 0b0100) ? $s[0] : $d[2]); $d[1] = ((p & 0b0010) ? $s[0] : $d[1]); $d[0] = ((p & 0b0001) ? $s[0] : $d[0]); |
| shift $d, $s, $t | signed SHIFT left or right; multiply by 2$t | $d = (($t < 0) ? ($s >> -$t) : ($s << $t)) |
| st $t, $s | STore | memory[$s] = $t |
| unpack $d, $s[p] | UNPACK from byte positions p | $d = (((p & 0b1000) ? $s[3] : 0) +
((p & 0b0100) ? $s[2] : 0) + ((p & 0b0010) ? $s[1] : 0) + ((p & 0b0001) ? $s[0] : 0)); |
| sys | SYStem call | this does a bunch of things... |
| xor $d, $s, $t | bitwise eXclusive OR 32-bit integers | $d = $s ^ $t |
A few details about the above:
Determining how to encode the above instructions as bit patterns is a key part of your project. Given that some instructions have 3 registers specified, and each register requires 4 bits, it seems obvious that you'll have a 4-bit opcode field. However, there are actually 20 different types of instructions! Don't worry; you can still figure-out an encoding scheme. In fact, there are lots of different, perfectly reasonable, ways to encode this instruction set.
By now you're probably thinking that loQ Don is a pretty strange little instruction set. Well, it sort-of is. However, it's not as strange as you might think in that virtually every modern processor has SWAR support... and most are substantially more complex than this. However, that is not all the parallelism here. Remember how each instruction is only 16 bits long while data words are 32 bits wide? Well, later on you'll see that this instruction set is designed to make it easy to fetch two instructions each clock cycle for superscalar processing... but that's a topic for later in the course. :-)
The loQ Don instruction set only directly refers to 16 registers (although there might be more accessed by renaming). Just as in MIPS, each register has a number and a symbolic name. All those names should all be predefined using AIK's .const construct. In reality, only the first two registers are special in the hardware, but we have names and suggested uses for all 16:
| Register Number | Register Name | Read/Write? | Use |
|---|---|---|---|
| $0 | $zero | Read only | ZERO; constant 0x00000000 |
| $1 | $pc | Read only | Program Counter; address this instruction was fetched from |
| $2 | $sp | Read/Write | the Stack Pointer |
| $3 | $fp | Read/Write | the Frame Pointer |
| $4 | $ra | Read/Write | the Return Address |
| $5 | $rv | Read/Write | the Return Value |
| $6 | $u0 | Read/Write | User register 0 |
| $7 | $u1 | Read/Write | User register 1 |
| $8 | $u2 | Read/Write | User register 2 |
| $9 | $u3 | Read/Write | User register 3 |
| $10 | $u4 | Read/Write | User register 4 |
| $11 | $u5 | Read/Write | User register 5 |
| $12 | $u6 | Read/Write | User register 6 |
| $13 | $u7 | Read/Write | User register 7 |
| $14 | $u8 | Read/Write | User register 8 |
| $15 | $u9 | Read/Write | User register 9 |
Well, that's about it.
Your project is simply to design the instruction set encoding and implement an assembler using AIK. Here's a simple test case:
.text add $u4,$u5,$u6 addv $u4,$u5,$u6 TextTest: and $u4,$u5,$u6 any $u4,$u5 anyv $u4,$u5 jnz $u4,$u5 jz $u4,$u5 ld $u4,$u5 li $u4,1 morei $u4,1 neg $u4,$u5 negv $u4,$u5 nop or $u4,$u5,$u6 pack $u4[1],$u5 shift $u4,$u5,$u6 st $u4,$u5 sys unpack $u4,$u5[1] xor $u4,$u5,$u6 .word zero .word pc .word sp .word fp .word ra .word rv .word u0 .word u1 .word u2 .word u3 .word u4 .word u5 .word u6 .word u7 .word u8 .word u9 .word DataTest .word TextTest .data .word zero DataTest: .word pc .word sp .word fp .word ra .word rv .word u0 .word u1 .word u2 .word u3 .word u4 .word u5 .word u6 .word u7 .word u8 .word u9 .word DataTest .word TextTest
Obviously, I can't show you sample output without giving-away how I've encoded the instructions... but I can show you what things should look like after I've replaced the things that are up to you with "?":
//generated by AIK version 20070512 @0000 ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? 0000 0001 0002 0003 0004 0005 0006 0007 0008 0009 000a 000b 000c 000d 000e 000f 0001 0002 //end
//generated by AIK version 20070512 @0000 00000000 00000001 00000002 00000003 00000004 00000005 00000006 00000007 00000008 00000009 0000000a 0000000b 0000000c 0000000d 0000000e 0000000f 00000001 00000002 //end
The recommended due date for this assignment is before class, Friday, September 30, 2016. This submission window will close when class begins on Monday, October 3, 2016. You may submit as many times as you wish, but only the last submission that you make before class begins on Monday, October 3, 2016 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 loQDon.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.