Assignment 1: Assembling The Gr8BOnd

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 Spring 2020 CPE480. However, this design is not complete -- each student must devise their own encoding of the instructions and implement their own assembler using AIK. The instruction set architecture specification for Spring 2020, missing the instruction encoding, is Gr8BOnd (pronounced "Great Beyond").

Overview Of The Instruction Set

Each semester's processor ISA has at least a few interesting features. Here's what's special in the Gr8BOnd:

• First and foremost, Gr8BOnd is intended to be an experiment in implementation of posit arithmetic -- an alternative to floating point. Only a few hardware designs for posit arithmetic are in the open literature, and as of February 2020, we have found no implementations of complete processors. The closest is Deep Positron: A Deep Neural Network Using the Posit Number System, which was posted January 19, 2019, and is a "soft core" design intended to be used to implement a neural network accelerator in an FPGA. There is a significant possibility that the projects implementing Gr8BOnd might result in a research publication for the class....
• Gr8BOnd is a SWAR (SIMD Within A Register) design, implementing both scalar and SIMD/vector arithmetic. Ok, the vectors are just 16 bits long containing two 8-bit values, but that's still giving you the experience of dealing with hardware design for vectorized operations. SWAR is very common in modern processor designs, but it's not something commonly seen in computer architecture course projects.
• Gr8BOnd has an unusual way of dealing with constants. In particular, it has the notion of a constant vector handled by the cii instruction.

Of course, there are also the not-so-special choices made in the Gr8BOnd ISA:

• It's a 16-bit machine. Addresses are 16 bits long, data are 16 bits long (even if they're a pair of 8-bit values), each instruction is encoded in 16 bits, and each memory address or register holds a 16-bit word.
• There are separate code (.text) and data (.data) memories, each able to hold 65536 16-bit words. Neither memory is byte addressed.
• To maximally leverage the 16-bit SWAR structure, Gr8BOnd recognizes four data types. That's a record number of data types for a CPE480 project, so it's a large part of what you'll be dealing with in designing the hardware... but not in this assignment, where you'll just build an assembler. Many of instructions have a suffix that tells you the data type they work on: i for a 16-bit signed integer, ii for a pair of 8-bit signed integers, p for a 16-bit posit value, and pp for a pair of 8-bit posit values. Incidentally, your assembler will not understand encoding of posit values: each posit value will have to be entered as an integer bit pattern, e.g., in binary or hexadecimal.
• There are sixteen general-purpose 16-bit registers, numbered 0-15. Register names start with a $, so $5 is register five... and so is $2+3. Several of the registers have recommended uses, such as $15 being $sp (the stack pointer), but they're all ordinary registers that can be read or written.
• No instruction takes more than two operands. Binary operations, such as addi, take two register names and the first is both a source and the destination. Unary operations, such as not, only take a single register operand. The various ways to load constant values, such as ci8, all take a destination register and an 8-bit immediate constant. The two branch instructions, bnz and bz, take a register to test and a 16-bit address to branch to; however, the address should be encoded in the instruction as an 8-bit offset computed as "address-.". Oh yeah, the trap instruction takes no arguments.

So, you basically start by looking at the list of Gr8BOnd instructions and grouping them together by how you want to encode them. Think about where the register numbers, 8-bit constants, and opcode will go within an instruction word. Each group of instructions can then be written-out as one pattern per instruction type -- or you could use .alias and have just one pattern per group of similarly-encoded instructions. Either way, it's really quite straightforward.

That's about all there is to it... well, almost....

Pseudos

Most assembly pseudo-instructions for Gr8BOnd can simply use the AIK defaults. You don't need to worry about things like renaming .equate. For example, .word is used for allocating an initialized 16-bit word and .origin is used for setting the location counter in the currently active segment. Of course, don't forget to define the two segments and define the register names using .const.

However, the table of Gr8BOnd assembly language instructions given here also includes four things that look like instructions, but aren't. They're the ones where the functionality says "by shortest sequence of instructions." Like the MIPS li pseudo-instruction, each of these are supposed to generate the shortest possible implementation using one or more of the "real" instructions. In effect, they're span-dependent instructions, generating a variable-size encoding depending on the operand value. The first is ci $d,c16, in which c16 is a 16-bit constant value. Depending on that value, there are several possible encodings:

• If c16 has the top 9 bits either all 0s or all 1s, then sign-extending the low 8 bits will get you the value in a single ci8 instruction.
• If the top 8 bits of c16 match the bottom 8 bits, then a single cii can load the value.
• If neither of the above cases applies, it will generally take a sequence of two instructions. Any 16-bit value can be loaded into a register by first getting the correct value in the bottom 8 bits, which can be done using either a ci8 or cii (you don't care which because you'll be overwriting the top 8 bits next). To set the top 8 bits correctly, simply use a cup instruction.

