EECS 31/CSE 31/ICS 151 Homework 8 Questions with Strategies

View Questions Only
View Questions with Solutions

Problem 1

Question

(Instruction formats) Write a sequence of instructions that will compute the value of y = x2 + 2x + 3 for a given x using

  1. three-address instructions
  2. two-address instructions
  3. one-address instructions

Strategy

Assume that no register file is available in the processor, except a single accumulator for subproblem ( c ).

Problem 2

Question

(Addressing modes) Write procedures for reading from and writing to a FIFO queue, using a two-address format, in comjunction with:

  1. indirect addressing
  2. relative addressing

Strategy

  1. Let us assume that R1 stores the address of the Front, and R2 stores the address of Back.
  2. In the case of relative addressing , we assume that the front of the queue is fixed at some offset and that R1 contains the number of reading performed and R2 contains the number of writings performed at this point of time.

Problem 3

Question

(Addressing modes) Write a sequence of instructions that will compute Sumaixi where A = [a1, a2, ..., a100] and X = [x1, x2, ..., x100] represent arrays that are stored in the main memory. Use two-address instructions, in conjunction with:

  1. direct addressing
  2. relative addressing
  3. indexed addressing with an auto-increment mode

Strategy

  1. Direct addressing: assume that A starts at address 1000, and X starts at 2000.
  2. In this case, we assume that there is a base register, BR, which stores the starting point of A. We further assume that X immediately follows A in the memory.

Problem 4

Question

(Instruction set) Add a dedicated base register ( BR ) to the 16-bit processor shown in Figure 9.9, and then show the changes this requires in the instruction set and the processor schematic.

Strategy

Adding a dedicated base register ( BR ) to the 16-bit processor shown in Figure 9.9 would require the following changes to the instruction set:

First, we would need to add one instruction to load the base. Then we would need to change relative addressing, since the RF[Src2] is explicity replaced by BR.

Problem 5

Question

(Reduced instruction set) Using the instruction set presented in Figure 9.11, propose the changes that enable it so to accommodate a register file with:

  1. 16 registers
  2. 32 registers
  3. 64 registers
  4. 256 registers

Strategy

  1. (a, b) Four bits are required to address 16 registers, and five bits are needed to address 32 registers. The simplest change to the instruction set would be to reduce the size of the constant and offset fields by three bits to increase the bits used in the register fields.
  2. (c, d) For larger register files, simply reducing the offset and constant fields will not be enough. Register instructions can altered by either removing the constant field or by assuming that one of the Src fields also acts as the Dest frees up bits.
  3. Memory instructions to load and store relative to some address can be changed through the inclusion of a base register and removal of the Src2 field.
  4. The branching instruction can be divided into two instructions, a comparison instruction and a branch instruction based upon a status register.

Problem 6

Question

(IS flowchart) Develop an IS flowchart for the reduced instruction set presented in Figure 9.11.

Strategy

None available.

Problem 7

Question

(Branch prediction) Write a program that will compute absolute value for the RISC processor shown in Figure 9.12. Develop a timing diagram for this processor,

  1. without branch prediction
  2. with branch prediction

Strategy

In order to compute absolute value, we need to follow an algorithm that passes positive values and make negative values positive before passing them on. As such, the algorithm could be described by:


if ( a >= 0 )
    val = a;
else
    val = -a;