Introduction to Computer Organization (ICO, CCIT 4026)

HKU SPACE Community College — AY2526S2

Q1 — strlen() Procedure (30 marks)

Problem Description

Strings are arrays of characters (bytes) terminated by the null character (byte value 0). Given that $a0 points to a character string, the procedure strlen() returns the length of the string in register $v0 by reading the string one byte at a time until the null character is encountered. Complete the main program and procedure strlen() by filling in the blanks for 10 incomplete lines.

Reconstructed Code (with blanks filled in)

Below is the complete MIPS assembly program. The bolded comments indicate the 10 blank lines that need to be filled in.

        .data
1   str:    .asciiz "Hello, World!"
2   msg:    .asciiz "\nString length = "
        .text
        .globl main
3   main:
4       li   $v0, 4              # print string syscall
5       la   $a0, msg
6       syscall
7
8       la   $a0, str            # *** BLANK (Line 8) ***
9       jal  strlen              # *** BLANK (Line 9) ***
10
11      move $a0, $v0            # *** BLANK (Line 11) ***
12      li   $v0, 1              # print integer syscall
13      syscall
14
15      li   $v0, 10             # exit syscall
16      syscall
17
18  # -----------------------------------------------
19  # Procedure: strlen
20  # Input:  $a0 = address of a null-terminated string
21  # Output: $v0 = length of the string
22  # -----------------------------------------------
23  strlen:
24      addi $sp, $sp, -4        # *** BLANK (Line 24) ***
25      sw   $ra, 0($sp)         # *** BLANK (Line 25) ***
26      li   $v0, 0              # *** BLANK (Line 26) ***
27  loop:
28      lb   $t0, 0($a0)         # *** BLANK (Line 28) ***
29      beq  $t0, $zero, done    # *** BLANK (Line 29) ***
30      addi $a0, $a0, 1         # *** BLANK (Line 30) ***
31      addi $v0, $v0, 1         # increment length counter
32      j    loop                # repeat
33  done:
34      lw   $ra, 0($sp)         # *** BLANK (Line 34) ***
35      addi $sp, $sp, 4         # restore stack pointer
36      jr   $ra                 # return to caller

Answer Table

Line Instruction Explanation
Line 8 la $a0, str Load the address of the string str into register $a0, which is the argument register for the strlen procedure.
Line 9 jal strlen Jump and Link to the strlen procedure. This saves PC+4 into $ra and jumps to strlen.
Line 11 move $a0, $v0 Move the return value (string length in $v0) into $a0 so it can be printed by the print_int syscall ($v0 = 1).
Line 24 addi $sp, $sp, -4 Prologue: Allocate 4 bytes on the stack by decrementing the stack pointer. This creates space to save $ra.
Line 25 sw $ra, 0($sp) Save the return address register $ra onto the stack. This is necessary because strlen was called via jal, and $ra must be preserved.
Line 26 li $v0, 0 Initialize the length counter $v0 to 0 before starting the loop. (Equivalent to move $v0, $zero.)
Line 28 lb $t0, 0($a0) Load Byte: Read one byte (character) from the memory address pointed to by $a0 into $t0.
Line 29 beq $t0, $zero, done Branch if Equal: If the loaded byte $t0 equals zero (null terminator), branch to label done — the end of the string has been reached.
Line 30 addi $a0, $a0, 1 Advance the string pointer $a0 by 1 byte to point to the next character in the string.
Line 34 lw $ra, 0($sp) Epilogue: Restore the return address $ra from the stack before returning to the caller.

How strlen Works — Step by Step

  1. Prologue (Lines 24–25): Allocate stack space and save $ra.
  2. Initialize (Line 26): Set the counter $v0 = 0.
  3. Loop (Lines 28–32): - Load the byte at $a0 into $t0. - If $t0 == 0 (null terminator), exit the loop. - Otherwise, increment the pointer ($a0 += 1) and the counter ($v0 += 1). - Jump back to the beginning of the loop.
  4. Epilogue (Lines 34–36): Restore $ra, deallocate the stack, and return via jr $ra.

For the string "Hello, World!" (13 characters), the procedure returns $v0 = 13.

Q2 — Single-Cycle Processor Execution (40 marks)

Given Information

Instruction sequence:

        addi $t1, $zero, 2       # Instruction ①
