CS61C-Notes in practice

2025-07-05

学习

8k words

阅读次

我的所有实现可以在汇总仓库看到。

Project 1: Game of life

Project 2: RISC-V Classifier

Project 3: CPU

Project 4:

下面是对于所有lab和project的一些记录，如需要更详细的介绍可以在Home Page 里浏览。

Lab 01

在命令行中调试c程序

1
2
3

gcc -g -o hello hello.c # -g 调试
gcc -o hello hello.c
./hello

CGDB

在命令行中进行debug，虽然不一定用得上（

1	cgdb hello

启动与运行 (Starting & Running)

set args <arg1> <arg2> ...
- 功能：在程序运行前，设置传递给 main 函数的命令行参数。
run
- 功能：启动程序执行。
run < input.txt
- 功能：(重要技巧) 启动程序，并从文件 input.txt 读取标准输入（stdin），用于调试需要用户输入的程序。

断点控制 (Breakpoint Control)

break <line_num> (简写: b <line_num>)
- 功能：在指定行号设置断点。
break <function_name> (简写: b <function_name>)
- 功能：在指定函数入口处设置断点。
info breakpoints
- 功能：查看所有已设置的断点信息。
delete <breakpoint_num>
- 功能：删除指定编号的断点。

执行控制 (Execution Control)

next (简写: n)
- 功能：单步跳过 (Step Over)。执行当前行，若此行为函数调用，则不进入函数内部，直接执行完函数。
step (简写: s)
- 功能：单步进入 (Step In)。执行当前行，若此行为函数调用，则进入函数内部的第一行暂停。
continue (简写: c)
- 功能：继续执行。从当前位置恢复运行，直到遇到下一个断点或程序结束。
finish
- 功能：继续执行，直到当前函数运行完毕返回。

数据查看 (Inspecting Data)

print <variable or expression> (简写: p <... >)
- 功能：打印一个变量或表达式的值。例如 p my_var 或 p 1+2。
display <variable>
- 功能：自动显示。设置一个变量，使其在每次程序暂停时（如 n 或 s 后）都自动显示其当前值。
info locals
- 功能：显示当前函数作用域内所有局部变量及其值。

退出 (Quitting)

quit (简写: q)
- 功能：退出 GDB/CGDB 会话。

Valgrind

1	valgrind ./segfault_ex

Lab02

Makefile

一、基本概念

目的：自动化编译过程，管理大型项目的依赖关系，极大提高编译效率。
工作方式：通过比较文件（目标和依赖）的修改时间，决定是否需要重新执行命令来生成目标。
执行：在终端中运行 make <目标名>。如果只运行 make，则默认执行文件中的第一个目标。

二、核心组成：变量 (Variables)

定义：使用 = 或 := 定义变量，通常放在文件开头，便于维护。
- CC = gcc
- CFLAGS = -Wall -std=c99
引用：使用 $(变量名) 或 ${变量名} 来引用变量的值。
- 示例：$(CC) $(CFLAGS) my_program.c

三、核心组成：规则 (Rules)

语法结构：

1 2	目标 (target): 依赖 (prerequisites) <Tab> 命令 (command) # 注意：必须是 Tab 键

目标 (Target)：通常是希望生成的文件（如可执行文件 app，目标文件 main.o）。
依赖 (Prerequisites)：生成“目标”所需要的文件或其他的“目标”。
命令 (Command)：构建“目标”所执行的 Shell 命令。

四、目标 (Target) 的种类

文件目标 (File Targets)：
- 代表实际的文件，如 lfsr 或 lfsr.o。
- make 会检查其依赖，如果依赖比目标新，则执行命令重新生成。
- 示例：lfsr: lfsr.o test_lfsr.o
伪目标 (Phony Targets)：
- 不代表真实文件名，只是一个标签，用于执行一组命令。
- 常用伪目标：
  - all: 约定俗成的名字，用于构建所有最终程序。通常是 Makefile 的第一个目标，作为默认目标。
  - clean: 用于删除所有生成的文件（.o 文件、可执行文件等），清理工作目录。
- 最佳实践：使用 .PHONY: all clean 来明确声明它们是伪目标，避免与同名文件冲突。

五、重要规则类型

显式规则 (Explicit Rules)：

1 2	lfsr: lfsr.o test_lfsr.o $(CC) -o lfsr lfsr.o test_lfsr.o

隐式规则 (Implicit Rules)：
1
2
.c.o:
$(CC) -c $(CFLAGS) $<
- 含义：定义了如何将任何 .c 文件编译成对应的 .o 文件。这让你无需为每个源文件都写一条编译规则。
无命令规则 (Command-less Rules)：
- 只定义依赖关系，不执行命令。
- 作用：告诉 make 文件间的依赖关系。
- 示例：lfsr.o: lfsr.h
- 含义：如果 lfsr.h 文件被修改了，那么 lfsr.o 就被认为是“过期的”，需要重新生成。

