CMU 10-714 Assignments 实验笔记

CMU 10-714 Assignments 实验笔记

随缘更新ing

前置要求:微积分、线性代数(可能需要一点矩阵论)、DL基础、Python(熟悉 numpy 和 pytorch 更好)。

几乎不使用任何第三方库实现几个深度学习库,包括自动微分、常见神经网络、数据加载器、优化器,并使用 CUDA 实现 GPU 加速。代码量适中,但是基本 pytorch 中有的东西都有了。如果还想深入了解 torch.compiler 相关内容,可以继续学习Machine Learning Compiler,通过 TVM 介绍了 AI Compiler 中的大部分内容。

实验环境为 Arch Linux,环境如下:

既然这门课为 DL Systems, 本文将重点放在实现上,而不是各种数学公式的推导。

由于官方自动评分系统目前不再接受非选课学生注册,因此本代码仅保证能够通过已有测试样例。

本人不是特别熟悉 python 语法,实现过程中可能有不符合 python 规范的地方,欢迎大家指正。

资源存档

课程官网:Deep Learning Systems

实验要求即测试:Assignments

环境配置

采用 conda 进行包管理。 Arch 用户直接 yay 安装 anaconda 即可。

1
2
3
4
source /opt/anaconda/bin/activate base
conda --crate needle python=3.12
conda activate needle
pip install pytest numpy mugrade

HW0

实验仓库地址:Assignment 1

第一个 homework 主要用于简要复习 Machine Learning 的内容。需要实现包括训练两层的线性神经网络在内的 7 个函数。

Basic add function

用来熟悉评测系统,简单的返回 a + b 即可。

1
2
def add(x, y):
return x + y

然后根据实验提示看看 test 文件内的测试框架,确保无误(谁家好人 a + b 能写错)后运行 python3 -m pytest -k "add" 进行测试。

paese_mnist

读取 MNIST 手写数字数据集。LeCun 老爷子的博客 内对这个数据集的格式作了详细介绍,直接看 FILE FORMATS FOR THE MNIST DATABASE 这个部分即可。

整个数据集分为 4 个文件,分别为 train_image, train_label, test_imgae, test_label。整个数据集直接使用原始的二进制来存储,前 \(2\) 个字节固定为 \(0\),第 \(3\) 个字节表明数据类型,第 \(4\) 个字节表明维度数。之后的 \(n * 4\) 个字节表明数据的各个维度大小,其中 \(n\) 为将第 \(4\) 个字节视为 uint8 之后的大小。之后即 MNIST 数据集的实际图片。

例如 0x00 0x00 0x08 0x03 60000 28 28 表明,数据集采用 uint8 格式存储(第 \(4\) 个字节为 0x08,约定 0x08 为 uint8),数据集有 \(3\) 个维度(第 \(4\) 个字节为 0x03),之后的 \(3 * 4 = 12\) 个字节表明数据集的维度为 (60000 * 28 * 28)。

具体实现中,使用 gzip 库对文件进行 按字节 读取,最后进行标准化即可(每个像素灰度值除以 \(255\))。

1
2
3
4
5
6
7
8
9
10
11
12
13
def parse_mnist(image_filename, label_filename):
with gzip.open(image_filename, 'rb') as image:
zero, dtype, dims = struct.unpack('>HBB', image.read(4))
shape = tuple(struct.unpack('>I', image.read(4))[0] for _ in range(dims))
image_data = np.frombuffer(image.read(), dtype=np.uint8).reshape(shape[0], -1)
image_data = image_data.astype(np.float32) / 255.0

with gzip.open(label_filename, 'rb') as label:
zero, dtype, dims = struct.unpack('>HBB', label.read(4))
shape = tuple(struct.unpack('>I', label.read(4))[0] for _ in range(dims))
label_data = np.frombuffer(label.read(), dtype=np.uint8).reshape(shape[0])

return (image_data, label_data)

Softmax loss

实现交叉熵损失函数。照着公式写即可,不再赘述:

1
2
3
4
def softmax_loss(Z, y):
sum_log = np.log(np.sum(np.exp(Z), axis=1)) # shape (batch_size)
prob = Z[np.arange(Z.shape[0]), y]
return np.mean(sum_log - prob)

SGD for Softmax Regression

实现 softmax 回归的一个 epoch 上的训练过程。

首先从数据中每次拿出一个 batch 大小的数据,然后根据公式算即可。label 转换为 one-hot 的小 trick:I_y = np.eye(num_classes)[y_batch]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def softmax_regression_epoch(X, y, theta, lr = 0.1, batch=100):
m = X.shape[0]
num_classes = theta.shape[1]

for start in range(0, m, batch):
end = min(start + batch, m)
X_batch = X[start:end]
y_batch = y[start:end]
batch_size = X_batch.shape[0]

logits = X_batch @ theta
exp_logits = np.exp(logits)
Z = exp_logits / np.sum(exp_logits, axis=1, keepdims=True)
I_y = np.eye(num_classes)[y_batch]

grad = X_batch.T @ (Z - I_y) / batch_size
theta -= lr * grad

SGD for Two-layer nn

实现一个双层感知机在一个 epoch 上的训练过程。

ReLu 本质为和 \(0\) 取最大值,张量版本的 max 为 np.maximum。需要注意的是,除法运算能提前就提前,否则可能会导致精度不够。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def nn_epoch(X, y, W1, W2, lr = 0.1, batch=100):
def ReLU(X):
return np.maximum(0, X)

m = X.shape[0]
num_classes = W2.shape[1]

for start in range(0, m, batch):
end = min(start + batch, m)
X_batch = X[start:end, ]
y_batch = y[start:end]
batch_size = X_batch.shape[0]

Z1 = ReLU(X_batch @ W1)
Z2_exp = np.exp(Z1 @ W2)
I_y = np.eye(num_classes)[y_batch]
G2 = Z2_exp / np.sum(Z2_exp, axis=1, keepdims=True) - I_y
G1 = G2 @ W2.T * (Z1 > 0).astype(np.float32)

G_W1 = X_batch.T @ G1 / batch_size
G_W2 = Z1.T @ G2 / batch_size

W1 -= lr * G_W1
W2 -= lr * G_W2

Softmax Regression by cpp

使用 cpp 实现上面的 Softmax 回归。

与 Python 版本不懂,cpp 没有那么多的语法糖,需要手写矩阵乘法,需要处理多维数据映射为一维。不过在处理 ont-hot 方面比 Python 自由了很多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
void softmax_regression_epoch_cpp(const float *X, const unsigned char *y,
float *theta, size_t m, size_t n, size_t k,
float lr, size_t batch)
{
for (size_t i = 0;i < m;i += batch) {
assert(batch != 0);
size_t batch_size = std::min(batch, m - i);
const float *X_b = X + i * n;
const unsigned char *y_b = y + i;

float *logits = new (std::nothrow) float[batch_size * k];
float *grad_logits = new (std::nothrow) float[batch_size * k];
float *grad_theta = new (std::nothrow) float[n * k]();

if (!logits || !grad_logits || !grad_theta) {
delete[] logits;
delete[] grad_logits;
delete[] grad_theta;
return ;
}

// Forward pass: copute logits = X_b * theta
for (size_t b = 0;b < batch_size;b ++) {
for (size_t c = 0;c < k;c ++) {
float tot = 0.0f;
for (size_t d = 0;d < n;d ++) {
tot += X_b[b * n + d] * theta[d * k + c];
}
logits[b * k + c] = tot;
}
}

// Softmax and loss gradient
for (size_t b = 0;b < batch_size;b ++) {
float max_logit = logits[b * k];
for (size_t c = 1;c < k;c ++) {
if (logits[b * k + c] > max_logit) {
max_logit = logits[b * k + c];
}
}

// grad_logits = exp(x @ theta)
float sum_exp = 0.0f;
for (size_t c = 0;c < k;c ++) {
float exp_val = std::exp(logits[b * k + c] - max_logit);
grad_logits[b * k + c] = exp_val;
sum_exp += exp_val;
}

// grad_logits = Z
int true_class = static_cast<int>(y_b[b]);
for (size_t c = 0;c < k;c ++) {
grad_logits[b * k + c] /= sum_exp;
}
// grad_logits = Z - I_y
grad_logits[b * k + true_class] -= 1.0f;
}

// Backward
for (size_t b = 0;b < batch_size;b ++) {
for (size_t d = 0;d < n;d ++) {
float x_val = X_b[b * n + d];
for (size_t c = 0;c < k;c ++) {
// in-place transpose
grad_theta[d * k + c] += x_val * grad_logits[b * k + c];
}
}
}

float scale = lr / static_cast<float>(batch_size);
for (size_t j = 0;j < n * k;j ++) {
theta[j] -= scale * grad_theta[j];
}

delete[] logits;
delete[] grad_logits;
delete[] grad_theta;
}
}

HW0 总结

建议看完 Lecture 2 之后再写这个实验。没经过西瓜书拷打的同学一开始看到满屏幕的公式应该会很懵,不过好在熟悉推导之后实现起来还是比较简单的,很适合用来熟悉 NumPy 和基础 DL 模型。

HW1

这个 homework 共有 6 个部分:算子正向传播,梯度反向传播,拓扑排序、反向自动微分、softmax 损失以及双层感知机的 SGD。

Forward & Backward Computation

需要实现基本算子的前向传播和反向传播。

前两个部分关系比较紧密,这里放在一起说了。实现算子的时候,需要时刻清楚每一步的张量形状。还需要处理 NumPy 中无处不在的 广播。

推导梯度的时候需要注意:当前算子的 out_grad 形状和当前算子的前向运算形状相同,例如令 \(A \in \mathbb{R}^{m \times d}\),\(B \in \mathbb{R}^{d \times n}\),当前算子为 Matmul(A, B),则从后一层传过来的 out_grad 形状为 \(\mathbb{R}^{m \times n}\)。

对应参数的梯度形状和该参数相同。即当 \(X \in \mathbb{R}^{m \times n}\),则 \(\frac{\partial L}{\partial \mathbf{X}} \in \mathbb{R}^{m \times n}\)。

需要注意的是,前向传播中操作对象是 NDarray,即只进行单纯的数值运算。而反向传播需要扩展计算图,操作对象为 ndl.Tensor。强烈建议通读 needle/autograd.py 中的 class Tensor 的源码,对理解框架很有用。

  • PowerScalar

所有元素对一个标量进行幂运算。输入输出形状相同,张量梯度形式和标量相同。建议所有梯度都返回元组,方便后续写 AD 的时候进行解包。

1
2
3
4
5
6
7
8
9
10
11
class PowerScalar(TensorOp):
def __init__(self, scalar: int):
self.scalar = scalar

def compute(self, a: NDArray) -> NDArray:
return array_api.power(a, self.scalar)

def gradient(self, out_grad: Tensor, node: Tensor):
a = node.inputs[0]
grad = self.scalar * power_scalar(a, self.scalar - 1)
return (out_grad * grad, )
  • EWiseDiv

张量对应元素之间的除法。输入输出形状相同,张量梯度形式和标量相同。分别对分子分母求偏导数即可。

1
2
3
4
5
6
7
8
9
class EWiseDiv(TensorOp):
def compute(self, a, b):
return array_api.divide(a, b)

def gradient(self, out_grad, node):
lhs, rhs = node.inputs
lhs_grad = power_scalar(rhs, -1)
rhs_grad = negate(divide(lhs, power_scalar(rhs, 2)))
return (out_grad * lhs_grad, out_grad * rhs_grad)
  • DivScalar 所有元素对一个标量进行除法。输入输出形状相同,张量梯度形式和标量相同。对分子求导即可。
1
2
3
4
5
6
7
8
9
class EWiseDiv(TensorOp):
def compute(self, a, b):
return array_api.divide(a, b)

def gradient(self, out_grad, node):
lhs, rhs = node.inputs
lhs_grad = power_scalar(rhs, -1)
rhs_grad = negate(divide(lhs, power_scalar(rhs, 2)))
return (out_grad * lhs_grad, out_grad * rhs_grad)
  • Transpose

广义的矩阵转置,实际更类似 swap 轴的操作。设 \(A \in \mathbb{R}^{2, 3, 4, 5}\), 则 transpose(A, axes=(1, 3, )) 结果为 \(A \in \mathbb{R}^{2, 5, 4, 3}\),即第 \(1\) 轴和第 \(3\) 个轴交换。当 axes=None 时,默认交换最后两个轴。

因为 \(Y = X^T\),所以 \(Y_{ji} = X_{ij}\)。对损失 \(L\) 求导:

\[ \frac{\partial L}{\partial X_{ij}}=\sum_{k, l}\frac{\partial L}{\partial Y_{kl}}\cdot\frac{\partial Y_{kl}}{\partial X_{ij}} \]

而 \(\frac{\partial Y_{kl}}{\partial X_{ij}} = 1\) 当且仅当 \(k = j\) 且 \(l = i\),否则为 \(0\)。

因此有:

\[ \frac{\partial L}{\partial X_{ij}} = \frac{\partial L}{\partial Y_{ji}} \]

即

\[ \frac{\partial L}{\partial X} = {(\frac{\partial L}{\partial Y})}^T \]

所以 transpose 的梯度即为 out_grad 在相同维度上进行一次转置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Transpose(TensorOp):
def __init__(self, axes: Optional[tuple] = None):
self.axes = axes

