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 )) 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 ; } 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; } } 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]; } } 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; } 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[b * k + true_class] -= 1.0f ; } 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 ++) { 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 的源码,对理解框架很有用。
所有元素对一个标量进行幂运算。输入输出形状相同,张量梯度形式和标量相同。建议所有梯度都返回元组,方便后续写
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, )
张量对应元素之间的除法。输入输出形状相同,张量梯度形式和标量相同。分别对分子分母求偏导数即可。
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)
广义的矩阵转置,实际更类似 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), )
本质是重新对内存下标进行映射。
根据链式法则有:
\[
\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), )
广播操作本质是沿某个轴进行复制,根据链式法则有:
\[
\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,)
这个算子是沿特定轴进行求和,结果进行降维。如果
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), ) axes = tuple (ax % len (input_shape) if ax < 0 else ax for ax in self .axes) new_shape = list (input_shape) for ax in axes: new_shape[ax] = 1 return (broadcast_to(reshape(out_grad, tuple (new_shape)), input_shape), )
广义矩阵乘法。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))
按元素取负,梯度即为乘 -1。
1 2 3 4 5 6 7 8 9 10 class Negate (TensorOp ): def compute (self, a ): return array_api.negative(a) def gradient (self, out_grad, node ): return (negate(out_grad), )
这两个都没啥好说的。
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_orderdef 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]) 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)
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)
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 outclass 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) 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 ): 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 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
三个坑:
更新 running stats 务必用 .data
取裸数组,否则这些值会一直挂在计算图上,图越滚越大,带
memory_check 的测试直接 OOM。
running_mean/running_var 是普通
Tensor(requires_grad=False),不能包成
Parameter——它们是统计量而不是参数,被
parameters()
抓去交给优化器就完了。方差也必须是这里手搓的有偏估计,直接抄
x.var(axis=0)(PyTorch 默认无偏、除 \(N-1\) )会对不上 mugrade。
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
要点:
全程在 .data(裸 NDArray)上算,一点 autograd
都不要碰,否则每次 step()
都在往计算图上接新节点,图一直长,memory_check 测试立刻
OOM。
不要 in-place 改 param.grad(题目专门强调过)。这里的
weight decay 是加在梯度上的,相当于把 \(\frac{1}{2}\lambda\lVert\theta\rVert^2\)
并进 loss,而非 AdamW 那种 decoupled weight decay。
\(u/m/v\) 这类状态用 dict
按参数存,首次遇到某参数时 zeros_like 开一份;偏差修正用的
\(t\) 是全局步数,在 step
开头自增。忘了 bias correction,前期 \(m,
v\) 偏小会把步长带偏。
题目的动量公式带了 \((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 imgclass 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 : 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: 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] 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; }); }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 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; }); }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):
把要归约的轴 permute 到最后一维;
.compact() 让内存连续;
于是 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 有三个结构性差异:
一份逻辑拆成两层 :host 函数负责计算 grid/block 并
<<<>>> 启动,__global__
kernel 干活;
kernel 吃不了
STL :std::vector<int32_t>
传不进显存,于是有了 CudaVec——固定
MAX_VEC_SIZE = 8 的定长 struct,kernel 按值接收;
没有「遍历」,只有「一个线程一个元素」 :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 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]); }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); }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]); }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]; __shared__ __align__(16 ) float Bs[2 ][block_size][block_size * thread_n]; 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(); };load_tile (0 , 0 ); size_t bk = BK;int write_stage = 1 , 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) 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 = 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) { } else { 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。
这么做有两个好处:
每个线程读的是连续地址 :8 个元素变成两块连续 4
个,编译后是 2 条 LDS.128(vectorized shared
load),而自然列序(Bs[k][tx + n*16])需要 8 条
LDS.32。共享内存带宽是一样的,但指令数少 4
倍,对发射压力影响很大。
向量化没引入 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.0 f, a.ptr, b.ptr, 0.0 f, 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; } } } } } }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) { 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; constexpr size_t BN = block_size * thread_n; 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); 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 HOST := $(shell hostname) 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
与对齐、异步拷贝的可见性与同步边界。
几个我认为最值得记住的点:
stride 是万能的 :广播就是 stride 0,切片就是
step*stride,转置就是置换 stride。能不拷贝就不拷贝。
边界与对齐要一起处理 :Matmul
必须支持任意尺寸,所以每条快路径都要有慢速兜底,且越界必须填 0
而非跳过。
__restrict__ 和 assume_aligned
不是可选项 :CPU 分块那 12
倍提升主要来自它们,而非分块本身。
双缓冲的正确性靠两处同步 :wait_prior(1)
管「数据到了没」,__syncthreads() 管「别人看得见没 /
还在不在读」。写反了不报错,只是结果偶尔错,极难查。
CUDA 错误是异步的 :每个 kernel 启动后都该
cudaGetLastError(),否则出错表现为「结果是 0」。
异步 API 的计时同样是个坑 :a @ b
返回不代表算完,c.numpy() 里夹着一次 D2H
拷贝。我在一个错误的计时器上为「只有峰值 26%」找了一堆原因,换成
cudaDeviceSynchronize() 才是真实的 11500 GFLOP/s(~55%
峰值、cuBLAS 的 0.9×)。基准测试第一件事是先确认自己到底在量什么。
到这里 needle 已经有了一套自己的、能跑在 GPU 上的张量后端。HW4
会把它接回 autograd,让前面手写的算子在真实训练里跑起来。