L1:     add  $t3, $t3, $t1       # Instruction ②
        sub  $t3, $t3, $t2       # Instruction ③
        beq  $t3, $t4, Exit      # Instruction ④
        j    L1                   # Instruction ⑤
Exit:   add  $t4, $t3, $s0       # Instruction ⑥
  • Clock cycle time = 200 ns
  • Execution starts at t = 0
  • Initial register values: $s0 = 10, $t1 = 1, $t2 = 1, $t3 = 2, $t4 = 5

Part (a) — Execution Trace (10 marks)

Cycle-by-Cycle Trace

Cycle Time Range (ns) Instruction Executed Operation Register Change
1 0 – 200 addi $t1, $zero, 2 $t1 ← 0 + 2 = 2 $t1 = 2
2 200 – 400 add $t3, $t3, $t1 $t3 ← 2 + 2 = 4 $t3 = 4
3 400 – 600 sub $t3, $t3, $t2 $t3 ← 4 − 1 = 3 $t3 = 3
4 600 – 800 beq $t3, $t4, Exit 3 ≠ 5 → not taken —
5 800 – 1000 j L1 Jump to L1 —
6 1000 – 1200 add $t3, $t3, $t1 $t3 ← 3 + 2 = 5 $t3 = 5
7 1200 – 1400 sub $t3, $t3, $t2 $t3 ← 5 − 1 = 4 $t3 = 4
8 1400 – 1600 beq $t3, $t4, Exit 4 ≠ 5 → not taken —
9 1600 – 1800 j L1 Jump to L1 —
10 1800 – 2000 add $t3, $t3, $t1 $t3 ← 4 + 2 = 6 $t3 = 6
11 2000 – 2200 sub $t3, $t3, $t2 $t3 ← 6 − 1 = 5 $t3 = 5
12 2200 – 2400 beq $t3, $t4, Exit 5 = 5 → branch taken —
13 2400 – 2600 add $t4, $t3, $s0 $t4 ← 5 + 10 = 15 $t4 = 15

Register Value Table (write value only when changed)

Register (t=0) C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13
$t1 1 2
$t2 1
$t3 2 4 3 5 4 6 5
$t4 5 15

Instruction (executed at each cycle):

C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13
① ② ③ ④ ⑤ ② ③ ④ ⑤ ② ③ ④ ⑥

Summary

Total number of instructions executed = 13

Total execution time = 13 × 200 ns = 2600 ns

Explanation: The loop body (instructions ②–⑤) executes 3 iterations. In the 3rd iteration, the beq condition is satisfied ($t3 = $t4 = 5), so the branch is taken to Exit. After Exit instruction ⑥, the total is: 1 (addi) + 3 × 4 (loop iterations, but 3rd iteration has no j) = 1 + 4 + 4 + 3 + 1 = 13.

Part (b) — Final Register Values (6 marks)

After the complete instruction sequence finishes:

$t3 = 5

$t4 = 15

Derivation:

  • After 3 loop iterations, $t3 converges to the value 5 (equal to the initial $t4), which triggers the beq branch.
  • At Exit, $t4 = $t3 + $s0 = 5 + 10 = 15.

Part (c) — Processor State at t = 2050 ns (24 marks)

Identifying the Instruction

At t = 2050 ns, we are in clock cycle 11 (time range 2000–2200 ns).

The instruction being executed is:

sub $t3, $t3, $t2

This is an R-type instruction.

MIPS R-type Instruction Format

| opcode (6) | rs (5) | rt (5) | rd (5) | shamt (5) | funct (6) |
|  [31-26]   |[25-21] |[20-16] |[15-11] |  [10-6]   |  [5-0]    |

For sub $t3, $t3, $t2: - opcode = 000000 (R-type) - rs = $t3 = register 11 = 01011 - rt = $t2 = register 10 = 01010 - rd = $t3 = register 11 = 01011 - shamt = 00000 - funct = 100010 (subtract)

Register Values at the Start of Cycle 11

At the beginning of cycle 11, the register file contains (after cycle 10 updated $t3 to 6): - $t3 = 6 - $t2 = 1

Answer Table

