為什麼用OpenMP並行計算會出現比單線程還要慢？該怎樣正確使用OpenMP？

01-23

看到網上很多人都有同樣的問題，但是回答很簡略，我沒有真正理解清楚。請哪位大神具體解釋一下阿？

OpenMP的parallel region結束時，線程之間需要同步：即主線程需要等待所有其他線程完成工作之後才能繼續，這個過程可以稱做barrier。一個簡單的barrier的實現如下

_Atomic int finished = 0; int num_threads = N; void barrier() { atomic_add (finished, 1); while (atomic_read(finished) &< num_threads); return; }

在支持compare-and-swap指令的硬體平台上，atomic_add可以用cas指令實現。下面這個表格（來源是這本書：Is Parallel Programming Hard, And, If So, What Can You Do About It?）給出了cas指令的延遲數據：

在上面的barrier代碼中，假定threads被不同的CPU core執行，那麼一定會出現CAS cache miss。假設只有兩個threads，分別被CPU1和CPU2執行。thread1執行atomic_add時，假設正好滿足best-case CAS，即存放finished的cache line正好在CPU1的local cache里。那麼在thread2執行atomic_add時就會發生CAS cache miss，即CPU2要從CPU1的cache中先獲得finished的cache line數據，然後再寫入自己的結果。

根據上面的表格，CAS cache miss需要500個CPU cycles，現代體系結構的CPU每個cycle可以執行不止1條指令，所以500個cycle理想情況下可以執行500條以上的指令。所以，就算只有兩個threads，並且threads之間完全沒有其他通信，如果parallel region單線程執行時需要不到500個cycles，那麼由於barrier的開銷，OpenMP多線程就會比單線程還慢。

上述barrier只是一個簡化了很多的示例，OpenMP一個parallel region還有很多其他額外開銷。另外，如果threads之間還要共享其他數據，並且訪問共享數據時需要「鎖」的保護，一次鎖操作也需要至少一條cas指令，這又增加了額外的開銷。

所以，最好的OpenMP使用場景是線程之間沒有很多需要鎖保護的共享訪問，另外parallel region應該儘可能大，以抵消OpenMP多線程帶來的額外同步開銷。

1.各個thread負載不均衡造成先算完的thread在等沒算好的。解決：用dynamic,guided代替static，代價：overhead，也就是動態調度時間會上去，當然對於本身循環體內運算大的程序來說，這個可以不計。對於可以nowait的地方盡量用。

2.公有變數在thread中有update，這時numa架構要求cache與主內存不斷地刷新。解決方案：盡量用private

我曾經遇到過三種：一種是由於各個線程之間有共享的需要寫入的一個變數，並行的時候發生了衝突。解決方法應該是對共享的變數加鎖。

第二種就是上面所說的對於共享的變數加鎖，不過我用的是atomic原子操作測試的，而且循環體內就這一條語句，貌似是一個循環裡面就一條相加的語句。這個程序邏輯上根本不是並行的，強行並行化+原子操作好像也會造成比單核慢。

第三種是嵌套循環，內層循環並行。並行線程的創建與銷毀會有開銷，在嵌套循環的時候如果對內層for並行的話，這個開銷會很大。解決方法是把並行放在外層的for。

以上三種情況基本上都不是優化不好的範疇，而是根本就是出錯的範疇。寫下來給新上手的同學參考一下。當年我第一次小心翼翼的加上pragma omp for的時候發現比單核慢了好多，那時候真心是懵逼的……