Part A: Use the Iowa Logic Specification Language to describe the extended version of the exclusive OR gate documented in section 6 of the notes for lecture 10.
circuit xxor; -- extended xor
inputs
a, b, -- the normal inputs to an xor gate
aenab, benab, xenab; -- function control inputs
outputs
out;
parts
agate, bgate, xgate: nand(3);
outgate: nand(2);
wires
a to agate.in(1), xgate.in(1);
b to bgate.in(1), xgate.in(2);
aenab to agate.in(2);
benab to bgate.in(2);
xenab to xgate.in(3);
xgate.out to agate.in(3), bgate.in(3);
agate.out to outgate.in(1);
bgate.out to outgate.in(2);
outgate.out to out;
end;
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.
-- inputs are a,b,aenab,benab,xenab in that order
-- output always low
00000
01000
10000
11000
-- output always low
00001
01001
10001
11001
-- pass b
00010
01010
10010
11010
-- pass b and not a
00011
01011
10011
11011
-- pass a
00100
01100
10100
11100
-- pass a and not b
00101
01101
10101
11101
-- pass a or b
00110
01110
10110
11110
-- pass a xor b
00111
01111
10111
11111
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.
Script started on Fri Mar 2 14:37:14 2001
jones@tempest [101]% bin/logicsim
IOWA Logic Simulator, Ver. 10
Source file name: t
======================================================================
circuit name = xxor
input interval = 1.0us If you need help, type h.
output interval= 500ns
----------------------------------------------------------------------
TIME:OUTPUTS :INPUTS
----:------- :------
500:out : a
ns : | : |b
: | : ||aenab
: | : |||benab
: | : ||||xenab
: | : : |||||
======================================================================
0:| :INPUT: r t.vec
0:|- :INPUT: -- inputs are a,b,aenab,benab,xenab in that order
1:| : : 00000
2:| :INPUT: -- output always low
3:| : : 00000
4:| :INPUT: 00000
5:| : : 00000
6:| :INPUT: 01000
7:| : : 01000
8:| :INPUT: 10000
9:| : : 10000
10:| :INPUT: 11000
11:| : : 11000
12:| :INPUT: -- output always low
13:| : : 11000
14:| :INPUT: 00001
15:| : : 00001
16:| :INPUT: 01001
17:| : : 01001
18:| :INPUT: 10001
19:| : : 10001
20:| :INPUT: 11001
21:| : : 11001
22:| :INPUT: -- pass b
23:| : : 11001
24:| :INPUT: 00010
25:| : : 00010
26:| :INPUT: 01010
27:|_ : : 01010
28: |:INPUT: 10010
29: _|: : 10010
30:| :INPUT: 11010
31:|_ : : 11010
32: |:INPUT: -- pass b and not a
33: |: : 11010
34: |:INPUT: 00011
35: _|: : 00011
36:| :INPUT: 01011
37:|_ : : 01011
38: |:INPUT: 10011
39: _|: : 10011
40:| :INPUT: 11011
41:|- : : 11011
42:| :INPUT: -- pass a
43:| : : 11011
44:| :INPUT: 00100
45:| : : 00100
46:| :INPUT: 01100
47:| : : 01100
48:| :INPUT: 10100
49:|_ : : 10100
50: |:INPUT: 11100
51: |: : 11100
52: |:INPUT: -- pass a and not b
53: |: : 11100
54: |:INPUT: 00101
55: _|: : 00101
56:| :INPUT: 01101
57:| : : 01101
58:| :INPUT: 10101
59:|_ : : 10101
60: |:INPUT: 11101
61: _|: : 11101
62:| :INPUT: -- pass a or b
63:| : : 11101
64:| :INPUT: 00110
65:| : : 00110
66:| :INPUT: 01110
67:|_ : : 01110
68: |:INPUT: 10110
69: |: : 10110
70: |:INPUT: 11110
71: |: : 11110
72: |:INPUT: -- pass a xor b
73: |: : 11110
74: |:INPUT: 00111
75: _|: : 00111
76:| :INPUT: 01111
77:|_ : : 01111
78: |:INPUT: 10111
79: |: : 10111
80: |:INPUT: 11111
81: _|: : 11111
82:| :INPUT: q
Simulation ends.
jones@tempest [102]%
script done on Fri Mar 2 14:37:54 2001
We can construct an "average" basic block as follows:load load immediate operate store -- one average assignment statement load load immediate operate store -- another average assignment statement load load immediate compare conditional branch -- one average conditional exit load load immediate operate store -- another average assignment statement unconditional branch -- half the blocks end with thisSo, assuming a load-store architecture, half of the basic blocks are 16 instructions long, of which one is a conditional, and the other half have an unconditional branch at the end. (note that if the final exit from the block is not by a fall through, it must be by an unconditional branch).So, to a first approximation, 1/16 of all instructions are conditional or branches (4 bits of opcode is about right to indicate this), and about 1/32 of all instructions are unconditional branches (5 bits of opcode is about right to indicate this).
Part B: How many bits per memory reference instruction should be devoted to the absolute address of a simple variable referenced?
We are told that the average program references about 32 distinct simple variables, so a 5 bit memory address field will suffice for most programs. There will, of course, have to be some way to address more variables in those rare programs that have more.
Part C: How many bits per instruction should be devoted to indicating that the instruction is a store instruction.
The average basic block constructed to help answer part A had about 16 instructions, of which 3 were store instructions. So, about 3/16 of all instructions will be store instructions. This suggests allocating no fewer than 2 and no more than 3 bits to the opcode indicating store. Alternately, we could imagine allocating 3 distinct 4-bit opcodes to different flavors of the 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.
We know that 1/2 of all memory references involve simple variables, so one bit will distinguish this case from others. 1/4 are subscript references (indexed addressing), requiring 2 bits, and 1/8 have a field selection operator, requiring 3 bits.If we've set aside 3 of 16 4-bit opcodes for store operations, it would make almost equal sense to use one for each addressing mode or to use two for simple variables and to use the other for the rarer addressing modes.
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.
The 16-bit ultimate RISC with 16 arithmetic operations on each of 16 registers uses almost a full 16 bits for each simple variable reference, while 5 would be sufficient. It uses 16 additional bits to load, add to or store any of the accumulators, far more than the 4 to 6 bits we can justify for distinguishing a direct load or store operation. Branches are similarly inefficient, with a 16 bit destination address used to identify the operation as a branch, when we can only justify 4 or 5 bits. The logic of conditional branches takes an entire extra 32 bit instruction, yet conditional branches are actually more common than unconditional branches according to our statistics! In sum, the ultimate RISC is a pretty miserable machine, even with a decent multiple register ALU.