Week 4 — Advanced MIPS Programming 第4周 — 高级MIPS编程

2D arrays, algorithms, and complex data structures in MIPS MIPS中的二维数组、算法和复杂数据结构

                
                    📋 Week Overview
                    📋 本周概览
                
                2D Arrays — Matrix representation and access patterns
                        二维数组 — 矩阵表示和访问模式
Sieve of Eratosthenes — Prime number algorithms
                        埃拉托斯特尼筛法 — 质数算法
Random Mathematics — Random number generation and usage
                        随机数学 — 随机数生成和使用
Class Management — Structured data handling
                        班级管理 — 结构化数据处理

            

🎯 Learning Objectives 🎯 学习目标

✓ Work with 2D arrays in MIPS ✓ 在MIPS中处理二维数组
✓ Implement classic algorithms ✓ 实现经典算法
✓ Handle structured data ✓ 处理结构化数据
✓ Optimize memory access patterns ✓ 优化内存访问模式

📚 Key Concepts 📚 关键概念

• 2D array addressing: base + row*col_size + col • 二维数组寻址：基址 + 行*列大小 + 列
• Algorithm optimization techniques • 算法优化技术
• Structured data layout in memory • 内存中的结构化数据布局
• Nested loops and efficiency • 嵌套循环和效率

2D Arrays in MIPS MIPS中的二维数组

Memory Layout 内存布局

In MIPS, 2D arrays are stored in row-major order as contiguous memory. To access element [i][j] in an M×N array: 在MIPS中，二维数组以行优先顺序作为连续内存存储。要访问M×N数组中的元素[i][j]：

# Address calculation for array[i][j]
# address = base_address + (i * N + j) * element_size

# For integers (4 bytes each):
la $t0, array_base     # load base address
li $t1, i             # row index
li $t2, j             # column index
li $t3, N             # number of columns

# Calculate offset: (i * N + j) * 4
mul $t4, $t1, $t3     # i * N
add $t4, $t4, $t2     # i * N + j
sll $t4, $t4, 2       # multiply by 4 (for integers)

# Access element
add $t5, $t0, $t4     # address of array[i][j]
lw $t6, 0($t5)       # load value

⚠️ Performance Note ⚠️ 性能说明

Row-major access (accessing elements in the same row consecutively) is more cache-friendly than column-major access. 行优先访问（连续访问同一行中的元素）比列优先访问更缓存友好。

Sieve of Eratosthenes 埃拉托斯特尼筛法

Algorithm Overview 算法概述

The Sieve of Eratosthenes efficiently finds all prime numbers up to a given limit N: 埃拉托斯特尼筛法高效地找出所有小于等于给定数N的质数：

Create boolean array of size N+1, initialized to true 创建大小为N+1的布尔数组，初始化为true
Mark 0 and 1 as non-prime 标记0和1为非质数
For each number from 2 to √N: 对于从2到√N的每个数：
If the number is prime, mark all its multiples as non-prime 如果该数是质数，标记其所有倍数为非质数

.data
array_size: .word 101     # Find primes up to 100
prime_array: .space 101   # Boolean array (0=non-prime, 1=prime)
prompt:     .asciiz "Enter limit (2-100): "
result_msg: .asciiz "Primes found: "
newline:    .asciiz "\n"
space:      .asciiz " "

.text
main:
    # Initialize prime array
    li $t0, 1           # Start from 1 (index 0 unused)
init_loop:
    li $t1, 101
    bge $t0, $t1, init_done
    li $t2, 1
    sb $t2, prime_array($t0)  # Mark as prime
    addi $t0, $t0, 1
    j init_loop

init_done:
    # Mark 0 and 1 as non-prime
    sb $zero, prime_array($zero)
    li $t0, 1
    sb $zero, prime_array($t0)

    # Sieve algorithm
    li $t0, 2           # Current number
sieve_outer:
    li $t1, 101
    bge $t0, $t1, sieve_done

    # Check if current number is prime
    lb $t2, prime_array($t0)
    beq $t2, $zero, sieve_next  # Skip if not prime

    # Mark multiples as non-prime
    li $t3, 2           # Multiplier start
sieve_inner:
    mul $t4, $t0, $t3   # Calculate multiple
    li $t5, 101
    bge $t4, $t5, sieve_inner_done

    sb $zero, prime_array($t4)  # Mark as non-prime
    addi $t3, $t3, 1
    j sieve_inner

sieve_inner_done:
sieve_next:
    addi $t0, $t0, 1
    j sieve_outer

sieve_done:
    # Count and print primes
    li $t0, 2           # Start from 2
    li $t1, 0           # Prime counter

