算法加速的一些方法思路

0 引入

在实际软件层面应用来说&＃xff0c;一把算法的执行速度还是能够满足需求的&＃xff0c;但是在大数据和复杂计算的过程中&＃xff0c;由于算法模型的选择和硬件甚至是语言的选择都会影响到算法输出结果的时间&＃xff0c;在实时性要求比较高的场合&＃xff0c;算法加速往往是绕不开的话题&＃xff0c;本文从算法到最后输出的环节&＃xff0c;来提供一些可以优化的思想

• 算法优化&＃xff0c;指降低算法计算复杂度&＃xff0c;设计新算法快速求解&＃xff0c;比如Hungarian匹配算法。或牺牲一些内存&＃xff0c;预计算一些重复计算的过程&＃xff0c;减少程序层面的复杂度。
• 语言更换&＃xff0c;指将自己算法迁移到更加底层的算法&＃xff0c;越是低级的算法&＃xff0c;执行速度越快。常见地&＃xff0c;将Matlab、Python等解释性代码移植到C&＃43;&＃43;平台&＃xff0c;往往有5-20倍的加速效果。
• 算法并行&＃xff0c;指将自己算法的独立计算部分&＃xff0c;分成几块&＃xff0c;利用CPU指令集、多核或GPU的特性实现加速。多核并行和CUDA并行最为常见。
• 汇编加速&＃xff0c;将自己的一片代码指定为自己设计的汇编语言。多种C&＃43;&＃43;编译器实际上也是将语言转换为汇编代码&＃xff0c;对汇编进行加速在嵌入式中常见。(该方法对平台有需求&＃xff0c;并不常见)
• 硬件加速&＃xff0c;利用特殊硬件处理特殊算法&＃xff0c;降低CPU架构的复杂度。常见的就是FPGA。
• cccccccccccccccccccc光学加速&＃xff0c;利用参数制作特定的光散射模型&＃xff0c;输入目标光源直接得到输出结果。&＃xff08;离谱的加速方式&＃xff0c;目前停留在概念&＃xff09;

1、算法优化

算法优化分为两种类型&＃xff1a;① 降低算法复杂度&＃xff1b;② 减少重复计算过程。

2、语言选择

**越是高级的语言&＃xff0c;开发效率越高&＃xff0c;执行速度越慢。**


• 尽量用当前语言的官方库&＃xff0c;官方库往往对算法做了足够的加速。
• 将部分简单函数编译成C&＃43;&＃43;进行调用&＃xff0c;比如Python调用C&＃43;&＃43;&＃xff0c;或Matlab调用C&＃43;&＃43;。
• 对并行性较强的&＃xff0c;且用了少量STL库的算法使用CUDA加速。
• 大矩阵运算考虑Eigen&＃xff0c;cublas等专用库。
• 对并行性较强&＃xff0c;且用了大量STL库的算法使用多核并行加速。
  将高级代码转换为C&＃43;&＃43;项目&＃xff0c;这也是最简单的转换方法了&＃xff0c;这样开发出的算法非常容易落地。

–

3、算法并行

**并行思想从小到大可以总结为&＃xff1a;**指令集开发->多核并行->CUDA**并行&＃xff0c;**


3.1 指令集加速

指令集加速&＃xff0c;一般是针对CPU架构进行的底层优化&＃xff0c;常见于OpenCV和Tensorflow的CPU版本。之所以OpenCV是个经典的开源图像框架&＃xff0c;很大原因是因为其在多个平台上执行效率很高&＃xff0c;其中底层的优化&＃xff0c;比如指令集优化&＃xff0c;起到了关键作用。

数据并行的两种实现在计算机体系中&＃xff0c;数据并行有两种实现路径&＃xff1a;

• MIMD&＃xff08;Multiple Instruction Multiple Data&＃xff0c;多指令流多数据流&＃xff09;。MIMD的表现形式主要有多发射、多线程、多核心&＃xff0c;在当代设计的以处理能力为目标驱动的处理器中&＃xff0c;均能看到它们的身影。

