汉振分享 | 算法的工程优化技术

当一个算法实现之后，需要集成到产品中去，这时就要面临性能问题。在实际工程应用中，除采用降低算法的复杂度去解决性能问题外，通常也会选择优化代码以及良好运用硬件等方式。接下来将针对在不改动算法情况下，对纯工程方面做性能优化的技术作一个介绍。

1. 流程优化

对初始算法进行流程优化主要有：

A.避免算法执行过程中的重复操作及冗余计算。

B.避免算法中循环语句内部有过多依赖和跳转。

C.定点化：定点化的思想是将浮点型运算转换为整型运算，具体做法是将数据乘上一个很大的数后，将所有运算转为整型计算，例如某个乘法只关心小数点后3位，那把数据都乘上10000后，进行整型运算的结果也就满足所需的精度。

D.以空间换时间：空间换时间(zui)经典的就是查找表，某些计算相当耗时，但其自变量的值域是比较有限的，这样的情况可以预先计算好每个自变量对应的函数值，存在一个表格中，每次根据自变量的值去索引对应的函数值即可。

E.预先分配内存：把握算法整个执行过程中内存的使用，提前分配好内存，避免内存不断开辟与释放而产生的耗时。

2. 指令优化

SIMD即(Single Instruction Multiple Data)，单指令多数据流，是CPU中能够复制多个操作数，并把它们打包在大型寄存器的一组指令集。

目前PC上I-n-t-e-l指令集有SSE、AVX等，SSE/AVX是对其X86体系的SIMD扩展指令集，它基于SIMD向量化技术，提高X86硬件的计算性能，增强了X86多核向量处理器的图像和视频处理能力。SSE/AVX指令支持向量化数据并行，一个指令可以同时对多个操作数进行操作，同时操作的数据个数由向量寄存器的长度和数据类型共同决定。

SIMD属于细粒度的并行，对于图像算法中利用SIMD技术优化，可以一次性对多个像素进行处理，性能提升明显，大部分情况下都有3-4倍的提升。

3. 多线程优化

当系统有多个线程/进程时，CPU会按一定的调度策略，把它们尽可能放在不同的核上执行，多线程优化就是把算法拆成多个子任务，跑在不同的线程上，利用CPU多个核的能力，并行执行算法。

比较有名的框架就是OpenMP，OpenMP是一种共享内存并行系统的多线程程序设计方案，支持的编程语言包括C、C++和Python。OpenMP提供了对并行算法的高层抽象描述，特别适合在多核CPU机器上的并行程序设计。编译器根据程序中添加的pragma指令，自动将程序并行处理，使用OpenMP简化了并行程序设计。OpenMP采用fork-join的执行模式，开始的时候只存在一个主线程，当需要并行计算的时候，派生出若干个分支线程来执行并行任务。当并行代码执行完成之后，分支线程汇合，并把控制流程交给单独的主线程。一个典型的fork-join执行模型如图1所示。

 图1. fork-join执行模型示意图

4. GPU加速

GPU即(Graphic Processing Unit)，图形处理器。如图2所示，CPU功能模块很多，能适应复杂运算环境；GPU构成则相对简单，目前流处理器和显存控制器占据了绝大部分晶体管。CPU中大部分晶体管主要用于构建控制电路（比如分支预测等）和Cache，只有少部分的晶体管来完成实际的运算工作。而GPU的控制相对简单，且对Cache的需求小，所以大部分晶体管可以组成各类电路、多条流水线，使得GPU的计算速度有了突破性的飞跃，拥有了更强大的处理浮点运算的能力。

 图2. GPU和CPU架构

要使用GPU进行通用计算，需要基于一个框架，目前的框架主要有CUDA和OpenCL。

CUDA是一种由NVIDIA推出的通用并行计算架构，该架构使GPU能够解决复杂的计算问题。 它包含了CUDA指令集架构（ISA）以及GPU内部的并行计算引擎。这个架构只能在装配了NVIDIA显卡的机器上使用。

OpenCL是一个为异构平台编写程序的框架，此异构平台可由CPU，GPU或其他类型的处理器组成。OpenCL由一门用于编写kernels（在OpenCL设备上运行的函数）的语言（基于C99）和一组用于定义并控制平台的API组成。OpenCL提供了基于任务分割和数据分割的并行计算机制。