一、为啥我要写这篇（没啥用的）文章？

当年大四毕业的时候，那时候搞复杂网路，写出来的程序一天能跑出来的数据量相比我需要的，粗略来看至少差两个数量级。后来在网上四处搜索，怎么入门并行计算，看了看一些CSDN上的博客，找了找一些书，零零散散拼凑了一些知识。

当时确定的学习路径就是OpenMP+CUDA双轨制。现在来看这个路径基本上没问题，基本上算是入门最快的了。但是当时碎片化的学习模式的极大弊端就是基础不稳，当时尝试用的omp parallel for语句，跑了几天感觉不对劲，发现因为线程之间互相冲突，多核跑的比单核还慢。当时的我无力解决这个问题，后来随便混了个毕业不了了之了。

后来上了一门讲CUDA的课（在此给科大的同学强烈安利一发周斌老师的课程，课名忘了，反正带CUDA这个词，讲的真好），后来各个组讲project的时候，可能处于降低要求的考虑，说加速比的时候，和CPU程序对应好像没有强调是用多核并行的。我还记得有一个程序的加速比大概是2……感觉CPU上跑个多核应该就能反杀了吧。其实和CPU比的话，CUDA的对手应该是多核+SIMD指令下的CPU更合适一点，毕竟GPU基本上也是SIMD的。

之前看CPU上的SIMD的应用，似乎都麻烦了点。直到前一段时间偶然看到OpenMP4.0的新标准，支持了SIMD编译指导语句。就初步尝试了一下。

至于为啥说这篇文章没啥用，因为简单的向量化，编译器就已经可以实现了。最最简单的两个向量之和这样的运算，gcc -O3就可以搞定。

而且我也不太清楚这个玩意用在啥地方合适……大规模的计算用显卡或者专业计算卡应该更合适，小规模的计算又省不了多少时间。

不过还是在这里写写吧。如果有后来的同学，就像当年四处找博客的我一样，出于某些原因需要半路出家找寻一些信息，这个也许可以提供一丁丁点的帮助。

二、开始前先闲聊一下

为什么SIMD可以加速？

为什么GPU可以加速？

为什么并行可以加速？

GPU那么厉害，是不是以后可以把CPU扔了？

为什么想要实现加速要写的代码，写起来都那么蛋疼……

这一切的源头，都是因为「天底下没有免费的午餐」啊。

（下面的东西主要源于个人理解，如有问题欢迎大家来帮我指正～）

首先感谢这个回答

应该如何理解No Free Lunch Theorems for Optimization? - DanWuWisc的回答 - zhihu.com/question/3977

当初就是这个回答让我知道了这个定理。（刚刚发现自己竟然没给点赞，赶紧补上～）

大概在1995年到1996年，Wolpert和Macready证明了「没有免费的午餐定理」（No Free Lunch Theorem，即NFL定理），它可以大概表述为：

对于所有可能的问题，任意的两个演算法的平均表现度量是一样的。

比如说，为什么对于同一个物种，基因多样性对于维持种群如此重要？

（我猜）如果把基因当做一种「解决问题的方法」，在环境中生存当做「要解决的问题」的话，那么很明显：如果环境一成不变，那么不需要基因多样性，经过遗传演算法代代优化应该可以收敛到一个局部最优解。

但是环境是会变化的，当环境变化之后，如果对以前的环境太适应了，那么对于新环境的适应一定就会出问题。

适应性的两面：对于变化的世界的适应和对于给定的环境的最佳适应，两者存在本质的冲突。

所以这个世界要多一点温情，对于弱者要有一点宽容。

只剩下强者的世界，离毁灭就不远了。

嗯……刚才扯了点别的。现在回到我们的问题上来。

既然对于所有可能的问题，任意两个演算法都没啥区别。

那么让它们产生区别的，就是它们对于特定问题的契合程度。

能够最大化的利用问题的特征的演算法，上限一定会更高。

我们要解决的问题是什么类型的？

当然有串列的：先要烧砖，然后才能盖房子。

