並行編程和C++

Question

最近我寫了很多關於並行計算和編程的書，我注意到在並行計算方面出現了很多模式。注意到微軟已經發布了一個庫以及Microsoft Visual C++ 2010社區技術預覽版（命名爲並行模式庫），我想知道你使用和遇到的常見並行編程模式可能值得記住嗎？你有沒有遵循的習慣用法，以及你在用C++編寫並行程序時似乎一直彈出的模式？

Answer 1

模式：

• 農產品/消費

  • 一個線程產生數據
  • 一個線程消費數據

• 循環並行

  • 如果你能證明每個迴路是獨立
    每次迭代可以在sperate線程來完成

• 重新拉線

  • 其他線程做的工作和更新數據結構，但一個線程重新繪製屏幕。

• 主事件線程

  • 多個線程可產生事件
  • 一個線程必須處理該事件（如順序很重要）
  • 應儘量分開事件線程/ RE - 線程
    這（幫助）可以防止用戶界面凍結
    但如果不仔細做，可能會導致過度的重新繪製。

• 工作組

  • 一組線程等待上闕的工作。
  • 線程從隊列中提取一個工作項（如果沒有可用的，則等待）。
    線程在一個工作項上工作直到完成
    線程完成後返回隊列。

Answer 2

首先，您必須在共享內存計算和無共享計算之間進行選擇。共享內存是比較容易的，但沒有規模那麼好 - 你會使用共享什麼，如果你要麼

一）有一個羣集，而不是多處理器系統，或

B）如果你有多個CPU （比如說> 60）和高度的非均勻內存

對於共享內存，常見的解決方案是使用線程;它們很容易理解爲一個概念，並且易於在API中使用（但難以調試）。

對於無共享，您使用某種消息。在高性能計算中，MPI被建立爲消息中間件。

然後，您還需要爲並行活動設計架構。最常見的方法（又因爲它很容易理解）是農民工模式（又名主從）。

Answer 3

並行執行模式

具有確定性圖案結構化並行編程主要是基於反覆並行執行模式的集合的高層次的方法，通常被稱爲算法骨架或並行結構，這些抽象的程序描述和隱藏低級多線程細節以及許多程序員並行的固有複雜性。

這些可重複使用的模式可以自動執行許多並行範例相關例程，例如同步，通信，數據分區或任務調度，並在內部處理它們。這種高層次的方法嘗試傳統的低級線程鎖定模型，提供更多的抽象和更簡單的方式來表達並行性，集中生產力和可編程性而不是性能。

有很多常用的模式，如：地圖，減少，的fork-join，管道或並行循環...

論文

「結構化並行編程與確定性模式」是一個文件，該文件討論這些模式。您還可以看到「MHPM：多尺度混合編程模型：靈活的並行化方法」，它描述了這種方法的C++實現，名爲XPU。

庫

XPU是基於任務的C++庫從一組可複用的執行模式組成。它允許在單個齊次編程模型中以幾個粒度級別表達幾種類型的並行性。它很容易使用，並說明使用模式設計並行程序的重要性。

例如它允許的表達：

1. 任務並行模式：

   簡單或分層叉/加入執行一些功能，例如如 自動檢測和共享數據的保護圖案。

2. 數據並行模式：

   具有可縮放數據分區

   並行迴路圖案。

3. 顳平行圖案：

   管道執行模式。

Answer 4

您必須對螺栓並行的程序的一部分的基本知識。 C++ 17中有很多（例如foreach，排序，查找和朋友，map_reduce，map，reduce，prefix_sum ...的並行版本）請參閱C++ Extensions for Parallelism

然後，您將獲得像continuations這樣的項目。認爲std::future但繼續。有很少的方法來實現這些（boost有一個很好的現在，因爲標準沒有下一個（...）或然後（...）方法，但最大的好處是，一個人不必等待它做下一個任務

auto fut = async([](){..some work...}).then([](result_of_prev){...more work}).then... ; 
fut.wait(); 

缺乏後續任務之間的同步是作爲任務/線程間通信重要/ ...是什麼減慢並行程序。

因此，與基於任務並行有一個任務調度程序，你只需將任務關閉然後走開，它們可能有方法（如信號量）來進行通信，但這不是強制性的。Intel Thread Building Blocks和Microsoft Parallel Pattern Library都有fa這個功能。

之後，我們有fork/join模式。它並不意味着爲每個任務創建N個線程。只要你有這些N，理想情況下獨立的事情（fork），當它們完成時，在某個地方有一個同步點（join）。

auto semaphore = make_semaphore(num_tasks); 
add_task([&semaphore]() {...task1...; semaphore.notify(); }); 
add_task([&semaphore]() {...task2...; semaphore.notify(); }); 
... 
add_task([&semaphore]() {...taskN...; semaphore.notify(); }); 
semaphore.wait(); 

從上面你可以開始看到這是一個流圖的模式。未來是（A >> B >> C >> D），叉加入是（A | B | C | D）。有了這個，你可以將它們組合起來形成一個圖表。 （A1 >> A2 | B1 >> B2 >> B3 | C1 | D1 >> D2 >>（E1 >> E2 | F1））其中A1 >> A2表示A1必須在A2之前，A | B表示A和B可以同時運行。緩慢的部分在事物相遇的圖/子圖的末尾。

目標是找到不需要溝通的系統的獨立部分。如上所述，並行算法幾乎在所有情況下比其順序對應的算法慢，直到工作負載變得足夠高或者規模變得足夠大（假設通信不太健談）。例如排序。在4核心計算機上，您將獲得2.5倍左右的性能，因爲合併很瑣碎，需要大量同步，並且在第一輪合併後無法運行所有內核。在N很大的GPU上，可以使用效率較低的類型，比如Bitonic，而且速度非常快，因爲你有很多工作人員來完成工作，每個人都很安靜地做自己的事情。

一些技巧，以減少commmunication包括，使用陣列對的結果，使得每個任務是不是想以推動一個值，以鎖定對象。通常以後減少這些結果可能會非常快。

但是，對於所有類型的並行性來說，緩慢來自通信。減少它。