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

View Questions Only
View Questions with Strategies

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

Solution

  1. three-address instructions 
    
Mult z, x, x
Mult y, 2, x 
Add y, y, z
Add y, y, 3
  2. two-address instructions 
    
Move z, x
Mult z, x
Move y, 3
Add y, z
Move z, x
Mult z, 2
Add y, z
  3. one-address instructions 
    
Move x
Mult x
Store z
Move x
Mult 2
Add z
Add 3
Store y

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

Solution

  1. 
Reading: Loadindirect R3, R1
         Inc R1
Writing: Storeindirect R2, Data
         Inc R2
  2. if we have a fixed base register called BR: 
    
Reading: Move temp, BR
         Move BR, R1
         Loadrel R4, offset
         Inc R1
         Move BR, temp
Writing: Move temp, BR
         Move BR, R2
         Storerel offset, Data
         Inc R2
         Move BR, temp

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

Solution

  1. Direct addressing: 
    
Move Sum, 0
Load Temp1, 1000
Load Temp2, 2000
Mult Temp1, Temp2
Add Sum, Temp1
...
Load Temp1, 1099
Load Temp2, 2099
Mult Temp1, Temp2
Add Sum, Temp1
  2. relative addressing 
    
Move Sum, 0
Loadrel Temp1, 0
Loadrel Temp2, 100
Mult Temp1, Temp2
Add Sum, Temp1
...
Loadrel Temp1, 99
Loadrel Temp2, 199
Mult Temp1, Temp2
Add Sum, Temp1
  3. indexed addressing with an auto-increment mode 
    
    Move Sum, 0
    Move IR, 0
L1: Loadindex Temp1, 1000
    Loadindex Temp2, 2000
    Mult Temp1, Temp2
    Add Sum, Temp1
    Cmp IR, 100
    Bne L1

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.

Solution

Add one instruction to load the base:


    Lbase Address : BR <-- Address

Change relative addressing:


    Lrel Dest, Base : RF[Dest] <-- Mem[BR + Offset]
    Srel Srcl, Base : Mem[BR + Offset] <-- RF[Srcl]

The processor would need to be modified in the following manner:

Homework 8 Problem 4 Answer

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

Solution

  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.

Solution

Homework 8 Problem 6 Answer

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

Solution

  1. To realize this algorithm using our RISC instructions on the processor without branch prediction, we could program it as follows:

    Address Instruction
    100 Bgeq a, 0, +9
    101 N o - op
    102 N o - op
    103 N o - op
    104 sub val, 0, a
    105 jump + 5
    106 N o - op
    107 N o - op
    108 N o - op
    109 N o - op
    110 ...

    Timing diagram when branch is not taken ( a < 0 )

    Problem 7A Timing Diagram no Branch

    Timing diagram when branch is taken ( a >= 0)

    Problem 7A Timing Diagram with Branch

  2. The program would change slightly when tuned for the processor with branch prediction

    Address Instruction
    100 Bgeq a, 0, +3
    101 sub val, 0, a
    102 jump + 2
    103 mov val, a
    104 ...

    Timing diagram when branch is not taken ( a < 0 )

    Problem 7B Timing Diagram no Branch

    Timing diagram when branch is taken ( a >= 0 )

    Problem 7B Timing Diagram with Branch