Signal / Field Value Explanation
instruction[31-26] 000000 R-type opcode is always 000000.
instruction[25-21] 01011 rs = $t3 = register 11.
instruction[20-16] 01010 rt = $t2 = register 10.
instruction[15-11] 01011 rd = $t3 = register 11 (destination).
instruction[5-0] 100010 Funct code for sub (subtract).
Read data 1 output 6 (decimal) Value read from register $t3. After cycle 10's add, $t3 = 4 + 2 = 6.
Read data 2 output 1 (decimal) Value read from register $t2. $t2 has remained 1 throughout.
ALU result 5 (decimal) ALU computes subtraction: 6 − 1 = 5.
RegDst 1 R-type: destination register is rd (instruction[15-11]).
ALUSrc 0 R-type: second ALU input comes from register file (Read data 2), not immediate.
MemtoReg 0 R-type: data written to register comes from ALU result, not memory.
RegWrite 1 R-type: result is written back to the destination register.
MemRead 0 R-type: no memory read operation.
MemWrite 0 R-type: no memory write operation.
Branch 0 R-type: not a branch instruction.
ALUOp[1:0] 10 R-type: ALUOp = 10, which tells the ALU control to look at the funct field to determine the ALU operation.

Control Signal Summary for R-type (sub)

RegDst ALUSrc MemtoReg RegWrite MemRead MemWrite Branch ALUOp
1 0 0 1 0 0 0 10

Q3 — Stuck-at Fault Analysis (30 marks)

Reference: Normal Control Signal Values

Control Signal R-type lw sw beq j
RegDst 1 0 X X X
ALUSrc 0 1 1 0 X
MemtoReg 0 1 X X X
RegWrite 1 1 0 0 0
MemRead 0 1 0 0 0
MemWrite 0 0 1 0 0
Branch 0 0 0 1 0
ALUOp[1:0] 10 00 00 01 XX
Jump 0 0 0 0 1

(a) RegWrite = 0 (stuck at 0)

Effect: The register file can never be written. Any instruction that needs to store a result in a register will fail.

Instruction Class Working Y/N? Explanations
R-type N R-type instructions (add, sub, and, or, slt, etc.) need RegWrite = 1 to write the ALU result to the destination register rd. With RegWrite stuck at 0, the computed result cannot be written back to the register file. The ALU still computes the correct result, but it is discarded.
Load Word N lw needs RegWrite = 1 to write the data loaded from memory into the destination register rt. With RegWrite stuck at 0, the loaded data cannot be stored, making the instruction useless.
Store Word Y sw normally has RegWrite = 0 — it reads two registers (base address and data) and writes to memory, not to the register file. Since RegWrite = 0 is the correct value for sw, it works perfectly.
Branch Y beq normally has RegWrite = 0 — it only reads two registers for comparison and conditionally updates the PC. No register file write is needed, so it works correctly.
Jump Y j normally has RegWrite = 0 — it only updates the PC with the jump target address. No register file write is involved, so it works correctly.

(b) ALUOp[1] = 0 (stuck at 0)

Effect: The ALUOp[1] bit is permanently 0. This changes the ALU control behavior for R-type instructions.

  • R-type: ALUOp should be 10 → becomes 00 (same as lw/sw → ALU always performs addition)
  • lw: ALUOp = 00 → stays 00 ✓
  • sw: ALUOp = 00 → stays 00 ✓
  • beq: ALUOp = 01 → stays 01 ✓ (only bit 1 is affected, bit 0 is unchanged)
  • j: ALUOp = XX → doesn't matter ✓
Instruction Class Working Y/N? Explanations
R-type N ALUOp changes from 10 to 00. With ALUOp = 00, the ALU control unit ignores the funct field and always performs addition. This means: add still works (since it is addition), but sub, and, or, slt, and all other R-type operations produce incorrect results because the ALU performs addition instead of their intended operations.
Load Word Y lw uses ALUOp = 00 to compute the memory address via addition (base + offset). Since ALUOp[1] = 0 doesn't change the value 00, address calculation is correct and the instruction works normally.
Store Word Y sw uses ALUOp = 00 for address calculation, same as lw. The addition for address computation is unaffected, so sw works correctly.
Branch Y beq uses ALUOp = 01 to perform subtraction for the equality comparison. Since only bit 1 is stuck at 0 and bit 0 remains 1, ALUOp stays 01. The subtraction comparison works correctly.
Jump Y j does not depend on the ALU operation. The jump target address is computed directly from the instruction's address field. ALUOp is don't-care for j.

