实验指导：程序性能优化方法

实验指导

实验五：性能优化

实验指导：程序性能优化方法

1. 算法层优化

在考虑 CPU 指令和缓存细节之前，先选择正确的数据结构和算法。一个好的算法设计往往能带来数倍甚至数十倍的性能提升。

更高级的算法会在《数据结构》与《算法基础》课程中系统讲解。在本课程中不作展开。

2. 体系结构层优化

除了算法层面的优化，理解并利用现代 CPU 的体系结构特性也是提升性能的关键。

当 CPU 执行一段代码时，它同时受到三个方面的限制：

数据依赖：如果指令 B 需要指令 A 的计算结果，B 必须等 A 完成
资源约束：CPU 的执行单元数量有限（例如只有 2 个浮点乘法器）
内存访问：访问内存远比访问寄存器慢（延迟可能相差几个数量级）

理解这三点，就能理解为什么有些优化方法有效。

2.1 消除循环中的重复计算

在循环的每次迭代中，某些计算的结果都完全相同（不依赖于迭代变量），显然，重复计算会浪费 CPU 周期。将这些不变的计算提取到循环外部，可以提升性能。

案例分析

考虑以下求和代码：

int sum(int a[]) {
    int s = 0;
    for (int i = 0; i < length(a); i++) { // 每次都会调用 length()
        s += a[i];
    }
    return s;
}

由于数组 a 的长度在循环中是固定不变的，每次迭代都调用 length(a)（如果是字符串 strlen 更是 $O(n)$ 复杂度）会造成严重的性能浪费。

优化方案

int sum(int a[]) {
    int s = 0;
    int len = length(a); // 提前提取到循环外
    for (int i = 0; i < len; i++) {
        s += a[i];
    }
    return s;
}

在lab5卷积操作中，卷积核的大小（K_SIZE）和偏移量（K_RADIUS）应当在最外层计算好，不要在最内层像素点计算时重复执行加减法逻辑。

2.2 寄存器变量

内存访问（Load/Store）比寄存器操作慢得多。尽量使用局部变量暂存累加结果。

案例分析

void mult(int a[], int *dst) {
    int len = length(a);
    for (int i = 0; i < len; i++) {
        *dst = *dst * a[i]; // 每次迭代都要读写一次内存
    }
}

CPU 无法确定指针 dst 是否可能指向数组 a 中的某个元素（内存别名风险），因此每次都会老老实实地从内存读出 *dst，计算后再写回内存。

优化方案

通过引入局部变量（通常会被分配至寄存器）暂存中间计算结果。

void mult(int a[], int *dst) {
    int len = length(a);
    int temp = *dst; // 暂存到寄存器
    for (int i = 0; i < len; i++) {
        temp = temp * a[i];
    }
    *dst = temp; // 最终写回
}

lab5中，在计算某个像素的卷积和时，使用一个 float sum = 0.0f; 局部变量累加，等 Kernel 的乘法全部完成后，再把结果写回 dst[i*n + j]。

2.3 循环展开与指令级并行

核心思想：通过增加单次迭代中计算元素的数量，减少循环控制开销（索引自增、条件判断）。

硬件机制

现代 CPU 不是一条一条指令地执行，而是同时处理多条指令（例如一条在 ALU，一条在浮点乘法器，一条在 Load/Store 单元）如果后续指令依赖于前一条指令的结果，CPU 必须停工等待（称为"停顿"），如果不依赖则可以同时发射多条指令。

案例分析

float result = 0.0f;
for (int i = 0; i < 1000; i++) {
    result = result * array[i];  // 有数据依赖
}

执行时序：

周期 0：乘法指令 1 发射（延迟 3-5 个周期）
周期 1-2：CPU 空闲，等待指令 1 的结果
周期 3-4：CPU 空闲，等待指令 1 的结果
周期 5：乘法指令 2 发射
周期 6-8：CPU 空闲，等待指令 2 的结果
...

浪费了大量 CPU 周期。

解决方案：循环展开与多个累加器

示例：

// 展开因子为 4（处理 4 个独立的累加）
float result1 = 0.0f, result2 = 0.0f, result3 = 0.0f, result4 = 0.0f;
for (int i = 0; i < 1000; i += 4) {
    result1 = result1 * array[i];
    result2 = result2 * array[i+1];  // ✓ 不依赖于 result1
    result3 = result3 * array[i+2];  // ✓ 不依赖于 result1
    result4 = result4 * array[i+3];  // ✓ 不依赖于 result1
}
float result = result1 * result2 * result3 * result4;

执行时序：

周期 0：乘法指令 1（结果1） 发射
周期 1：乘法指令 2（结果2） 发射
周期 2：乘法指令 3（结果3） 发射
周期 3：乘法指令 4（结果4） 发射
周期 4-5：CPU 继续处理其他指令或缓存
周期 6：结果1 准备好，开始处理下一组指令
...

4 条不相关的指令可以并发执行。

编译器的自动展开

现代编译器（如 -O3 优化等级）会自动尝试展开循环。但对于固定的小循环（如 $3 \times 3$ 卷积），手动展开往往更清晰，也能确保编译器按你的意图行动。

2.4 内存层级结构与分块技术

lab5的图像处理操作是典型的内存密集型 计算任务。优化此类程序的关键不在于减少算术运算，而在于如何高效地调度数据在存储器层级结构 中的流动，最大化缓存命中率 。

存储器层级结构

