# Pthreads，第 3 部分：并行問題（獎金） > 原文：<https://github.com/angrave/SystemProgramming/wiki/Pthreads%2C-Part-3%3A-Parallel-Problems-%28Bonus%29> ## 概觀 下一節討論 pthreads 碰撞時會發生什么，但如果我們讓每個線程完全不同，沒有重疊怎么辦？ 我們發現最大加速并行問題？ ## 令人尷尬的并行問題 在過去幾年中，對并行算法的研究已經爆發。一個令人尷尬的并行問題是任何需要很少努力轉向并行的問題。他們中的很多人都有一些同步概念，但并非總是如此。你已經知道一個可并行化的算法，Merge Sort！ ```c void merge_sort(int *arr, size_t len){ if(len > 1){ //Mergesort the left half //Mergesort the right half //Merge the two halves } ``` 通過對線程的新理解，您需要做的就是為左半部分創建一個線程，為右半部分創建一個線程。鑒于您的 CPU 有多個真實核心，您將看到符合 [Amdahl 定律](https://en.wikipedia.org/wiki/Amdahl's_law)的加速。時間復雜度分析也很有趣。并行算法運行在 O（log ^ 3（n））運行時間（因為我們假設我們有很多核心的花式分析。 但在實踐中，我們通常會做兩處更改。一，一旦數組變得足夠小，我們就會拋棄并行 mergesort 算法并執行快速排序或其他算法，這些算法可以在小數組上快速運行（某些東西可以緩存一致性）。我們知道的另一件事是 CPU 沒有無限核心。為了解決這個問題，我們通常會保留一個工作人員池。 ## 工人池 我們知道 CPU 的內核數量有限。很多時候，我們啟動了許多線程，并在空閑時為他們提供任務。 ## 另一個問題，平行地圖 假設我們想要將一個函數應用于整個數組，一次一個元素。 ```c int *map(int (*func)(int), int *arr, size_t len){ int *ret = malloc(len*sizeof(*arr)); for(size_t i = 0; i < len; ++i) ret[i] = func(arr[i]); return ret; } ``` 由于沒有任何元素依賴于任何其他元素，您將如何進行并行化？您認為在線程之間拆分工作的最佳方法是什么？ ## 調度 分離工作有幾種方法。 * 靜態調度：將問題分解為固定大小的塊（預定義），并讓每個線程都在每個塊上運行。當每個子問題花費大致相同的時間時，這很有效，因為沒有額外的開銷。您需要做的就是編寫一個循環并將 map 函數賦予每個子數組。 * 動態調度：當一個新問題變得可用時，有一個線程為它服務。當您不知道調度需要多長時間時，這非常有用 * 引導式調度：這是上述各種利益和權衡的混合。您可以從靜態計劃開始，并根據需要緩慢移動到動態 * 運行時調度：你完全不知道問題需要多長時間。不要自己決定，讓程序決定做什么！ [來源](https://software.intel.com/en-us/articles/openmp-loop-scheduling)，但無需記憶。 ## 幾個缺點 由于緩存一致性和調度額外線程之類的東西，你不會馬上看到加速。 ## 其他問題 來自[維基百科](https://en.wikipedia.org/wiki/Embarrassingly_parallel) * 一次將 Web 服務器上的靜態文件提供給多個用戶。 * Mandelbrot 集，Perlin 噪聲和類似圖像，其中每個點都是獨立計算的。 * 渲染計算機圖形。在計算機動畫中，每個幀可以獨立渲染（參見并行渲染）。 * 密碼學中的暴力搜索。[8]值得注意的現實世界的例子包括 distributed.net 和加密貨幣中使用的工作證明系統。 * BLAST 在生物信息學中搜索多個查詢（但不是針對單個大型查詢）[9] * 大規模面部識別系統，其將數千個任意獲取的面部（例如，經由閉路電視的安全或監視視頻）與類似大量的先前存儲的面部（例如，盜賊畫廊或類似的觀察列表）進行比較。[10] * 計算機模擬比較許多獨立場景，例如氣候模型。 * 進化計算元啟發式算法，如遺傳算法。 * 數值天氣預報的集合計算。 * 粒子物理中的事件模擬與重建。 * 行進方塊算法 * 篩分步驟的二次篩和數字篩。 * 隨機森林機器學習技術的樹木生長步驟。 * 離散傅里葉變換，其中每個諧波是獨立計算的。