六、高级功能

自动变量 (Automatic Variables)：
- $@: 代表目标名 (target)。
- $<: 代表第一个依赖名 (prerequisite)。
- $^: 代表所有依赖名，用空格隔开。
- 示例（使用自动变量改写）：
  1
  2
  lfsr: lfsr.o test_lfsr.o
  $(CC) -o $@ $^
条件逻辑 (Conditional Logic)：
- 使 Makefile 能适应不同环境（如不同操作系统）。
- $(shell command): 执行一个 Shell 命令并返回其输出。
- ifeq / ifneq ... else ... endif: 条件判断语句。
- 示例：根据操作系统设置不同参数。
  1
  2
  3
  4
  5
  ifeq ($(UNAME_S), Darwin) # 如果是 macOS
  LIBS = -framework CoreFoundation
  else
  LIBS = -lm
  endif

Lab 03

RISC-V Sample

.data
.word 2, 4, 6, 8
n: .word 9

.text
main:
    add t0, x0, x0
    addi t1, x0, 1
    la t3, n
    lw t3, 0(t3)
fib:
    beq t3, x0, finish
    add t2, t1, t0
    mv t0, t1
    mv t1, t2
    addi t3, t3, -1
    j fib
finish:
    addi a0, x0, 1
    addi a1, t0, 0
    ecall # print integer ecall
    addi a0, x0, 10
    ecall # terminate ecall

n: .word 9 的意思是：在数据段中分配一个字（4 字节）的空间，给它一个标签（别名）叫做 n，并把数值 9 存入这个空间。

两个ecall的意思：

第一个 ecall (在第 21 行)

含义：打印一个整数。
原因：在它之前，指令 addi a0, x0, 1 将 1 存入了 a0。在 Venus 环境中，a0=1 是“打印整数”服务的编号。要打印的整数本身则从 a1 寄存器中读取。

第二个 ecall (在第 23 行)

含义：终止程序。
原因：在它之前，指令 addi a0, x0, 10 将 10 存入了 a0。在 Venus 环境中，a0=10 是“退出程序”服务的编号。

1 2	la t3, n lw t3, 0(t3)

的作用：第一步存的是n所在的地址，存进了t3（la是伪指令，auipc+addi，20+12位存储）

第二步把t3中写的东西作为地址去找这个地址存的数，放进t3

Lab 04

RISC-V汇编代码。

Lab 05

基本电路。

Lab 06

基本电路。

Lab 07

Cache理解。

Lab 08

Virtual Memory理解。

Camera是一个比较有简易的可视化界面。VMSIM没找到在哪儿。

Lab 09

SIMD理解。

帮助理解SIMD的工具1

工具2

Intel 函数说明，勾选所有SEE选项来了解。

使用了 #include <x86intrin.h>

其中的一些函数：

好的，没问题。这是根据我们之前的讨论，为您汇总的SIMD内联函数总表，方便您查阅和对比。

SIMD 内联函数总览

函数 (Function)	核心功能	用法与解释	所需技术
浮点操作
`_mm_div_ps`	并行单精度浮点除法	`__m128 _mm_div_ps(__m128 a, __m128 b);` 将向量`a`中的四个浮点数逐个除以向量`b`中对应的浮点数。	SSE
整数操作
`_mm_max_epi8`	并行有符号8位整数求最大值	`__m128i _mm_max_epi8(__m128i a, __m128i b);` 逐个比较两个向量中的16个`char`，返回包含每对最大值的新向量。	SSE4.1
`_mm_srai_epi16`	并行有符号16位整数算术右移	`__m128i _mm_srai_epi16(__m128i a, int imm8);` 将向量`a`中的8个`short`，统一算术右移一个立即数（常量）指定的位数。	SSE2
`_mm_add_epi32`	并行32位整数加法	`__m128i _mm_add_epi32(__m128i a, __m128i b);` 将两个向量中对应的4个`int`分别相加。	SSE2
`_mm_cmpgt_epi32`	并行32位整数比较大于	`__m128i _mm_cmpgt_epi32(__m128i a, __m128i b);` 比较`a`和`b`中的`int`，若`a > b`，结果对应元素全为1（`0xFFFFFFFF`），否则全为0，用于生成掩码。	SSE2
数据设置与移动
`_mm_setzero_si128`	创建全零向量	`__m128i _mm_setzero_si128();` 返回一个所有位都为0的128位向量，常用于初始化累加器。	SSE2
`_mm_set1_epi32`	广播单个整数到向量	`__m128i _mm_set1_epi32(int a);` 创建一个向量，其所有4个32位整数元素的值都等于`a`。	SSE2
`_mm_loadu_si128`	从内存加载（不对齐）	`__m128i _mm_loadu_si128(__m128i const* mem_addr);` 从内存地址加载128位数据到向量中，不要求地址16字节对齐。	SSE2
`_mm_storeu_si128`	存储到内存（不对齐）	`void _mm_storeu_si128(__m128i* mem_addr, __m128i a);` 将向量`a`的内容存入内存地址，不要求地址16字节对齐。	SSE2
逻辑操作
`_mm_and_si128`	向量按位与 (AND)	`__m128i _mm_and_si128(__m128i a, __m128i b);` 对两个128位向量进行按位与操作。常用于将比较后生成的掩码应用于数据向量。	SSE2