count_loop:
    li $t2, 101
    bge $t0, $t2, count_done

    lb $t3, prime_array($t0)
    beq $t3, $zero, count_skip

    addi $t1, $t1, 1    # Increment counter

count_skip:
    addi $t0, $t0, 1
    j count_loop

count_done:
    # Print result
    li $v0, 4
    la $a0, result_msg
    syscall

    li $v0, 1
    move $a0, $t1
    syscall

    li $v0, 4
    la $a0, newline
    syscall

    # Exit
    li $v0, 10
    syscall

Random Mathematics 随机数学

Random Number Generation 随机数生成

MIPS doesn't have built-in random functions, but we can implement simple pseudorandom generators: MIPS没有内置的随机函数，但我们可以实现简单的伪随机生成器：

# Linear Congruential Generator
# seed = (seed * A + C) % M

.data
seed:       .word 1234    # Initial seed
A:          .word 1664525
C:          .word 1013904223
M:          .word 2147483647  # 2^31-1

.text
# Function to generate random number
# Returns random number in $v0
random:
    lw $t0, seed
    lw $t1, A
    lw $t2, C
    lw $t3, M

    # seed = (seed * A + C) % M
    mul $t4, $t0, $t1
    add $t4, $t4, $t2
    div $t4, $t3
    mfhi $t4              # Get remainder (modulus)

    sw $t4, seed          # Update seed
    move $v0, $t4         # Return result
    jr $ra

                    
                        Random Number Applications
                        随机数应用
                    
                    • Monte Carlo simulations
                            • 蒙特卡洛模拟
• Statistical sampling
                            • 统计抽样
• Game mechanics
                            • 游戏机制
• Algorithm testing
                            • 算法测试

                

Class Management System 班级管理系统

Structured Data Example 结构化数据示例

Implementing a simple student record system with structured data: 实现一个带有结构化数据的简单学生记录系统：

# Student record structure:
# [0:3]   student_id (4 bytes)
# [4:7]   name (16 bytes, 4 characters)
# [8:11]  assignment1_score (4 bytes)
# [12:15] assignment2_score (4 bytes)
# [16:19] exam_score (4 bytes)
# Total: 20 bytes per student

.data
max_students: .word 10
student_size: .word 20
students:     .space 200  # 10 students * 20 bytes

# Student data initialization
student1_id:    .word 1001
student1_name:  .asciiz "Alice"
student1_a1:    .word 85
student1_a2:    .word 90
student1_exam:  .word 78

.text
# Function to calculate student average
# Input: $a0 = student index
# Output: $v0 = average (scaled by 100)
calculate_average:
    li $t0, 20          # Size of each student record
    mul $t1, $a0, $t0   # Offset to student

    la $t2, students     # Base address
    add $t3, $t2, $t1   # Student address

    # Load scores
    lw $t4, 8($t3)      # assignment1_score
    lw $t5, 12($t3)     # assignment2_score
    lw $t6, 16($t3)     # exam_score

    # Calculate weighted average
    # Average = (a1 * 0.25 + a2 * 0.25 + exam * 0.5)
    mul $t4, $t4, 25    # Scale by 0.25 * 100
    mul $t5, $t5, 25    # Scale by 0.25 * 100
    mul $t6, $t6, 50    # Scale by 0.5 * 100

    add $t7, $t4, $t5
    add $t7, $t7, $t6

    # Divide by 100 to get final average
    li $t8, 100
    div $t7, $t8
    mflo $v0            # Result in $v0

    jr $ra

Challenge Exercises 挑战练习

Advanced Programming Challenges 高级编程挑战

🧮 Ackermann Function 🧮 阿克曼函数

Implement the recursive Ackermann function, a classic example of a computable function that is not primitive recursive. 实现递归的Ackermann函数，这是一个可计算但非原始递归函数的经典例子。

# Ackermann function: A(m, n)
# A(0, n) = n + 1
# A(m, 0) = A(m-1, 1) for m > 0
# A(m, n) = A(m-1, A(m, n-1)) for m, n > 0

🎭 Polymipsism 🎭 多重MIPS

Create a program that can interpret and execute simple MIPS instructions stored in data memory. 创建一个可以解释和执行存储在数据内存中的简单MIPS指令的程序。

# Idea: Simple MIPS interpreter
# Read instructions from data memory
# Decode opcode, rs, rt, rd, immediate
# Execute using jump tables or conditional branches

📊 Matrix Operations 📊 矩阵运算

Implement matrix multiplication, transpose, or determinant calculation using 2D arrays. 使用二维数组实现矩阵乘法、转置或行列式计算。