ICS Lab

Lab1

根据 Lab1 3.4 小节的提示，将 $a\times b$ 拆解为 $a_0\times (2^0\times b)+a_1\times (2^1\times b)+\cdots +a_{63}\times (2^{63}\times b)$ 。其中 $a_n$ 是 $a$ 的二进制表示中的第 $n$ 位，即 $a=(a_{63}{a}_{62}\cdots a_0{)}_2$。

这个算式一共有三个部分：$a_i\times x$、$2^i\times b$ 和 $x+y$。

由于 $a_i\in \{0,1\}$，因此乘法 $a_i\times x$ 只需要一个 if 语句就可以实现。

接下来实现 $2^i\times b\mathrm{mod}m$ 。考虑使用递推的方法计算，即：

• $2^0\times b\equiv b(\mathrm{mod}m)$
• $2^i\times b\equiv 2^{i-1}\times b+2^{i-1}\times b(\mathrm{mod}m)$

继续实现 $(x+y)\mathrm{mod}m$ ，结果记为 mod_add(x, y, m)。需要注意这个加法仍然可能溢出 64-bit 整数。不妨记 $(x+y)\mathrm{mod}{2}^{64}$ 的结果是 $t$，

• 如果加法溢出 64-bit 整数，那么一定会有 $t<x\wedge t<y$，那么 $x+y\equiv t+2^{64}\equiv (t\mathrm{mod}m)+(2^{64}\mathrm{mod}m)(\mathrm{mod}m)$。 注意到右侧仍然是一个可能溢出 64-bit 整数的加法，因此需要递归调用 mod_add。但是由于 $2^{64}\mathrm{mod}m<m<2^{64}$ ，因此 mod_add 递归时 $x+y$ 的结果一定会越来越小，直至不再溢出，递归也会终止。

对于 $2^{64}\mathrm{mod}m$，可以通过 $(((2^{64}-1)\mathrm{mod}m)+1)\mathrm{mod}m$ 计算，因为 $(2^{64}-1)\mathrm{mod}m<m<2^{64}$，因此$((2^{64}-1)\mathrm{mod}m)+1<2^{64}$，一定不会溢出。

选做题存在反例？并没有保证 (double)a * b 的精度足以计算 mod ？

#include <stdio.h>
#include <stdint.h>
 
int64_t multimod_fast(int64_t a, int64_t b, int64_t m) {
    int64_t t = (a * b - (int64_t)((double)a * b / m) * m) % m;
    return t < 0 ? t + m : t;
}
 
int64_t standard_multimod(__int128 a, __int128 b, __int128 m) {
    return (int64_t)((a * b) % m);
}
 
int main() {
    int64_t a = (1LL<<62LL) - 1LL;
    int64_t b = (1LL<<62LL) - 1LL;
    int64_t m = 100000;
    printf("%ld\n", multimod_fast(a, b, m));      // 24193
    printf("%ld\n", standard_multimod(a, b, m));  // 37409
}

$ gcc -fwrapv -Wall -Wextra -std=c11 a.c
24193
37409

python 给出的结果是后者

$ python -c 'print( ((1<<62)-1) * ((1<<62)-1) % 100000 )'
37409

Lab2

题目只需要考虑 x86-64 架构，而 x86-64 指令集中有一些便捷的指令可以使用：

• asm_add：一行 add 指令即可
• asm_popcnt：一行 popcnt 指令即可，也可以参考给出的 C 代码使用循环和 if （ test 和 jz）实现
• asm_memcpy：一行 rep moves byte 指令即可，也可以使用循环（ test 和 jz）实现

setjmp 理论上需要保存所有寄存器的状态，但是 setjmp 作为一个函数，在调用者调用这个函数时会遵守调用约定。在 GNU/Linux x86-64 上，GCC 默认使用 System V ABI。因此可以偷懒只保存 7 个被调用者保存寄存器（易失寄存器）、 栈寄存器、函数返回地址共 9 个数据即可。（其他平台如 Windows 则使用另一个调用约定，对应另一组需要保存的寄存器）

PS：如果你想偷懒，还可以使用 no_callee_saved_registers 调用约定。在这种情况下，编译器会在调用 setjmp 之前帮你保存所有的寄存器状态到栈上，你只需要在 setjmp 中保存栈寄存器和返回地址即可。

longjmp 将所有寄存器恢复为 setjmp 保存的状态，设置函数返回地址，并且将调用约定中的返回值寄存器设为需要返回的值即可。 也可以参考 musl 的实现，直接弹出调用栈并使用 jmp 命令离开 longjmp 函数。

Lab3

性能优化主要考虑几个方面：

• 执行的计算指令数量
• 执行的访存指令数量
• 缓存命中率、分支预测准确率……

其中，计算指令数量可以通过改写算法提升，降低算法的复杂度。例如利用质因数分解的性质，只对“是素数的数”执行内层循环。或者利用质因数分解的唯一性，进一步只对一个数的最小的质因数执行内层循环（欧拉筛法）。访存指令数量也会随着算法的优化大幅减少。

缓存命中率和分支预测的优化比较玄学，提升缓存命中率需要使访存范围更加集中。可以尝试将 is_prime 改为 bitmap，减少一个元素占用的内存空间，进而使 cache 可以装载更多的区域，提升命中率。

从 Lab3 最后的示例信息来看，优化过后与优化前相比，执行的指令数量减少到了原来的 60%，cache 的命中率有所降低，但 cache 装载次数少了 80% 以上。综合这些因素，执行所需的总周期数降低到了原来的 10% 。

（WSL 不支持性能计数器，建议用物理机）

Lab4

init_cache 需要程序能够初始化不同数据大小、不同关联度的 cache，捋清楚地址各个部分与 cache 的关系即可。

// |            访问地址             |
// | 主存标记 | Cache 索引 | 块内地址 |

// common.h 中规定内存共 2^25 Byte，即访问地址共 26 位。
// common.h 中块大小为 BLOCK_SIZE，块内地址有 BLOCK_WIDTH 位
// Cache 共 total_size_width 位
//   = 2^total_size_width / 2^block_width 行
//   = 2^total_size_width / 2^block_width / 2^associativity_width 组
// 因此 Cache 索引应有
//   total_size_width - block_width - associativity_width 位
// 剩下位数作为主存标记

性能统计部分只需要实现 cycle_increase，并在 display_statistic 中打印周期数即可。框架给出的 cpu.c 和 mem.c 会分别在执行 cpu_read/cpu_write 和 cache miss 时的 mem_read/mem_write 的时候调用 cycle_increase 增加周期数。