使用OpenMP給程式加速（三）負載平衡與并行性能--轉載

在執行計算任務時擁有一枚閑置核心無異于擁有一項廢棄資源，在該核心上實施有效并行操作會延長線程化應用的整體運作時間。這枚核心處于閑置狀态的原因有很多種，需要從記憶體或 I/O 中取出便是其中一個原因。盡管完全避免核心進入閑置狀态不太可能，但程式設計人員仍然可以采取一些措施來縮短閑置時間，如采用重疊 I/O、記憶體預取的方式或重新排列資料通路模式的順序，提高高速緩存使用率。

同樣，閑置線程在執行多線程任務時也相當于廢棄資源。配置設定給各線程的工作量不一樣會導緻名為“負載不均衡”的狀況發生。這種不均衡程度越大，保持閑置狀态的線程就會越多，完成計算任務所需的時間便會越長。配置設定給可用線程的各部分計算任務越均衡，完成整個計算任務的時間将會越短。

例如，一項任務由十二項獨立任務組成，完成這些獨立任務所需要的時間分别是：{10, 6, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1}。假設現有四條線程共同承擔這項計算任務，最簡單的任務配置設定法是按照上述時間排列順序為每條線程配置設定三項任務，即線程 0 完成所有配置設定的任務需要 20 個時間單元（10+6+4），線程 1 需要 8 個時間單元（4+2+2），線程 2 需要 5 個時間單元（2+2+1），線程 3 則隻需要 3 個時間單元（1+1+1）。圖 1（a）展示了這一任務配置設定狀态，由此可見，完成全部十二項任務總共需要 20 個時間單元（完成整個任務所需時間應以最後完成的子任務用時為準）。

圖 1：四條線程之間的任務配置設定示例。

您也可以采用一種更合理的任務配置設定法，即線程 0 完成一項任務所需時間是 {10}，線程 1 完成四項任務所需時間是 {4, 2, 1, 1}，線程 2 完成三項任務所需時間是 {6, 1, 1}，而線程 3 完成四項任務所需時間是 {4, 2, 2, 2}（如圖 1（b）所示）。這樣安排時間的優勢是完成整個任務隻需 10 個時間單元，四條線程中隻有兩條線程分别閑置了 2 個時間單元。

建議

如果完成所有任務所需時間長度相同，則在可用線程之間實施靜态任務配置設定（即将整個任務劃分為相同數量的子任務組并将每個子任務組配置設定給每條線程）是一種簡單且合理的解決方案。但實際上就算事先已知道所有任務的執行時間長度，要找到一個線上程間實施最佳任務配置設定的方法仍然十分困難。如果各項子任務的執行時間長度不同，則可能需要采用一種更加動态的任務配置設定法來配置設定線程任務。

在預設情況下，OpenMP* 向線程排程疊代的政策是靜态排程（如果不是靜态排程則會另外注明）。當疊代之間的工作負載不同以及負載模式不可預知時，采用動态排程疊代的方法可以更好地平衡負載。動态排程和指數排程這兩種靜态排程替代方案都會通過 schedule 子句指定。在動态排程下，疊代資料塊配置設定給線程；一旦配置設定完成，線程會申請獲得一個新的疊代資料塊。Schedule 子句的可選資料塊參數會指明用于動态排程的疊代資料塊固定尺寸。

- collapse source view plain copy to clipboard print ?

1. #pragma omp parallel for schedule(dynamic, 5) 
2.   for (i = 0; i < n; i++) 
3.   { 
4.     unknown_amount_of_work(i); 
5.   } 

指數排程最初會向線程配置設定大型疊代資料塊；配置設定給所需線程的疊代數量會随着未配置設定疊代集的減少而減少。由于配置設定模式不同，指數排程的開銷往往少于動态排程。Schedule 子句的可選資料塊參數會指明在指數排程下一個資料塊中所配置設定的疊代最低數量。

- collapse source view plain copy to clipboard print ?

1. #pragma omp parallel for schedule(guided, 8) 
2.   for (i = 0; i < n; i++) 
3.   { 
4.     uneven_amount_of_work(i); 
5.   } 

其中一個特例是疊代之間的工作負載單調遞增或遞減。例如，下三角形矩陣中每行元素數量會以正規表達式的形式增加。在此類情況下，通過靜态排程設定一個相對較低的資料塊尺寸（建立大量資料塊/任務）可能有助于實作良好的負載平衡，同時還不會産生采用動态排程或指數排程所導緻的開銷。

- collapse source view plain copy to clipboard print ?

1. #pragma omp parallel for schedule(static, 4) 
2.   for (i = 0; i < n; i++) 
3.   { 
4.     process_lower_triangular_row(i); 
5.   } 

如果排程政策不明顯，采用運作時排程可以随意改變資料塊尺寸和排程類型，而無需對程式進行重新編譯。

在使用英特爾® 線程構模組化塊（英特爾® TBB）的 parallel_for 算法時，排程程式會将疊代空間劃分為可配置設定給線程的小型任務。一旦某些疊代的計算用時比其它疊代長，英特爾® TBB 排程程式能夠從線程中動态“盜取”任務，以便更好地實作線程間的工作負載平衡。

顯式線程模式（如 Windows* 線程、Pthreads* 和 Java* 線程）無法自動為線程排程一系列獨立任務。程式設計人員必須根據需要将這種能力編入應用程式中。靜态排程任務是一種十分簡單、直接的排程方法，而動态排程任務則可通過兩種相關的方法輕松予以實施：生産者/消費者（Producer/Consumer）模式和老闆/勞工（Boss/Worker）模式。在前一個模式下，一條線程（生産者）會将任務置入共享隊列結構中，而消費者線程會根據需要清除要處理的任務。生産者/消費者模式通常适用于在任務配置設定給消費者線程之前需要進行預處理之時（但也并非一定得采用這種模式）。

在老闆/勞工模式下，勞工線程與老闆線程會在需要直接配置設定的工作任務增多時會合。在劃分任務十分簡單的情況下（如将各類指數配置設定給數組進行處理），可以采用具備适宜同步化程度的全局計數器來取代單獨的老闆線程，即勞工線程通路目前數值并針對下一條需要承擔更多工作任務的線程調整（可能增加）計數器。

無論采用哪種任務排程模式，您都必須使用适量的線程和正确的線程組合，以確定這些肩負工作任務的線程執行所需計算任務，而不是進入閑置狀态。例如，如果消費者線程有時處于閑置狀态，則您需要減少消費者線程數量或可能需要再配備一條生産者線程。采用何種解決方案主要取決于算法以及需要配置設定的任務數量與執行時間長度。

使用指南

所有動态任務排程方法都将因配置設定任務而産生一定的開銷。将獨立的小型任務整合成為一項可配置設定的工作任務有助于減少上述開銷；相應地，如果采用 OpenMP schedule 子句，您需要在任務内設定代表最少疊代次數的非預設資料塊尺寸。将一項任務劃分成多項計算任務的最佳方法取決于需要完成的計算量、線程的數量以及執行計算任務時可以使用的其它資源。