def compute(self, a):
ndim = a.ndim
if self.axes is None:
axis1, axis2 = ndim - 2, ndim - 1
else:
axis1, axis2 = self.axes
return array_api.swapaxes(a, axis1, axis2)

def gradient(self, out_grad, node):
return (transpose(out_grad, self.axes), )
  • Reshape

本质是重新对内存下标进行映射。

根据链式法则有:

\[ \frac{\partial L}{\partial x_i}=\sum_j\frac{\partial L}{\partial y_j}\cdot\frac{\partial y_j}{\partial x_i} \]

由于 reshape 只是对元素的重排列,某个 \(y_j\) 要么是由某个唯一的 \(x_i\) 直接复制过来,要么和 \(x_i\) 没有任何关系,有 \(\frac{\partial{y_j}}{\partial{x_i}} = 1\),当且仅当 \(j = i\) 时成立。

即

\[ \frac{\partial L}{\partial x_i}=\frac{\partial L}{\partial y_j} \]

即把 \(\frac{\partial L}{\partial y}\) 按相反的方式进行 reshape 即得到 \(\frac{\partial L}{\partial y}\)。

1
2
3
4
5
6
7
8
9
10
class Reshape(TensorOp):
def __init__(self, shape):
self.shape = shape

def compute(self, a):
return array_api.reshape(a, self.shape)

def gradient(self, out_grad, node):
shape = node.inputs[0].shape
return (reshape(out_grad, shape), )
  • BoardCast

广播操作本质是沿某个轴进行复制,根据链式法则有:

\[ \frac{\partial L}{\partial x_i}=\sum_{j\in\text{由 }x_i\text{ 复制得到的位置}}\frac{\partial L}{\partial y_j} \cdot \frac{\partial{y_j}}{\partial{x_i}} \]

由于 \(y_j = x_i\),即 \(\frac{\partial{y_j}}{\partial{x_i}} = 1\),即沿着广播的轴对 out_grad 进行求和即可。由于 NumPy 中的广播可能会升维,所以最后进行一次 reshape 对齐 \(X\) 的维度即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class BroadcastTo(TensorOp):
def __init__(self, shape):
self.shape = shape

def compute(self, a):
return array_api.broadcast_to(a, self.shape).copy()

def gradient(self, out_grad, node):
input_shape = node.inputs[0].shape
output_shape = self.shape

if input_shape == output_shape:
return (out_grad, )

ndim_added = len(output_shape) - len(input_shape)
axes = list(range(ndim_added)) # 添加的维度
for i, (in_dim, out_dim) in enumerate(zip(input_shape, output_shape[ndim_added:])):
if in_dim == 1 and out_dim > 1: # 广播的维度
axes.append(ndim_added + i)

if axes:
out_grad = summation(out_grad, tuple(axes))

out_grad = reshape(out_grad, input_shape)
return (out_grad,)
  • Summation

这个算子是沿特定轴进行求和,结果进行降维。如果 axes=None,则对全局进行求和,返回标量。

以 \(y = x1 + x2\) 举例,有

\[ \frac{\partial y}{\partial x_1}=1,\quad\frac{\partial y}{\partial x_2}=1 \]

由链式法则有:

\[ \begin{aligned} & \frac{\partial L}{\partial x_1}=\frac{\partial L}{\partial y}\cdot1=\frac{\partial L}{\partial y} \\ & \frac{\partial L}{\partial x_2}=\frac{\partial L}{\partial y}\cdot1=\frac{\partial L}{\partial y} \end{aligned} \]

即 \(y\) 的梯度值对所有参与求和的 \(x\) 值都是相同的。所以只需要将 out_grad 沿着求和的轴广播回去即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Summation(TensorOp):
def __init__(self, axes: Optional[tuple] = None):
self.axes = axes

def compute(self, a):
return array_api.sum(a, axis=self.axes)

def gradient(self, out_grad, node):
input_shape = node.inputs[0].shape

# 全局求和
if self.axes is None:
new_shape = (1, ) * len(input_shape)
return (broadcast_to(reshape(out_grad, new_shape), input_shape), )

# 标准化处理,避免 slef.axes 中出现负数轴
axes = tuple(ax % len(input_shape) if ax < 0 else ax for ax in self.axes)
new_shape = list(input_shape)
# 把求和的那几个轴改为1,方便进行广播
for ax in axes:
new_shape[ax] = 1

return (broadcast_to(reshape(out_grad, tuple(new_shape)), input_shape), )
  • Matmul

广义矩阵乘法。NumPy 支持高维矩阵乘法,只需要最后两维度满足矩阵乘法的要求即可,前面的维度都视为 batch。如果维度不匹配,会进行升维或广播。

在计算梯度的时候,根据 Lecture 1中介绍的凑形状方法,可以得到如下两个表达式:

\[ \frac{\partial L}{\partial Y}\frac{\partial Y}{\partial A} = G B^T \\ \frac{\partial L}{\partial Y}\frac{\partial Y}{\partial B} = A^T G \]

但是 NumPy 会进行 reshape 和 boardcast,根据链式法则,需要进行一次规约。沿着广播轴进行求和,并 reshape 为输入的形状即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MatMul(TensorOp):
def compute(self, a, b):
return array_api.matmul(a, b)

def gradient(self, out_grad, node):
lhs, rhs = node.inputs
lhs_grad = matmul(out_grad, transpose(rhs))
rhs_grad = matmul(transpose(lhs), out_grad)

def reduce_to_shape(grad, shape):
if grad.shape == shape:
return grad
ndim_added = len(grad.shape) - len(shape)
axes = list(range(ndim_added))
for i, (s, gs) in enumerate(zip(shape, grad.shape[ndim_added:])):
if s == 1 and gs > 1:
axes.append(ndim_added + i)
if axes:
grad = summation(grad, tuple(axes))
return reshape(grad, shape)

return (reduce_to_shape(lhs_grad, lhs.shape),
reduce_to_shape(rhs_grad, rhs.shape))
  • Negate

按元素取负,梯度即为乘 -1。

1
2
3
4
5
6
7
8
9
10
class Negate(TensorOp):
def compute(self, a):
### BEGIN YOUR SOLUTION
return array_api.negative(a)
### END YOUR SOLUTION

def gradient(self, out_grad, node):
### BEGIN YOUR SOLUTION
return (negate(out_grad), )
### END YOUR SOLUTION
  • Log & Exp

这两个都没啥好说的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Log(TensorOp):
def compute(self, a):
return array_api.log(a)

def gradient(self, out_grad, node):
a = node.inputs[0]
return (divide(out_grad, a), )

class Exp(TensorOp):
def compute(self, a):
return array_api.exp(a)

def gradient(self, out_grad, node):
a = node.inputs[0]
return (out_grad * exp(a), )

Topological Sort

这部分需要实现拓扑排序。文档里叽里呱啦说了半天,说白了就是 后续遍历的 DFS 序即为逆拓扑序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def find_topo_sort(node_list: List[Value]) -> List[Value]:
visited = dict()
topo_order = []
for node in node_list:
if not visited.get(node, False):
topo_sort_dfs(node, visited, topo_order)
return topo_order

def topo_sort_dfs(node: Value, visited: dict, topo_order: List[Value]) -> None:
"""Post-order DFS"""
for fa in node.inputs:
if not visited.get(fa, False):
topo_sort_dfs(fa, visited, topo_order)
visited[node] = True
topo_order.append(node)

有同学会问,为什么不用 BFS 的方式求。答维护每个节点的入度是很大的开销。

reverse mode AD

开始措自动微分了。核心代码和 Lecture 3 中讲的都差不多。autograd.py 中还给我们提供了一个 sum_node_list 函数,对一系列 node 进行求和,对应伪代码中 $=_j 的部分。

由于 ops 中的算子都是继承自 TensorOp,会自动调用 make_from_op,然后拓展计算图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def compute_gradient_of_variables(output_tensor, out_grad):
node_to_output_grads_list: Dict[Tensor, List[Tensor]] = {}
node_to_output_grads_list[output_tensor] = [out_grad]

reverse_topo_order = list(reversed(find_topo_sort([output_tensor])))

for node in reverse_topo_order:
node.grad = sum_node_list(node_to_output_grads_list[node])

# not a initial/leaf node
if len(node.inputs) > 0:
grad = node.op.gradient(node.grad, node)
for i, fa in enumerate(node.inputs):
node_to_output_grads_list.setdefault(fa, [])
node_to_output_grads_list[fa].append(grad[i])

Softmax loss

用 ndl.Tensor 的算子实现 softmax loss。为了方便计算,已经很贴心的把 \(y\) 替换成了独热编码。没啥好说的,照着公式写即可。

1
2
3
4
5
def softmax_loss(Z: ndl.Tensor, y_one_hot: ndl.Tensor):
sum_log = ndl.log(ndl.summation(ndl.exp(Z), axes=(1, )))
prob = ndl.summation(ndl.multiply(Z, y_one_hot), axes=(1, ))
tot_loss = ndl.summation(sum_log - prob)
return ndl.divide_scalar(tot_loss, Z.shape[0])

SGD for nn

利用前面的逐渐,实现一个双层感知机一个 epoch 的训练过程。需要注意,这里传入的 \(y\) 是 label 类型,需要转换为独热编码。然后在更新权重的时候,建议转换成 NumPy 计算,否则会把不必要的运算加入计算图,导致计算图指数级增长。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def nn_epoch(X, y, W1, W2, lr=0.1, batch=100):
m = X.shape[0]
num_classes = W2.shape[1]
y_one_hot = np.eye(num_classes)[y]

for start in range(0, m, batch):
end = min(start + batch, m)
X_batch = X[start:end, ]
y_batch = y_one_hot[start:end]
batch_size = X_batch.shape[0]

X_tensor = ndl.Tensor(X_batch)
y_tensor = ndl.Tensor(y_batch)
Z1 = ndl.relu(ndl.matmul(X_tensor, W1))
Z2 = ndl.matmul(Z1, W2)
loss = softmax_loss(Z2, y_tensor)
loss.backward()

new_W1 = ndl.Tensor(W1.numpy() - lr * W1.grad.numpy())
new_W2 = ndl.Tensor(W2.numpy() - lr * W2.grad.numpy())
W1, W2 = new_W1, new_W2

return W1, W2

HW1 总结

强度已经明显大了很多,主要难在推公式上,全靠 GPT 大人推导()。

HW2

使用 deepseek v4.1 flash 生成

Weight Initialization

这四种初始化方法目标一致:让信号在前向传播时每一层的方差都维持在稳定区间,既不会越传越强、也不会逐层衰减,从而避免梯度消失 / 梯度爆炸。实现上就是按 fan_in / fan_out 反推出均匀分布的范围或正态分布的标准差,再交给 init.rand / init.randn 生成张量。

正态分布版本: \[ \text{xavier}: \sigma^2 = \frac{2}{\text{fan\_in}+\text{fan\_out}}, \quad \text{kaiming(relu)}: \sigma^2 = \frac{2}{\text{fan\_in}} \]

均匀分布 \(U(-a, a)\) 的方差是 \(a^2/3\),反推回去就有 \(a=\sqrt{6/(\text{fan\_in}+\text{fan\_out})}\)(xavier)和 \(a=\sqrt{6/\text{fan\_in}}\)(kaiming)。两者的差别在分母:kaiming 只看 fan_in,是专门为 ReLU 设计的——\(\text{ReLU}\) 会把一半激活压成 0,方差得乘回 2(即 gain \(=\sqrt 2\));而反向传播时信号希望 fan_in 和 fan_out 对称,这正是 xavier 分母里多出一个 \(\text{fan\_out}\) 的原因。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def xavier_uniform(fan_in, fan_out, gain=1.0, **kwargs):
a = gain * math.sqrt(6 / (fan_in + fan_out))
return rand(fan_in, fan_out, low=-a, high=a, **kwargs)

def xavier_normal(fan_in, fan_out, gain=1.0, **kwargs):
std = gain * math.sqrt(2 / (fan_in + fan_out))
return randn(fan_in, fan_out, std=std, **kwargs)

def kaiming_uniform(fan_in, fan_out, nonlinearity="relu", **kwargs):
assert nonlinearity == "relu", "Only relu supported currently"
bound = math.sqrt(6 / fan_in)
return rand(fan_in, fan_out, low=-bound, high=bound, **kwargs)

def kaiming_normal(fan_in, fan_out, nonlinearity="relu", **kwargs):
assert nonlinearity == "relu", "Only relu supported currently"
std = math.sqrt(2 / fan_in)
return randn(fan_in, fan_out, std=std, **kwargs)

nn Basic Module

python/needle/nn/nn_basic.py。这里有条贯穿全程的规矩:Module.parameters() 只认 Parameter 类型(见 _unpack_params),凡是要被优化的张量都得包一层 Parameter(...),否则优化器根本看不见它。另外 needle 不做隐式广播,w * x + b 之前得手动 broadcast_to。

先看模板里已经写好的骨架(虽然不用自己实现,但决定了所有模块的写法):parameters() 会递归扫描 self.__dict__ 里的 dict / list / tuple,只要把 Parameter 挂成成员变量就能被挖出来;eval() / train() 也同样递归,会把整棵子树的 training flag 一并改掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Parameter(Tensor):
"""A special kind of tensor that represents parameters."""