Keep in mind that bits don't have types -- operations on them impose typed interpretations of the bit patterns. As long as the bit pattern in the register ends up as it should be, for example, one could perfectly well use a ci8 to load a pair of 8-bit posit values.

The three other pseudo-instructions are all types of jump instruction, jmp, jnz, and jz. Depending on the 16-bit target address, each of these pseudo-instructions can take from one to four instructions to implement:

• It should be obvious that a jnz or jz can be implemented using the corresponding bnz or bz if the target address is in range. Perhaps less obvious is how to do an unconditional jmp using a branch instruction when there isn't an unconditional branch instruction? Well, the stack pointer, $sp, better not be pointing at memory location 0 -- so, bnz $sp,addr is essentially an unconditional branch. Yeah, I know that's sneaky. ;-)
• If the target address of a jmp isn't within branch range, you'll need to load a register with the target address and then use a jr to jump to that register. That requires an extra register, for which you should use $at, so the jump will end with a jr $at. The fun thing is that loading the address into $at can be done in any of the three ways used to implement ci! Yup; if you think about it, you'll need four separate patterns for AIK to pick between for coding a jmp addr (with appropriate ... definitions):

  bnz $sp,addr
  
  ci8 $at, ... 
  jr $at
  
  cii $at, ... 
  jr $at
  
  cii $at, ... 
  cup $at, ... 
  jr $at
  

• If the target address of a jnz or jz isn't within branch range, you've got a problem because there isn't a conditional jump. So, instead you'll branch over the unconditional jump sequence using the opposite condition. Again, there are a total of four possible patterns, but these can be up to four instructions long! For example, a jnz $reg, addr could become any of (with appropriate ... definitions):

  bnz $reg, addr
  
  bz $reg, .+3
  ci8 $at, ... 
  jr $at
  
  bz $reg, .+3
  cii $at, ... 
  jr $at
  
  bz $reg, .+4
  cii $at, ... 
  cup $at, ... 
  jr $at
  

Keep in mind that the way AIK specifies pattern right sides doesn't look like assembly instructions, but a list of field values and sizes. To output a sequence of two instruction bit patterns, you need to list values for twice as many (32 bits total) on the right side of the pattern. The pattern that generates four words worth of instructions thus specify values for a total of 64 bits on the right hand side.

Ok, I imagine about now you're looking at the above and wondering what a nightmare this is going to be. Well, they will require a few long lines of AIK specification. To be precise, ci will take three AIK patterns to implement, jmp will take four, and jnz and jz can share four more patterns (if you alias them appropriately). So, we're really talking about as little as 12 lines of AIK specification for all the span-dependent pseudo-instructions. That said, get your assembler working without these pseudo-instructions first. You can still get a good grade if these aren't implemented, but not if the core instruction set doesn't work....

Your Project

Your project is simply to design the instruction set encoding and implement an assembler using AIK. Here's a simple test case:

	.text
start:
	addi	$1, $2
	addii	$1, $2
	addp	$1, $2
	addpp	$1, $2
	and	$1, $2
	anyi	$1
	anyii	$1
	bnz	$1, place
	bz	$1, place
	ci8	$1, 42
	cii	$1, two
	cup	$1, 42
	i2p	$1
	ii2pp	$1
	jr	$ra
place:	ld	$1, $2
	muli	$1, $2
	mulii	$1, $2
	mulp	$1, $2
	mulpp	$1, $2
	.data			; switch to data segment
	.word	42
	.word	601
two:	.word	480
	.text			; back to text segment
	negi	$1
	negii	$1
	not	$1
	or	$1, $2
	p2i	$1
	pp2ii	$1
	shi	$1, $2
	shii	$1, $2
	slti	$1, $2
	sltii	$1, $2
	st	$1, $2
	trap
	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.... Honestly, testing your assembler is virtually impossible; it'll be easy when you have Verilog code implementing the machine to execute these instructions, but not now. So, make sure that the logic behind your encoding is clear, either by the structure of your AIK code or by actual documentation of your reasoning in your Implementor's Notes. Make the TA's grading job easy.

Due Dates

The recommended due date for this assignment is before class, Wednesday, February 19, 2020. This submission window will close when class begins on Friday, February 21, 2020. You may submit as many times as you wish, but only the last submission that you make before class begins on Friday, February 21, 2020 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 AIK source file gr8bond.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).