Due: Thursday, Feb. 9
1. FSM (15 points)
The combination of the lock to the K-Lab has been changed to 1 1 2 35 (3 and 5 are pressed simultaneously). Where the three and five must be pressed together. You are to design the finite state machine that will open this lock. The state machine has five inputs B1 thru B5 one output O. Write the state machine that sets O to 1 whenver this sequence is pressed in that order. Label each state and write out the equation for that state in terms of inputs and other states. You can write the equations symbolically, i.e., using symbols for inputs and state names like B5 and S1 rather than some binary encoding.
2. + (15 points)
Consider the following three implementations for a 16-bit adder:
For each adder, what are the gate delays of each one of the 16 sum bits (0 thru 15)?
3. ++ (15 points)
Integer adders are very useful in processors, but so are incrementers, adders in which one of the inputs is a constant. For instance, the circuit that computes the default next PC is an incrementer: +4 in MIPS, +1 in P37X. Incrementers are interesting because they can be optimized even more so than conventional adders.
Assume you are to design a 16-bit +1 incrementer, by setting the carry-in signal to 1, and then assuming that one of the inputs (e.g., B) is zero. Draw the gate-level diagram (or write the equations) for a "full-incrementer" (the incrementer equivalent for a full adder), a 2-bit CLA incrementer block and a 4-bit CLA incrementer block. Repeat the calculations from question 2 for each of the three different implementations of incrementer.
4. * (10 points)
Trace out the steps for the "addition-only" algorithm (the 3rd version in which the product register is shifted right) and the "modified Booth's" algorithm for the 8-bit multiplication of 55 and -93 with -93 as the multiplicand. In each step, write out (in binary) the contents of the product/multiplier register and the addend (the amount being added in). Also, label the action in each step (e.g., P = (P+A)>>1 or P=P>>1.
5. / (5 points)
Divide 104 by 7 using the 2nd version of the division algorithm. Show the remainder/quotient register and the addend in each step and label the actions. Again, use 8 bits.
6. P37X (40 points) This part due: Wednesday, Feb. 15 (midnight)
Now that you have written the worm game, you will write a second little P37X program that will exercise a different part of the OS and force you to think about a different set of programming idioms and algorithms.
In this assignment, you will write a simple, accumulator style integer calculator program calc. calc will be entirely console based; it will not use the display. Here are the skeleton codes for the application and the OS. These files are also in :eniac:~amir/cse371/p37x-code/calc/.
An "accumulator-style" calculator has a single memory location which holds
the most recently computed value. In calc, this location is called ACCUMULATOR. calc executes the following loop. It prints the string
"calc" followed by the current
value of ACCUMULATOR and then
waits for input. There are two possible valid inputs. The null input (just
hit return) causes calc to
print the string "bye!" and
exit. The other possible input is a string that obeys the expression +|-|*|/ [-]d*, i.e., one of the four
basic arithmetic commands, followed by a space, followed by some integer which
may be negative. If this is the string, calc performs the specified operation on ACCUMULATOR and stores the result in
ACCUMULATOR and loops. If
calc doesn't understand the
command, it prints "error!"
without modifying ACCUMULATOR.
Here is a sample calc
transcript (output is in bold).
calc 0 + 25
calc 25 * -2
calc -50 / -5
calc 10
bye!
For this assignment, you have to write two OS routines, three application routines, and complete the main application loop.
The OS routines you must write are GETS and EGETS, which read unechoed and echoed strings from the console respectively. The end of a string is recognized by the appearance of the linefeed character (x000A).
Because of some confusion having to do with nested TRAP calls in the first assignment (actually the problem is not with nested TRAP calls per se, it is with nested RTT, but anyway), I've changed the way the OS works and you can look to see how the existing TRAP implementations have been restructured in calcos.asm. To allow OS routines to call one another, I replaced the register save area with an explicit OS stack. OS routines are now prefaced by OS_ and simply use the OS stack; they can be called from within other OS routines using JSR and they return using JUMPR. Each OS routine that can also be "called" from user code has a trap wrapper that starts with TRAP_. All trap wrappers are the same: they save the user return address and stack pointer, switch the stack pointer from the user stack to the OS stack, call the corresponding OS function, and when it returns restore the user stack pointer and return address and do a "return from trap". This is the way actual OS code works. Anyway...
The three application routines you have to write are DIV (divide, P37X doesn't have a divide instruction), ATOI (ascii-to-integer, a function that converts a decimal string to an integer), and ITOA (integer-to-ascii, a function that converts an integer to a string, and which is trickier to implement than first glance might suggest). All of these functions should handle both negative and positive numbers. Note, for DIV you don't have to implement it the "hardware" way with shifts and masks (that would be doable, but difficult considering you don't have instructions that can operate on 32-bit shift registers). You can implement division the "software" way using loops and subtraction.
Here is an update version of PennSim.jar (it has some bug fixes and it supports the .STRINGZ directive correctly).
Clarifications: The point of this exercise is to get you to understand the algorithms for binary-to-decimal and decimal-to-binary conversions, get you familiar with a different style of OS code programming (one that uses an explicit OS stack), and get you some more practice with assembly idioms. The point is not to teach you to write industrial strength code in assembly. In DIV, you should handle the divide-by-0 case in some way other than going into an infinite loop (e.g., returning 0, HALTing, or printing an error and returning the dividend), but for ATOI you don't have to handle badly formatted decimal strings, or 16-bit overflow, and in GETS and EGETS you can handle input strings longer than the supplied buffer in any way you want as long as you don't overflow the buffer itself, e.g., you can drop the additional characters, you can print an error and return the null string, you can stop reading characters when you get to the end of the buffer and leave them in the queue for the next call to GETS or EGETS. Whatever. Your code will not be tested for behavior on illegal inputs.