簡介《并行算法的設(shè)計(jì)與分析》課件圍繞異步并行模型下的排序與選擇問題展開適合計(jì)算機(jī)專業(yè)學(xué)生、研究者以及需要掌握并行計(jì)算基礎(chǔ)知識的開發(fā)者學(xué)習(xí)。課件對應(yīng)經(jīng)典教材“Parallel Algorithms”第5章重點(diǎn)講解MIMD-CREW模型上的異步枚舉排序算法、MIMD-TC模型上的異步快速排序算法和分布式k-選擇算法涵蓋異步算法基本框架、排序二叉樹的構(gòu)造思路、算法偽代碼、示例演示與時(shí)間分析并對進(jìn)程同步、數(shù)據(jù)依賴、通信開銷等關(guān)鍵設(shè)計(jì)點(diǎn)做了說明。其中異步枚舉排序通過為每個(gè)元素創(chuàng)建獨(dú)立進(jìn)程實(shí)現(xiàn)無通信并行異步快速排序則將串行快排遷移到共享內(nèi)存并行環(huán)境分布式k-選擇算法面向數(shù)據(jù)分散場景查找第k小元素。壓縮包為單個(gè)pptx演示文稿約236KB按章節(jié)組織便于課堂演示或自學(xué)復(fù)習(xí)。目前已有45人學(xué)習(xí)瀏覽對希望理解異步并行算法設(shè)計(jì)思路與經(jīng)典模型應(yīng)用的讀者具有一定參考價(jià)值。1. 并行算法的設(shè)計(jì)與分析這份.pptx講稿背后的工程鏈路“并行算法的設(shè)計(jì)與分析”這六個(gè)字搭配 .pptx 后綴乍看是一門課的題目實(shí)際上對應(yīng)著一條貫穿多核 CPU、GPU 和集群開發(fā)的工程鏈路。碰到并行優(yōu)化任務(wù)沒受過訓(xùn)練的做法是直接開線程、開進(jìn)程跑慢了兩眼一黑而按這套方法論走的人會先從任務(wù)分解和粒度選擇入手再決定數(shù)據(jù)怎么映射最后用加速比、效率和擴(kuò)展性三個(gè)指標(biāo)閉環(huán)。這套鏈路能解決三類典型訴求讓單機(jī)多核計(jì)算真正提速、把算法改造成能在集群上運(yùn)行的結(jié)構(gòu)、把串行程序整理成可流式處理的流水線。適合兩類讀者正寫著并行程序卻說不清瓶頸在哪的從業(yè)者以及準(zhǔn)備把并行計(jì)算做成內(nèi)部培訓(xùn)課、需要大量可復(fù)現(xiàn)案例支撐的講師。接下來我按能直接照做的順序拆開講先講任務(wù)怎么拆再講性能怎么算然后給三個(gè)實(shí)用設(shè)計(jì)模板最后排雷和立驗(yàn)收習(xí)慣。2. 并行算法設(shè)計(jì)的第一公里任務(wù)分解的三種姿勢與粒度邊界很多人寫并行程序失敗不是因?yàn)椴粫貌⑿袔於侨蝿?wù)分解這一步就沒做對。這一章把“怎么拆任務(wù)”講透后面所有性能分析才有意義。2.1 粒度先于并行度拆太細(xì)與拆太粗的兩個(gè)極端粒度指的是一次派給單個(gè)線程或進(jìn)程的獨(dú)立工作量。常犯的錯(cuò)誤是只關(guān)注“開了多少個(gè)線程”卻忽略每個(gè)線程實(shí)際干了多少活。一個(gè)典型反例處理一張 4096 乘 4096 的灰度圖有人按像素生成一千多萬個(gè)任務(wù)每個(gè)任務(wù)只算幾個(gè)像素結(jié)果任務(wù)創(chuàng)建和調(diào)度的開銷比計(jì)算本身還貴整體比單線程慢一大截。這就是粒度拆得太細(xì)。拆得太粗則是另一個(gè)極端。把整個(gè)數(shù)據(jù)集切成四塊四個(gè)核各拿一塊聽起來很合理但一旦各塊計(jì)算量差異明顯比如圖像分割里有的區(qū)域邊緣復(fù)雜、有的區(qū)域幾乎是空白快的核十幾秒干完就開始空轉(zhuǎn)慢的核拖到最后一刻才交活。整體耗時(shí)等于最慢那塊的時(shí)間加速比很難看。我一般會用一條經(jīng)驗(yàn)線做初判單個(gè)任務(wù)的最小執(zhí)行時(shí)間至少應(yīng)該是任務(wù)派發(fā)成本的 50 到 100 倍。任務(wù)派發(fā)成本包括創(chuàng)建、入隊(duì)、同步這些開銷在主流線程庫下通常幾微秒。換句話說如果你預(yù)估每次任務(wù)的計(jì)算量只有幾微秒先把任務(wù)合并讓單次計(jì)算量提到幾百微秒甚至毫秒級。粗估時(shí)可以先按“核數(shù)乘以 4 到 8 倍任務(wù)數(shù)”來切跑完看負(fù)載均衡情況再調(diào)。負(fù)載看什么看每個(gè)線程的實(shí)際耗時(shí)分布而不是看 CPU 占用率。2.2 域分解、功能分解與流水線三種拆法的適用邊界任務(wù)分解大體有三條路域分解、功能分解、流水線。域分解是最常用的一種把數(shù)據(jù)切成塊每個(gè)處理單元負(fù)責(zé)一塊塊與塊之間只在邊界處交換必要的數(shù)據(jù)。網(wǎng)格迭代、圖像濾波、矩陣乘法都適合這種拆法因?yàn)閿?shù)據(jù)局部性好通信模式固定分析起來也容易。功能分解則是按“處理階段”來切而不是按數(shù)據(jù)來切。典型場景是音視頻處理里的采集、變換、編碼、寫入四個(gè)階段每個(gè)階段由不同處理單元負(fù)責(zé)數(shù)據(jù)從上一個(gè)階段流向下一個(gè)階段。它的優(yōu)點(diǎn)是各階段可以獨(dú)立開發(fā)和優(yōu)化缺點(diǎn)是階段之間有依賴整體吞吐受最慢階段限制。流水線可以看作是功能分解的時(shí)序化形態(tài)把各階段重疊起來執(zhí)行就像工廠生產(chǎn)線。流水線的好處是天然支持流式數(shù)據(jù)壞處是每條流水線的吞吐上限由最慢環(huán)節(jié)決定而且階段數(shù)越多調(diào)度和緩沖的復(fù)雜度越高。怎么選先問數(shù)據(jù)能不能切。能切優(yōu)先域分解這是最簡單、最容易分析性能的路徑。數(shù)據(jù)切不了再看處理過程能不能按階段分開。階段之間有明確的單向數(shù)據(jù)流就考慮功能分解或流水線。下表是三者的對照分解策略切分對象通信特點(diǎn)典型場景域分解數(shù)據(jù)塊塊邊界少量鄰居通信網(wǎng)格迭代、圖像處理、矩陣運(yùn)算功能分解處理階段階段間單向全量傳遞音視頻處理、ETL 流程流水線階段 時(shí)序順流傳遞可重疊執(zhí)行流式計(jì)算、并行編譯2.3 數(shù)據(jù)映射共享內(nèi)存和分布式內(nèi)存的分配策略差異任務(wù)拆完之后數(shù)據(jù)放在哪、由誰訪問這一步?jīng)Q定通信開銷。共享內(nèi)存模型下所有線程看到同一份地址空間數(shù)據(jù)映射的核心不是“能不能訪問”而是“訪存是否局部”。常見問題是 NUMA 架構(gòu)下線程訪問了遠(yuǎn)端內(nèi)存延遲比本地內(nèi)存高一個(gè)數(shù)量級。常見做法是讓每個(gè)線程優(yōu)先處理自己內(nèi)存附近的數(shù)據(jù)也就是綁核之后再做數(shù)據(jù)分區(qū)而不是讓線程隨機(jī)訪問整個(gè)大數(shù)組。分布式內(nèi)存模型下數(shù)據(jù)映射的核心變成“數(shù)據(jù)在哪一側(cè)就要付出多少通信代價(jià)”。映射策略主要三種復(fù)制、分區(qū)、按需拉取。復(fù)制適合只讀數(shù)據(jù)每個(gè)節(jié)點(diǎn)一份完全消除讀通信分區(qū)適合可寫數(shù)據(jù)每份數(shù)據(jù)只有一個(gè)歸屬節(jié)點(diǎn)按需拉取適合訪問模式稀疏的場景但要控制拉取頻率否則容易把網(wǎng)絡(luò)打滿。我在動手前通常會做四個(gè)小判斷這份數(shù)據(jù)誰在寫、誰在讀、寫讀比例大概多少、跨節(jié)點(diǎn)訪問頻率高不高。寫多讀少的數(shù)據(jù)必須分區(qū)讀多寫少的數(shù)據(jù)優(yōu)先復(fù)制讀寫都頻繁的數(shù)據(jù)就要重新考慮任務(wù)劃分是否合理。一句話建立心智模型共享內(nèi)存下地址決定熱區(qū)分布式下通信決定邊界。數(shù)據(jù)映射方案在寫代碼之前定下來比寫完再改省力得多。3. 性能分析不能只算加速比把指標(biāo)吃透才能定位瓶頸設(shè)計(jì)做完下一步是回答“它到底快了多少、值不值得”。只看單次耗時(shí)是遠(yuǎn)遠(yuǎn)不夠的加速比、效率、擴(kuò)展性三個(gè)指標(biāo)配合起來才能定位瓶頸在哪一層。3.1 加速比與效率固定問題規(guī)模才算得準(zhǔn)加速比的定義是 S(p)T(1)/T(p)其中 T(1) 是單處理單元的最優(yōu)串行耗時(shí)T(p) 是 p 個(gè)處理單元并行后的耗時(shí)。效率是 ES(p)/p它衡量的是每個(gè)處理單元的利用率。四核跑出三倍加速比效率是 75%十六核跑出十二倍效率是 75%不對是 75% 的加速比算一下十二除以十六等于百分之七十五效率仍然不錯(cuò)但十六核只跑出十二倍說明每增加一個(gè)核帶來的收益在遞減。這里有個(gè)非常關(guān)鍵的細(xì)節(jié)T(1) 必須用可比較的最優(yōu)串行實(shí)現(xiàn)而不是隨便寫一版循環(huán)就當(dāng)基線。有些人為了顯得并行效果好故意用一個(gè)沒開編譯優(yōu)化的串行版本當(dāng)對照這屬于自欺欺人。我一般會先把串行版本用編譯器高優(yōu)化等級跑一遍確認(rèn)沒有明顯可優(yōu)化的垃圾代碼再把它作為 T(1)。實(shí)際測量時(shí)還會遇到一個(gè)常見現(xiàn)象加速比并不是隨著核數(shù)單調(diào)上升而是先升后降。這是因?yàn)楹藬?shù)增加后通信和同步開銷的增長超過了計(jì)算收益。以固定問題規(guī)模為例常見趨勢是2 核接近 1.9 倍4 核約 3.7 倍8 核約 6.3 倍16 核可能只有 7.5 倍左右。后面的效率跌得很快說明瓶頸已經(jīng)從“算不過來”變成“溝通不過來”。3.2 Amdahl 與 Gustafson兩套公式各管一個(gè)場景性能分析繞不開 Amdahl 定律和 Gustafson 定律但很多人把兩套公式用錯(cuò)了場景。Amdahl 定律說的是如果程序里有 s 比例的部分無法并行那么無論加多少核加速比上限是 1/s。公式是 S1/(s(1-s)/p)。舉個(gè)例子串行部分占 5%16 核理論的加速比上限約 9.1 倍64 核也到不了 14 倍。這個(gè)公式的適用前提是問題規(guī)模固定不變所以我們想要的是“同樣的問題跑得更快”。Gustafson 定律則適用于另一個(gè)場景時(shí)間預(yù)算固定問題規(guī)?？梢噪S核數(shù)擴(kuò)大。它的表達(dá)式是 S≈sp(1-s)在這個(gè)假設(shè)下串行占比 5% 時(shí)16 核可以得到約 15.25 倍的加速比看起來比 Amdahl 樂觀得多。這不是矛盾而是前提不同一個(gè)是固定工作量一個(gè)是固定時(shí)間、允許“加核的同時(shí)加規(guī)模”。判斷你的場景該用哪套就問一個(gè)問題業(yè)務(wù)允許結(jié)果規(guī)模變化嗎如果算法輸出必須是指定尺寸、指定精度的結(jié)果按 Amdahl 定律做預(yù)算先集中精力壓縮串行段如果業(yè)務(wù)是“單位時(shí)間內(nèi)產(chǎn)出越多越好”比如數(shù)值模擬里網(wǎng)格分辨率可以提高、搜索場景里候選集可以擴(kuò)大那就參照 Gustafson 定律來設(shè)計(jì)擴(kuò)展路徑。定律適用前提核心變量加速比上限Amdahl問題規(guī)模固定串行占比 s極限 1/sGustafson時(shí)間固定、規(guī)模隨核數(shù)擴(kuò)展并行占比接近線性增長3.3 強(qiáng)擴(kuò)展與弱擴(kuò)展用四條曲線判斷性能上限擴(kuò)展性分析可以看作是把上述兩套定律落到實(shí)測里。強(qiáng)擴(kuò)展測試固定問題規(guī)模只增加處理單元數(shù)觀察加速比是否接近線性弱擴(kuò)展測試固定每個(gè)處理單元的工作量總規(guī)模隨處理單元數(shù)增大觀察效率是否維持穩(wěn)定。這兩條曲線是判斷算法設(shè)計(jì)是否健康的核心依據(jù)。具體操作分三步。第一步選定一個(gè)中等規(guī)模數(shù)據(jù)集能把單線程跑完但時(shí)間不要太短比如 20 到 60 秒太短了測量噪聲影響太大。第二步分別用 1、2、4、8、16 個(gè)處理單元跑同一份數(shù)據(jù)每個(gè)配置至少跑 5 次取中位數(shù)避免偶爾的系統(tǒng)抖動污染結(jié)果。第三步換弱擴(kuò)展1 個(gè)核處理一定量數(shù)據(jù)2 個(gè)核就處理兩倍4 個(gè)核處理四倍同樣記錄耗時(shí)和效率。for p in 1 2 4 8 16; do ./bench --threads $p --size 4096 --repeats 5 done上面的腳本只是一個(gè)最小示例。size 固定時(shí)得到的是強(qiáng)擴(kuò)展數(shù)據(jù)如果想讓 size 隨線程數(shù)線性增長就把 size 改成 p 的倍數(shù)比如--size $((p * 1024))這就是弱擴(kuò)展數(shù)據(jù)。repeats 取中位數(shù)而不是平均值是因?yàn)椴⑿谐绦驅(qū)ο到y(tǒng)噪聲很敏感偶爾一次調(diào)度抖動會把平均值拉高中位數(shù)更能代表典型表現(xiàn)。讀曲線也有經(jīng)驗(yàn)可循。強(qiáng)擴(kuò)展的加速比曲線從接近線性開始逐漸掉頭掉頭最明顯的位置往往就是通信或同步開銷開始壓過計(jì)算收益的臨界點(diǎn)這個(gè)臨界點(diǎn)對應(yīng)的核數(shù)就是你當(dāng)前實(shí)現(xiàn)的實(shí)際適用范圍。弱擴(kuò)展的效率曲線如果保持平穩(wěn)說明數(shù)據(jù)劃分方式經(jīng)得住規(guī)模增長如果效率隨核數(shù)明顯下滑優(yōu)先懷疑跨節(jié)點(diǎn)通信或者共享數(shù)據(jù)的爭用。4. 三個(gè)高頻可復(fù)現(xiàn)的設(shè)計(jì)模板分治、規(guī)約、前綴和設(shè)計(jì)方法不能只停留在概念上需要落到具體模板。這一章給出三個(gè)高頻使用的并行模式前兩個(gè)在工程里幾乎天天遇到第三個(gè)是檢驗(yàn)“設(shè)計(jì)與分析”基本功的最佳案例。4.1 分治模板遞歸劃分的可用與濫用邊界分治模板適合“子問題相互獨(dú)立”的任務(wù)數(shù)組求和、快速排序、分塊矩陣乘都是典型場景。核心思路是把大問題遞歸拆成小問題各處理單元并行解決小問題再合并結(jié)果。它有一個(gè)很明確的適用邊界子問題不能有強(qiáng)依賴。如果后一階段必須等前一階段全部完成才能開始就不要硬套分治改走規(guī)約或流水線。下面是一個(gè)簡化的分治求和偽碼展示了設(shè)計(jì)思路def parallel_sum(data, cutoff): if len(data) cutoff: return sum(data) # 小段走串行減少調(diào)度開銷 mid len(data) // 2 left task_pool.submit(parallel_sum, data[:mid], cutoff) right task_pool.submit(parallel_sum, data[mid:], cutoff) return left.get() right.get()cutoff 是串行截止值默認(rèn)可以取 512 到 4096 個(gè)元素。取值太小任務(wù)數(shù)量會膨脹調(diào)度與同步開銷覆蓋掉并行收益取值太大并行度不足多核閑著。一般先從 4096 開始逐步減半對比耗時(shí)找到性能拐點(diǎn)。任務(wù)總數(shù)控制在核數(shù)的 4 到 8 倍通常比較合適任務(wù)太多調(diào)度器反而成了瓶頸。另一個(gè)要注意的點(diǎn)是如果各子任務(wù)的計(jì)算量差異很大靜態(tài)劃分會嚴(yán)重負(fù)載不均這時(shí)要改用動態(tài)調(diào)度比如工作竊取策略。實(shí)現(xiàn)上可以用線程池配合帶有竊取能力的任務(wù)隊(duì)列而不是自己寫遞歸線程。4.2 樹形規(guī)約把串行瓶頸換成 log 深度規(guī)約問題是指把一組數(shù)據(jù)通過某個(gè)滿足結(jié)合律的運(yùn)算合并成一個(gè)結(jié)果比如求和、求最大值、內(nèi)積。串行實(shí)現(xiàn)很直接循環(huán)累加即可但并行化之后你會發(fā)現(xiàn)最后一輪的合并結(jié)果只有一個(gè)處理單元能拿到其他單元都在空等。樹形規(guī)約就是為了解決這個(gè)“扇形收斂”的問題。以分布式內(nèi)存為例每個(gè)進(jìn)程先算本地部分和然后按步長成對合并每輪通信之后活躍進(jìn)程數(shù)減半。偽碼如下value local_partial_sum stride 1 while stride size: if rank % (2 * stride) 0: received recv(rank stride) value received elif rank % (2 * stride) stride: send(rank - stride, value) break # 發(fā)送完即退出本輪 stride * 2這里的 stride 是合并步長每輪翻倍所以通信輪次是 log2(p) 而不是 p。參數(shù)要注意兩點(diǎn)前半段進(jìn)程在接收后半段進(jìn)程在發(fā)送后直接退出活躍進(jìn)程數(shù)逐輪減半這本身是一種負(fù)載不均衡只是它換來的是通信次數(shù)的大幅減少如果做的是全局規(guī)約也就是所有進(jìn)程都要拿到最終結(jié)果那么還需要一輪廣播或者改用蝶形算法。實(shí)際工程里能用現(xiàn)成庫的 Allreduce 就用現(xiàn)成的大多數(shù)成熟實(shí)現(xiàn)會按消息大小自動選擇樹形還是蝶形比自己手寫的版本更穩(wěn)。樹形規(guī)約的意義在于讓你理解為什么通信次數(shù)可以從線性降到對數(shù)級。4.3 并行前綴和檢驗(yàn)設(shè)計(jì)與分析是否上手的試金石前綴和也叫掃描要求對輸入數(shù)組的每個(gè)位置輸出它之前所有元素的和?？雌饋硖烊淮幸?yàn)榈?i 個(gè)輸出依賴前 i-1 個(gè)輸出但并行算法可以用兩階段思路繞過這個(gè)依賴鏈。常見做法是塊內(nèi)掃描加全局偏移修正# 階段 1每個(gè)處理單元對本地塊做排他前綴和 local_prefix exclusive_scan(local_chunk) # 階段 2計(jì)算每個(gè)塊的總和對塊和再做一次排他前綴和 block_sum sum(local_chunk) block_offset exclusive_scan(all_block_sum) # 階段 3本地前綴和加上全局偏移得到正確答案 result local_prefix block_offset這個(gè)過程能跑通依賴的是前綴和運(yùn)算的結(jié)合律。第一階段是純并行每塊獨(dú)立計(jì)算第二階段把塊和匯總數(shù)據(jù)量已經(jīng)縮小到塊數(shù)級別第三階段再次純并行把偏移量廣播回各塊并相加。總時(shí)間大約是 O(n/p log p)n 是數(shù)據(jù)總量p 是處理單元數(shù)。前半部分是本地計(jì)算開銷后半部分是全局通信開銷。為什么說這是試金石因?yàn)樗瑫r(shí)訓(xùn)練了“設(shè)計(jì)”和“分析”兩件事設(shè)計(jì)體現(xiàn)在三個(gè)階段的劃分和映射上分析體現(xiàn)在你能否準(zhǔn)確地說出時(shí)間都花在哪一段。如果你能給同事講明白這個(gè)案例說明你對并行算法的任務(wù)劃分、通信模式和復(fù)雜度分析都有感覺了。從做講稿的角度看這也是最容易讓聽眾建立信心的案例因?yàn)樗鼜摹安豢赡懿⑿小钡健叭问浇鉀Q”的轉(zhuǎn)折足夠清晰。5. 并行算法踩坑排查五個(gè)高頻問題的現(xiàn)象、原因與對策并行程序跑不出預(yù)期性能一般不是算法思想錯(cuò)了而是落在幾個(gè)固定坑里。這一章我把高頻問題按“現(xiàn)象到對策”整理出來可以直接當(dāng)排查手冊用。5.1 負(fù)載不均衡核全在忙總時(shí)間卻紋絲不動現(xiàn)象任務(wù)管理器里所有核心的占用率都不低甚至接近 100%但加速比就是上不去有時(shí) 8 核跑出來只有 1.5 倍。原因任務(wù)被靜態(tài)等量劃分但各任務(wù)的實(shí)際計(jì)算量差異很大整體耗時(shí)被最慢的那個(gè)任務(wù)拖死。比如網(wǎng)格計(jì)算里某塊區(qū)域的迭代次數(shù)遠(yuǎn)高于其他區(qū)域或者圖像處理中不同分塊的邊緣復(fù)雜程度差別很大。解決把靜態(tài)劃分改成動態(tài)調(diào)度。共享內(nèi)存場景下用帶任務(wù)竊取的線程池誰先干完誰去拿新任務(wù)分布式場景下可以把任務(wù)切得更小讓工作節(jié)點(diǎn)按需領(lǐng)取而不是一次性把大塊分完。另外日志里為每個(gè)任務(wù)記錄開始和結(jié)束時(shí)間做完一輪后看各任務(wù)耗時(shí)的分布如果最大和最小差了 3 倍以上負(fù)載不均衡基本可以坐實(shí)。5.2 緩存?zhèn)喂蚕斫Y(jié)果正確速度卻比單線程還慢現(xiàn)象多線程版本的輸出完全正確但耗時(shí)比單線程還長而且性能工具顯示緩存一致性相關(guān)的等待很高。原因多個(gè)線程頻繁寫入不同的變量但這些變量恰好落在同一條緩存行上比如 64 字節(jié)的緩存行里有兩個(gè)相鄰數(shù)組元素分別被兩個(gè)線程更新。每次寫入都會讓整條緩存行在其他核心失效于是兩個(gè)線程互相拖累。解決把不相干的數(shù)據(jù)用填充的方式隔開讓它們落在不同的緩存行上。也可以讓每個(gè)線程先寫自己的私有緩沖區(qū)全部算完之后再一次性合并到共享數(shù)組。這個(gè)坑最容易出現(xiàn)在“按索引并行處理數(shù)組”的場景里排查時(shí)優(yōu)先檢查同一數(shù)組相鄰下標(biāo)是否被不同線程并發(fā)更新。5.3 鎖爭用與死鎖共享數(shù)據(jù)結(jié)構(gòu)讓你“部分快、整體崩”現(xiàn)象加鎖之后并行效率斷崖式下跌系統(tǒng)態(tài) CPU 占用明顯升高更嚴(yán)重的情況是程序掛起幾秒后無響應(yīng)。原因前者通常是全局鎖把關(guān)鍵路徑串行化了比如所有線程都要更新同一個(gè)計(jì)數(shù)器后者是死鎖兩個(gè)線程互相持有對方需要的鎖誰都不肯釋放。解決先分析共享數(shù)據(jù)能否分區(qū)。計(jì)數(shù)器可以改成每個(gè)線程一個(gè)本地計(jì)數(shù)最后匯總鏈表可以用細(xì)粒度鎖或者無鎖隊(duì)列。死鎖的處理我習(xí)慣按四個(gè)條件倒查互斥、持有并等待、不可搶占、循環(huán)等待。代碼里只要破壞其中任意一個(gè)條件就不會死鎖最常用的辦法是規(guī)定全局一致的加鎖順序所有線程都按相同順序獲取多個(gè)鎖。排查死鎖時(shí)先看線程棧里每個(gè)線程在等哪把鎖再畫依賴環(huán)環(huán)的起點(diǎn)就是問題所在。5.4 通信放大頻繁小消息比數(shù)據(jù)量大更致命現(xiàn)象計(jì)算部分很快但整個(gè)程序運(yùn)行時(shí)間依然很長統(tǒng)計(jì)下來通信占了八成以上。原因消息次數(shù)太多每次消息體又很小。比如分布式場景里每個(gè)迭代向其他節(jié)點(diǎn)發(fā)送一個(gè)幾十字節(jié)的狀態(tài)信息一萬次迭代就是上萬次網(wǎng)絡(luò)往返延遲完全吃掉了計(jì)算收益。通信成本由兩個(gè)因素決定消息次數(shù)和消息體積而在多數(shù)網(wǎng)絡(luò)環(huán)境下次數(shù)比體積更致命。解決把頻繁的小消息合并成批量緩沖區(qū)攢夠一批再發(fā)送。另一種思路是改變計(jì)算結(jié)構(gòu)讓數(shù)據(jù)盡量在本地處理只在邊界處同步。判斷通信是否健康可以在日志里統(tǒng)計(jì)兩個(gè)數(shù)每秒消息次數(shù)和平均消息字節(jié)數(shù)。如果次數(shù)在十萬級而平均字節(jié)數(shù)只有幾十優(yōu)先做合并。5.5 超線性加速比是驚喜但先別高興現(xiàn)象16 核跑出了 18 倍的加速比理論上不可能但它確實(shí)發(fā)生了。原因并行版本把大數(shù)組拆成了小塊每個(gè)核處理的小塊恰好完全放進(jìn)了處理器緩存而串行版本的數(shù)據(jù)會不斷在各級緩存和內(nèi)存之間搬運(yùn)相當(dāng)于并行版本白賺了一筆“內(nèi)存帶寬紅利”。算法本身并沒有變得更快只是數(shù)據(jù)局部性變好了。解決先不要把這個(gè)結(jié)果寫進(jìn)匯報(bào)回去做兩個(gè)驗(yàn)證。第一確認(rèn)串行基線版本是不是同一份代碼在相同編譯優(yōu)化等級下的最優(yōu)實(shí)現(xiàn)第二把問題規(guī)模擴(kuò)大一倍再測如果超線性消失說明確實(shí)是緩存效果而非算法突破。這個(gè)坑看似是好事但它會誤導(dǎo)后續(xù)的優(yōu)化方向。下表匯總了這五個(gè)問題的快速對照高頻問題典型現(xiàn)象根本原因優(yōu)先檢查手段負(fù)載不均衡核占用高但加速比低任務(wù)計(jì)算量差異大統(tǒng)計(jì)各任務(wù)耗時(shí)分布緩存?zhèn)喂蚕碚_但慢單線程反而快多線程爭用同一條緩存行檢查共享數(shù)組相鄰下標(biāo)訪問鎖爭用與死鎖加鎖后效率驟降或掛起全局鎖串行化、鎖依賴環(huán)查看線程棧等待關(guān)系通信放大計(jì)算快但總耗時(shí)長消息次數(shù)過多、消息體過小統(tǒng)計(jì)消息次數(shù)與平均字節(jié)數(shù)超線性加速加速比大于核數(shù)緩存與內(nèi)存帶寬紅利擴(kuò)大規(guī)模復(fù)測確認(rèn)6. 把分析能力變成驗(yàn)收習(xí)慣三個(gè)每次迭代必做的自查到這一步設(shè)計(jì)與分析的框架已經(jīng)完整最后要解決的是“怎么保證自己每次改動都在進(jìn)步”的問題。我的做法是固化三個(gè)自查動作每個(gè)迭代都過一遍。第一個(gè)自查先有串行基線再談并行加速。固定數(shù)據(jù)集、固定機(jī)器、固定編譯優(yōu)化等級把最優(yōu)串行耗時(shí)記錄成基準(zhǔn)。并行實(shí)現(xiàn)沒跑過這個(gè)基準(zhǔn)就是失敗不要用“理論上應(yīng)該有加速”安慰自己。這里要小心的是編譯器開啟優(yōu)化后某些串行代碼會被自動向量化這時(shí)候并行版本的優(yōu)勢會被縮小但這才是真實(shí)的對比基線。第二個(gè)自查一次只改一個(gè)變量。線程數(shù)、任務(wù)分塊大小、調(diào)度方式、數(shù)據(jù)布局這些參數(shù)每次只動一個(gè)然后記錄三個(gè)數(shù)字總耗時(shí)、同步或通信耗時(shí)占比、各線程利用率。改完兩個(gè)參數(shù)再跑如果性能變了你無法判斷是哪個(gè)起了作用等于白跑。記錄下來的數(shù)據(jù)按日期和參數(shù)存好后續(xù)排查問題時(shí)能快速回溯。第三個(gè)自查強(qiáng)擴(kuò)展和弱擴(kuò)展兩條曲線都留檔。固定問題規(guī)模跑強(qiáng)擴(kuò)展固定每核負(fù)載跑弱擴(kuò)展每條曲線至少五個(gè)數(shù)據(jù)點(diǎn)。每次代碼改動后重跑一輪把曲線圖和原始耗時(shí)數(shù)據(jù)存成文件。不要靠記憶也不要只留最終數(shù)字否則換了測試機(jī)器、換了編譯器之后你會發(fā)現(xiàn)之前的所有判斷都沒法復(fù)現(xiàn)。我在給內(nèi)部一個(gè)圖像處理 Demo 做并行化時(shí)早期只拍了 4 核和 8 核兩組耗時(shí)加速比看著還行換到 32 核機(jī)器上直接翻車返工點(diǎn)恰好就在數(shù)據(jù)劃分策略上。那之后我才立了這三條自查。做并行優(yōu)化前也先算一筆投入產(chǎn)出賬優(yōu)化本身的開發(fā)時(shí)間加上反復(fù)調(diào)試的時(shí)間值不值得做。只要業(yè)務(wù)是計(jì)算密集、數(shù)據(jù)可分區(qū)、需要反復(fù)驗(yàn)證的場景這套前期投入很快就能回本。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取