Homework 5

22C:122/55:132, Spring 2001

Due Friday Feb 16, 2001, in class

1. Background: Consider the multifunction ALU listed in section 6 of the notes for lecture 10 (Feb 9).

   Note, the purpose of this assignment is to get you started using the logic simulator to deal with something simple. You will have to create two files and run the simulator with both as input (one file describes a circuit, the other contains input to that circuit).

   Part A: Use the Iowa Logic Specification Language to describe the extended version of the exclusive OR gate documented in the notes (with enable inputs Aenab, Benab and Xenab as well as the usual A and B inputs).

   Part B: Construct a test vector (file of test inputs) for this circuit documented with comments indicating the outputs you expect each input line to produce.

   Part C: Turn in the output resulting from submitting your circuit to the logic simulator with your input data. The UNIX script command is one way to create a transcript for later printing of an entire session using the simulator.

2. Definition: Any program can be broken into a sequence of basic blocks. A basic block is a block of instructions with a single entry point (the first instruction in the block) and any number of exit points. All but the final exit point may be by a conditional branch. The final exit point is always unconditional, either an unconditional branch or a fall-through into the next block.

   Background: Consider the following information to be factual (in fact, it is made up for the purpose of this assignment):

   • The average basic block contains 3 assignment statements.
   • The average basic block contains 2 exit points.
   • Half as many basic blocks have n+1 exit points as have n.
   • Half of all final exit points are by fall-through.
   • The average assignment has 2 source operands and one destination.
     • Half of all source operands are constants.
     • Addition is twice as likely as subtraction.
     • Subtraction is twice as likely as multiplication.
     • Multiplication is twice as likely as division.
   • The average boolean expression on a conditional has 2 operands.
     • Comparison for equality is twice as common as greater-than.
     • Greater-than is just as common as less-than or not-equal.
   • Half of all memory reference operands are simple variables.
   • The average program references about 32 distinct simple variables.
   • 1/4 of memory references involve subscript expressions.
   • 1/8 of memory references involve record field selection.
   • 1/8 of memory references involve following pointers.

   Part A: How many bits per instruction should be devoted to distinguishing branch operations from other operations?

   Part B: How many bits per memory reference instruction should be devoted to the absolute address of a simple variable referenced?

   Part C: How many bits per instruction should be devoted to indicating that the instruction is a store instruction.

   Part D: In addition to part C, how many bits of each store instruction should be devoted to distinguishing between the different addressing modes a store instruction might use.

   Part E: Write briefly but convincingly about the optimality of the instruction coding of the Ultimate RISC, assuming a 16 bit word, and assuming 16 registers and 16 ALU operations. Quantitative comparisons with some of the results from parts A through D may be useful in supporting your conclusions.