然而也有并行的：搬砖的时候，可以一次拿一块砖头（SISD），可以一次拿好多块砖头（

SIMD）。

还可以这个人搬砖，另一个人抹水泥（MIMD？）

也就是说，我们要解决的问题，天生就含有并行分量。

可以并行的类型，还不止一种。

这就是为什么并行计算可以起到加速作用，但是并不能解决所有问题。在可以被并行解决的问题的规模给定的情况之下，随著并行计算能力的提高，总共解决问题所花费的时间将越来越被串列的，不能被并行的部分限制（阿姆达尔定律）。

SIMD的意思，是「单指令多数据」，指的是一个指令，同时操作好几个数据。

比如在图像的一些处理上，需要同时处理RGB这三个通道的数据，而操作是一样的。这就是SIMD可以大显身手的地方。

在遥远的586时代，CPU被从硬体上给予了这方面的能力，并且引入的新的指令集，叫做MMX，后来继续发展SSE，还有现在的AVX，AVX2。

比较适合处理像我说的一个人搬砖，一个人抹水泥的情况的计算任务的，多核就很合适。

以上讨论全部基于小规模的计算，不涉及大规模的集群啥的，因为这东西我用不到，学了都忘了……

那么回来再顺便说说这一小节开头说的那几个问题：

GPU和CPU的本质一样，都是「计算」。但是它是专门为了图形计算所做的硬体设计，比如强大的SIMD计算能力。

但是通用性，将会被不可避免的牺牲，两者不可兼得。

也就是说，GPU之所以能加速，是因为它针对了所要解决的问题进行了特殊的设计，这个特殊的设计，就是它能加速的本质原因，也是它不能取代CPU的原因。（CPU可以取代GPU，但是性能一定不能做到同样工艺下的GPU的水平）

当然现在的GPU因为向通用化方面发展（解决的问题的特征发生了变化），通用性有所增强，通用计算的代码的书写难度有所下降。

但是归根到底，这份加速所需的代价还是有的，还是需要人或者高度只能的机器来分析问题：哪里可以并行，并行需要怎么分配……等等等等。

这就是为啥代码不好写的原因。像OpenCL这种适应多平台而且接近底层的，就比较难学……我反正是没学会（大哭）

三、并行计算工具的简要介绍

OpenMP：GCC自带，VisualStudio似乎只支持到2.0.共享内存模型。非常适合一台电脑上面写多核。入门非常容易。基于CPU，不过貌似最新的标准加入了OpenACC的支持，开始涉足GPU了？

MPI：适合大量的不同的电脑不共享存储空间的计算。

CUDA：NVIDIA开发的用来在它家的卡上跑的平台。容易学习。GPU计算入门推荐。

C++AMP：微软开发的，好像只能在VisualStudio上用？可以使用A家和N家的卡。（没学过不会……）

OpenCL：支持CPU，GPU，A卡，N卡，连Intel的卡好像都有支持……，接近底层，通用性最好。性能不如CUDA。学习难度较高。

OpenACC：新出的，跨平台，难度约等于OpenMP，据说很有前途（想学ing）

入门推荐OpenMP（CPU）和CUDA（GPU）。

四、OpenMP最最最最简要的一点说明：

这里介绍一下最最最最常用的，for循环的并行方法。

那就是在for循环的上一行，写上

#pragma omp parallel for

这样子，下面紧接著的那个for循环就会被并行化。

而SIMD的用法，则是：

#pragma omp simd

还可以组合：

#pragma omp parallel for simd

接下来在例子中具体来看。

五、开始啦～

我的电脑是Haswell的i5，具体型号忘了。系统是Ubuntu16.04，GCC5.4，自带OpenMP4.5.

原型程序是陈国良老师在《并行计算——结构·演算法·编程》第398页的程序，我这里写的长这样：

#include <iostream>