__m128i _mm_setzero_si128()

用途：创建一个所有位都为0的128位向量。
在此程序中的作用：完美适用于在循环开始前初始化一个用于累加的向量，我们称之为“累加向量”，其初始值应为[0, 0, 0, 0]。

__m128i _mm_loadu_si128(__m128i const\* mem_addr)

用途：从内存中加载128位（即4个整数）数据到向量中。u代表“unaligned”，意味着不要求内存地址对齐，更具通用性。
在此程序中的作用：在循环中，用它从vals数组的当前位置一次性加载4个整数到向量中进行处理。

__m128i _mm_cmpgt_epi32(__m128i a, __m128i b)

用途：并行比较两个向量中的4对32位有符号整数。gt代表“greater than”。
在此程序中的作用：这是实现if(vals[i] >= 128)条件判断的关键。你可以用它将加载进来的数据向量与一个[127, 127, 127, 127]的向量（代码中已为你创建的 _127）进行比较。如果数据大于127，结果向量的对应位置将全为1，否则全为0，从而生成一个掩码（mask）。

__m128i _mm_and_si128(__m128i a, __m128i b)

用途：对两个向量进行按位与（AND）操作。
在此程序中的作用：将上一步生成的掩码应用到原始数据向量上。这样，不满足条件（即 <= 127）的元素将因与0相与而被清零，而满足条件的元素将保持不变。

__m128i _mm_add_epi32(__m128i a, __m128i b)

用途：将两个向量中对应的4个整数分别相加。
在此程序中的作用：将经过掩码处理后（不满足条件的元素已为0）的向量加到你的“累加向量”上，实现并行求和。

void _mm_storeu_si128(__m128i\* mem_addr, __m128i a)

用途：将一个向量中的数据存回内存。
在此程序中的作用：循环结束后，你的“累加向量”中包含了4个独立的局部和。你需要用这个函数将它存到一个普通的4元素整型数组中。

Lab 10

熟悉多线程（multi-threading）与多进程（multi-processing）编程。

OpenMP编程

#pragma omp parallel：创建一支线程团队。
#pragma omp for：将 for 循环的计算任务（i 从 0 到 arr_size）分配给团队中的各个线程。每个线程负责一部分 i 的计算。
int omp_get_num_threads(); 返回 omp parallel 块中的线程数量
int omp_get_thread_num();返回线程 ID
#pragma omp critical：这创建了一个临界区。它的规则是：在任何时刻，只允许一个线程进入该区域执行代码。
1
2
3
4
5
6
7
#pragma omp parallel
{
#pragma omp for
for (int i = 0; i < arr_size; i++)
#pragma omp critical
global_sum += x[i] * y[i];
}
但这样会导致线程一直排队。手动优化：为每个线程设置一个local_sum，只加一次到global里。
或者：reduction 是 OpenMP 中的一个子句（Clause），专门用于解决并行计算中的“归约”问题。所谓归约，就是将一组值通过某个操作合并成一个单一值的过程，例如对一个数组求和、求乘积、或者找到其中的最大/最小值。reduction 子句通常附加在像 #pragma omp parallel 或 #pragma omp for 这样的并行指令上。它的基本语法是： reduction(operator: variable_list)。比如：
1
2
3
4
5
6
#pragma omp parallel
{
#pragma omp for reduction(+ : global_sum)
for (int i = 0; i < arr_size; i++)
global_sum += x[i] * y[i];
}

伪共享是如何发生的？

CPU的每个core有自己的cache，之间有缓存一致性协议（Cache Coherency Protocol）来沟通（课上讲过）

假设我们有以下场景：

一个多核 CPU，每个核心都有自己的 L1 缓存。
缓存行大小为 64 字节。
我们有一个数组 int results[2];，一个 int 占 4 字节。
线程 0 只需要更新 results[0]。
线程 1 只需要更新 results[1]。

从程序逻辑上看，results[0] 和 results[1] 是两个完全独立的变量，线程 0 和线程 1 之间没有任何数据共享。

