北航计算机组成原理P2课下

通过阅读本文，你可以大致了解北京航空航天大学2023级计算机组成原理P2课下的相关内容，希望能对你有所帮助

前言

在分享此次P2附加题做题思路前，我想对于在做题过程中错误和技巧进行总结与反思

对于栈的使用

为了使用栈，~~首先我们要有一个栈~~，而且对于某些递归程序或者传递参数较多的程序，频繁地对栈指针进行加减操作可能会出现某些难以察觉的问题，所以常常对于入栈和出栈操作封装函数
.data
stack: .space 400

.macro push(%int)
addi $sp, $sp, -4
sw %int, $sp
.end_macro

.macro pop(%int)
lw %int $sp
addi $sp, $sp, 4
.end_macro

.text
la $sp, stack
addi $sp, $sp, 400

对于含有多个参数的递归程序，比如汉罗塔问题（四个参数用寄存器其实也还可以），将会使用栈传递和接收参数，同时还需要使用栈保护寄存器，所以可以规定自己的一套规则（在函数的开始接收参数再保存寄存器，调用函数前先保护寄存器再传递参数），总之一定要明白每次出入栈的真正含义，例如对于下面的c语言代码翻译

void hanoi(int base, char from, char via, char to) {
  if (base == 0) {
      ...
  }
  hanoi(base - 1, from, via, to);
  move(base, from, via);
  ...
}

main:
    push($t0) # 传参数
    ...
    jal hanoi
    
hanoi:
    pop($t3) # 接收参数
    ...
    push($ra) # 保存返回地址
    
    # if模块
    
    push($t0) # 保存参数
    ...

    addi $t0, $t0, -1
    push($t0) # 传递参数
    ...
    jal hanoi
    
    pop($t3) # 取出保留的参数
    ...
    print($t0, $t1, $t2)


    pop($ra) # 取出返回地址
    jr $ra

如果你喜欢，可以永远只在调用函数前保留所有的参数，但是我个人比较喜欢在函数的开头保留$ra和$s（不过似乎从来没这样用过），然后在每一个返回的地方pop($ra); jr $ra，这样可以避免出现$ra混乱（可能是叶子函数但是弹了一个不是$ra的值，可能是中间函数使用了上层函数的$ra，莫名其妙出现一些很奇怪的bug）
push($ra) # 保存返回地址

if_begin:
...
pop($ra) # 取出返回地址
jr $ra

jal others
...
pop($ra) # 取出返回地址
jr $ra

如果出现了调用栈时的bug可以从顶层模块开始将各个部分拆分出来，例有如下调用关系main -> hanoi -> move/hanoi，我们编写main函数的栈使用时，将假设hanoi等下层的函数正确地使用了栈，所以在调用前后除了传递进去的参数其他部分应该保持完全一致，不必纠结下层函数中间如何使用栈，然后依次向下编写hanoi、move函数，方能条理清晰、面面俱到

hanoi:

    push($t0) # 保护寄存器
    push($t1)

    push($t0) # 传递参数
    push($t1)

    jal hanoi # 可以理解除了传递的参数，调用函数前后栈结构不变

    pop($t1) # 取出保护的寄存器
    pop($t0)

调用函数前栈内容


                                     
                          
                         +-------------+ <-$sp               
                  -->    |  传递参数    |     -->           
+--------+ <-$sp  准备   +-------------+     调用       
| ...    |               |  ...        |

调用函数后栈内容

+----------------+ <-$sp
|被调用者保存寄存器| 
+----------------+      
|  返回地址       |    -->  
+----------------+    返回  +----------+ <-$sp
|  ...           |          | ...      |

MIPS汉罗塔
MIPS全排列反转(其实是P1课下一摸一样)

P2_extra_1 1206-33 puzzle

本题看起来就像DP算法，但是想了好半天也没有找到一个可靠的状态转移方程（我不会算法，我是fw），所以我就正常使用递归来写了

首先我们确认探索的起点
有四个可选择方向，上下左右
判断向某个方向走是否会出边界
判断某个方向是否有路，以及是否是此次寻找的完整路径已经走过的结点

最后以走到的结点为下一次探索的起点

#include <stdio.h>
#include <stdlib.h>

int matrix[8][8] = {0};  // 定义矩阵
int visited[8][8] = {0}; // 记录访问状态

int row, col;
int end_r, end_c;

int dfs(int s_row, int s_col) {
    // 找到终点
    if (s_row == end_r - 1 && s_col == end_c - 1)
        return 1;

    // 四个方向：上、下、左、右
    int dir_r[4] = {-1, 1, 0, 0};
    int dir_c[4] = {0, 0, -1, 1};
    int total = 0;

    visited[s_row][s_col] = 1; // 标记当前节点为已访问

    // 遍历四个方向
    for (int i = 0; i < 4; i++) {
        int new_r = s_row + dir_r[i];
        int new_c = s_col + dir_c[i];

        // 边界检查
        if (0 <= new_r && new_r < row && 0 <= new_c && new_c < col) {
            // 如果该位置没有障碍物且未被访问
            if (!matrix[new_r][new_c] && !visited[new_r][new_c] ) {
                total += dfs(new_r, new_c); // 递归搜索
            }
        }
    }

    visited[s_row][s_col] = 0; // 回溯，解除当前节点的访问标记
    return total;
}

