CSE410		HOMEWORK #4		Due: Thursday, May 1 

1. Assume a 2-address machine, multiple general purpose registers, and all
types of operand addressing (direct, immediate, indirect, and base
displacement).  Each memory and register cell is large enough to hold an
integer or memory address.  The architecture supports the instructions:

	move, comp, br, beq, blt, bgt, bne, bge, ble, add, sub, lshift, and
rshift

where COMP compares its two operands and stores the results of the
comparison in a hidden register (condition code) for future use by a
conditional branch, BR is an unconditional branch, and BEQ, BLT, BGT, BNE,
BGE, and BLE are conditional branches with one operand such that the branch
is taken if the results of the most recent comp operation are equal, less
than, greater than, not equal, greater than or equal, and less that or
equal, respectively.

You are given an array A of integers, sorted in ascending sequence.  A is
stored in sequential locations in main memory.  Write an assembly language
program that performs a binary search over A, looking for a given value x.  
If x is not in A, your program should leave the integer 0 in a register.  
If x is in A, then the program should leave a 1 in the register and the
address, say adr, such that A[adr]=x in a memory location called match (in
assembly language).

Assume that the first element of A is stored in A_start, that size contains
the number of elements in A, and that x, the value for the search, is stored
in value.

2. Consider Figures 6.2 and 6.3 on page 439 of PH, and the load word (lw)
instruction of MIPS.  Suppose that a clever designer manages to combine the
last two components of the instruction cycle (Data access and Register
write) into one component (call it DARW) that takes 2 ns to complete; i.e.,
a lw instruction will now have 4 components, Instruction fetch, Register
read, ALU operation, and DARW, and will take a total of 7 ns.

 (a) Redraw both parts of Figure 6.3 assuming this new design.

 (b) What is the approximate speed-up under ideal conditions in a pipelined
execution?  Show your work.