层级	访问延迟	容量
寄存器	~1 纳秒	几十个
L1 Cache	~4 纳秒	32 KB
L2 Cache	~12 纳秒	256 KB
L3 Cache	~40 纳秒	8 MB
主内存 DRAM	~100 纳秒	16 GB
磁盘存储	~毫秒级	TB 级

越往上速度越快，容量越小，而我们优化让尽可能多的数据访问命中 L1 Cache，避免 DRAM 访问。

缓存行与访存步长

硬件层面的数据交换并非以字节为单位，而是以缓存行 (Cache Line) 为基本单位（在现代处理器上通常为 64-byte）。

当 CPU 访问地址 A 时：

硬件判断 A 属于哪条缓存行（比如缓存行 k）
自动将整条缓存行 k 加载到 L1 Cache（包含 16 个 float）
之后的 15 次访问（A+4, A+8, …, A+60）直接命中 L1（无延迟）

然而，在大步长访问时（例如按列访问），每次访问都会产生一次缓存失效，迫使 CPU 停工等待内存控制器从高延迟的 DRAM 中搬运数据。

示例：

// 按行访问：内存地址连续，高缓存命中率
float matrix[1024][1024];
int i, j;
for (i = 0; i < 1024; i++) {
    for (j = 0; j < 1024; j++) {
        matrix[i][j] = 0; // 连续访问：matrix[i][0], matrix[i][1], ..., matrix[i][15]在同一条缓存行
    }
}

第一次访问 matrix[i][0]：CPU 发现这条缓存行不在 L1 Cache，于是从主存把包含它的 64 字节（16 个 float）一次性加载到 L1。
接下来访问 matrix[i][1] 到 matrix[i][15]：全部命中 L1 Cache，不需要访问主存，几乎没有延迟。

// 按列访问：内存地址不连续，步长很大
for (j = 0; j < 1024; j++) {
    for (i = 0; i < 1024; i++) {
        matrix[i][j] = 0; // 每次访问的地址都间隔 1024*4=4096 字节，远大于64字节的缓存行
    }
}

第一次访问 matrix[0][j]：加载一条缓存行到 L1。
下一次访问 matrix[1][j]：地址和上一次差了 4096 字节，根本不在刚才加载的缓存行里，又要去主存加载新的缓存行。
结果：每次访问都要访问主存，CPU 只能停工等待，性能直接暴跌。

分块技术

当图像维度 $N$ 较大（如 $N \ge 1024$ ）时，由于单行数据量可能已超过 L1/L2 Cache 的容量，传统的线性扫描仍会导致缓存行在被重用前就被踢出。分块是一种针对性技术，旨在将大矩阵划分为子块，使每个小块的数据能完全驻留在缓存中。

示例：

// 伪代码：未分块的二维卷积
void conv2d(float input[N][N], float kernel[K][K], float output[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            float sum = 0.0f;
            for (int ki = 0; ki < K; ki++) {
                for (int kj = 0; kj < K; kj++) {
                    sum += input[i+ki][j+kj] * kernel[ki][kj];
                }
            }
            output[i][j] = sum;
        }
    }
}

当 $N=1024$ 时，input 矩阵一行有 1024 个 float（4KB），L1 Cache 装不下一整行，数据会频繁被替换。

// 伪代码：分块优化的二维卷积，BLOCK_SIZE 设为 32（根据 L1 Cache 大小调整）
#define BLOCK_SIZE 32

void conv2d_blocked(float input[N][N], float kernel[K][K], float output[N][N]) {
    // 外层循环：按块处理输入矩阵
    for (int i_block = 0; i_block < N; i_block += BLOCK_SIZE) {
        for (int j_block = 0; j_block < N; j_block += BLOCK_SIZE) {
            // 内层循环：处理当前块内的所有元素
            for (int i = i_block; i < i_block + BLOCK_SIZE; i++) {
                for (int j = j_block; j < j_block + BLOCK_SIZE; j++) {
                    float sum = 0.0f;
                    for (int ki = 0; ki < K; ki++) {
                        for (int kj = 0; kj < K; kj++) {
                            sum += input[i+ki][j+kj] * kernel[ki][kj];
                        }
                    }
                    output[i][j] = sum;
                }
            }
        }
    }
}

每次只处理 $BLOCK\_SIZE \times BLOCK\_SIZE$ 大小的子块（比如 $32 \times 32 = 1024$ 个 float，仅 4KB），这个大小的块可以完整放在 L1 Cache 里。
处理当前块时，数据被反复访问都能命中缓存，不需频繁访问主存。

2.5 分支消除

现代处理器的流水线执行高度依赖分支预测器。一旦预测失败，处理器必须丢弃已进入流水线的后续指令，代价极高。我们需尽量减少热点代码中的条件分支，尤其是那些方向不确定的分支。

lab5应用：

在卷积最内层循环中实施边界检查 if (row >= 0 && row < n ...) 会引入大量方向不确定的条件分支，严重干扰指令预取与执行。
优化方案：通过在原始图像外围填充一层宽度等于卷积半径的空白区域，可以将复杂的边界处理逻辑从热点路径中剥离。将计算核心转化为无分支的线性代码流。

原始图像：         
┌───────┐
│ · · · │
│ · · · │
│ · · · │
└───────┘ 
填充后：
┌───────────┐
│ 0 0 0 0 0 │
│ 0 · · · 0 │
│ 0 · · · 0 │
│ 0 · · · 0 │
│ 0 0 0 0 0 │
└───────────┘

在填充后的图像上进行卷积计算时，内层循环不再需要边界检查，消除了所有条件分支（以及由此引起的分支预测失败），提升性能。

卷积性能优化实验要求与检查