但是，在内存中，results[0] 和 results[1] 是紧挨着存放的。由于一个 int 只有 4 字节，这两个变量（总共 8 字节）会被放进同一个 64 字节的缓存行中。

现在，灾难发生了：

加载数据：
- 线程 0 在 核心 0 上运行，想要给 results[0] 加 1。它将包含 results[0] 和 results[1] 的整个缓存行加载到 核心 0 的缓存中。
- 同时，线程 1 在 核心 1 上运行，想要给 results[1] 加 1。它也将同一个缓存行加载到 核心 1 的缓存中。
修改与作废：
- 核心 0 修改 results[0]。根据缓存一致性协议，它必须通知其他核心：“我修改了这个缓存行，你们手里的版本都作废了！”
- 核心 1 收到了这个“作废”消息，于是把它自己缓存中的这个缓存行标记为“无效”，尽管它关心的 results[1] 根本没被修改。
重新加载：
- 现在轮到 核心 1 修改 results[1] 了。它发现自己的缓存行已经无效，于是被迫从主内存（或核心 0 的缓存）重新获取这个缓存行的最新数据。这个过程非常耗时。
- 核心 1 修改完 results[1] 后，它同样会发出一个“作废”通知。
恶性循环：
- 核心 0 收到了来自核心 1 的“作废”消息，也把自己缓存中的缓存行标记为无效。当下一次它要修改 results[0] 时，又必须去重新加载…

如何避免？

避免伪共享的核心思想是：确保被不同线程独立访问的数据，不会被分配在同一个缓存行中。

最常用的方法是 数据填充（Padding）。

我们手动在两个变量之间插入一些“无用”的数据，把它们在内存中的距离拉开，强迫它们落入不同的缓存行。

举例：

// 使用结构体和填充来避免伪共享
struct padded_int {
    int value;
    char padding[CACHE_LINE_SIZE - sizeof(int)];
};

多进程编程

多线程与多进程之间的主要区别在于，在多线程中，线程共享相同的地址空间，而在多进程中，每个进程拥有自己的地址空间。从性能角度来看，这一区别导致两个观察结果：

线程具有较低的额外开销（低内存和其他资源占用），并且线程之间的通信成本较低，因为线程只能读取/写入同一地址空间中的内存地址。
共享内存意味着我们需要小心处理并发问题：当多个线程可以读取/写入同一内存地址时，很难推理其正确性。

fork创建一个子进程，如果一切正常，调用 fork 应该将正在创建的子进程的进程 ID 返回给调用进程，并将 0 返回给新创建的进程（通常称为子进程）。如果创建子进程失败，则返回负值。

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
int main () {
  pid_t child_pid;
  printf("Main process id = %d (parent PID = %d)\n",
(int) getpid(), (int)  getppid());
  child_pid = fork(); // 在这里分流，child_pid对于父进程而言是9076，对于子进程而言是0
  if (child_pid != 0)
printf("Parent: child's process id = %d\n", child_pid);
  else
printf("Child:  my process id = %d\n", (int) getpid()); 
  return 0;
}
// may output:
Main process id = 9075 (parent PID = 32146)
Parent: child's process id = 9076
Child:  my process id = 9076

Categories

Tags

Archives

Recent Posts

CS61C-Notes in practice

Lab 01

CGDB

启动与运行 (Starting & Running)

断点控制 (Breakpoint Control)

执行控制 (Execution Control)

数据查看 (Inspecting Data)

退出 (Quitting)

Valgrind

Lab02

Makefile

一、基本概念

二、核心组成：变量 (Variables)

三、核心组成：规则 (Rules)

四、目标 (Target) 的种类

五、重要规则类型

六、高级功能

Lab 03

RISC-V Sample

Lab 04

Lab 05

Lab 06

Lab 07

Lab 08

Lab 09

SIMD 内联函数总览

Lab 10

OpenMP编程

伪共享是如何发生的？

如何避免？

多进程编程

Lab 11

Project 1

Project 2

Project 3

Project 4

Categories

Tags

Archives

Recent Posts

Lab 01

CGDB

启动与运行 (Starting & Running)

断点控制 (Breakpoint Control)

执行控制 (Execution Control)

数据查看 (Inspecting Data)

退出 (Quitting)

Valgrind

Lab02

Makefile

一、基本概念

二、核心组成：变量 (Variables)

三、核心组成：规则 (Rules)

四、目标 (Target) 的种类

五、重要规则类型

六、高级功能

Lab 03

RISC-V Sample

Lab 04

Lab 05

Lab 06

Lab 07

Lab 08

Lab 09

SIMD 内联函数总览

Lab 10

OpenMP编程

False Sharing 伪共享

伪共享是如何发生的？

如何避免？

多进程编程

Lab 11

Project 1

Project 2

Project 3

Project 4