def _unpack_params(value):
if isinstance(value, Parameter):
return [value]
elif isinstance(value, Module):
return value.parameters()
elif isinstance(value, dict):
params = []
for k, v in value.items():
params += _unpack_params(v)
return params
elif isinstance(value, (list, tuple)):
params = []
for v in value:
params += _unpack_params(v)
return params
else:
return []

class Module:
def __init__(self):
self.training = True

def parameters(self):
"""Return the list of parameters in the module."""
return _unpack_params(self.__dict__)

def _children(self):
return _child_modules(self.__dict__)

def eval(self):
self.training = False
for m in self._children():
m.training = False

def train(self):
self.training = True
for m in self._children():
m.training = True

def __call__(self, *args, **kwargs):
return self.forward(*args, **kwargs)
  • Linear

self.weight 的形状是 (in_features, out_features),所以 forward 里是 X @ W 而非 PyTorch 的 X @ W.T。注意要先初始化 weight 再初始化 bias——两者都会消耗随机数,顺序一换,后面 mugrade 的期望值就全对不上了。bias 借 kaiming 生成一个 (out_features, 1) 再转置成 (1, out_features),把标准差控制在合适范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Linear(Module):
def __init__(self, in_features, out_features, bias=True, device=None, dtype="float32"):
super().__init__()
self.in_features = in_features
self.out_features = out_features

weight_tensor = init.kaiming_uniform(in_features, out_features, dtype=dtype, device=device)
self.weight = Parameter(weight_tensor, requires_grad=True)
if bias == True:
bias_tensor = init.kaiming_uniform(out_features, 1, dtype=dtype, device=device)
self.bias = Parameter(ops.transpose(bias_tensor), requires_grad=True)
else:
self.bias = None

def forward(self, X):
result = ops.matmul(X, self.weight)
if self.bias is None:
return result
else:
return result + ops.broadcast_to(self.bias, result.shape)
  • ReLU

HW1 里那个用缓存输入开 mask 的 ops_mathematic.ReLU 直接拿来当模块用即可。

1
2
3
class ReLU(Module):
def forward(self, x):
return ops.relu(x)
  • Sequential / Flatten / Residual

Sequential 正着调一遍即可;Flatten 保留 batch 维,把剩下全部展平,本质就是个 reshape;Residual 直接把输入原样加上去。三者都无需多言。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Sequential(Module):
def __init__(self, *modules):
super().__init__()
self.modules = modules

def forward(self, x):
out = x
for module in self.modules:
out = module(out)
return out

class Flatten(Module):
def forward(self, X):
B = X.shape[0]
return X.reshape((B, -1))

class Residual(Module):
def __init__(self, fn):
super().__init__()
self.fn = fn

def forward(self, x):
return x + self.fn(x)

LogSumExp 和 LogSoftmax

在 ops/ops_logarithmic.py 里,这是 SoftmaxLoss 的零件,核心在数值稳定性:直接算 \(\exp(1000)\) 会溢出成 inf,\(\exp(-1000)\) 会下溢成 0。做法是先提出最大值 \(M=\max z\):

\[ \log\sum_i e^{z_i} = \log\left(e^{M}\sum_i e^{z_i-M}\right) = M + \log\sum_i e^{z_i - M} \]

显见所有指数都 \(\le 1\),从根上避免溢出;那些仍然下溢的项本来就相对最大值可忽略,无伤大雅。参考:https://indii.org/blog/gradients-of-softmax-and-logsumexp/

梯度方面 \(\frac{\partial \text{LSE}(z)}{\partial z_i} = \frac{e^{z_i}}{\sum_j e^{z_j}} = \exp(z_i - \text{LSE}(z))\),恰好就是 softmax。这里有个坑:compute 里我把归约掉的轴 squeeze 掉了(与 Summation 保持一致),反向传回来的 out_grad 因此少了几维,得先 reshape 成对应轴为 1 的形状再广播回去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class LogSumExp(TensorOp):
def __init__(self, axes=None):
self.axes = axes

def compute(self, Z):
max_z = array_api.max(Z, axis=self.axes, keepdims=True)
sum_z = array_api.sum(array_api.exp(Z - max_z), axis=self.axes, keepdims=True)
out = array_api.log(sum_z) + max_z
if self.axes is None:
return array_api.squeeze(out)
return array_api.squeeze(out, axis=self.axes)

def gradient(self, out_grad, node):
Z = node.inputs[0]
ndim = len(Z.shape)
axes = range(ndim) if self.axes is None else self.axes
shape = tuple([1 if i in axes else Z.shape[i] for i in range(ndim)])

out_grad_fixed = out_grad.reshape(shape).broadcast_to(Z.shape)
node_fixed = node.reshape(shape).broadcast_to(Z.shape)
grad = exp(Z - node_fixed) * out_grad_fixed
return (grad, )

LogSoftmax 沿 axis=1 归一化,输入按题目约定是 2D 的,\(\text{logsoftmax}(z)_i = z_i - \text{LSE}(z)\)。它的雅可比 \(\partial y_i/\partial z_j = \delta_{ij} - p_j\)(\(p=\text{softmax}(z)\)),所以反向传播恰好是个 rowmatvec:

\[ \text{grad}_z = \text{out\_grad} - p\,\sum_j \text{out\_grad}_j \]

官方签名载的是 LogSoftmax(axes),但既然已约定只处理 2D + axis=1,我便图省事把 axes 写死在 compute 里。规范做法是放进 __init__。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class LogSoftmax(TensorOp):
def compute(self, Z):
axes = (1, )
max_z = array_api.max(Z, axis=axes, keepdims=True)
sum_z = array_api.sum(array_api.exp(Z - max_z), axis=axes, keepdims=True)
return Z - array_api.log(sum_z) - max_z

def gradient(self, out_grad, node):
Z = node.inputs[0]
probs = exp(node) # node 存的是 logsoftmax,exp 回去就是 softmax

grad_sum = summation(out_grad, axes=(1, ))
grad_sum = grad_sum.reshape((Z.shape[0], 1)).broadcast_to(Z.shape)
grad = out_grad - probs * grad_sum
return (grad, )

SoftmaxLoss

把 HW1 里那个 loss 用 LogSumExp 重写一遍: \[ \ell_{\text{softmax}}(z,y) = \log\sum_{i=1}^{k}\exp z_i - z_y = -\,\text{logsoftmax}(z)_y \]

也就是拿 logsoftmax 的输出点乘 one-hot,全求和再取负并除以 batch_size。one-hot 现在直接用 init.one_hot 生成即可。

1
2
3
4
5
6
7
class SoftmaxLoss(Module):
def forward(self, logits, y):
batch_size, num_classes = logits.shape
log_probs = ops.logsoftmax(logits)
y_one_hot = init.one_hot(num_classes, y)
loss = ops.summation(log_probs * y_one_hot)
return -(loss / batch_size)

LayerNorm1d

沿 axis=1(特征维)归一化,与 BatchNorm 沿 axis=0(batch 维)恰好相反,因此完全不受 batch 影响,推理时也不需 running stats。方差用题目指定的有偏估计(除 \(N\),而非 \(N-1\))。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class LayerNorm1d(Module):
def __init__(self, dim, eps=1e-5, device=None, dtype="float32"):
super().__init__()
self.dim = dim
self.eps = eps
self.weight = Parameter(init.ones(1, dim, device=device, dtype=dtype), device=device, dtype=dtype)
self.bias = Parameter(init.zeros(1, dim, device=device, dtype=dtype), device=device, dtype=dtype)

def forward(self, x):
batch_size, feature_size = x.shape

mean = ops.summation(x, axes=(1, )) / feature_size
mean = mean.reshape((batch_size, 1)).broadcast_to(x.shape)

square = (x - mean) ** 2
var = ops.summation(square, axes=(1, )) / feature_size
var = var.reshape((batch_size, 1)).broadcast_to(x.shape)

weight = self.weight.broadcast_to(x.shape)
bias = self.bias.broadcast_to(x.shape)
x_norm = (x - mean) / ops.power_scalar(var + self.eps, 0.5)

out = weight * x_norm + bias
return out

weight 全 1、bias 全 0,形状均为 (1, dim),两者都能直接 broadcast_to(x.shape);它们同样要包成 Parameter,否则这两条仿射参数不会被优化。均值方差全靠 summation + reshape + broadcast_to 手搓——needle 不做隐式广播,只能这样。

BatchNorm1d

式子与 LayerNorm 完全一致,只是统计量改沿 batch 维计算,并多出一套 running_mean / running_var:训练时用当前 batch 的统计量,同时以 momentum 滑动更新运行估计;推理(self.training == False)时改用运行估计,来一个样本也能正常前向传播(batch_size = 1)。

