Homework 5

22C:122, Fall 1999

Due Monday Sept 27, 1999, in class

1. Background: Consider the following simple idea for a stack machine such as the B 5000 or the Minimal CISC, keep the top 2 words, so we replace TOP with TOPA and TOPB. As a result, the ALU inputs are TOPA and TOPB, conditional branch uses TOPA for the destination address, conditional on the value of TOPB, and so on.

   Our goal by using 2 registers to hold the top 2 items on the stack is to cut down on the number of memory cycles when there is a sequence of operations that alternate push and pop. For example, to evaluate A + B + C, we'd do something like PUSHA, LOAD, PUSHB, LOAD, ADD, PUSHC, LOAD, ADD, and in theory, given the registers TOPA and TOPB, this can be done with no memory references other than those used to actually fetch the operands from the variables A, B and C.

   If we naively translate push(X) operation into "M[SP++]=TOPB; TOPB=TOPA; TOPA=X", and we translate pop() into "return(TOPA); TOPA=TOPB; TOPB=M[--SP]", we gain nothing! To make this scheme lead to an improvement, we need to keep a record of the state of TOPA and TOPB, and allow a pop to leave TOPA or both TOPA and TOPB vacant so that a push can be done without taking any memory cycles.

   As an aside, the Rockwell AAMP-2 had 4 registers in the CPU to hold the top items on the stack; thus giving the AAMP-2 even greater performance.

   Part A: One way to do this is to add a special 2-bit register to the CPU called TOPSTATE. If TOPSTATE is zero, TOPA and TOPB are both vacant. If TOPSTATE is one, TOPA is vacant and the top of stack is in TOPB. If TOPSTATE is two, TOPA is the top of stack, and TOPB holds the word below it. Rewrite the code describing the Minimal CISC CPU given about 1/3 of the way into the Minimal CISC notes so it uses this idea.

   Part B: Evaluate the impact of this improvement on the execution of the benchmark code shown about 3/5 of the way into the paper by counting instruction cycles required to execute one pass through the loop body with and without this improvement.

2. Background: Assume you have been given the job of designing an upgraded version of the Minimal CISC with 4 bits per instruction syllable. You have instrumented the C compiler for the Minimal CISC and found the following:
   • Approximately half of all "macro operations" issued by the compiler are operations to push immediate constants on the stack.
   • Approximately half of all immediate constants are small integers. The values -1, 1 and 2 are most common. 5, 9, 10, 3, 4 and 12 are very common. Numbers like 20, 30, 32, 64 and 100 stand out a bit from the background, but about half of all immediate constants are random 16 bit integers representing memory addresses.
   • Approximately 1 in 3 "macro operations" is an arithmetic operation, with add twice as likely as subtract, and with negate and subtract about equally likely. Logical operations such as and, or, not, and xor are common enough to be worthy of consideration.
   • Branches make up about 1 in 6 "macro operations." Half of all branches are unconditional. Of the remainder, about half are tests for equality or inequality, while the remainder involve magnitude comparisons.

   A Problem: Given what you know about efficient instruction encoding, propose how you would use the 4-bit instruction syllables of our modified machine. Note that for operations with a likelyhood of less than 1/16, you should use multiple syllables to encode the operation, and you may use fractions of syllables as well as entire following syllables for operand fields.