• SIMD&＃xff08;Single Instruction Multiple Data&＃xff0c;单指令流多数据流&＃xff09;。随着多媒体、大数据、人工智能等应用的兴起&＃xff0c;为处理器赋予SIMD处理能力变得愈发重要&＃xff0c;因为这些应用存在大量细粒度、同质、独立的数据操作&＃xff0c;而SIMD天生就适合处理这些操作。SIMD本身并不是一种指令集&＃xff0c;而是一种处理思想&＃xff0c;现在的一些指令集都支持SIMD。&＃xff08;简单来说&＃xff0c;计算1000维向量的点积&＃xff0c;乘法是独立的&＃xff0c;多核心不值得&＃xff0c;这时候就可以利用指令集一次性计算4次或8次乘法&＃xff0c;同样的&＃xff0c;之后的加法也同样可以用指令集计算&＃xff09;
  CPU指令集的发展&＃xff08;针对Intel的x86指令集系列&＃xff09;&＃xff1a;

• MMX指令集 (Multi Media eXtension, 多媒体扩展指令集)。MMX指令集率先在Pentium处理器中使用&＃xff0c;MMX指令集支持算数、比较、移位等运算&＃xff0c;MMX指令集的向量寄存器是64bit。

• SSE指令集&＃xff08;Streaming SIMD Extensions&＃xff0c;单指令多数据流扩展&＃xff09;&＃xff0c;所有的SSE系列指令的向量寄存器都是128bit&＃xff0c;也就是一次性可以计算4个int。SSE最早出现在1999年&＃xff0c;在之后的近10年内&＃xff0c;推出了SSE,SSE2&＃xff0c;SSE3&＃xff0c;SSE4.1&＃xff0c;SSE4.2。
  AVX指令集&＃xff08;Advanced Vector Extensions&＃xff0c;高级向量扩展&＃xff09;。AVX指令集是在之前的SSE128位扩展到和256位的单指令多数据流。AVX出现在2008年&＃xff0c;之后出了AVX2&＃xff0c;2014年&＃xff0c;AVX-512将数据bit由256bit扩展到了512bit。AVX是目前比较常用的指令集&＃xff0c;256位的类型可以一次计算4个double&＃xff0c;有效的提升性能。
  利用CPU-Z软件可以查看电脑的CPU信息,查看电脑支持哪些指令集。

现代编译器有三种方式来支持 SIMD&＃xff1a;
&＃xff08;1&＃xff09;编译器能够在没有用户干预的情况下生成 SIMD 代码&＃xff0c;称之为自动矢量化。
&＃xff08;2&＃xff09;用户可以插入 Intrinsics 函数实现 SIMD。
&＃xff08;3&＃xff09;用户可以使用矢量 C&＃43;&＃43; 类 (仅限ICC编译器) 来实现 SIMD。
在C&＃43;&＃43;中使用SIMD指令集需要包含头文件,在QT中需要包含头文件

3.2 多核编程

多核编程可以理解为就是多线程编程&＃xff0c;总体上可以分为三个部分&＃xff1a;OpenMP并行&＃xff0c;opencv并行和多线程并行。在设计相关代码时候&＃xff0c;切记变量可以被多个线程访问&＃xff0c;但同一时间只能被一个线程修改&＃xff0c;如果多个线程想修改同一个变量&＃xff0c;可使用原子操作或加锁。 当然&＃xff0c;多核编程不止这些&＃xff0c;还有tbb&＃xff0c;mkl等等。