\[ \hat{x}_{new} = (1-m)\,\hat{x}_{old} + m\,x_{observed} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class BatchNorm1d(Module):
def __init__(self, dim, eps=1e-5, momentum=0.1, device=None, dtype="float32"):
super().__init__()
self.dim = dim
self.eps = eps
self.momentum = momentum

self.weight = Parameter(init.ones(1, dim, device=device, dtype=dtype), device=device, dtype=dtype)
self.bias = Parameter(init.zeros(1, dim, device=device, dtype=dtype), device=device, dtype=dtype)

self.running_mean = Tensor(init.zeros(dim), device=device, dtype=dtype, requires_grad=False)
self.running_var = Tensor(init.ones(dim), device=device, dtype=dtype, requires_grad=False)

def forward(self, x):
# training
if self.training == True:
batch_size, feature_size = x.shape
mean_batch = ops.summation(x, axes=(0, )) / batch_size
mean = mean_batch.broadcast_to(x.shape)

square = (x - mean) ** 2
var_batch = ops.summation(square, axes=(0, )) / batch_size
var = var_batch.broadcast_to(x.shape)

self.running_mean = (1 - self.momentum) * self.running_mean + self.momentum * mean_batch.data
self.running_var = (1 - self.momentum) * self.running_var + self.momentum * var_batch.data

weight = self.weight.broadcast_to(x.shape)
bias = self.bias.broadcast_to(x.shape)
x_norm = (x - mean) / ops.power_scalar(var + self.eps, 0.5)

out = weight * x_norm + bias
return out
# reasoning
else:
weight = self.weight.broadcast_to(x.shape)
bias = self.bias.broadcast_to(x.shape)
x_norm = (x - self.running_mean) / ops.power_scalar(self.running_var + self.eps, 0.5)

out = weight * x_norm + bias
return out

三个坑:

  1. 更新 running stats 务必用 .data 取裸数组,否则这些值会一直挂在计算图上,图越滚越大,带 memory_check 的测试直接 OOM。
  2. running_mean/running_var 是普通 Tensor(requires_grad=False),不能包成 Parameter——它们是统计量而不是参数,被 parameters() 抓去交给优化器就完了。方差也必须是这里手搓的有偏估计,直接抄 x.var(axis=0)(PyTorch 默认无偏、除 \(N-1\))会对不上 mugrade。
  3. train() / eval() 是 Module 递归设置的 flag,藏在 Sequential/Residual 里的 Dropout、BatchNorm 都会跟着切换(test_nn_batchnorm_check_model_eval_switches_training_flag 测的正是这点)。此外,官方文档里 eval 的公式没写仿射项,但 PyTorch 实际是带 \(w, b\) 的,这里照 PyTorch 处理。

Dropout

以概率 \(p\) 置零,再除以 \(1-p\) 把期望拉回来(inverted dropout),这样推理时可直接恒等返回、无需再缩放:

\[ \mathbb{E}[\text{Dropout}(z_j)] = (1-p)\cdot\frac{z_j}{1-p} + p\cdot 0 = z_j \]

1
2
3
4
5
6
7
8
9
10
class Dropout(Module):
def __init__(self, p=0.5):
super().__init__()
self.p = p

def forward(self, x):
if not self.training:
return x
mask = init.randb(*x.shape, p=1 - self.p)
return x * mask / (1 - self.p)

init.randb 返回 bool 张量,直接乘上去当 mask 用。注意 \(p\) 是「丢弃」的概率,采样参数应写 \(1-p\)。

优化器

python/needle/optim.py。SGD(带动量和权重衰减):

\[ u_{t+1} = \beta u_t + (1-\beta)\nabla_\theta f(\theta_t), \qquad \theta_{t+1} = \theta_t - \alpha u_{t+1} \]

1
2
3
4
5
6
7
8
def step(self):
for param in self.params:
if param.grad is not None:
if param not in self.u.keys():
self.u[param] = ndl.zeros_like(param.data, requires_grad=False)
self.u[param] = self.momentum * self.u[param] + (1 - self.momentum) * \
(param.grad.data + self.weight_decay * param.data)
param.data = param.data - self.lr * self.u[param]

Adam 再加二阶动量和偏差修正:

\[ \begin{split} u_{t+1} &= \beta_1 u_t + (1-\beta_1) g_t \\ v_{t+1} &= \beta_2 v_t + (1-\beta_2) g_t^2 \\ \hat u_{t+1} &= u_{t+1}/(1-\beta_1^t), \hat v_{t+1} = v_{t+1}/(1-\beta_2^t) \\ \theta_{t+1} &= \theta_t - \alpha\, \hat u_{t+1}/(\hat v_{t+1}^{1/2}+\epsilon) \end{split} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def step(self):
self.t += 1
for param in self.params:
if param.grad is not None:
if param not in self.m.keys():
self.m[param] = ndl.zeros_like(param.data, requires_grad=False)
if param not in self.v.keys():
self.v[param] = ndl.zeros_like(param.data, requires_grad=False)
grad = param.grad.data + self.weight_decay * param.data
self.m[param] = self.beta1 * self.m[param].data + (1 - self.beta1) * grad.data
self.v[param] = self.beta2 * self.v[param].data + (1 - self.beta2) * grad.data * grad.data
u_hat = self.m[param].data / (1 - self.beta1 ** self.t)
v_hat = self.v[param].data / (1 - self.beta2 ** self.t)
param.data = param.data - self.lr * u_hat.data / (ndl.power_scalar(v_hat.data, 0.5) + self.eps).data

要点:

  1. 全程在 .data(裸 NDArray)上算,一点 autograd 都不要碰,否则每次 step() 都在往计算图上接新节点,图一直长,memory_check 测试立刻 OOM。
  2. 不要 in-place 改 param.grad(题目专门强调过)。这里的 weight decay 是加在梯度上的,相当于把 \(\frac{1}{2}\lambda\lVert\theta\rVert^2\) 并进 loss,而非 AdamW 那种 decoupled weight decay。
  3. \(u/m/v\) 这类状态用 dict 按参数存,首次遇到某参数时 zeros_like 开一份;偏差修正用的 \(t\) 是全局步数,在 step 开头自增。忘了 bias correction,前期 \(m, v\) 偏小会把步长带偏。
  4. 题目的动量公式带了 \((1-\beta)\),与 PyTorch 的 SGD(\(u\leftarrow \beta u + g\)、没有 \(1-\beta\))不同,照题目来才能对上 mugrade。

数据管道

python/needle/data/ 下面分三块来写。

  • 数据增广在 data_transforms.py:随机水平翻转就是掷骰子决定要不要 np.flip(img, axis=1)(注意轴是 1,即 W);随机裁剪先 np.pad 补一圈零,再按随机偏移 \(\in[-padding, padding]\) 切回原尺寸。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class RandomFlipHorizontal(Transform):
def __init__(self, p=0.5):
self.p = p

def __call__(self, img):
"""H x W x C NDArray -> 以概率 p 水平翻转"""
flip_img = np.random.rand() < self.p
if flip_img:
img = np.flip(img, axis=1)
return img

class RandomCrop(Transform):
def __init__(self, padding=3):
self.padding = padding

def __call__(self, img):
"""零填充后随机裁剪回原尺寸"""
shift_x, shift_y = np.random.randint(low=-self.padding, high=self.padding+1, size=2)
img_size = img.shape
img = np.pad(img, ((self.padding, self.padding), (self.padding, self.padding), (0, 0)), 'constant')
img = img[self.padding + shift_x:self.padding + shift_x + img_size[0],
self.padding + shift_y:self.padding + shift_y + img_size[1], :]
return img
  • MNISTDataset:__init__ 直接复用 HW1 的 parse_mnist 读入 images/labels;__getitem__ 先 reshape 成 28x28x1 才能喂给 transforms(它们约定输入是 HxWxC),最后返回 (image, label) 二元组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class MNISTDataset(Dataset):
def __init__(self, image_filename, label_filename, transforms=None):
self.images, self.labels = parse_mnist(image_filename, label_filename)
self.transforms = transforms

def __getitem__(self, index):
x = self.images[index]
if self.transforms is not None:
# transforms 要求输入是 H x W x C
x = self.apply_transforms(x.reshape((28, 28, 1)))
return x, self.labels[index]

def __len__(self):
return self.images.shape[0]

Dataset 基类已经把 apply_transforms(依次跑一遍 transforms 列表)写好了,子类只需要实现 __getitem__ 和 __len__。

  • DataLoader 的 __iter__ / __next__:shuffle=False 时 __init__ 已把 np.arange(len(dataset)) 用 np.array_split 切好;shuffle=True 时须在 __iter__(即每个 epoch 开头)重新 np.random.permutation 一次,并把游标 self.idx 归零——所以 __iter__ 不是摆设,少了它第二个 epoch 就没数据。__next__ 取一段索引、把样本 np.stack 起来,取完 raise StopIteration 让 for 循环正常结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class DataLoader:
def __init__(self, dataset, batch_size=1, shuffle=False):
self.dataset = dataset
self.shuffle = shuffle
self.batch_size = batch_size
if not self.shuffle:
self.ordering = np.array_split(np.arange(len(dataset)),
range(batch_size, len(dataset), batch_size))

def __iter__(self):
if self.shuffle:
# reshuffle the data at the beginning of every epoch
self.ordering = np.array_split(
np.random.permutation(len(self.dataset)),
range(self.batch_size, len(self.dataset), self.batch_size),
)
self.idx = 0
return self

def __next__(self):
if self.idx >= len(self.ordering):
raise StopIteration
batch_indices = self.ordering[self.idx]
self.idx += 1
batch = [self.dataset[i] for i in batch_indices]
# dataset 可能返回单个数组,也可能返回 (image, label) 这种 tuple
if isinstance(batch[0], tuple):
return tuple(Tensor(np.stack(col)) for col in zip(*batch))
return Tensor(np.stack(batch))

文档说 __next__ 返回 NDArray,但这版测试是拿 batch[0].numpy() 取值的,所以要包成 Tensor。zip(*batch) 把「(图, 标签) 的列表」转成「(图堆叠, 标签堆叠)」,顺带解决 label 各自形状 (1,) 对不齐的问题。

MLP ResNet

apps/mlp_resnet.py。残差块为 Linear → norm → ReLU → Dropout → Linear → norm,外面套一层 nn.Residual 再接一个 ReLU:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def ResidualBlock(dim, hidden_dim, norm=nn.BatchNorm1d, drop_prob=0.1):
return nn.Sequential(
nn.Residual(
nn.Sequential(
nn.Linear(dim, hidden_dim),
norm(hidden_dim),
nn.ReLU(),
nn.Dropout(drop_prob),
nn.Linear(hidden_dim, dim),
norm(dim))
),
nn.ReLU()
)

def MLPResNet(dim, hidden_dim=100, num_blocks=3, num_classes=10,
norm=nn.BatchNorm1d, drop_prob=0.1):
return nn.Sequential(
nn.Linear(dim, hidden_dim),
nn.ReLU(),
*[ResidualBlock(hidden_dim, hidden_dim // 2, norm, drop_prob) for _ in range(num_blocks)],
nn.Linear(hidden_dim, num_classes),
)

「Modules should be initialized to match the order of execution」这句并不是建议——每个 nn.Linear 都消耗随机数,构造顺序一变,后面所有层的权重全跟着变,mugrade 期望输出立刻对不上。

epoch 靠 opt 是否给定来切模式:给了就 .train(),没给就 .eval()(测试会故意先调成反方向,就为校验这一点);loss 和错误率都按样本数加权累加,最后除以总样本数。np.random.seed(4) 是对确定性的要求。train_mnist 就是搭两个 dataloader(训练集 shuffle=True)、建模型、建优化器,再循环 epoch。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def epoch(dataloader, model, opt=None):
np.random.seed(4)
if opt is not None:
model.train()
else:
model.eval()
total_error, total_loss, total_samples = 0.0, 0.0, 0
loss_fn = nn.SoftmaxLoss()
for X, y in dataloader:
batch_size = X.shape[0]
logits = model(X)
loss = loss_fn(logits, y)
if opt is not None:
opt.reset_grad()
loss.backward()
opt.step()
total_loss += loss.numpy() * batch_size
pred = logits.numpy().argmax(axis=1)
total_error += np.sum(pred != y.numpy())
total_samples += batch_size
return total_error / total_samples, total_loss / total_samples

默认超参(Adam、lr=1e-3、weight_decay=1e-3、batch=100、hidden=100、3 个 block)跑满 10 epoch,i9-11980HK 上约 7 秒一个 epoch:

epoch train err train loss test err test loss
1 12.11% 0.3975 4.71% 0.1521
2 4.71% 0.1565 4.03% 0.1263
5 2.18% 0.0721 3.08% 0.1011
10 1.49% 0.0485 2.71% 0.0918

测试错误率约 2.7%,比 HW1 手搓的 MLP 好太多。注意后期 train err 仍在降、test err 已基本不降,过拟合的迹象来了。

HW2 总结

比 HW1 更磨人的是各种「隐形约定」而非算法本身:.data 忘了就是拿内存换计算图,Parameter 忘了包就被优化器无视,初始化顺序错一位整套权重就换一套,train/eval flag 决定 BatchNorm 和 Dropout 到底生不生效,需要给每种场景写两套流程。

到这一个基本的 DL System 就已经完成了。接下来就是实现 GPU 后端,以及更复杂的神经网络。

HW3

使用 claude haiku 5.5 生成

前两个作业都在 NumPy 的暖房里写算子,HW3 把这层地基抽掉:自己实现一个 NDArray 库,同时提供 CPU (ndarray_backend_cpu.cc) 与 CUDA (ndarray_backend_cuda.cu) 两套原生后端,矩阵乘法要用分块、共享内存、寄存器 tile 手搓到「只比 BLAS 慢几倍」的量级。

仓库:Assignment 3。HW3 只需改 python/needle/backend_ndarray/ 与 src/,HW1/HW2 的代码完全用不上。

设计哲学:元数据在 Python,计算在 C++

一个 n 维数组在内存里永远是扁平的一维 float data[size],靠四个字段把「一维内存」映射到「n 维结构」:

字段 含义
_shape 各维长度
_strides 各维步长(元素为单位,不是字节)
_offset 首个元素在 handle 里的下标
_device BackendDevice,包装了具体后端模块

关键约定:凡是能靠改 stride 做到的,一律不碰内存。reshape / permute / broadcast_to / __getitem__ 全都返回共享同一块 handle 的新视图(测试里 check_same_memory 专门校验 _handle.ptr() 相等);只有真的要做数值运算或布局重排,才下到 C++/CUDA。

BackendDevice 是个薄壳,__getattr__ 直接把属性转发给后端模块,所以 self.device.ewise_add 就是 C++ 里 m.def("ewise_add", ...) 注册的函数。backend_selection.py 用环境变量 NEEDLE_BACKEND 在 nd(自研后端)和 np(numpy 后端)间切换,all_devices() 返回 [cpu(), cuda(), cpu_numpy()],测试靠 device.name 区分。

需要注意 cuda() 的写法:ndarray_backend_cuda 导入失败时返回一个 mod=None 的 device,enabled() 为 False,测试据此 skip;所以 CUDA 没编译出来时测试是 SKIPPED 而不是 FAILED,别被绿色迷惑。

Part 1: Python 层的元数据操作

四个函数,全都不分配内存。

  • reshape:先检查 prod(shape) 相等,且 is_compact()。因为纯布局重排只对连续内存成立,非 compact 的数组必须先 .compact()。新 strides 直接取 compact_strides(new_shape),handle 与 offset 原样带走。
1
2
3
4
5
6
7
def reshape(self, new_shape):
if prod(self._shape) != prod(new_shape):
raise ValueError(...)
if not self.is_compact():
raise ValueError(...)
return self.make(shape=new_shape, strides=self.compact_strides(new_shape),
device=self._device, handle=self._handle, offset=self._offset)
  • permute:轴序置换,shape 和 strides 一起跟着换,什么都不用算。
1
2
new_shape = tuple(self._shape[i] for i in new_axes)
new_strides = tuple(self._strides[i] for i in new_axes)
  • broadcast_to:这是整个 HW3 里最优雅的一处——广播的轴把 stride 设成 \(0\) 就完事了。因为偏移 idx * 0 = 0,无论下标怎么走都落在同一个元素上,天然就是「复制」语义,却零拷贝。前面要补的维度同样补 stride 0。
1
2
3
4
5
6
7
8
9
pad = len(new_shape) - self.ndim
padded_shape = (1,) * pad + self._shape
padded_strides = (0,) * pad + self._strides

new_strides = []
for u, v, w in zip(padded_shape, padded_strides, new_shape):
if u == w: new_strides.append(v) # 原样
elif u == 1: new_strides.append(0) # 广播
else: raise AssertionError(...)
  • __getitem__:模板已把「整数下标 / 负下标 / 负切片」统一规整成 start、stop、step 全非负的 slice。于是

\[ \text{new\_shape}_i = \left\lfloor\frac{\text{stop}_i - 1 - \text{start}_i}{\text{step}_i}\right\rfloor + 1, \quad \text{new\_stride}_i = \text{step}_i \cdot \text{stride}_i, \quad \text{new\_offset} = \text{offset} + \sum_i \text{start}_i \cdot \text{stride}_i \]

整数下标会被转成 slice(s, s+1, 1),因此 __getitem__ 永远不降维:A[2, 2] 返回的是 2D 的 1x1 数组,而非标量。这点和 numpy 不同,是为了让后面 ewise_setitem 的 shape 处理统一。

is_compact() 的判据是 strides == compact_strides(shape) 且 prod(shape) == handle.size——后者顺带保证了 offset 为 0 且尾部无冗余,这正是 C++ 里 Compact 可以直接顺序写的依据。

Part 2: CPU 后端 — Compact 与 setitem

三个函数本质是同一件事:在「strided 视图」和「顺序内存」之间搬运。理论上要写 ndim 层嵌套循环,但 ndim 是运行时才知道的,所以模板里给了个更聪明的做法——里程表(odometer)式的 next_offset:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
template <typename ShapeContainer, typename StrideContainer,
typename StateContainer>
inline int64_t next_offset(const ShapeContainer &shape,
const StrideContainer &strides,
StateContainer &state, int64_t idx) {
const int32_t ndim = static_cast<int32_t>(shape.size());
int64_t offset = idx;
for (int32_t d = ndim - 1; d >= 0; --d) {
state[d] += 1;
offset += static_cast<int64_t>(strides[d]);
if (state[d] < static_cast<int64_t>(shape[d]))
break;
offset -= static_cast<int64_t>(strides[d]) * shape[d];
state[d] = 0;
}
return offset;
}

template <typename ShapeContainer, typename StrideContainer,
typename StateContainer, typename OffsetT, typename Function>
void for_each_element(const ShapeContainer &shape,
const StrideContainer &strides, StateContainer &state,
OffsetT offset, Function &&fn) {
int64_t tot = 1;
for (auto s : shape)
tot *= static_cast<int64_t>(s);

int64_t idx = static_cast<int64_t>(offset);
for (int64_t cnt = 0; cnt < tot; ++cnt) {
fn(cnt, idx);
idx = next_offset(shape, strides, state, idx);
}
}

state 记录每一维当前走到哪,每步只做「加一个 stride,若溢出则减回去并进位」。均摊 \(O(1)\),且不用为每一维写一遍循环嵌套。外层再套一层 for_each_element,把 (序号 cnt, 物理偏移 offset) 交给 lambda:

1
2
3
4
5
6
void Compact(const AlignedArray &a, AlignedArray *out, const std::vector<int32_t> &shape,
const std::vector<int32_t> &strides, size_t offset) {
for_each_element(shape, strides, offset, [&](int64_t cnt, int64_t offset) {
out->ptr[cnt] = a.ptr[offset];
});
}

三个函数的差异只在谁读谁写:Compact 从 strided 读、往紧凑写;EwiseSetitem 从紧凑的 a 读、往 strided 的 out 写;ScalarSetitem 把标量写进 strided 的 out。注意签名方向的不对称——a 永远假设是 compact 的(Python 侧已经 .compact() 过),只有 out 带 strides 和 offset。

AlignedArray 用 posix_memalign 向 256 字节对齐,这不是洁癖:后面的 AlignedDot 要靠对齐才能让编译器安全地向量化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void EwiseSetitem(const AlignedArray &a, AlignedArray *out,
std::vector<int32_t> shape, std::vector<int32_t> strides,
size_t offset) {
for_each_element(shape, strides, offset, [&](int64_t cnt, int64_t offset) {
out->ptr[offset] = a.ptr[cnt];
});
}

void ScalarSetitem(const size_t size, scalar_t val, AlignedArray *out,
std::vector<int32_t> shape, std::vector<int32_t> strides,
size_t offset) {
for_each_element(shape, strides, offset, [&](int64_t cnt, int64_t offset) {
out->ptr[offset] = val;
});
}

Part 3: CPU 后端 — 逐元素与标量算子

要实现的十几对函数形式完全一样,硬写就是大量复制粘贴。用一对模板 + lambda 收敛掉:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename BinaryFn>
void EwiseOp(const AlignedArray &a, const AlignedArray &b, AlignedArray *out, BinaryFn &&fn) {
for (size_t i = 0; i < a.size; ++i) out->ptr[i] = fn(a.ptr[i], b.ptr[i]);
}

template <typename UnaryFn>
void UnaryOp(const AlignedArray &a, AlignedArray *out, UnaryFn &&fn) {
for (size_t i = 0; i < a.size; ++i) out->ptr[i] = fn(a.ptr[i]);
}

void EwiseMul(const AlignedArray &a, const AlignedArray &b, AlignedArray *out) {
EwiseOp(a, b, out, [](scalar_t l, scalar_t r) { return l * r; });
}
// EwiseDiv / EwiseMaximum / ScalarMul / ScalarDiv / ScalarPower / EwiseLog ...
void EwiseEq(const AlignedArray &a, const AlignedArray &b, AlignedArray *out) {
EwiseOp(a, b, out, [](scalar_t l, scalar_t r) { return static_cast<scalar_t>(l == r); });
}

比宏好在 lambda 能被内联、能断点,也不用担心宏展开出意外。注意比较类算子返回的是 float 的 0.0/1.0 而非 bool——NDArray 的 __ne__、__gt__ 都是靠 1 - (self == other) 这种算术组合出来的,bool 会炸。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// binary operator helper function
template <typename BinaryFn>
void EwiseOp(const AlignedArray &a, const AlignedArray &b, AlignedArray *out,
BinaryFn &&fn) {
for (size_t i = 0; i < a.size; ++i) {
out->ptr[i] = fn(a.ptr[i], b.ptr[i]);
}
}

// unary operator helper function
template <typename UnaryFn>
void UnaryOp(const AlignedArray &a, AlignedArray *out, UnaryFn &&fn) {
for (size_t i = 0; i < a.size; ++i) {
out->ptr[i] = fn(a.ptr[i]);
}
}

void EwiseMul(const AlignedArray &a, const AlignedArray &b, AlignedArray *out) {
EwiseOp(a, b, out, [](scalar_t l, scalar_t r) { return l * r; });
}

void EwiseDiv(const AlignedArray &a, const AlignedArray &b, AlignedArray *out) {
EwiseOp(a, b, out, [](scalar_t l, scalar_t r) { return l / r; });
}

void EwiseMaximum(const AlignedArray &a, const AlignedArray &b,
AlignedArray *out) {
EwiseOp(a, b, out, [](scalar_t l, scalar_t r) { return std::max(l, r); });
}

void EwiseEq(const AlignedArray &a, const AlignedArray &b, AlignedArray *out) {
EwiseOp(a, b, out, [](scalar_t l, scalar_t r) {
return static_cast<scalar_t>(l == r);
});
}

void EwiseGe(const AlignedArray &a, const AlignedArray &b, AlignedArray *out) {
EwiseOp(a, b, out, [](scalar_t l, scalar_t r) {
return static_cast<scalar_t>(l >= r);
});
}

void ScalarMul(const AlignedArray &a, scalar_t val, AlignedArray *out) {
UnaryOp(a, out, [val](scalar_t l) { return l * val; });
}

void ScalarDiv(const AlignedArray &a, scalar_t val, AlignedArray *out) {
UnaryOp(a, out, [val](scalar_t l) { return l / val; });
}

void ScalarMaximum(const AlignedArray &a, scalar_t val, AlignedArray *out) {
UnaryOp(a, out, [val](scalar_t l) { return std::max(l, val); });
}

void ScalarEq(const AlignedArray &a, scalar_t val, AlignedArray *out) {
UnaryOp(a, out,
[val](scalar_t l) { return static_cast<scalar_t>(l == val); });
}

void ScalarGe(const AlignedArray &a, scalar_t val, AlignedArray *out) {
UnaryOp(a, out,
[val](scalar_t l) { return static_cast<scalar_t>(l >= val); });
}

void ScalarPower(const AlignedArray &a, scalar_t val, AlignedArray *out) {
UnaryOp(a, out, [val](scalar_t l) { return std::pow(l, val); });
}

void EwiseLog(const AlignedArray &a, AlignedArray *out) {
UnaryOp(a, out, [](scalar_t l) { return std::log(l); });
}

void EwiseExp(const AlignedArray &a, AlignedArray *out) {
UnaryOp(a, out, [](scalar_t l) { return std::exp(l); });
}

void EwiseTanh(const AlignedArray &a, AlignedArray *out) {
UnaryOp(a, out, [](scalar_t l) { return std::tanh(l); });
}

还有个必踩的坑:函数实现完必须去文件底部的 PYBIND11_MODULE 里把 m.def(...) 取消注释。Python 侧报 AttributeError: module ... has no attribute 'ewise_mul' 时,先查这里而不是查 C++ 逻辑。

Part 4: CPU 后端 — 归约

难点不在 C++,在「怎么把任意 axis 的归约变成「对连续内存块归约」」。这份脏活 Python 侧已经干了(reduce_view_out):

  1. 把要归约的轴 permute 到最后一维;
  2. .compact() 让内存连续;
  3. 于是 ReduceSum/ReduceMax 只需处理「每 reduce_size 个连续元素归约成一个」这一种形态。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def reduce_view_out(self, axis, keepdims=False):
if axis is None:
view = self.compact().reshape((1,) * (self.ndim - 1) + (prod(self.shape),))
out = NDArray.make((1,), device=self.device)
else:
if isinstance(axis, (tuple, list)):
assert len(axis) == 1, "Only support reduction over a single axis"
axis = axis[0]
view = self.permute(tuple([a for a in range(self.ndim) if a != axis]) + (axis,))
out = NDArray.make(
tuple(1 if i == axis else s for i, s in enumerate(self.shape)) if keepdims
else tuple(s for i, s in enumerate(self.shape) if i != axis),
device=self.device)
return view, out

axis=None 时把整个数组压成一长条,输出 shape 是 (1,),再由上层 broadcast_to 回需要的形状。

C++ 侧就三行:

1
2
3
4
5
6
7
8
void ReduceSum(const AlignedArray &a, AlignedArray *out, size_t reduce_size) {
for (size_t i = 0; i < out->size; i++) {
const scalar_t *base = a.ptr + i * reduce_size;
scalar_t res = 0;
for (size_t j = 0; j < reduce_size; j++) res += base[j];
out->ptr[i] = res;
}
}

ReduceMax 记得用 base[0] 初始化,别用 0 或 -inf(前者在负数域直接错)。

1
2
3
4
5
6
7
8
9
void ReduceMax(const AlignedArray &a, AlignedArray *out, size_t reduce_size) {
for (size_t i = 0; i < out->size; i++) {
const scalar_t *base = a.ptr + i * reduce_size;
scalar_t res = base[0];
for (size_t j = 0; j < reduce_size; j++)
res = std::max(base[j], res);
out->ptr[i] = res;
}
}

Part 5: CPU 后端 — 矩阵乘法

两个版本,差距是天壤之别。

朴素版三个循环,i, j, k 顺序,sum 放在寄存器里累加:

1
2
3
4
5
6
7
8
9
10
11
12
void Matmul(const AlignedArray &a, const AlignedArray &b, AlignedArray *out,
uint32_t m, uint32_t n, uint32_t p) {
for (uint32_t i = 0; i < m; ++i) {
for (uint32_t j = 0; j < p; ++j) {
float sum = 0.0f;
for (uint32_t k = 0; k < n; ++k) {
sum += a.ptr[i * n + k] * b.ptr[k * p + j];
}
out->ptr[i * p + j] = sum;
}
}
}

算得对,但 \(B\) 是列访问,每个元素被 cache line 拉进来只用一次,实测 1023³ 只有 2.2 GFLOP/s,比 numpy 慢了两个数量级——正是题目说的「naive 会慢 100 倍」。

分块版:内存被重排成 4D 的 float[M/TILE][N/TILE][TILE][TILE](TILE = 8),Python 侧负责转换:

1
2
3
def tile(a, tile):
return a.as_strided((a.shape[0] // tile, a.shape[1] // tile, tile, tile),
(a.shape[1] * tile, tile, a.shape[1], 1))

即区块下标 (bi, bj) 对应偏移 bi*n*t + bj*t,块内 (i, j) 对应 i*n + j,规整成 4D compact 后再交给 C++。C++ 侧就是把三循环换成「块级三循环 + 块内小矩阵乘」:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void MatmulTiled(const AlignedArray &a, const AlignedArray &b,
AlignedArray *out, uint32_t m, uint32_t n, uint32_t p) {
const uint32_t M = m / TILE;
const uint32_t K = n / TILE;
const uint32_t N = p / TILE;

for (size_t i = 0; i < out->size; ++i) {
out->ptr[i] = 0.0f;
}

for (uint32_t i = 0; i < M; ++i) {
for (uint32_t j = 0; j < N; ++j) {
float *out_block = out->ptr + (i * N + j) * TILE * TILE;
for (uint32_t k = 0; k < K; ++k) {
const float *a_block = a.ptr + (i * K + k) * TILE * TILE;
const float *b_block = b.ptr + (k * N + j) * TILE * TILE;
AlignedDot(a_block, b_block, out_block);
}
}
}
}

AlignedDot 自己还是 8x8x8 的三循环,但它带了两条给编译器承诺:内存已经对齐了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline void AlignedDot(const float *__restrict__ a, const float *__restrict__ b,
float *__restrict__ out) {
a = (const float *)__builtin_assume_aligned(a, TILE * ELEM_SIZE);
b = (const float *)__builtin_assume_aligned(b, TILE * ELEM_SIZE);
out = (float *)__builtin_assume_aligned(out, TILE * ELEM_SIZE);

for (uint32_t i = 0; i < TILE; ++i) {
for (uint32_t j = 0; j < TILE; ++j) {
float sum = 0.0f;
for (uint32_t k = 0; k < TILE; ++k) {
sum += a[i * TILE + k] * b[k * TILE + j];
}
out[i * TILE + j] += sum;
}
}
}

__restrict__ 让编译器知道写 out 不影响读 a/b(否则向量化会改变语义),assume_aligned 让它敢用对齐的宽 load/store,于是 8 元素的内层循环被展成 AVX 指令。这两个关键字是分块性能的主要来源,不是「顺手加上」。

注意 AlignedDot 是累加(out[i*TILE+j] += sum),因为 \(k\) 维被拆到了外层块循环上。这也解释了上面的清零。

效果:1024³ 从 2.2 GFLOP/s 到 26 GFLOP/s,约 12 倍。落回朴素路径的条件是 m、n、p 任一不是 8 的倍数:

1
if hasattr(self.device, "matmul_tiled") and all(d % self.device.__tile_size__ == 0 for d in (m, n, p)):

顺带一提,CUDA 后端故意不暴露 matmul_tiled,所以 GPU 永远走通用的 Matmul,它自己要处理任意尺寸。

Part 6: CUDA 后端 — Compact 与 setitem

从 CPU 迁到 GPU 有三个结构性差异:

  1. 一份逻辑拆成两层:host 函数负责计算 grid/block 并 <<<>>> 启动,__global__ kernel 干活;
  2. kernel 吃不了 STL:std::vector<int32_t> 传不进显存,于是有了 CudaVec——固定 MAX_VEC_SIZE = 8 的定长 struct,kernel 按值接收;
  3. 没有「遍历」,只有「一个线程一个元素」:gid = blockIdx.x * blockDim.x + threadIdx.x,第一句永远是 if (gid >= size) return;。
1
2
3
4
5
6
7
8
9
#define BASE_THREAD_NUM 256

CudaDims CudaOneDim(size_t size) {
CudaDims dim;
size_t num_blocks = (size + BASE_THREAD_NUM - 1) / BASE_THREAD_NUM; // 上取整
dim.block = dim3(BASE_THREAD_NUM, 1, 1);
dim.grid = dim3(num_blocks, 1, 1);
return dim;
}

CPU 端那个 next_offset 里程表在 GPU 上不成立(每个线程独立,不能共享 state),于是换成从全局下标反解多维坐标:

1
2
3
4
5
6
7
8
9
__device__ __forceinline__ size_t flatten_index(size_t gid, const CudaVec &shape, const CudaVec &strides) {
size_t pi = 0, cur = gid;
const int32_t ndim = static_cast<int32_t>(shape.size);
for (int32_t i = ndim - 1; i >= 0; --i) {
pi += (cur % shape.data[i]) * strides.data[i];
cur /= shape.data[i];
}
return pi;
}

除法和取模比 CPU 版的进位慢,但换来线程间的完全独立。CudaArray 用 cudaMalloc 分配,失败时抛 std::runtime_error(cudaGetErrorString(err))——CUDA 的错误是异步的,不加检查的话出错只会表现为「结果莫名是 0」。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
__global__ void CompactKernel(const scalar_t *a, scalar_t *out, size_t size,
CudaVec shape, CudaVec strides, size_t offset) {
size_t gid = blockIdx.x * blockDim.x + threadIdx.x;
if (gid >= size)
return;
out[gid] = a[offset + flatten_index(gid, shape, strides)];
}

__global__ void EwiseSetitemKernel(const scalar_t *a, scalar_t *out,
size_t size, CudaVec shape, CudaVec strides,
size_t offset) {
size_t gid = blockIdx.x * blockDim.x + threadIdx.x;
if (gid >= size)
return;
out[offset + flatten_index(gid, shape, strides)] = a[gid];
}

__global__ void ScalarSetitemKernel(const scalar_t val, scalar_t *out,
size_t size, CudaVec shape, CudaVec strides,
size_t offset) {
size_t gid = blockIdx.x * blockDim.x + threadIdx.x;
if (gid >= size)
return;
out[offset + flatten_index(gid, shape, strides)] = val;
}

Part 7: CUDA 后端 — 逐元素与标量算子

和 CPU 一样用模板收敛,但 CUDA 的坑在于 lambda 不能直接当 kernel 参数传,于是改用「函子(functor)」,每个算子一个 struct,operator() 标 __device__ __forceinline__:

1
2
3
4
5
6
7
8
9
struct MulOp { __device__ __forceinline__ scalar_t operator()(scalar_t a, scalar_t b) const { return a * b; } };
struct DivOp { __device__ __forceinline__ scalar_t operator()(scalar_t a, scalar_t b) const { return a / b; } };
struct PowOp { __device__ __forceinline__ scalar_t operator()(scalar_t a, scalar_t b) const { return powf(a, b); } };
struct MaxOp { __device__ __forceinline__ scalar_t operator()(scalar_t a, scalar_t b) const { return a > b ? a : b; } };
struct EqOp { __device__ __forceinline__ scalar_t operator()(scalar_t a, scalar_t b) const { return a == b ? 1.0f : 0.0f; } };
struct GeOp { __device__ __forceinline__ scalar_t operator()(scalar_t a, scalar_t b) const { return a >= b ? 1.0f : 0.0f; } };
struct LogOp { __device__ __forceinline__ scalar_t operator()(scalar_t a) const { return logf(a); } };
struct ExpOp { __device__ __forceinline__ scalar_t operator()(scalar_t a) const { return expf(a); } };
struct TanhOp{ __device__ __forceinline__ scalar_t operator()(scalar_t a) const { return tanhf(a); } };

三个通用 kernel(二元、标量二元、一元)以 Op 为模板参数,实例化时算子被完全内联,无额外开销:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// 逐元素二元: out[i] = op(a[i], b[i])
template <typename Op>
__global__ void EwiseOpKernel(const scalar_t *a, const scalar_t *b,
scalar_t *out, size_t size, Op op) {
size_t gid = blockIdx.x * blockDim.x + threadIdx.x;
if (gid >= size)
return;
out[gid] = op(a[gid], b[gid]);
}

// 逐元素二元: out[i] = op(a[i], val)
template <typename Op>
__global__ void ScalarOpKernel(const scalar_t *a, scalar_t val, scalar_t *out,
size_t size, Op op) {
size_t gid = blockIdx.x * blockDim.x + threadIdx.x;
if (gid >= size)
return;
out[gid] = op(a[gid], val);
}

// 逐元素一元: out[i] = op(a[i])
template <typename Op>
__global__ void EwiseUnaryKernel(const scalar_t *a, scalar_t *out, size_t size,
Op op) {
size_t gid = blockIdx.x * blockDim.x + threadIdx.x;
if (gid >= size)
return;
out[gid] = op(a[gid]);
}

// Host 启动封装
template <typename Op>
static inline void LaunchEwiseOp(const CudaArray &a, const CudaArray &b,
CudaArray *out, Op op) {
if (out->size == 0)
return;
CudaDims dim = CudaOneDim(out->size);
EwiseOpKernel<Op>
<<<dim.grid, dim.block>>>(a.ptr, b.ptr, out->ptr, out->size, op);
}

template <typename Op>
static inline void LaunchScalarOp(const CudaArray &a, scalar_t val,
CudaArray *out, Op op) {
if (out->size == 0)
return;
CudaDims dim = CudaOneDim(out->size);
ScalarOpKernel<Op>
<<<dim.grid, dim.block>>>(a.ptr, val, out->ptr, out->size, op);
}

template <typename Op>
static inline void LaunchEwiseUnary(const CudaArray &a, CudaArray *out, Op op) {
if (out->size == 0)
return;
CudaDims dim = CudaOneDim(out->size);
EwiseUnaryKernel<Op>
<<<dim.grid, dim.block>>>(a.ptr, out->ptr, out->size, op);
}

host 侧再用宏批量生成 18 个对外函数,一行一个:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#define DEFINE_EWISE(NAME, OP) \
void NAME(const CudaArray &a, const CudaArray &b, CudaArray *out) { \
LaunchEwiseOp(a, b, out, OP{}); \
}

#define DEFINE_SCALAR(NAME, OP) \
void NAME(const CudaArray &a, scalar_t val, CudaArray *out) { \
LaunchScalarOp(a, val, out, OP{}); \
}

#define DEFINE_UNARY(NAME, OP) \
void NAME(const CudaArray &a, CudaArray *out) { \
LaunchEwiseUnary(a, out, OP{}); \
}

DEFINE_EWISE(EwiseMul, MulOp)
DEFINE_SCALAR(ScalarMul, MulOp)

DEFINE_EWISE(EwiseDiv, DivOp)
DEFINE_SCALAR(ScalarDiv, DivOp)

DEFINE_EWISE(EwiseMaximum, MaxOp)
DEFINE_SCALAR(ScalarMaximum, MaxOp)

DEFINE_EWISE(EwiseEq, EqOp)
DEFINE_SCALAR(ScalarEq, EqOp)

DEFINE_EWISE(EwiseGe, GeOp)
DEFINE_SCALAR(ScalarGe, GeOp)

DEFINE_SCALAR(ScalarPower, PowOp)

DEFINE_UNARY(EwiseLog, LogOp)
DEFINE_UNARY(EwiseExp, ExpOp)
DEFINE_UNARY(EwiseTanh, TanhOp)

#undef DEFINE_EWISE
#undef DEFINE_SCALAR
#undef DEFINE_UNARY

用 powf/logf/expf/tanhf 而不是双精度版本——scalar_t 是 float,混用 double 会在 PTX 层多出转换指令,还会让单精度 SFU 用不上。

Part 8: CUDA 后端 — 归约

题目明说「简单起见,一个归约项一个线程即可」。于是 kernel 极简:每个线程读自己那段连续的 reduce_size 个元素,串行折叠。

1
2
3
4
5
6
7
8
__global__ void ReduceSumKernel(const scalar_t *a, scalar_t *out, size_t out_size, size_t reduce_size) {
size_t gid = blockIdx.x * blockDim.x + threadIdx.x;
if (gid >= out_size) return;
const scalar_t *p = a + gid * reduce_size;
scalar_t s = 0.0f;
for (size_t j = 0; j < reduce_size; ++j) s += p[j];
out[gid] = s;
}

Python 侧的 reduce_view_out 已经把归约轴排到了最后并 compact 过,所以这里可以直接 gid * reduce_size 定位。真实场景下应该做分层归约(先块内 warp shuffle 聚合,再二级聚合),否则 .max(axis=None) 会退化成一个线程干全部活——但本节不追求性能。

out->size == 0 要提前 return,否则会以 grid.x == 0 启动非法 kernel。

Part 9: CUDA 后端 — 共享内存 + 双缓冲 SGEMM

这是整个 HW3 的高潮。目标是把 C[M×P] = A[M×N] · B[N×P] 做到显存带宽和算力都接近饱和。

参数选择

参数 值 说明
block_size 16 线程块 16x16 = 256 线程,__launch_bounds__(256)
thread_m × thread_n 12 × 8 每线程算 \(12\times8=96\) 个输出
BM × BN 192 × 128 每块产出的 C 子块
BK 16 每步沿 K 前进的深度
共享内存 As[2][192][16] + Bs[2][16][128] \(2 \times (192{\cdot}16 + 16{\cdot}128) \times 4\text{B} = 40\text{KB}\)

40KB 在 48KB 的默认静态上限内还有余量,这是选 12×8 而非 16×8 的重要约束:后者两份 buffer 是 \(2(256{\cdot}16 + 16{\cdot}128){\cdot}4 = 48\text{KB}\),正好顶满上限、一点不剩(若要更大就得走 cudaFuncSetAttribute 动态申请)。12:8 的长宽比也顺手让写 C 时每行更连续。

双缓冲流水线

朴素分块的问题是:load → sync → compute → sync 里线程在等全局内存。双缓冲把「下一块的加载」和「当前块的计算」重叠——用 cuda_pipeline 的异步拷贝,拷贝请求发出后线程立刻返回,不必等数据落地:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
__shared__ __align__(16) float As[2][block_size * thread_m][block_size];   // [2][192][16]
__shared__ __align__(16) float Bs[2][block_size][block_size * thread_n]; // [2][16][128]

const size_t tid = threadIdx.y * block_size + threadIdx.x;

auto load_tile = [&](int stage_idx, size_t k_offset) {
copy_tile_to_smem<BM, BK, BK, NUM_THREADS, true, true>(As[stage_idx], A, K, M, K, blockIdx.y * BM, k_offset, tid);
copy_tile_to_smem<BK, BN, BN, NUM_THREADS, true, true>(Bs[stage_idx], B, N, K, N, k_offset, blockIdx.x * BN, tid);
__pipeline_commit(); // 把上面这批 async copy 打包成一个 commit group
};

load_tile(0, 0); // 预热:先装入第 0 块

size_t bk = BK;
int write_stage = 1, read_stage = 0;

for (; bk < K; bk += BK) {
load_tile(write_stage, bk); // ① 发出第 bk 块的异步拷贝
__pipeline_wait_prior(1); // ② 只等「还剩 1 个 group 未完成」,即第 bk-BK 块已到位
__syncthreads(); // ③ 全块确认数据可见

// ④ 用 read_stage 计算
#pragma unroll 8
for (size_t k = 0; k < BK; ++k)
for (size_t m = 0; m < thread_m; ++m) {
float a_val = As[read_stage][threadIdx.y * thread_m + m][k];
for (size_t n = 0; n < thread_n; ++n)
sum[m][n] += a_val * Bs[read_stage][k][b_tile_col<CHUNK_W, CHUNK_STRIDE>(n, threadIdx.x)];
}

__syncthreads(); // ⑤ 计算完才能覆盖 read_stage
read_stage = write_stage; // ⑥ 交换角色
write_stage = 1 - write_stage;
}
__pipeline_wait_prior(0); __syncthreads(); // 尾块单独算一遍

三个易错点:

  • wait_prior(1) 的参数是「允许仍有几个 commit group 在飞」,不是「等第几个完成」。写作 wait_prior(0) 就退化成同步拷贝,双缓冲白搭。
  • 两次 __syncthreads() 缺一不可:③ 保证所有人看到数据(异步拷贝只保证「写进 smem 了」,不保证对其他线程可见);⑤ 保证没人还在读 read_stage 时就有人开始覆盖它。
  • 循环里 bk < K 而非 bk <= K,最后一块在循环外补算,避免多加载一块越界的数据。

拷贝路径:copy_tile_to_smem

这一层要做的事比看起来多:通常路径要向量化成 float4(一次搬 16 字节,4 倍少的访存指令),但要能处理「矩阵尺寸不是 4 的倍数」「块落在矩阵边界外」这些情况。所以按能力分档,快的路径优先:

1
2
3
4
5
6
if (aligned && tile_inside) {          // 最理想:列数 4 对齐 + 整块在界内
// float4 / __pipeline_memcpy_async 直接搬
} else {
// 逐元素档:in4 才用 float4,否则标量拷贝,越界填 0
dst[r][c + i] = (gr < src_rows && gcc < src_cols) ? src[gr * src_ld + gcc] : 0.0f;
}

填 0 是必须的:Matmul 要支持任意尺寸((72, 73, 74) 这种),边界块读进来的垃圾值会直接污染 sum。模板参数 ASYNC / SMEM_VEC 把「用不用异步」「用不用 float4」做成编译期开关(全部实例化时是 true, true),static_assert(ROWS * COLS % 4 == 0) 保证按 4 分组时不会切坏。

B 的 smem 布局:为什么需要 b_tile_col

计算内层是这行:

1
sum[m][n] += a_val * Bs[read_stage][k][b_tile_col<CHUNK_W, CHUNK_STRIDE>(n, threadIdx.x)];

其中

1
2
3
4
template <size_t CHUNK_W, size_t CHUNK_STRIDE>
__device__ __forceinline__ size_t b_tile_col(size_t n, size_t tx) {
return (n / CHUNK_W) * CHUNK_STRIDE + tx * CHUNK_W + (n % CHUNK_W);
}

也就是把 Bs[k] 这一行按线程切块存储,而不是按自然列序。线程 tx 需要的 8 个元素变成「两块连续 4 个」:tx*4 与 64 + tx*4。

这么做有两个好处:

  1. 每个线程读的是连续地址:8 个元素变成两块连续 4 个,编译后是 2 条 LDS.128(vectorized shared load),而自然列序(Bs[k][tx + n*16])需要 8 条 LDS.32。共享内存带宽是一样的,但指令数少 4 倍,对发射压力影响很大。
  2. 向量化没引入 bank conflict:LDS.128 不是一次服务整个 warp,而是按 8 线程一批分 4 相处理。一批 8 个线程请求的是 tx*4 ... tx*4+3(tx = 0..7),即 32 个连续 float,恰好铺满 32 个 bank,互不相交。这正是 CHUNK_STRIDE 取 64(32 的整数倍)的意义——跨 chunk 的偏移不会打乱 bank 对齐。若 CHUNK_STRIDE 不是 32 的倍数,同一批线程的起始 bank 会错位重叠,LDS.128 立刻退化成多路冲突。

static_assert(NCHUNK * CHUNK_STRIDE == BN) 用来保证这种切块刚好铺满 128 列。

对应的,A 不需要重排(As[threadIdx.y * thread_m + m][k],同一线程固定行号,warp 内 16 个线程访问 16 个不同行,天然错开)。

写回:store_c_tile

同样向量化,一次 float4 写 4 个输出,并且支持 alpha / beta 语义(C = alpha*sum + beta*C):

1
2
3
4
5
6
res.x = alpha * sum[m][s + 0]; ...
if (beta != 0.0f) {
const float4 old_c = *reinterpret_cast<const float4 *>(&C[c_idx]);
res.x += beta * old_c.x; ...
}
*reinterpret_cast<float4 *>(&C[c_idx]) = res;

不满足对齐/边界时退回标量循环。Matmul 传的是 alpha=1.0f, beta=0.0f,所以 beta 分支被整体跳过。

启动配置与命名陷阱

1
2
3
4
5
6
7
8
9
constexpr size_t block_size = 16, thread_m = 12, thread_n = 8;
constexpr size_t BM = block_size * thread_m; // 192
constexpr size_t BN = block_size * thread_n; // 128

dim3 block(block_size, block_size);
dim3 grid((P + BN - 1) / BN, (M + BM - 1) / BM);

sgemm_double_buffering<block_size, thread_m, thread_n>
<<<grid, block>>>(M, P, N, 1.0f, a.ptr, b.ptr, 0.0f, out->ptr);

注意实参顺序是 (M, P, N):kernel 的签名是 sgemm(M, N, K) 即 C[M×N],所以这里的 N 形参收到的是 P、K 形参收到的是 N。Python 侧写惯了 (m, n, p),很容易在这里传错,症状是结果整体错位而不报错。

grid.x 沿 P 方向(列),grid.y 沿 M 方向(行)——对应 blockIdx.x * BN 用于 B 的列偏移、blockIdx.y * BM 用于 A 的行偏移。启动后用 cudaGetLastError() 兜底,越界或非法配置能立刻暴露:

1
2
cudaError_t err = cudaGetLastError();
if (err != cudaSuccess) throw std::runtime_error(cudaGetErrorString(err));

#pragma unroll 8 加在 k 循环上(而非全展开 16)是刻意的:FP32 核心的发射周期决定了一次性堆太多指令会挤掉寄存器,8 是这套参数下的经验值。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
template <size_t ROWS, size_t COLS, size_t DST_STRIDE, size_t NUM_THREADS,
bool ASYNC, bool SMEM_VEC>
__device__ __forceinline__ void copy_tile_to_smem(
float (&dst)[ROWS][DST_STRIDE], const float * __restrict__ src,
size_t src_ld, size_t src_rows, size_t src_cols,
size_t row0, size_t col0, size_t tid) {
static_assert(ROWS * COLS % 4 == 0, "tile element count must be multiple of 4");
constexpr size_t NVEC = ROWS * COLS / 4;
constexpr size_t NPER = (NVEC + NUM_THREADS - 1) / NUM_THREADS;
const bool aligned = (src_ld % 4 == 0);
const bool tile_inside = (row0 + ROWS <= src_rows) && (col0 + COLS <= src_cols);

if (aligned && tile_inside) {
#pragma unroll
for (size_t v = 0; v < NPER; ++v) {
if (v * NUM_THREADS >= NVEC) break;
const size_t q = tid + v * NUM_THREADS;
if (NPER * NUM_THREADS > NVEC) {
if (q >= NVEC) break;
}
const size_t e = q * 4;
const size_t r = e / COLS;
const size_t c = e - r * COLS;
const float *sp = &src[(row0 + r) * src_ld + col0 + c];

if (SMEM_VEC) {
if (ASYNC) {
__pipeline_memcpy_async(&dst[r][c], sp, sizeof(float4));
} else {
*reinterpret_cast<float4 *>(&dst[r][c]) =
*reinterpret_cast<const float4 *>(sp);
}
} else if (ASYNC) {
#pragma unroll
for (size_t i = 0; i < 4; ++i) {
__pipeline_memcpy_async(&dst[r][c + i], sp + i, sizeof(float));
}
} else {
const float4 t = *reinterpret_cast<const float4 *>(sp);
dst[r][c + 0] = t.x;
dst[r][c + 1] = t.y;
dst[r][c + 2] = t.z;
dst[r][c + 3] = t.w;
}
}
return;
}

#pragma unroll
for (size_t v = 0; v < NPER; ++v) {
if (v * NUM_THREADS >= NVEC) break;
const size_t q = tid + v * NUM_THREADS;
if (NPER * NUM_THREADS > NVEC) {
if (q >= NVEC) break;
}
const size_t e = q * 4;
const size_t r = e / COLS;
const size_t c = e - r * COLS;
const size_t gr = row0 + r;
const size_t gc = col0 + c;
const bool in4 = (gr < src_rows) && (gc + 3 < src_cols);

if (in4 && aligned && SMEM_VEC && ASYNC) {
__pipeline_memcpy_async(&dst[r][c], &src[gr * src_ld + gc], sizeof(float4));
} else if (in4 && ASYNC) {
#pragma unroll
for (size_t i = 0; i < 4; ++i) {
__pipeline_memcpy_async(&dst[r][c + i], &src[gr * src_ld + gc + i], sizeof(float));
}
} else if (in4 && aligned && SMEM_VEC) {
*reinterpret_cast<float4 *>(&dst[r][c]) =
*reinterpret_cast<const float4 *>(&src[gr * src_ld + gc]);
} else if (in4 && aligned) {
const float4 t = *reinterpret_cast<const float4 *>(&src[gr * src_ld + gc]);
dst[r][c + 0] = t.x;
dst[r][c + 1] = t.y;
dst[r][c + 2] = t.z;
dst[r][c + 3] = t.w;
} else {
#pragma unroll
for (size_t i = 0; i < 4; ++i) {
const size_t gcc = gc + i;
dst[r][c + i] = (gr < src_rows && gcc < src_cols)
? src[gr * src_ld + gcc] : 0.0f;
}
}
}
}

template <size_t CHUNK_W, size_t CHUNK_STRIDE>
__device__ __forceinline__ size_t b_tile_col(size_t n, size_t tx) {
return (n / CHUNK_W) * CHUNK_STRIDE + tx * CHUNK_W + (n % CHUNK_W);
}

template <size_t TM, size_t TN, size_t CHUNK_W = TN, size_t CHUNK_STRIDE = CHUNK_W>
__device__ __forceinline__ void store_c_tile(
float (&sum)[TM][TN], size_t row0, size_t col0,
size_t M, size_t N, float alpha, float beta, float * __restrict__ C) {
static_assert(TN % CHUNK_W == 0, "thread_n must be multiple of CHUNK_W");
static_assert(CHUNK_W % 4 == 0, "CHUNK_W must be multiple of 4");
constexpr size_t NCHUNK = TN / CHUNK_W;
const bool row_aligned = (N % 4 == 0);
#pragma unroll
for (size_t m = 0; m < TM; ++m) {
const size_t g_row = row0 + m;
if (g_row >= M) continue;
#pragma unroll
for (size_t c = 0; c < NCHUNK; ++c) {
const size_t chunk_col = col0 + c * CHUNK_STRIDE;
#pragma unroll
for (size_t v = 0; v < CHUNK_W / 4; ++v) {
const size_t g_col = chunk_col + v * 4;
if (row_aligned && g_col + 3 < N) {
const size_t c_idx = g_row * N + g_col;
const size_t s = c * CHUNK_W + v * 4;
float4 res;
res.x = alpha * sum[m][s + 0];
res.y = alpha * sum[m][s + 1];
res.z = alpha * sum[m][s + 2];
res.w = alpha * sum[m][s + 3];
if (beta != 0.0f) {
const float4 old_c = *reinterpret_cast<const float4 *>(&C[c_idx]);
res.x += beta * old_c.x;
res.y += beta * old_c.y;
res.z += beta * old_c.z;
res.w += beta * old_c.w;
}
*reinterpret_cast<float4 *>(&C[c_idx]) = res;
} else {
#pragma unroll
for (size_t i = 0; i < 4; ++i) {
const size_t gc = g_col + i;
if (gc >= N) break;
const size_t c_idx = g_row * N + gc;
const float old_c = (beta != 0.0f) ? beta * C[c_idx] : 0.0f;
C[c_idx] = alpha * sum[m][c * CHUNK_W + v * 4 + i] + old_c;
}
}
}
}
}
}

// ======================= double buffering kernel =======================

template<const size_t block_size = 16,
const size_t thread_m = 12,
const size_t thread_n = 8>
__global__ void __launch_bounds__(block_size * block_size) sgemm_double_buffering(
const size_t M, const size_t N, const size_t K,
const float alpha, const float* __restrict__ A, const float* __restrict__ B,
const float beta, float* __restrict__ C) {

__shared__ __align__(16) float As[2][block_size * thread_m][block_size];
__shared__ __align__(16) float Bs[2][block_size][block_size * thread_n];

const size_t tid = threadIdx.y * block_size + threadIdx.x;
constexpr size_t NUM_THREADS = block_size * block_size;

float sum[thread_m][thread_n] = {0.0f};

const size_t BM = block_size * thread_m;
const size_t BN = block_size * thread_n;
const size_t BK = block_size;

constexpr size_t CHUNK_W = 4;
constexpr size_t NCHUNK = thread_n / CHUNK_W;
constexpr size_t CHUNK_STRIDE = block_size * CHUNK_W;
static_assert(thread_n % CHUNK_W == 0, "thread_n must be multiple of 4");
static_assert(NCHUNK * CHUNK_STRIDE == BN, "chunks must fill BN exactly");

auto load_tile = [&](int stage_idx, size_t k_offset) {
copy_tile_to_smem<BM, BK, BK, NUM_THREADS, true, true>(
As[stage_idx], A, K, M, K, blockIdx.y * BM, k_offset, tid);
copy_tile_to_smem<BK, BN, BN, NUM_THREADS, true, true>(
Bs[stage_idx], B, N, K, N, k_offset, blockIdx.x * BN, tid);
__pipeline_commit();
};

load_tile(0, 0);

size_t bk = BK;
int write_stage = 1;
int read_stage = 0;

for (; bk < K; bk += BK) {
load_tile(write_stage, bk);

__pipeline_wait_prior(1);
__syncthreads();

#pragma unroll 8
for (size_t k = 0; k < BK; ++k) {
#pragma unroll
for (size_t m = 0; m < thread_m; ++m) {
float a_val = As[read_stage][threadIdx.y * thread_m + m][k];
#pragma unroll
for (size_t n = 0; n < thread_n; ++n) {
sum[m][n] += a_val * Bs[read_stage][k][b_tile_col<CHUNK_W, CHUNK_STRIDE>(n, threadIdx.x)];
}
}
}

__syncthreads();
read_stage = write_stage;
write_stage = 1 - write_stage;
}

__pipeline_wait_prior(0);
__syncthreads();

#pragma unroll 8
for (size_t k = 0; k < BK; ++k) {
#pragma unroll
for (size_t m = 0; m < thread_m; ++m) {
float a_val = As[read_stage][threadIdx.y * thread_m + m][k];
#pragma unroll
for (size_t n = 0; n < thread_n; ++n) {
sum[m][n] += a_val * Bs[read_stage][k][b_tile_col<CHUNK_W, CHUNK_STRIDE>(n, threadIdx.x)];
}
}
}

store_c_tile<thread_m, thread_n, CHUNK_W, CHUNK_STRIDE>(
sum, blockIdx.y * BM + threadIdx.y * thread_m,
blockIdx.x * BN + threadIdx.x * CHUNK_W, M, N, alpha, beta, C);
}

void Matmul(const CudaArray &a, const CudaArray &b, CudaArray *out, uint32_t M,
uint32_t N, uint32_t P) {
/**
* Multiply two (compact) matrices into an output (also comapct) matrix. You
* will want to look at the lecture and notes on GPU-based linear algebra to
* see how to do this. Since ultimately mugrade is just evaluating
* correctness, you _can_ implement a version that simply parallelizes over
* (i,j) entries in the output array. However, to really get the full
* benefit of this problem, we would encourage you to use cooperative
* fetching, shared memory register tiling, and other ideas covered in the
* class notes. Note that unlike the tiled matmul function in the CPU
* backend, here you should implement a single function that works across
* all size matrices, whether or not they are a multiple of a tile size. As
* with previous CUDA implementations, this function here will largely just
* set up the kernel call, and you should implement the logic in a separate
* MatmulKernel() call.
*
*
* Args:
* a: compact 2D array of size m x n
* b: comapct 2D array of size n x p
* out: compact 2D array of size m x p to write the output to
* M: rows of a / out
* N: columns of a / rows of b
* P: columns of b / out
*/

constexpr size_t block_size = 16;
constexpr size_t thread_m = 12;
constexpr size_t thread_n = 8;
constexpr size_t BM = block_size * thread_m; // 192
constexpr size_t BN = block_size * thread_n; // 128

dim3 block(block_size, block_size);
dim3 grid((P + BN - 1) / BN, (M + BM - 1) / BM);

sgemm_double_buffering<block_size, thread_m, thread_n>
<<<grid, block>>>(M, P, N,
/*alpha=*/1.0f, a.ptr, b.ptr,
/*beta=*/0.0f, out->ptr);

cudaError_t err = cudaGetLastError();
if (err != cudaSuccess)
throw std::runtime_error(cudaGetErrorString(err));
}

编译与调试

CMakeLists.txt 有几处值得抄走的写法:

  • pybind11 用解释器自己找,避免 PATH 里的 python3 和 find_package(Python) 找到的不是同一个:
1
2
3
4
execute_process(COMMAND ${Python_EXECUTABLE} -m pybind11 --cmakedir
RESULT_VARIABLE __pybind_exit_code OUTPUT_VARIABLE __pybind_path
OUTPUT_STRIP_TRAILING_WHITESPACE)
find_package(pybind11 PATHS ${__pybind_path})
  • CUDA 用 find_package(CUDAToolkit)(FindCUDA 在 CMake 3.27 已被移除),并显式指定 CMAKE_CUDA_COMPILER,因为 nvcc 常在 /opt/cuda/bin 而不在 PATH 里;
  • CMAKE_CUDA_ARCHITECTURES native:有 GPU 就只为本机架构编译(快);nvidia-smi 不存在时退回 7.5(Colab T4),因为 CUDA 12+ 不再支持 K80 的 sm_37;
  • .so 直接输出到 python/needle/backend_ndarray/,省掉安装步骤。

本机的 Makefile 我自己加了两条防呆(因为 build/ 里缓存了 CUDA 路径、GPU 架构和 -march=native 产出的对象文件):

1
2
3
4
5
6
# build/ 记录了配置它的那台机器;换机器(比如 Colab 的 Drive 跨 runtime)就整个重来
HOST := $(shell hostname)
# clangd 无法展开 nvcc 的 --options-file 响应文件,会误报 pybind11/numpy.h not found;
# Ninja 生成器会把 include 路径内联,所以优先 Ninja
NINJA := $(shell command -v ninja 2>/dev/null)
GEN := $(if $(NINJA),Ninja,Unix Makefiles)

测试用 -k 精确筛,一次只跑一部分,改完 .cc/.cu 必须先 make:

1
2
3
4
5
python3 -m pytest -v -k "(compact or setitem) and cpu"
python3 -m pytest -v -k "(ewise_fn or ewise_max or log or exp or tanh or (scalar and not setitem)) and cpu"
python3 -m pytest -v -k "reduce and cpu"
python3 -m pytest -v -k "matmul and (cpu or tiled)"
python3 -m pytest -v -k "matmul and cuda"

全部 140 个用例在 i9-11980HK + RTX 3080 Laptop 上约 0.4 s 跑完。

性能实测

先踩一个坑:计时方式

第一版基准是这样写的:

1
2
3
4
5
for _ in range(reps):
t0 = time.perf_counter()
c = a @ b
c.numpy() # ← 罪魁祸首
best = min(best, time.perf_counter() - t0)

a @ b 只是把一个异步 kernel 塞进流里就返回了,真正让 CPU 停下来等待的是 .numpy() 里的 D2H 拷贝。于是计时变成了「kernel + 一次全量回拷」:1024³ 多算 4 MB、2048³ 多算 16 MB。数字被压到只有真实值的三分之一到一半,而当时的我并不知情,还煞有介事地为「只有理论峰值 26%」找了一堆解释——结论全错。

正确做法是用 cudaDeviceSynchronize() 卡住两端,中间不碰数据(perf_counter 前后各 sync 一次即可;更严格可用 CUDA event):

1
2
3
4
rt = ctypes.CDLL("libcudart.so")
rt.cudaDeviceSynchronize(); t0 = time.perf_counter()
c = a @ b
rt.cudaDeviceSynchronize(); dt = time.perf_counter() - t0

教训:异步 API 的基准测试里,「等它跑完」和「读回结果」是两件不同的事,混在一起就量错了对象。

kernel 本体 vs Python 接口

分开量这两层,才看得清差距在哪:

规模 裸 kernel 经 a @ b Python 开销
512³ 0.105 ms 2557 GFLOP/s 0.116 ms 2316 GFLOP/s 11 μs
1024³ 0.205 ms 10463 GFLOP/s 0.341 ms 6300 GFLOP/s 136 μs
2048³ 1.495 ms 11490 GFLOP/s 1.939 ms 8860 GFLOP/s 444 μs
4096³ 11.600 ms 11848 GFLOP/s 12.408 ms 11076 GFLOP/s 808 μs

「裸 kernel」是复用同一个输出 NDArray、直接调 device.matmul(a_handle, b_handle, out_handle, M, N, K)。和 a @ b 的差值就是 NDArray.__matmul__ 的 Python 侧成本:两次 compact()(每次都 NDArray.make + 一次设备内拷贝)+ 一次输出分配。1024³ 上是 136 μs,比 kernel 本体(205 μs)的一半还多。

这是个值得记住的量级:Python 每层抽象大约值 100 μs 量级,所以 a @ b 的曲线在 512³ 以下完全被它主导——512³ 的 kernel 只要 105 μs。真跑小矩阵时该做的不是优化 kernel,而是把这一层开销削掉(缓存 compact 结果、复用输出 buffer)。

与 cuBLAS 对比

本机 RTX 3080 Laptop:6144 个 FP32 核心 × 2 × 1.71 GHz boost = 21.0 TFLOP/s 理论峰值。固定配置 <16,12,8> 与 cuBLAS fp32 在同一进程内交替计时(加速比 = cuBLAS 耗时 ÷ 本实现耗时):

规模 本实现 cuBLAS 加速比
128³ 0.029 ms 147 GFLOP/s 0.006 ms 731 GFLOP/s 0.20×
256³ 0.053 ms 638 0.009 ms 3572 0.18×
512³ 0.094 ms 2841 0.033 ms 8166 0.35×
1024³ 0.191 ms 11254 0.181 ms 11860 0.95×
2048³ 1.512 ms 11360 1.367 ms 12571 0.90×
4096³ 11.920 ms 11530 11.265 ms 12200 0.95×
8192³ 91.565 ms 12008 74.534 ms 14752 0.92×

1024³ 及以上几何平均 0.93×;单看 11500 GFLOP/s 是理论峰值的 ~55%。这对一个几百行、没有 tensor core、没有 autotuning 的手写 SGEMM 来说已经是很好的成绩——cuBLAS 在 fp32 上也远达不到峰值。所谓「理论峰值」是给纯 FMA 且共享内存/带宽都无限供应的理想情况留的余量,实际 SGEMM 能达到 60% 就已经接近这个架构的天花板了。

输在哪

  • 小尺寸惨败(128³ 只有 0.20×):BM×BN = 192×128,128³ 只切出 1×1 个 block,整个 GPU 只有 256 个线程在跑,6144 个核心闲着 96%。cuBLAS 对小矩阵有专门的小 tile kernel。这也说明固定 tile 的通用性代价——想补救就是 autotuning(small tile 19x8x4 之类)或按 M/N/P 选 kernel。
  • 大尺寸缓慢滑落(8192³ 掉到 0.81×):越大的矩阵对 L2 越不友好,cuBLAS 会用 split-K、更激进的 cp.async 多级流水和 L2 prefetch hint,而我们只有两级双缓冲、CHUNK_W=1 时每个 chunk 只搬 As 的 12 行,全局访存占比偏高。
  • 40KB 共享内存只够双缓冲:想要更深流水就得减小 tile(CHUNK_W 减半),但那样每次 mma 之外要多付同步与填充开销,实测下来不划算。

顺带一提 CPU 侧:分块对朴素是 26.2 vs 2.2 GFLOP/s(1024³,约 12×),单线程手写、无 SIMD、无多线程,25 GFLOP/s 大概是 AVX2 单核在这个尺寸下的合理上限;numpy 走多线程 BLAS,输给它不丢人。

HW3 总结

HW3 和前两个作业是两种难度。HW1/HW2 难在推导,公式对了代码就对了;HW3 难在机器模型——stride 与 offset 的含义、ndim 运行时才知道时怎么写循环、GPU 里没有「遍历」只有「下标」、共享内存的 bank 与对齐、异步拷贝的可见性与同步边界。

几个我认为最值得记住的点:

  1. stride 是万能的:广播就是 stride 0,切片就是 step*stride,转置就是置换 stride。能不拷贝就不拷贝。
  2. 边界与对齐要一起处理:Matmul 必须支持任意尺寸,所以每条快路径都要有慢速兜底,且越界必须填 0 而非跳过。
  3. __restrict__ 和 assume_aligned 不是可选项:CPU 分块那 12 倍提升主要来自它们,而非分块本身。
  4. 双缓冲的正确性靠两处同步:wait_prior(1) 管「数据到了没」,__syncthreads() 管「别人看得见没 / 还在不在读」。写反了不报错,只是结果偶尔错,极难查。
  5. CUDA 错误是异步的:每个 kernel 启动后都该 cudaGetLastError(),否则出错表现为「结果是 0」。
  6. 异步 API 的计时同样是个坑:a @ b 返回不代表算完,c.numpy() 里夹着一次 D2H 拷贝。我在一个错误的计时器上为「只有峰值 26%」找了一堆原因,换成 cudaDeviceSynchronize() 才是真实的 11500 GFLOP/s(~55% 峰值、cuBLAS 的 0.9×)。基准测试第一件事是先确认自己到底在量什么。

到这里 needle 已经有了一套自己的、能跑在 GPU 上的张量后端。HW4 会把它接回 autograd,让前面手写的算子在真实训练里跑起来。


CMU 10-714 Assignments 实验笔记
https://acmicpc.top/2026/05/23/CMU-10717/
作者
江欣婷
发布于
2026年5月23日
许可协议