int main() {
    int start_r, start_c;

    // 输入矩阵的行数和列数
    scanf("%d%d", &row, &col);

    // 读入矩阵
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }

    // 输入起点和终点坐标
    scanf("%d%d%d%d", &start_r, &start_c, &end_r, &end_c);

    // 调用DFS并输出结果
    int total_paths = dfs(start_r - 1, start_c - 1);
    printf("%d\n", total_paths);
    return 0;
}

这道题翻译大概率不会有$ra的问题，因为虽然我全程使用的是栈传递，但是因为这个递归函数有返回值，所以每次返回前我都需要将返回值压栈，自然会想到返回地址的问题

但是因为是多个条件的if判断，触发任何一个不满足条件直接跳出即可

# read in new_r
lw $t4, dir_r($t3)
add $t4, $t4, $t0

# 0 <= new_r
slt $t5 ,$t4, $zero 
bne $t5, $zero, if_end_2

# new_r < row
slt $t5, $t4, $s0 
beq $t5, $zero, if_end_2

# read in new_c
lw $t3, dir_c($t3) 
add $t3, $t3, $t1

# 0 <= new_c
slt $t5, $t3, $zero 
bne $t5, $zero, if_end_2

# new_c < col
slt $t5, $t3, $s1 # new
beq $t5, $zero, if_end_2

# !matrix[i][j]
read_matrix($t4, $t3, $s1, $t5)
bne $t5, $zero, if_end_2

# !visited[i][j]
read_visited($t4, $t3, $s1, $t5)
bne $t5, $zero, if_end_2

虽然我没找到DP的写法，但是可以开一个数组path[i][j]表示(i,j)位置到(end_r,end_c)的路径数，这样如果这个值不是0就可以不用继续递归了，效率应该还是略低于DP（如果有的话），请教我DP！！！

p2_extra_1 1206-418 factorial

高精度！！！
本题应该纯粹是考察高精度的，目测数据不强，~~毕竟我只能算不到600位也过了~~，测试数据应该是远远没有1000位的
如果你选了6系人都爱的oop，你一定很喜欢java；如果你喜欢java，你就会知道里面有一个很有趣的类BigInteger
private final int signum; //存储数字符号
private final int[] mag; //存储二进制块
- BigInteger将大数字分为若干二进制块(unsigned)，动态调整存储这些二进制块的数组，BigInteger理论上可以表示任意大的数字（受限于java数组只能开Integer.MAX_VALUE大小，所以最大大概可以表示 $ (2 \times 2147483648) ^ {2147483648} $
- 显然，BigInteger挑选了一个很大的值作为基准，所以我们可以参考它的思想，也像它这样存储大数，不过因为我们~~没有java那么nb~~，我们算乘法的值不能超过32位，所以base可以适当地取得小一点例如我取了10000也就是每一个进制块只能表示0 ~ 9999
最后，似乎大数乘法也有若干很神奇的优化，像什么FFT、Karatsuba什么什么算法，太高大上了看不懂怎么实现的（~~找了一段FFT + Karatsuba的诡异代码~~，明明每个操作都认识，放一起这么出来了这么奇怪的代码）

所以我使用了最最朴素的乘法*

#define BASE 1000

void multiply(int mag[], int *mag_size, int num) {
    int carry = 0;
    for (int i = 0; i < *mag_size; i++) {
        int prod = mag[i] * num + carry;
        mag[i] = prod % BASE;
        carry = prod / BASE;
    }

    while (carry) {
        mag[(*mag_size)++] = carry % BASE;
        carry /= BASE;
    }
}

一个提醒
- 最开始我一直有一个点没过，我以为有一个超级超级强的数据，而且还放在第一个，~~差点就回去看FFT + Karatsuba~~，后来发现我使用的beq指令，如果碰见计算0!下面这样的情况循环21亿多次才会结束（
  read_in($s0) # 读入n
  li $t0, 2 # 从2的阶乘开始算
  addi $s0, $s0, 1 # n = n + 1
  
  for_i_begin:
  beq $t0, $s0, for_i_end
  for_i_end:
- 数据还是很弱的，没有真的到1000位，主要还是考查高精度吧，助教们真好

鬼点子

接下来的一切内容全部不保真，~~仅供学习和交流使用~~
例如上面两道附加题，大概都是需要自己写出C语言代码再进行翻译，当然不乏有巨佬完全不需要这样orz，所以是否可以使用gcc编译器汇编并用objdump进行反汇编得到汇编代码
gcc -O3 -funroll-loops -finline-functions -fomit-frame-pointer -march=native factorial.c -o factorial
objdump -d factorial
然后观察生成的x86-64代码的思路，或者~~直接将其修改为mips汇编~~，感觉有可行性，但是不多，不过可以使用gcc编译器学一学汇编是真的，可以看编译器会这么使用寄存器和栈来实现一个结构、函数之类的
不过也许或者大概可能课上不会出现强优化的题目？（味精）