• OpenMP 并行。这种并行办法是最简单的一种并行方法&＃xff0c;直接在for循环前面添加#pragma omp parallel for即可&＃xff0c;程序会自动将for循环分解。值得注意的是&＃xff0c;该方法是在for循环前开始创建线程&＃xff0c;结束后并销毁&＃xff0c;这个过程会产生一些时间消耗&＃xff0c;大约在3-5ms之间&＃xff0c;做实时性应用开发的时候需要注意这个问题。&＃xff08;如果用到opencv&＃xff0c;内部也有并行&＃xff09;
• 多线程并行。上述的两种方法是针对一个for循环来解决的&＃xff0c;但是整个算法不可能就由一个for循环构成&＃xff0c;如果每个for循环都这么做的话&＃xff0c;创建线程的开销巨大&＃xff0c;因此&＃xff0c;多线程并行主要就是解决这类问题的。初始化时候创建好线程&＃xff0c;之后主线程串联算法&＃xff0c;子线程解决for循环问题&＃xff0c;线程可能会使用同步&＃xff0c;加锁等手段逐步执行&＃xff0c;最终获得输出结果。创建多线程时候&＃xff0c;系统本身就会将不同线程分到不同核心上&＃xff0c;有自己的调度手段&＃xff0c;所以该方法加速效果很明显&＃xff0c;就是过于面向过程&＃xff0c;不方便后续的改进。

3.3 CUDA 编程加速

• CUDA加速其实是最好的加速手段&＃xff0c;CUDA最大的特性就是核心数特别多&＃xff0c;一般是几千个&＃xff0c;相比于CPU&＃xff0c;加速倍数高达20-200倍之间。特别是推出的Jetson NX系列嵌入式卡&＃xff0c;核心数在128-512之间&＃xff0c;推进了更多算法的落地应用
  CUDA开发主要还是有C语言风格&＃xff0c;C&＃43;&＃43;用的很少&＃xff0c;切记一点避免在CUDA中动态分配内存&＃xff0c;最好通过参数传递内存指针。

4、汇编加速

用汇编加速的方法往往指的是C/C&＃43;&＃43;与汇编混合编程&＃xff0c;尽管多种编译器均有优化等级选项&＃xff0c;但是越是高级的语言&＃xff0c;时间损耗越多。
什么时候使用汇编加速呢&＃xff1f; 一般有两种情况需要嵌入汇编代码&＃xff1a;

• ① 升级项目&＃xff0c;项目原始版本是汇编代码&＃xff0c;现在需要用C&＃43;&＃43;开发&＃xff0c;重写汇编代码注定耗时&＃xff0c;直接调用汇编是个很好的解决方案。
• ② 不同的语言对算法一半都有特定的处理方法&＃xff0c;比如Matlab之类尽量使用矩阵运算&＃xff0c;C&＃43;&＃43;尽量使用指针访问等&＃xff0c;如果有个频繁调用的算法&＃xff0c;在汇编上有独特的计算方法&＃xff0c;那么直接在C&＃43;&＃43;调用这个汇编函数&＃xff0c;可以达到加速效果。
  如何嵌入汇编代码呢&＃xff1f; 方法很简单&＃xff0c;使用关键字__asm来加入一段汇编语言的程序&＃xff0c;C&＃43;&＃43;下具体的格式为&＃xff1a;__asm{ 指令 [;指令] /* comments */ … 指令}

5、硬件加速

前面介绍了各种通过编程加速的方法&＃xff0c;核心是将算法进行并行化处理&＃xff0c;总的来说

多核并行&＃xff0c;启动并行时需要开多线程&＃xff0c;需要少量的时间&＃xff08;<10ms)&＃xff0c;因此仅适用耗时较长的算法(>100ms)的并行。
CUDA并行&＃xff0c;算法不可避免串行过程&＃xff0c;因此许多时间在内存和显存之间的拷贝。
CPU指定集&＃xff0c;小规模加速&＃xff0c;但仅限于各种基本运算操作&＃xff08;加减乘除、位运算等&＃xff09;。
如今&＃xff0c;FPGA是日趋热门的一种加速方法&＃xff0c;与软件加速不同&＃xff0c;该方法是直接将算法设计在电路上&＃xff0c;变成专有模块进行并行。

6、引用

算法加速总的来说就是拿空间换时间&＃xff0c;在执行上并行运算&＃xff0c;达到加速效果。

1、是科研人就要快&＃xff01;加速你的算法&＃xff01;
2、C&＃43;&＃43;中使用SIMD的方法
3、深入代码优化 (二) 使用SIMD优化程序