整理一下常见的算法加速方法。一般来说，对于高计算量的算法，加速是必然要考虑的事情。理想情况下，在编写算法时就应该考虑让算法便于优化，下面就针对性谈谈。

1. 多层循环

图像处理算法大多需要遍历图像，如果遍历操作较为复杂，这部分的速度就会很慢。所以最好就是能保证最里层循环只有 连续内存 的 简单运算 。如果能够展开来不用 for 循环有时候也会些优化。

2. SIMD

意思就是单指令多数据流，允许一次处理多个数据，比如有 128bit 寄存器使用 SIMD 指令则可以一次处理 4 个 32bit 数据。前面提到的多层循环内连续内存的简单运算就可以通过 SIMD 进行大幅优化。SIMD 的使用需要特定的数据结构，函数可以通过查 Intrinsics 或者直接翻头文件找到。因为是处理器相关，需要看具体处理器是否支持，以及具体实现，比如 Intel 的 SSE，ARM 的 Neon。知道了用法替换起来就很方便了：

 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

// neon 下的矩阵乘法实现
void gemm_neon(const float *lhs, const float *rhs, float *out_mat, int rhs_rows, int rhs_cols)
{
    for (int j = 0; j < rhs_rows; ++j)
    {
        float *data1 = (float*)lhs;
        float *data2 = (float*)(rhs + j*rhs_cols);
        float32x4_t production = vdupq_n_f32(0.f);
        int i = 0;
        for (i = 0; i < rhs_cols-3; i+=4)
        {
            float32x4_t lfactor = vld1q_f32(data1);
            float32x4_t rfactor = vld1q_f32(data2);
            data1 += 4; data2 += 4;
            production = vmlaq_f32(production, lfactor, rfactor);
        }
        float sum = 0.0f;
        for (;  i< rhs_cols; ++i)
        {
            sum += (*data1)*(*data2);
            data1++; data2++;
        }
        float temp[4];
        vst1q_f32(temp, production);
        sum += (temp[0]+temp[1]+temp[2]+temp[3]);

        out_mat[j] = sum;
    }
}

3. 复杂算法重组

有时候算法的各步骤执行次序会对算法效率有很大影响，特别对于内存管理而言，最好集中在循环外处理。算法本身也可能会有冗余的计算，通过一些方法合并计算会带来一些性能优化。
这其中对于密集计算的特例就是向量化（Vectorization）。将 for 循环控制的计算转化为矩阵运算，这在使用 Python、Matlab 等来设计算法时可以说是必备的。

4. 牺牲空间换取速度

最为典型的就是查找表，通过预先计算一部分结果，并保存在一个大数组里，从而使后续算法能够加速运算。

5. 二维数组优化

我们习惯将图像表示为二维数组，这样处理起来也更方便，但是二维数组运算的方便却会导致运算效率的降低，根本原因在于内存的不连续。虽然对于优秀的程序员来说不是什么问题，但我比较想提一提这种方法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

float **init_matrix(int rows, int cols)
{
    int i;
    float **m;
    m = (float **)malloc((size_t)(rows * sizeof(float *)));
    m[0] = (float *)malloc((size_t)(rows * cols * sizeof(float)));
    for(i = 1; i < rows; ++i)
    {
        m[i] = m[i-1] + cols;
    }
    return m;
}
void delete_matrix(float **m)
{
    free(m[0]);
    free(m);
}

6. 矩阵分解

将空间滤波分解成行列滤波，可以提升速度以及降低容量，这部分在 Dlib 中有具体的实现，了解得不是很多，不过除了这种简单分解外估计还有不少门道。

7. L1 cache / 汇编 / 硬件

L1 cache 也就是利用缓存来优化密集存取的代码。大体来说减少变量的使用，尽量处理连续的空间。而汇编的话直接操作寄存器，可以对算法做非常底层的优化，针对具体芯片架构还会有更多可以优化的地方，甚至使用 FPGA 或 DSP 来并行运算、高速信号处理，或者合起来异构计算。这些我也不太了解，大概是 HPC 的内容了。

8. 多线程/多进程优化

也就是 pthread 之类的，在系统层面上做优化，开发的时候注意好 I/O 阻塞、共享资源加锁、进程间通信等问题就好了。
这里 Python 的 默认解释器 CPython 由于 全局解释锁（GIL） 的存在所以多线程不太灵光，可以采用多进程 + 协程的方式利用好多核 CPU。

9. 等价运算

对于一些算法，有时候可以在数学上找到等价的运算形式，相当于走捷径，比如矩阵运算的一些等价性质，DFT 处理实信号的一些性质；或者转换后能够结合具体软硬件环境进行加速，像 Winograd 用中间变量和加法运算来减少乘法运算。这些转换是可以直接替换原有算法或者视条件替代使用的。
还有一种比较邪门的方法就是寻找近似的计算，这方面是机器学习的特长。特别如果拥有大量的输入输出结果，但苦于设计映射的算法，这时候直接用机器学习去学习映射的矩阵会是简单又高效的做法。还有一种情况就是处理的数据自身存在大量冗余，传统方法计算量又很大，这时候可以通过在缩小冗余的数据上进行传统方法处理，然后用机器学习之类的方法对数据尺度进行扩大。NVIDIA 的 DLSS2.0 就是这种情况的优秀实现，在低分辨率下快速渲染，然后超采样获得高分辨率输出，利用了多帧信息以及各种奇技淫巧来使得最终输出就像直接处理高分辨率图像一样，这是相当有难度的，同时也是相当有价值的。