#include <sys/time.h>#include <cmath>#define N 100000000using namespace std;int main(){ timeval start,end; int i; double x,pi,sum=0; double step=1.0/N; gettimeofday(&start,NULL); for(i=0;i<N;i++) { x=(i+0.5)*step; sum+=4.0/(1.0+x*x); } gettimeofday(&end,NULL); pi=sum*step; int time_used=1000000*(end.tv_sec-start.tv_sec)+(end.tv_usec-start.tv_usec); cout<<"time_used="<<time_used<<endl; cout<<"PI="<<pi<<endl; return 1;}

编译指令：

g++ -O1 simd.cpp

这里后面的「-O1」是优化编译的意思，这里为了和后面的程序保持一致先加上了。理由后面会提到。

结果是

time_used=458181

PI=3.14159

现在让我们加上OpenMP编译指导语句：

在for循环前面，加上

#pragma omp parallel for reduction(+:sum) private(x)

这里解释一点之前没有解释的东西：

reduction子句：这个子句的意思是使用指定的操作对列表中出现的变数进行规约。这个例子中，制定的操作是加号」+「，规约的变数是sum。也就是对sum这个变数，并行的各个线程各自的结果最后进行一个加和。

private子句：表示列出的变数对于各个线程来说是私有的。这个例子中是x。也就是说每一个并行的线程都拥有自己的x值，互相之间不干扰。

以上这两个语句是让这个程序运行正确所必须要加上的。

然后编译的时候要加一点东西：

g++ -O1 -fopenmp simd.cpp

结果变成了：

time_used=220752

PI=3.14159

时间花费大概变成了之前的1/2，我的四核处理器变成了双核处理器（大哭）

慢著，要不再执行几次？

time_used=179538

PI=3.14159

time_used=144554

PI=3.14159

嗯～多核并行在运算时间方面确实会有点差别，这个慢慢习惯就好啦～

接下来我们要试试SIMD了！

把编译指导语句中的parallel for先删了，改成simd：

#pragma omp simd reduction(+:sum) private(x)

这一次，编译命令多了不少东西：

g++ -O1 -fopenmp -fopt-info-vec-optimized -ftree-vectorizer-verbose=2 simd.cpp

新增的两个东西的意思是：

-fopt-info-vec-optimized：显示被成功向量化的语句

-ftree-vectorizer-verbose=2：紧接著上一句，给出更多信息。想要对这两个了解更多的话，可以参考Using the GNU Compiler Collection (GCC)

这回试一试，发现输出的多了一个东西：

simd.cpp:17:10: note: loop vectorized

这说明，我们这个循环被向量化了。

这里试一下不要-O1这个选项：

g++ -fopenmp -fopt-info-vec-optimized -ftree-vectorizer-verbose=2 simd.cpp

提示成功向量化的那个输出没了！

这一点特别坑……要想使用SIMD这个编译指令，要加上-O1/2/3/fast一类的优化指令，才能开启。

顺便提一下，-O3自带自动向量化功能，一些简单的向量化，直接这个就可以搞定。不过这里这个有点复杂，-O3是不行的。

试试！

time_used=229064

PI=3.14159

time_used=230128

PI=3.14159

time_used=227775

PI=3.14159

加速比很稳定，大概2倍。

现在我们更进一步：多核和SIMD结合：

#pragma omp parallel for simd reduction(+:sum) private(x)

这里把parallel for加回来了。

再看看：

time_used=78656

PI=3.14159

time_used=120695

PI=3.14159

time_used=74148

PI=3.14159

波动挺大的，但是有的超过了4倍，说明两个加速协同起了作用。

最后补充一下，对于现在的处理器，可以在编译的时候加上-mavx，或者-mavx2一类的指令，或者干脆-march = native.AVX这种比较新的指令集，对于对的不那么齐的数据支持更好，好像。有一些逻辑上能SIMD但是实际没有成功并行化的语句加上这些指令会有效果。

这是我在知乎上应该是第一次输出干（水）货，如果说的还对的话给个赞支持下呗～有什么问题欢迎指出！谢谢啦～


推荐阅读：
相关文章