Question 6 of 6

Question 6 (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) an 8-instruction sequence with two independent lw/lw/add/sw groups on a 5-stage (IF-ID-EX-MEM-WB) pipeline where a load's result is available at the end of stage 4 (MEM) but a dependent instruction needs its operand at the start of stage 3 (EX). (b) a 4-instruction, 8-bit encoding table for a 4-register CPU.

Find. (a) a reordering of the 8 instructions with no load-use stalls. (b) the structural problems in the encoding table and a corrected field layout.

Approach. (a) since two back-to-back instructions place the load's MEM stage in the very same cycle as the dependent instruction's EX stage (one cycle too early), insert at least one independent instruction between every load and any instruction that consumes its result; interleave the two independent chains to supply those fillers for free. (b) decode each row's opcode bit positions and check whether they overlap with another row's operand-field bit positions for some operand value.

1. Part (a) — hazard-free schedule. With back-to-back instructions i and i+1, instruction i's MEM stage (cycle where a load's value becomes available) falls in the exact same cycle as instruction i+1's EX stage (where an ADD needs its operand, at the start of that cycle) — the value simply isn't ready yet, forcing a stall. Separating the load and its consumer by at least one independent instruction pushes the consumer's EX stage one cycle later, which now lines up with (or follows) the load's MEM/WB forwarding point, removing the stall. The original code has exactly two such hazards: lw $6→add $6,$5,$6 (adjacent) and lw $9→add $9,$8,$9 (adjacent). Because the two lw/lw/add/sw groups are entirely independent of each other (different registers, only sharing the read-only base $4), each group's extra load can be pulled forward to fill the other group's hazard slot:

   Reordered 8-instruction schedule

   Slot	Instruction	Note
   1	lw $5, 0($4)
   2	lw $6, 4($4)
   3	lw $8, 8($4)	independent filler (was slot 5)
   4	add $6, $5, $6	1 instr after lw $6: hazard-free
   5	lw $9, 12($4)	independent filler (was slot 6)
   6	sw $6, 0($7)
   7	add $9, $8, $9	1 instr after lw $9: hazard-free
   8	sw $9, 0($10)

   Reordered 8-instruction schedule: the two independent chains supply each other's load-use filler slot, so no stall cycle is needed anywhere.
   Every load is separated from any instruction that reads its destination register by at least one intervening independent instruction, so this schedule executes the same 8 instructions with zero load-use stalls, versus 2 stall cycles in the original order.
   ASSUMPTION (stated per the paper's NOTES): the reordering hoists lw $8, 8($4) and lw $9, 12($4) above sw $6, 0($7), so it preserves the program's meaning only if the store's target MEM[$7+0] does not alias either loaded address MEM[$4+8] or MEM[$4+12]. Nothing in the question relates $7 to $4, and a compiler performing this schedule would either prove independence or keep the store ahead of the two loads; the register dependences alone are unaffected either way.
2. Part (b) — encoding problems. Decoding the four rows by which BITS are fixed ("opcode-like") versus which carry an operand ("data-like") reveals the fault: Load and Store put their fixed bits in the LOW nibble (bits 3–0: 0000 and 0010) with the register fields R1/R2 occupying the HIGH nibble (bits 7–4); BZ also fixes its low nibble (0101) with Imm4 in the high nibble; but Add does the opposite — it fixes its HIGH nibble (1000) and puts its register fields R1/R2 in the LOW nibble. Because there is no single, position-consistent opcode field shared by every instruction, an instruction cannot be identified by looking at one fixed set of bits — and because R1/R2/Imm4 are unconstrained operand values, some combinations of a "data-like" field in one instruction exactly reproduce the fixed bit pattern of a different instruction:
   • Load R1=2, R2=0 encodes as 10 00 0000 = 0x80. Add $0,$0 encodes as 1000 00 00 = 0x80. Identical byte, two different instructions — the decoder cannot tell "load register 2 from the address in register 0" from "add register 0 to register 0."
   • Store R2=2, R1=0 encodes as 10 00 0010 = 0x82. Add R1=0, R2=2 encodes as 1000 00 10 = 0x82. Same collision.
   • Add R1=1, R2=1 encodes as 1000 0101 = 0x85. BZ Imm4=1000(=8) encodes as 1000 0101 = 0x85. Same collision, this time between Add and a branch.
   These are not edge cases to be excluded — every one of R1, R2, and Imm4 is a legal, in-range operand value, so the collisions are reachable by ordinary, syntactically valid programs, and the hardware has no way to disambiguate which instruction was intended.
   Check: reading the table literally, "Add R1 R2" is taken to mean the fixed bits are 1,0,0,0 at positions 7,6,5,4 and R1 occupies bits 3-2, R2 occupies bits 1-0 (the only reading consistent with the table's own column layout); the collisions above hold under this reading.
   Fix: reserve a fixed-position opcode field common to ALL four instructions, checked first by the decoder, at the SAME bit positions regardless of instruction — e.g. use the low 2 bits (bits 1–0) as a 2-bit opcode for all four instructions (00=Load, 01=Store, 10=Add, 11=BZ), freeing the remaining 6 bits for operands: Load/Store each need R1+R2 (4 bits, fits in 6), Add needs R1+R2 (4 bits, fits in 6), and BZ needs Imm4 (4 bits, fits in 6, even keeping its original width). Because the opcode field is now at an identical, fixed position for every instruction and is never itself reused as part of any operand field, no combination of operand values can ever alias one instruction's encoding onto another's. The core defect is a non-uniform opcode position (Add's fixed field sits in the high nibble while every other instruction's sits in the low nibble), which lets ordinary operand values collide with another instruction's fixed bits; the fix is a single fixed-position opcode field shared by all instructions.