一、為啥我要寫這篇（沒啥用的）文章？

當年大四畢業的時候，那時候搞複雜網路，寫出來的程序一天能跑出來的數據量相比我需要的，粗略來看至少差兩個數量級。後來在網上四處搜索，怎麼入門並行計算，看了看一些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但是實際沒有成功並行化的語句加上這些指令會有效果。

這是我在知乎上應該是第一次輸出干（水）貨，如果說的還對的話給個贊支持下唄～有什麼問題歡迎指出！謝謝啦～


推薦閱讀：
相关文章