CSE 141L Project 1: 9-Bit Instruction Set Architecture

Due Thursday, August 17th at the beginning of class.

Introduction

You will design the instruction set and write three programs for a new processor. The processor and instruction set will be optimized for a few specific tasks. In addition to a complete instruction set design, you will write the assembly and machine-language code – using your custom ISA – which implements the specified tasks. (You will design and test the hardware for your new processor in subsequent projects.)

Your ISA

We are setting several constraints on your design in advance, the first of which is: your ISA must feature fixed-width instructions, each of which is 9 bits wide. Given this extreme limit on instruction bits, the target programs and their needs should be considered carefully. The best designs will come from an iterative process of designing an ISA, coding the programs, identifying opportunities for changing the ISA to simplify either the programs or implementation, and then redesigning the ISA.

Your ISA specification must describe:

• What operations it supports and what their opcodes are.
• How many instruction formats it supports and what they are, in detail: how many bits for each field, where they're found in the instructions, and how to determine from an encoded instruction which format it uses. (Your instruction format description should be detailed enough that someone could write an assembler for it.)
• Number of registers, their names, and which are (if any) are specialized. Register storage will be 8 bits wide.
• The size of main memory. Main memory will be byte-addressed, with individual locations 8 bits wide. (Instruction memory will be separate.)
• Addressing modes supported, both for memory and branch instructions: how are addresses constructed/calculated?

In order to fit this all in 9 instruction bits, the memory demands of these programs will have to be small. However, for the programs you are going to run, you may not need that much. You should consider how much data space you will need before you finalize your instruction format. You can assume that instructions are stored in a separate memory from program memory, so that your data addresses need only be big enough to refer to the data you will use. The target programs are simple enough that your ISA probably won't need procedure calls and stack pointers. Main memory will be byte addressable, so your memory instructions will read or write exactly 8 bits at a time.

You will implement this ISA as a "single-cycle" processor, so realize that there is a limit to what can be done in a single cycle. In particular, you will assume single-ported data memory, which can only perform one read or one write per cycle, but not both. You will also assume a register file – or whatever internal storage you support – that can only write one register per cycle. (It will, of course, be able to read more than one register per cycle.) You may include up to 4 single-bit "condition-code" or "flag" storage locations, if you desire.

You must have a "halt" instruction in your ISA. This instruction has no operands, it simply instructs your processor to stop doing anything further.

Your ISA and processor will be specialized to perform three different tasks; you will write three programs in your ISA to accomplish these tasks. To simplify the ISA design process, you need only optimize for the following two goals:

1. Minimize the dynamic instruction count – that is, the number of instructions executed, including repeated instructions – of the programs.
2. Simplify the hardware required to implement your ISA.

There is clearly some tension between these two goals; goal #1 takes precedence, and is where you'll have an opportunity to distinguish your design (and resultant grade!). Goal #2 is still significant, however: designing instructions which are too complex for to implement and debug in time for the relevant deadlines will be disastrous.

We'd really like you to innovate, here: while the MIPS ISA shown in the text is informative and provides a decent starting point, you should do more than simply implement a general-purpose "mini-MIPS". See the "hints" section for more detail. Mini-MIPS can function, but won't lead to an impressive grade.

You will write and run three programs. You can assume each starts at instruction address 0, or you can assume that the first starts at 0, and the other two are found in memory after the end of the first program. However, the specification of your branch instructions may depend on which approach you take (where in instruction memory particular programs reside).

Report (Required!)

You must turn in a printed project report which is no more than eight pages long (excluding the program listings). Be sure to list the names of everyone in your group. The report must answer the following questions. In describing your architecture, keep in mind that the person grading it has much less experience with your ISA than you do, so describe things clearly.

For this project, your writeup is to be organized as follows. In addition to the directives, be sure to answer each explicit question:

