一、概述

算法加速在实际软件层面应用来说大数据和复杂计算的过程中

算法优化，指降低算法计算复杂度，设计新算法快速求解，比如Hungarian匹配算法。或牺牲一些内存，预计算一些重复计算的过程，减少程序层面的复杂度。

语言更换，指将自己算法迁移到更加底层的算法，越是低级的算法，执行速度越快。常见地，将Matlab、Python等解释性代码移植到C++平台，往往有5-20倍的加速效果。

算法并行，指将自己算法的独立计算部分，分成几块，利用CPU指令集、多核或GPU的特性实现加速。多核并行和CUDA并行最为常见。

汇编加速，将自己的一片代码指定为自己设计的汇编语言。多种C++编译器实际上也是将语言转换为汇编代码，对汇编进行加速在嵌入式中常见。(该方法对平台有需求，并不常见)

硬件加速，利用特殊硬件处理特殊算法，降低CPU架构的复杂度。常见的就是FPGA。
https://blog.csdn.net/ljsant/article/details/12707525https://blog.csdn.net/ljsant/article/details/12707525

本文主要介绍算法并行进行加速

其中，3、算法并行

**并行思想从小到大可以总结为：**指令集开发->多核并行->CUDA**并行，**

3.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信息,查看电脑支持哪些指令集。

现代编译器有三种方式来支持 SIMD：

（1）编译器能够在没有用户干预的情况下生成 SIMD 代码，称之为自动矢量化。

（2）用户可以插入 Intrinsics 函数实现 SIMD。

（3）用户可以使用矢量 C++ 类 (仅限ICC编译器) 来实现 SIMD。

在C++中使用SIMD指令集需要包含头文件<xmmintrin.h>,在QT中需要包含头文件<immintrin.h>

3.2 多核编程

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

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

1、利用x86转为x64提速，可以提高1倍的速度

2、多线程的openmp或Intel TBB提速，将cpu的利用率从20%多提高到100%

3、利用GPU提速，至少可以提高5~10倍的运算速度

OpenCV访问像素的三种方法

访问图像中像素的三种方法：1. 指针访问_雪易的博客-CSDN博客

访问图像中像素的三种方法：2. 迭代器访问_迭代器访问像素_雪易的博客-CSDN博客

访问图像中像素的三种方法：3. 动态地址计算配合at方法_雪易的博客-CSDN博客

二、加速方式

1、OpenMP

算法加速的一些方法思路_疯狂的挖掘机的博客-CSDN博客

OpenCV算法加速（1）OpenMP/PPL/TTB基础知识_利白的博客-CSDN博客_opencv加速

VS中启用OpenMP

在项目上右键->属性->配置属性->C/C++->语言->OpenMP支持，选择“是”即可。

提供指向 OpenMP API 中使用的构造的链接。

循环代码

openMP的一点使用经验_weixin_30449453的博客-CSDN博客

#pragma omp parallel for
     for (int i=0;i<10;i++)
         std::cout<<i<<std::endl;

2、TBB

TBB——使用lambda进行并行加速_tbb加速_windxgz的博客-CSDN博客

C++ 实现soble算子_qt sobel算子c++实现_酷小川的博客-CSDN博客

sobel算子实现原理和c++实现sobel（）检测边缘函数_共觞的博客-CSDN博客

TBB_lambda表达式

tbb::parallel_for(tbb::blocked_range<size_t>(0, n), [](const tbb::blocked_range<size_t>& r)

指令集 SIMD指令集(MMX、SSE、AVX)和MIPP

Intel® Intrinsics Guide 用法参考官网

SIMD(Single Instruction Multiple Data ),顾名思义,就是单条指令处理多个数据。

SIMD（Single Instruction Multiple Data）指令集，从第一代开始算起，也快有近20年的历史了，从最开始的MMX技术，到SSE，以及后来的SSE2、SSE3、SSE4、AVX以及11年以后的AVX2，逐渐的成熟和丰富，不过目前考虑通用性方面，AVX的辐射范围还是有限，大部分在优化时还是考虑使用128位的SSE指令集。

3、SSE指令级加速

Intel® Intrinsics Guide 用法参考官网

了解这一类用于进行初始化加载数据以及将暂存器的数据保存到内存相关的指令

使用的xmm0到xmm8的暂存器

其使用方法可以归纳为：“接-化-发”

__m128i p1 = _mm_cvtepu8_epi16(_mm_loadu_si128((__m128i*) (smoothImg + ((i - 1) * src.step + j - 1))));

使用SSE专门的LOAD指令从内存加载一个向量到寄存器。
使用SSE专门的OP指令对两个向量进行某种计算。
使用SSE专门的STORE指令把计算结果从寄存机写回到内存。

1. load系列，用于加载数据，从内存到暂存器

__m128 _mm_load_ss (float *p)  
__m128 _mm_load_ps (float *p)  
__m128 _mm_load1_ps (float *p)  
__m128 _mm_loadh_pi (__m128 a, __m64 *p)  
__m128 _mm_loadl_pi (__m128 a, __m64 *p)  
__m128 _mm_loadr_ps (float *p)  
__m128 _mm_loadu_ps (float *p)

MIPP

MIPP 是用 C++11 编写的向量内在函数 (SIMD) 的可移植和开源包装器（MIT 许可）。它适用于 SSE、AVX、AVX-512 和 ARM NEON（32 位和 64 位）指令。 MIPP 包装器支持简单/双精度浮点数以及有符号整数运算（64 位、32 位、16 位和 8 位）。

OpenMP+SSE TTB+SSE AVX加速

tbb+openMP 无法结合，因为他们都是多线程的多耗时25倍

总结

加速时会消耗内存以提高速度， 消耗内存就是空间换时间

算法分为空间复杂度和时间复杂度，一般在工作中时间要求更高，可以改变算法逻辑，必要情况下，哪怕提高空间复杂度也要降低时间复杂度

并发算法都是压榨设备的性能，特别是现在的多核处理器。但是如果设备性能不够高，即使很高的并发也实现不了，而且将串行修改成并行或者并发，都是要额外付出时间的，所以leader说没必要用二维度的range，就是因为公司电脑性能带不动二维，强行使用带不来较一维明显的效果，还压榨设备性能，也会造成硬件的加速老化。

实际项目中往往牺牲内存提升速度，通过开辟更大的内存，即扩大空间复杂度。来降低算法实现的时间复杂度所以同样的效果其实可以有很多实现方式，而且优劣分明。

加速算法主要就是在空间复杂度和时间复杂度上下文章。