是科研⼈就要快！加速你的算法！
在科研中，⼤多数论⽂其实还是看精度和效果的，对于速度其实没有那么⾼的追求，很多⼈⽤速度评价⾃⼰算法的复杂度很低，但实际上这是不准确的，当然在精度占优的情况下，能够提⾼速度，给⾃⼰的实验结果增彩。
关于算法程序的加速，在动⼿前先要按照如下流程进⾏思考，以决定从哪⾥⼊⼿加速。
算法优化，指降低算法计算复杂度，设计新算法快速求解，⽐如Hungarian匹配算法。或牺牲⼀些内存，预计算⼀些重复计算的过程，减少程序层⾯的复杂度。
语⾔更换，指将⾃⼰算法迁移到更加底层的算法，越是低级的算法，执⾏速度越快。常见地，将Matlab、Python等解释性代码移植到C++平台，往往有5-20倍的加速效果。
嵌入式多线程编程算法并⾏，指将⾃⼰算法的独⽴计算部分，分成⼏块，利⽤CPU指令集、多核或GPU的特性实现加速。多核并⾏和CUDA并⾏最为常见。
汇编加速，将⾃⼰的⼀⽚代码指定为⾃⼰设计的汇编语⾔。多种C++编译器实际上也是将语⾔转换为汇编代码，对汇编进⾏加速在嵌⼊式中常见。(该⽅法对平台有需求，并不常见)
硬件加速，利⽤特殊硬件处理特殊算法，降低CPU架构的复杂度。常见的就是FPGA。
光学加速，利⽤参数制作特定的光散射模型，输⼊⽬标光源直接得到输出结果。（离谱的加速⽅式，⽬前停留在概念）
强烈注意：
所有的优化，都是在⾃⼰算法流程不变的前提下进⾏优化，因为优化后的程序，⾼度⾯向过程，如果算法某个流程要换以达到更⾼精度，则改动⼯作量较⼤。
下⾯我对每种加速⽅法进⾏详细的说明（本⽂只列举加速⽅法，并给出⼏种参考⽰例，并不会详细讲解如何使⽤，仅介绍思想）。
加速⽅法详解
1 算法优化算法优化分为两种类型：① 降低算法复杂度；② 减少重复计算过程。
降低算法复杂度。在求解最优值时候，我们最容易想到的就是暴⼒求解。当数据量特别⼤的时候，这种⽅法耗时就异常⾼。在查、最有匹配中，有⼤量的优化算法解决这类问题（图论、数据结构、算法导论介绍了很多⽅法）。
例如，匈⽛利算法（Hungarian Algorithm）与KM算法（Kuhn-Munkres Algorithm）是在多⽬标跟踪的论⽂中见到的两种算法。他们都是⽤来解决多⽬标跟踪中的数据关联问题。匈⽛利算法与KM算法都是为了求解⼆分图的最⼤匹配问题。下图就是其中的⼆分图，⼆分图呢就是能分成两组，U,V。其中，U上的点不能相互连通，只能连去V中的点，同理，V中的点不能相互连通，只能连去U中的点。这样，就叫做⼆分图。在图像中，可以把⼆分图理解为视频中连续两帧中的所有检测框，第⼀帧所有检测框的集合称为U，第⼆帧所有检测框的集合称为V。同⼀帧的不同检测框不会为同⼀个⽬标，所以不需要互相关联，相邻两帧的检测框需要相互联通，最终将
相邻两帧的检测框尽量完美地两两匹配起来。⽽求解这个问题的最优解就要⽤到匈⽛利算法或者KM算法。
减少重复计算过程。这个⼀般来说具体算法具体分析，⼀般要么是记录共⽤的中间变量，要么就是把与输⼊⽆关的数据，在初始化变量时候计算好。简单来说，拟合参数时候，我们经常会⽤到公式的形式，即，这时候，定义，那么的形式，如果能预计算的话，每次获得这个矩阵经过有限次加法即可。2 语⾔更换越是⾼级的语⾔，开发效率越⾼，执⾏速度越慢。尽量⽤当前语⾔的官⽅库，官⽅库往往对算法做了⾜够的加速。将部分简单函数编译成C++进⾏调⽤，⽐如Python调⽤C++，或Matlab调⽤C++。对并⾏性较强的，且⽤了少量STL库的算法使⽤CUDA加速。⼤矩阵运算考虑Eigen，cublas等专⽤库。对并⾏性较强，且⽤了⼤量STL库的算法使⽤多核并⾏加速。
将⾼级代码转换为C++项⽬，这也是最简单的转换⽅法了，这样开发出的算法⾮常容易落地。
3 算法并⾏
并⾏思想从⼩到⼤可以总结为：指令集开发→多核并⾏→CUDA并⾏，在深度学习中，TensorRT是⼀种更⾼级的CNN⽹络加速⽅法。
3.1 指令集加速
Ax =b x =(A A )A b ′−1′A =
(a ,a ,...,a )12n ′A A =′a a ∑i =1n 1T 1a a 1T
1
指令集加速，⼀般是针对CPU架构进⾏的底层优化，常见于OpenCV和Tensorflow的CPU版本。之所以OpenCV是个经典的开源图像框架，很⼤原因是因为其在多个平台上执⾏效率很⾼，其中底层的优化，⽐如指令集优化，起到了关键作⽤。数据并⾏的两种实现在计算机体系中，数据并⾏有两种实现路径：
MIMD（Multiple Instruction Multiple Data，多指令流多数据流）。MIMD的表现形式主要有多发射、多线程、多核⼼，在当代设计的以处理能⼒为⽬标驱动的处理器中，均能看到它们的⾝影。
SIMD（Single Instruction Multiple Data，单指令流多数据流）。随着多媒体、⼤数据、⼈⼯智能等应⽤的兴起，为处理器赋予SIMD处理能⼒变得愈发重要，因为这些应⽤存在⼤量细粒度、同质、独⽴的数据操作，⽽SIMD天⽣就适合处理这些操作。SIMD本⾝并不是⼀种指令集，⽽是⼀种处理思想，现在的⼀些指令集都⽀持SIMD 。（简单来说，计算1000维向量的点积，乘法是独⽴的，多核⼼不值得，这时候就可以利⽤指令集⼀次性计算4次或8次乘法，同样的，之后的加法也同样可以⽤指令集计算）CPU指令集的发展（针对Intel的x86指令集系列）：
MMX指令集 (Multi Media eXtension, 多媒体扩展指令集)。MMX指令集率先在Pentium处理器中使⽤，MMX指令集⽀持算数、⽐较、移位等运算，MMX指令集的向量寄存器是64bit。
SSE指令集（Streaming SIMD Extensions，单指令多数据流扩展），所有的SSE系列指令的向量寄存器都是128bit，也就是⼀次性可以计算4个int。SSE最早出现在1999年，在之后的近10年内，推出了SSE,SSE2，SSE3，SSE4.1，SSE4.2。
AVX指令集（Advanced Vector Extensions，⾼级向量扩展）。AVX指令集是在之前的SSE128位扩展到和256位的单指令多数据流。AVX出现在2008年，之后出了AVX2，2014年，AVX-512将数据bit由256bit扩展到了512bit。AVX是⽬前⽐较常⽤的指令集，256位的类型可以⼀次计算4个double，有效的提升性能。利⽤CPU-Z软件可以查看电脑的CPU信息，
关于指令集的使⽤，在博客给出的源码中，使⽤了AVX指令集对代码进⾏处理，为了⽅便理解使⽤，我们以计算椭圆的采样点为例，其中分别为椭圆的中⼼点、长短轴及旋转⾓。表⽰椭圆参数⽅程⽤于采样。指令集的⽂档参考 。
x ,y ,R ,r ,θo o cost ,sint {x =Rcosθcost −rsinθsint +x o y =Rsinθcost +rcosθsint +y o
则利⽤指令集计算采样点的⽅法如下所⽰，显然原来需要计算VALIDATION_NUMBER次采样点的过程，现在仅需要
VALIDATION_NUMBER/8次(sizeof(__m256) / sizeof(float)=8)。
// 初始化旋转变换矩阵，这⾥angleRot = \theta
const float _ROT_TRANS[4]={ R *cos(angleRot),-r *sin(angleRot),
R  *sin(angleRot), r  *cos(angleRot)};
// Estimate the sampling points number N. Note: N = RoundEllipseCircum;
// Use SSE to faster the step of ellipse validation.
/
/ 考虑到指令集实际上⼀次性计算8个数据，
// 则_mm256_set1_ps的⽬的是⽤⼀个float初始化⼀个__m256
// 举个例⼦：假如需要初始化的float为k，则调⽤_mm256_set1_ps之后得到
// [k,k,k,k,k,k,k,k]
__m256 _rot_trans_0 =_mm256_set1_ps(_ROT_TRANS[0]),
_rot_trans_1 =_mm256_set1_ps(_ROT_TRANS[1]),
_rot_trans_2 =_mm256_set1_ps(_ROT_TRANS[2]),
_rot_trans_3 =_mm256_set1_ps(_ROT_TRANS[3]);
__m256 x_center =_mm256_set1_ps(xyCenter[0]),
y_center =_mm256_set1_ps(xyCenter[1]);
__m256 tmp_x, tmp_y, tmp_wx, tmp_wy, tmp_w;
for(int i =0; i < VALIDATION_NUMBER; i +=sizeof(__m256)/sizeof(float))
{
// ⼀次性读取256位数据，实际上就是加载8个float到base_x,base_y
// 这⾥的base_x = cost, base_y = sint
__m256 base_x =_mm256_load_ps(vldBaseDataX + i);
__m256 base_y =_mm256_load_ps(vldBaseDataY + i);
// calculate location x
// _mm256_mul_ps 计算乘法：计算每个float的乘法，_mm256_add_ps
// 举个例⼦：两个__m256数据为[k1,k2,...,k8], [p1,p2,...,p8]
// 调⽤_mm256_mul_ps之后，得到[k1p1,k2p2,...,k8p8]
// 调⽤_mm256_add_ps之后，得到[k1+p1,k2+p2,...,k8+p8]
tmp_x =_mm256_add_ps(
_mm256_mul_ps(_rot_trans_0, base_x),
_mm256_mul_ps(_rot_trans_1, base_y));
tmp_x =_mm256_add_ps(tmp_x, x_center);
// calculate location y
tmp_y =_mm256_add_ps(
_mm256_mul_ps(_rot_trans_2, base_x),
_mm256_mul_ps(_rot_trans_3, base_y));
tmp_y =_mm256_add_ps(tmp_y, y_center);
// Save location x, y
// _mm256_storeu_ps的⽬的是将计算后的8个float存⼊float矩阵中
_mm256_storeu_ps(sample_x + i, tmp_x);
_mm256_storeu_ps(sample_y + i, tmp_y);
}
其实后期测试速度发现，实际加速效果没有特别明显，毕竟⽤了⼤量中间变量，且函数的调⽤传递了参数，指令集实际上在汇编中⽤的多，如果在代码中内嵌指令集可能效果会更好。
参考资料：
1
3.2 CPU 多核编程
多核编程可以理解为就是多线程编程，总体上可以分为三个部分：OpenMP并⾏，opencv并⾏和多线程并⾏。在设计相关代码时候，切记变量可以被多个线程访问，但同⼀时间只能被⼀个线程修改，如果多个线程想修改同⼀个变量，可使⽤原⼦操作或加锁。 当然，多核编程不⽌这些，还有tbb，mkl等等。
OpenMP 并⾏。这种并⾏办法是最简单的⼀种并⾏⽅法，直接在for循环前⾯添加#pragma omp parallel for即可，程序会⾃动将for循环分解。值得注意的是，该⽅法是在for循环前开始创建线程，结束后并销毁，这个过程会产⽣⼀些时间消耗，⼤约在3-5ms之间，做实时性应⽤开发的时候需要注意这个问题。下⾯给出了⼀个并⾏⽰例。当然openmp有多种操作函数，感兴趣去对应的开发教程即可。
#include<iostream>
#include<omp.h>
using namespace std;
int main(){
omp_set_num_threads(4);
#pragma omp parallel for
for(int i =0; i <3; i++)
printf("i = %d, I am Thread %d\n", i,omp_get_thread_num());
getchar();
}
// i = 0, I am Thread 0
// i = 1, I am Thread 1
// i = 2, I am Thread 2
OpenCV 并⾏。 OpenCV提供了⼀种并⾏计算函数parallel_for_，内部集成多种并⾏框架。在c++11中，可以不必定⼀个类去继承并⾏计算循环体类ParallelLoopBody，可以直接使⽤。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。