1. Introduction. This should include the name of the architecture, overall philosophy, specific goals you've strived for, and which you've achieved.
2. Instruction formats. Give all formats and an example of each.
3. Operations. Give all instructions supported and their opcodes/formats.
4. Internal operands. How many registers are supported? Is there anything special about any of the registers?
5. Control flow (branches, jumps). What types of branches are supported? What branch conditions are supported? How are the target addresses calculated? What is the maximum branch distance supported?
6. Addressing modes. What addressing modes are supported? How are addresses calculated (including instruction addresses for branches)? Give examples for each addressing mode.
7. How large is the main memory?
8. In what ways did you optimize for dynamic instruction count? (Goal #1)
9. In what ways did you optimize for ease of design? (Goal #2)
10. If you optimized for anything else, what and how? (It's fine if you didn't.)
11. Your chief competitor just announced a load-store ISA, in which instructions have two explicit operands (so one source register is also the destination), four registers (i.e., a 2-bit register specifier), and 32 instructions (5 opcode bits). Tell me why your ISA is better.
12. What do you think will be the bottleneck in your ISA, if you were to use it for general-purpose programming? That is, which features (operations, addressing modes, etc.) that are not present in your design which you would miss the most, if you were to have to write other (longer) programs?
13. • (a) What would you have done differently if you had two more bits for each instruction (i.e., a 11-bit fixed-width ISA)?
    • (b) Two fewer bits?
14. Can you classify your machine in any of the classical ways (e.g., stack machine, accumulator, register, load-store)? If so, which? If not, give me a name for your new class of machine.
15. Give an example of an "assembly language" instruction in your machine, then translate it into machine code.

For questions 16-18, show assembly instructions, written in your ISA, which implement each program. Make sure your assembly format is either very obvious or well described, and that the code is well commented. If you also want to include machine code – the numerical translation of each assembly instruction – the effort will not be wasted, since you will need it later. (We will not correct/grade the machine code at this time, but when your processor is completed, it will need to execute your machine code and produce the correct outputs.)

State any assumptions you make. You cannot assume anything about the initial values in registers or data memory, other than those specifically given, when the program starts.

16. Program 1: Population count
    

    Write a program using your ISA that counts the number of "1" bits in an array, A. The array A begins in memory at byte address 32, and is 16 bytes long. Store the resulting count at memory location 2, as an unsigned eight-bit integer.

    16(b): What is the dynamic instruction count of this program if the value if the entire array is filled with zero-bytes? What is the dynamic instruction count if every byte of the array contains the value 0xAA?

17. Program 2: Word count
    

    Write a program using your ISA which counts the number of words (of text, not MIPS words) in a C string containing ASCII text. The string begins at memory address 51, and is variable in length. The string will not be longer than 60 characters (61 including the terminator), however you may not assume anything about the values following the terminator.

    Update: store the computed word count at memory location 4, as an unsigned eight-bit integer.

    For this program, a "word" is defined as a nonempty sequence of characters which contains no whitespace characters. The whitespace characters are:

    • 0x09: horizontal tab
    • 0x0A: newline
    • 0x0B: vertical tab
    • 0x0C: form feed
    • 0x0D: carriage return
    • 0x20: space

    Everything which is not whitespace, is considered a word character. C strings are terminated by a zero-byte, which does not count as either a "word" or a "space". So, your program will alternate between scanning for the start of a word, and then scanning for the end of that word, while watching for a terminating zero-byte the whole time. Example memory contents and word counts:

    Memory bytes (hex)	ASCII	Word count
    00	(empty string)	0
    09 20 00	(tab, space)	0
    23 2E 24 2A 00	#.$*	1
    0A 31 34 31 4C 20 46 54 57 20 21 00	(newline)141L FTW !	3

    17(b): What is the dynamic instruction count of this program, on the first and last example inputs?

18. Program 3: IPv4 header checksum
    

    Write a program in your ISA which computes the checksum for an outbound IPv4 packet, and stores it into the packet. The packet header begins at memory address 128; assume that it is 20 bytes long, and is valid.

    The IPv4 header checksum is based on a 16-bit, "one's complement" sum of the header, taken 16 bits at a time. The checksum itself is located at bytes 10 and 11 of the header; set those bytes to zero before beginning the computation.

    The steps to compute the checksum are:

    1. Store zeros to the checksum field of the header. That is, store zeros to header bytes 10 and 11 (memory addresses 138 and 139).
    2. Initialize a 16-bit variable, "sum", to zero.
    3. For each 16-bit value in the header:
       • Read in the next 16-bit value, most-significant-byte first.
       • Add that value to "sum", using a conventional 16-bit add. Consider the inputs and outputs unsigned.
       • Iff there is a carry-out (unsigned overflow) from the 16-bit addition, increment "sum" by adding 1 to it.
    4. After the entire header has been read, invert all of the bits of "sum".
    5. The checksum is now computed. Store it into the packet: store the high 8 bits of "sum" at byte 10 of the packet (address 138), and the low 8 bits at byte 11 (address 139).

    As a detailed example, we will compute the checksum for the following IPv4 header, which was captured from a machine attempting to contact Google (byte values are in hex):

    45 00 00 3C CE 2C 40 00 40 06 XX XX 84 EF 11 2E 42 66 07 63

    The checksum bytes are indicated in bold, and are shown as "XX" to indicate that we don't care what they are when we begin. First, we'll zero out the checksum field:

    45 00 00 3C CE 2C 40 00 40 06 00 00 84 EF 11 2E 42 66 07 63

    Next, we'll walk through the header, adding to "sum": (Values shown are in hex.)

    Initial "sum"	Next 16	"sum" after add	Carry out past 16?	"sum" after carry-adjust
    0000	4500	4500	No	4500
    4500	003C	453C	No	453C
    453C	CE2C	1368	Yes	1369
    1369	4000	5369	No	5369
    5369	4006	936F	No	936F
    936F	0000	936F	No	936F
    936F	84EF	185E	Yes	185F
    185F	112E	298D	No	298D
    298D	4266	6BF3	No	6BF3
    6BF3	0763	7356	No	7356

    Finally, we'll invert the final value of "sum" – swapping the "0" and "1" bits – and store it. We compute NOT 0x7356 as 0x8CA9, which we then store into the packet:

    45 00 00 3C CE 2C 40 00 40 06 8C A9 84 EF 11 2E 42 66 07 63

    The packet is now ready to transmit!

    18(b): What is the dynamic instruction count of your program, on this example packet?

Hints

• When designing your ISA, after reading the descriptions of the specific tasks your processor will perform, keep an eye out for opportunities for using special-purpose instructions to help out with goal #1. For example: suppose a program needed to calculate "(int)floor(log2(x))", where "x" is an integer value. One might soon realize that, given a binary integer representation of "x", one could compute the result by determining the left-most binary digit containing a "1". From this, straightforward code could consist of a loop which repeatedly shifts and tests a copy of "x" until the appropriate digit is identified. Upon reflection, however, a clever designer might realize that they could easily add hardware which, given an 8-bit integer, would directly output the index of the left-most "1" bit! This hardware, utilized by a special "int-floor-log2" instruction, would collapse dozens of conventional machine instructions into a single operation.
• Keep your instructions reasonably simple. For every instruction you include, you will eventually need to design a combinatorial logic block which implements that instruction within the register and memory constraints given above. So, if you're considering including an exotic instruction which, for example, measures the length of a string, or tests the primality of a number: stop and make sure you can sketch out a feasible implementation now, before it's too late.
• The IPv4 header checksum may look intimidating, but it's really just a bunch of 16-bit adds. The trick will be in accomplishing 16-bit adds with your 8-bit processor. (Note that this isn't the only way to compute a one's complement sum; if you're interested, RFC 1071 shows several others.)