(c) ALUSrc = 0 (stuck at 0)

Effect: The second ALU input always comes from the register file (Read data 2), never from the sign-extended immediate.

Instruction Class Working Y/N? Explanations
R-type Y R-type instructions normally have ALUSrc = 0, selecting Read data 2 (register rt) as the second ALU operand. Since ALUSrc is already 0 for R-type, there is no change and the instruction works correctly.
Load Word N lw needs ALUSrc = 1 to select the sign-extended 16-bit offset as the second ALU input for address calculation (base + offset). With ALUSrc stuck at 0, the second ALU input comes from Read data 2 (the value of register rt) instead of the offset. This produces an incorrect memory address, so the wrong data is loaded.
Store Word N sw also needs ALUSrc = 1 for address calculation (base + offset). With ALUSrc stuck at 0, the register value rt is used instead of the offset, producing an incorrect memory address. Data is written to the wrong memory location.
Branch Y beq normally has ALUSrc = 0, selecting Read data 2 for the subtraction comparison (rs − rt). The fault doesn't change the behavior, so beq works correctly.
Jump Y j does not depend on ALUSrc. The jump target is derived directly from the instruction's 26-bit address field, not from the ALU. It works correctly regardless of ALUSrc.

(d) RegDst = 1 (stuck at 1)

Effect: The write destination register is always selected from the rd field (instruction[15-11]), never from the rt field (instruction[20-16]).

Instruction Class Working Y/N? Explanations
R-type Y R-type instructions normally have RegDst = 1, selecting rd (instruction[15-11]) as the destination register. Since RegDst is already 1, there is no change and the instruction works correctly.
Load Word N lw needs RegDst = 0 to select rt (instruction[20-16]) as the destination register where the loaded data is written. With RegDst stuck at 1, the data is written to the register specified by instruction[15-11] (which is part of the 16-bit offset field in I-type format). This writes to the wrong register, corrupting an unintended register while leaving the intended destination unchanged.
Store Word Y sw does not write to the register file (RegWrite = 0), so RegDst is a don't-care signal. The fault has no effect on sw.
Branch Y beq does not write to the register file (RegWrite = 0), so RegDst is a don't-care signal. The branch comparison and PC update are unaffected.
Jump Y j does not write to the register file (RegWrite = 0), so RegDst is a don't-care signal. The jump operation is unaffected.

(e) MemWrite = 1 (stuck at 1)

Effect: The data memory always performs a write operation every clock cycle, regardless of the instruction being executed. This causes unintended memory corruption for all non-store instructions.

Instruction Class Working Y/N? Explanations
R-type N R-type normally has MemWrite = 0 (no memory write). With MemWrite stuck at 1, every R-type instruction will cause an unintended write to data memory — the ALU result is used as the memory address, and Read data 2 is written to that address. Although the register write may still be correct, the unwanted memory corruption makes the overall instruction behavior incorrect.
Load Word N lw normally has MemWrite = 0 (read-only). With MemWrite stuck at 1, a simultaneous write occurs to the same memory address being read. The value from Read data 2 (register rt) is written to the computed address, corrupting the memory contents. Even if the load itself reads the correct value in that cycle, the memory is corrupted for future accesses.
Store Word Y sw normally has MemWrite = 1 to write data to memory. Since MemWrite is already 1 for sw, the fault has no effect and the instruction works correctly.
Branch N beq normally has MemWrite = 0. With MemWrite stuck at 1, the ALU result (rs − rt) is used as a memory address and Read data 2 is written to that address. While the branch decision itself (comparing rs and rt) is still correct, the unintended memory write corrupts data memory, making the overall behavior incorrect.
Jump N j normally has MemWrite = 0. With MemWrite stuck at 1, an unintended memory write occurs with whatever values happen to be on the address and data lines. This causes memory corruption, making the behavior incorrect even though the PC update (jump) is correct.

Summary of Q3 Answers

Stuck-at Fault R-type lw sw beq j
(a) RegWrite = 0 N N Y Y Y
(b) ALUOp[1] = 0 N Y Y Y Y
(c) ALUSrc = 0 Y N N Y Y
(d) RegDst = 1 Y N Y Y Y
(e) MemWrite = 1 N N Y N N

— End of Assignment 4 Solutions —