[導(dǎo)讀]對于工程經(jīng)驗比較豐富的同學(xué)，并發(fā)應(yīng)該也并不是陌生的概念了，但是每個人所理解的并發(fā)問題，卻又往往并不統(tǒng)一，本文系統(tǒng)梳理了百度C 工程師在進行并發(fā)優(yōu)化時所作的工作。
導(dǎo)讀：對于工程經(jīng)驗比較豐富的同學(xué)，并發(fā)應(yīng)該也并不是陌生的概念了，但是每個人所理解的并發(fā)問題，卻又往往并不統(tǒng)一，本文系統(tǒng)梳理了百度C 工程師在進行并發(fā)優(yōu)化時所作的工作。
全文15706字，預(yù)計閱讀時間24分鐘。
一、背景
簡單回顧一下，一個程序的性能構(gòu)成要件大概有三個，即算法復(fù)雜度、IO開銷和并發(fā)能力。由于現(xiàn)代計算機體系結(jié)構(gòu)復(fù)雜化，造成很多時候，工程師的性能優(yōu)化會更集中在算法復(fù)雜度之外的另外兩個方向上，即IO和并發(fā)，在之前的《百度C 工程師的那些極限優(yōu)化（內(nèi)存篇）》中，我們介紹了百度C 工程師工程師為了優(yōu)化性能，從內(nèi)存IO角度出發(fā)所做的一些優(yōu)化案例。
這次我們就再來聊一聊另外一個性能優(yōu)化的方向，也就是所謂的并發(fā)優(yōu)化。和IO方向類似，對于工程經(jīng)驗比較豐富的同學(xué)，并發(fā)應(yīng)該也并不是陌生的概念了，但是每個人所理解的并發(fā)問題，卻又往往并不統(tǒng)一。所以下面我們先回到一個更根本的問題，重新梳理一下所謂的并發(fā)優(yōu)化。
這時第一個會冒出來的概念可能會是大規(guī)模，例如我們要設(shè)計大規(guī)模互聯(lián)網(wǎng)應(yīng)用，大規(guī)模機器學(xué)習(xí)系統(tǒng)?？墒俏覀冏屑毸伎家幌?，無論使用了那種程度的并發(fā)設(shè)計，這樣的規(guī)?；到y(tǒng)背后，都需要成百上千的實例來支撐。也就是，如果一個設(shè)計（尤其是無狀態(tài)計算服務(wù)設(shè)計）已經(jīng)可以支持某種小規(guī)模業(yè)務(wù)。那么當(dāng)規(guī)模擴大時，很可能手段并不是提升某個業(yè)務(wù)單元的處理能力，而是增加更多業(yè)務(wù)單元，并解決可能遇到的分布式問題。
其實真正讓并發(fā)編程變得有價值的背景，更多是業(yè)務(wù)單元本身的處理能力無法滿足需求，例如一次請求處理時間過久，業(yè)務(wù)精細化導(dǎo)致復(fù)雜度積累提升等等問題。那么又是什么導(dǎo)致了近些年來，業(yè)務(wù)單元處理能力問題不足的問題呈現(xiàn)更加突出的趨勢？可能下面這個統(tǒng)計會很說明問題：（https://www.karlrupp.net/2015/06/40-years-of-microprocessor-trend-data/）
上圖從一個長線角度，統(tǒng)計了CPU的核心指標(biāo)參數(shù)趨勢。從其中的晶體管數(shù)目趨勢可以看出，雖然可能逐漸艱難，但是摩爾定律依然尚能維持。然而近十多年，出于控制功耗等因素的考慮，CPU的主頻增長基本已經(jīng)停滯，持續(xù)增加的晶體管轉(zhuǎn)而用來構(gòu)建了更多的核心。
從CPU廠商角度來看，單片處理器所能提供的性能還是保持了持續(xù)提升的，但是單線程的性能增長已經(jīng)顯著放緩。從工程師角度來看，最大的變化是硬件紅利不再能透明地轉(zhuǎn)化成程序的性能提升了。隨時代進步，更精準(zhǔn)的算法，更復(fù)雜的計算需求，都在對的計算性能提出持續(xù)提升的要求。早些年，這些算力的增長需求大部分還可以通過處理器更新?lián)Q代來自然解決，可是隨著主頻增長停滯，如果無法利用多核心來加速，程序的處理性能就會隨主頻一同面臨增長停滯的問題。因此近些年來，是否能夠充分利用多核心計算，也越來越成為高性能程序的一個標(biāo)簽，也只有具備了充分的多核心利用能力，才能隨新型硬件演進，繼續(xù)表現(xiàn)出指數(shù)級的性能提升。而伴隨多核心多線程程序設(shè)計的普及，如何處理好程序的并發(fā)也逐漸成了工程師的一項必要技能。
上圖描述了并發(fā)加速的基本原理，首先是對原始算法的單一執(zhí)行塊拆分成多個能夠同時運行的子任務(wù)，并設(shè)計好子任務(wù)間的協(xié)同。之后利用底層的并行執(zhí)行部件能力，將多個子任務(wù)在時間上真正重疊起來，達到真正提升處理速度的目的。
需要注意的是還有一條從下而上的反向剪頭，主要表達了，為了正確高效地利用并行執(zhí)行部件，往往會反向指導(dǎo)上層的并發(fā)設(shè)計，例如正確地數(shù)據(jù)對齊，合理的臨界區(qū)實現(xiàn)等。雖然加速看似完全是由底層并行執(zhí)行部件的能力所帶來的，程序設(shè)計上只需要做到子任務(wù)拆分即可。但是現(xiàn)階段，執(zhí)行部件對上層還無法達到透明的程度，導(dǎo)致這條反向依賴對于最終的正確性和性能依然至關(guān)重要。既了解算法，又理解底層設(shè)計，并結(jié)合起來實現(xiàn)合理的并發(fā)改造，也就成為了工程師的一項重要技能。
上圖是Intel關(guān)于SIMD指令的一個示意圖，通過增加更大位寬的寄存器實現(xiàn)在一個寄存器中，“壓縮”保存多個較小位寬數(shù)據(jù)的能力。再通過增加特殊的運算指令，對寄存器中的每個小位寬的數(shù)據(jù)元素，批量完成某種相同的計算操作，例如圖示中最典型的對位相加運算。以這個對位相加操作為例，CPU只需要增大寄存器，內(nèi)存?zhèn)鬏敽陀嬎悴考粚?，針對這個特殊的應(yīng)用場景，就提升到了8倍的計算性能。相比將核心數(shù)通用地提升到8倍大小，這種方式付出的成本是非常少的，指令流水線系統(tǒng)，緩存系統(tǒng)都做到了復(fù)用。
從CPU發(fā)展的視角來看，為了能夠在單位周期內(nèi)處理更多數(shù)據(jù)，增加核心數(shù)的MIMD強化是最直觀的實現(xiàn)路徑。但是增加一套核心，就意味增加一套 完整的指令部件、流水線部件和緩存部件，而且實際應(yīng)用時，還要考慮額外的核心間數(shù)據(jù)分散和聚合的傳輸和同步開銷。一方面高昂的部件需求， 導(dǎo)致完整的核心擴展成本過高，另一方面，多核心間傳輸和同步的開銷針對小數(shù)據(jù)集場景額外消耗過大，還會進一步限制應(yīng)用范圍。為了最大限度利用好有限的晶體管，現(xiàn)代CPU在塑造更多核心的同時，也在另一個維度上擴展單核心的處理和計算位寬，從而實現(xiàn)提升理論計算性能（核心數(shù) * 數(shù)據(jù)寬度）的目的。
不過提起CPU上的SIMD指令支持，有一個繞不開的話題就是和GPU的對比。CPU上早期SIMD指令集（MMX）的誕生背景，和GPU的功能定位就十分類似，專注于加速圖像相關(guān)算法，近些年又隨著神經(jīng)網(wǎng)絡(luò)計算的興起，轉(zhuǎn)向通用矩陣類計算加速。但是由于GPU在設(shè)計基礎(chǔ)上就以面向密集可重復(fù)計算負載設(shè)計，指令部件、流水線部件和緩存部件等可以遠比CPU簡潔，也因此更容易在量級上進行擴展。這就導(dǎo)致，當(dāng)計算密度足夠大，數(shù)據(jù)的傳輸和同步開銷被足夠沖淡的情況下（這也是典型神經(jīng)網(wǎng)絡(luò)計算的的特性），CPU僅作為控制流進行指揮，而數(shù)據(jù)批量傳輸?shù)紾PU協(xié)同執(zhí)行反而 會更簡單高效。
由于Intel自身對SIMD指令集的宣傳，也集中圍繞神經(jīng)網(wǎng)絡(luò)類計算來展開，而在當(dāng)前工程實踐經(jīng)驗上，主流的密集計算又以GPU實現(xiàn)為主。這就導(dǎo)致了不少CPU上SIMD指令集無用論應(yīng)運而生，尤其是近兩年Intel在AVX512初代型號上的降頻事件，進一步強化了『CPU就應(yīng)該做好CPU該做的事情』這一論調(diào)。但是單單從這一的視角來認識CPU上的SIMD指令又未免有些片面，容易忽視掉一些真正有意義的CPU上SIMD應(yīng)用場景。
對于一段程序來講，如果將每讀取單位數(shù)據(jù)，對應(yīng)的純計算復(fù)雜度大小定義為計算密度，而將算法在不同數(shù)據(jù)單元上執(zhí)行的計算流的相同程度定義為模式重復(fù)度，那么可以以此將程序劃分為4個象限。在大密度可重復(fù)的計算負載（典型的重型神經(jīng)網(wǎng)絡(luò)計算），和顯著小密度和非重復(fù)計算負載（例如HTML樹狀解析）場景下，業(yè)界在CPU和GPU的選取上其實是有相對明確“最優(yōu)解”的。不過對于過渡地帶，計算的重復(fù)特征沒有那么強， 或者運算密度沒有那么大的場景下，雙方的弱點都會被進一步放大。即便是規(guī)整可重復(fù)的計算負載，隨著計算本身強度減小，傳輸和啟動成本逐漸顯著。另一方面，即便是不太規(guī)整可重復(fù)的計算負載，隨著計算負荷加大，核心數(shù)不足也會逐漸成為瓶頸。這時候，引入SIMD的CPU和引入SIMT 的GPU間如何選擇和使用，就形成了沒有那么明確，見仁見智的權(quán)衡空間。
即使排除了重型神經(jīng)網(wǎng)絡(luò)，從程序的一般特性而言，具有一定規(guī)模的重復(fù)特性也是一種普遍現(xiàn)象。例如從概念上講，程序中的循環(huán)段落，都或多或少意味著批量/重復(fù)的計算負載。盡管因為摻雜著分支控制，導(dǎo)致重復(fù)得沒有那么純粹，但這種一定規(guī)模的細粒度重復(fù)，正是CPU上SIMD發(fā)揮獨特價值的地方。例如最常見的SIMD優(yōu)化其實就是memcpy，現(xiàn)代的memcpy實現(xiàn)會探測CPU所能支持的SIMD指令位寬，并盡力使用來加速內(nèi)存?zhèn)鬏?。另一方面現(xiàn)代編譯器也會利用SIMD指令來是優(yōu)化對象拷貝，進行簡單循環(huán)向量化等方式來進行加速。類似這樣的一類優(yōu)化方法偏『自動透明』，也是默默支撐著主頻不變情況下，性能稍有上升的重要推手。
可惜這類簡單的自動優(yōu)化能做到的事情還相當(dāng)有限，為了能夠充分利用CPU上的SIMD加速，現(xiàn)階段還非常依賴程序?qū)舆M行主動算法適應(yīng)性改造，有 目的地使用，換言之，就是主動實施這種單線程內(nèi)的并發(fā)改造。一個無法自動優(yōu)化的例子就是《內(nèi)存篇》中提到的字符串切分的優(yōu)化，現(xiàn)階段通過編譯器分析還很難從循環(huán) 判斷分支提取出數(shù)據(jù)并行pattern并轉(zhuǎn)換成SIMD化的match
全文15706字，預(yù)計閱讀時間24分鐘。
一、背景
簡單回顧一下，一個程序的性能構(gòu)成要件大概有三個，即算法復(fù)雜度、IO開銷和并發(fā)能力。由于現(xiàn)代計算機體系結(jié)構(gòu)復(fù)雜化，造成很多時候，工程師的性能優(yōu)化會更集中在算法復(fù)雜度之外的另外兩個方向上，即IO和并發(fā)，在之前的《百度C 工程師的那些極限優(yōu)化（內(nèi)存篇）》中，我們介紹了百度C 工程師工程師為了優(yōu)化性能，從內(nèi)存IO角度出發(fā)所做的一些優(yōu)化案例。
這次我們就再來聊一聊另外一個性能優(yōu)化的方向，也就是所謂的并發(fā)優(yōu)化。和IO方向類似，對于工程經(jīng)驗比較豐富的同學(xué)，并發(fā)應(yīng)該也并不是陌生的概念了，但是每個人所理解的并發(fā)問題，卻又往往并不統(tǒng)一。所以下面我們先回到一個更根本的問題，重新梳理一下所謂的并發(fā)優(yōu)化。
二、為什么我們需要并發(fā)？
是的，這個問題可能有些跳躍，但是在自然地進展到如何處理各種并發(fā)問題之前，我們確實需要先停下來，回想一下為什么我們需要并發(fā)？這時第一個會冒出來的概念可能會是大規(guī)模，例如我們要設(shè)計大規(guī)模互聯(lián)網(wǎng)應(yīng)用，大規(guī)模機器學(xué)習(xí)系統(tǒng)?？墒俏覀冏屑毸伎家幌?，無論使用了那種程度的并發(fā)設(shè)計，這樣的規(guī)?；到y(tǒng)背后，都需要成百上千的實例來支撐。也就是，如果一個設(shè)計（尤其是無狀態(tài)計算服務(wù)設(shè)計）已經(jīng)可以支持某種小規(guī)模業(yè)務(wù)。那么當(dāng)規(guī)模擴大時，很可能手段并不是提升某個業(yè)務(wù)單元的處理能力，而是增加更多業(yè)務(wù)單元，并解決可能遇到的分布式問題。
其實真正讓并發(fā)編程變得有價值的背景，更多是業(yè)務(wù)單元本身的處理能力無法滿足需求，例如一次請求處理時間過久，業(yè)務(wù)精細化導(dǎo)致復(fù)雜度積累提升等等問題。那么又是什么導(dǎo)致了近些年來，業(yè)務(wù)單元處理能力問題不足的問題呈現(xiàn)更加突出的趨勢？可能下面這個統(tǒng)計會很說明問題：（https://www.karlrupp.net/2015/06/40-years-of-microprocessor-trend-data/）
上圖從一個長線角度，統(tǒng)計了CPU的核心指標(biāo)參數(shù)趨勢。從其中的晶體管數(shù)目趨勢可以看出，雖然可能逐漸艱難，但是摩爾定律依然尚能維持。然而近十多年，出于控制功耗等因素的考慮，CPU的主頻增長基本已經(jīng)停滯，持續(xù)增加的晶體管轉(zhuǎn)而用來構(gòu)建了更多的核心。
從CPU廠商角度來看，單片處理器所能提供的性能還是保持了持續(xù)提升的，但是單線程的性能增長已經(jīng)顯著放緩。從工程師角度來看，最大的變化是硬件紅利不再能透明地轉(zhuǎn)化成程序的性能提升了。隨時代進步，更精準(zhǔn)的算法，更復(fù)雜的計算需求，都在對的計算性能提出持續(xù)提升的要求。早些年，這些算力的增長需求大部分還可以通過處理器更新?lián)Q代來自然解決，可是隨著主頻增長停滯，如果無法利用多核心來加速，程序的處理性能就會隨主頻一同面臨增長停滯的問題。因此近些年來，是否能夠充分利用多核心計算，也越來越成為高性能程序的一個標(biāo)簽，也只有具備了充分的多核心利用能力，才能隨新型硬件演進，繼續(xù)表現(xiàn)出指數(shù)級的性能提升。而伴隨多核心多線程程序設(shè)計的普及，如何處理好程序的并發(fā)也逐漸成了工程師的一項必要技能。
上圖描述了并發(fā)加速的基本原理，首先是對原始算法的單一執(zhí)行塊拆分成多個能夠同時運行的子任務(wù)，并設(shè)計好子任務(wù)間的協(xié)同。之后利用底層的并行執(zhí)行部件能力，將多個子任務(wù)在時間上真正重疊起來，達到真正提升處理速度的目的。
需要注意的是還有一條從下而上的反向剪頭，主要表達了，為了正確高效地利用并行執(zhí)行部件，往往會反向指導(dǎo)上層的并發(fā)設(shè)計，例如正確地數(shù)據(jù)對齊，合理的臨界區(qū)實現(xiàn)等。雖然加速看似完全是由底層并行執(zhí)行部件的能力所帶來的，程序設(shè)計上只需要做到子任務(wù)拆分即可。但是現(xiàn)階段，執(zhí)行部件對上層還無法達到透明的程度，導(dǎo)致這條反向依賴對于最終的正確性和性能依然至關(guān)重要。既了解算法，又理解底層設(shè)計，并結(jié)合起來實現(xiàn)合理的并發(fā)改造，也就成為了工程師的一項重要技能。
三、單線程中的并行執(zhí)行
提到并行執(zhí)行部件，大家的第一個印象往往時多核心多線程技術(shù)。不過在進入到多線程之前，我們先來看看，即使是單線程的程序設(shè)計中，依然需要關(guān)注的那些并行執(zhí)行能力?；剡^頭再仔細看前文的處理器趨勢圖其實可以發(fā)現(xiàn)，雖然近年主頻不再增長，甚至穩(wěn)中有降，但是單線程處理性能其實還是有細微的提升的。這其實意味著，在單位時鐘周期上，單核心的計算能力依然在提升，而這種提升，很大程度上就得益于單核心單線程內(nèi)的細粒度并行執(zhí)行能力。3.1 SIMD
其中一個重要的細粒度并行能力就是SIMD（Single Instruction Multiple Data），也就是多個執(zhí)行單元，同時對多個數(shù)據(jù)應(yīng)用相同指令進行計算的模式。在經(jīng)典分類上，一般單核心CPU被歸入SISD（Single Instruction Single Data），而多核心CPU被歸入MIMD（Mingle Instruction Multiple D ata），而GPU才被歸入SIMD的范疇。但是現(xiàn)代CPU上，除了多核心的MIMD基礎(chǔ)模型，也同時附帶了細粒度SIMD計算能力。上圖是Intel關(guān)于SIMD指令的一個示意圖，通過增加更大位寬的寄存器實現(xiàn)在一個寄存器中，“壓縮”保存多個較小位寬數(shù)據(jù)的能力。再通過增加特殊的運算指令，對寄存器中的每個小位寬的數(shù)據(jù)元素，批量完成某種相同的計算操作，例如圖示中最典型的對位相加運算。以這個對位相加操作為例，CPU只需要增大寄存器，內(nèi)存?zhèn)鬏敽陀嬎悴考粚?，針對這個特殊的應(yīng)用場景，就提升到了8倍的計算性能。相比將核心數(shù)通用地提升到8倍大小，這種方式付出的成本是非常少的，指令流水線系統(tǒng)，緩存系統(tǒng)都做到了復(fù)用。
從CPU發(fā)展的視角來看，為了能夠在單位周期內(nèi)處理更多數(shù)據(jù)，增加核心數(shù)的MIMD強化是最直觀的實現(xiàn)路徑。但是增加一套核心，就意味增加一套 完整的指令部件、流水線部件和緩存部件，而且實際應(yīng)用時，還要考慮額外的核心間數(shù)據(jù)分散和聚合的傳輸和同步開銷。一方面高昂的部件需求， 導(dǎo)致完整的核心擴展成本過高，另一方面，多核心間傳輸和同步的開銷針對小數(shù)據(jù)集場景額外消耗過大，還會進一步限制應(yīng)用范圍。為了最大限度利用好有限的晶體管，現(xiàn)代CPU在塑造更多核心的同時，也在另一個維度上擴展單核心的處理和計算位寬，從而實現(xiàn)提升理論計算性能（核心數(shù) * 數(shù)據(jù)寬度）的目的。
不過提起CPU上的SIMD指令支持，有一個繞不開的話題就是和GPU的對比。CPU上早期SIMD指令集（MMX）的誕生背景，和GPU的功能定位就十分類似，專注于加速圖像相關(guān)算法，近些年又隨著神經(jīng)網(wǎng)絡(luò)計算的興起，轉(zhuǎn)向通用矩陣類計算加速。但是由于GPU在設(shè)計基礎(chǔ)上就以面向密集可重復(fù)計算負載設(shè)計，指令部件、流水線部件和緩存部件等可以遠比CPU簡潔，也因此更容易在量級上進行擴展。這就導(dǎo)致，當(dāng)計算密度足夠大，數(shù)據(jù)的傳輸和同步開銷被足夠沖淡的情況下（這也是典型神經(jīng)網(wǎng)絡(luò)計算的的特性），CPU僅作為控制流進行指揮，而數(shù)據(jù)批量傳輸?shù)紾PU協(xié)同執(zhí)行反而 會更簡單高效。
由于Intel自身對SIMD指令集的宣傳，也集中圍繞神經(jīng)網(wǎng)絡(luò)類計算來展開，而在當(dāng)前工程實踐經(jīng)驗上，主流的密集計算又以GPU實現(xiàn)為主。這就導(dǎo)致了不少CPU上SIMD指令集無用論應(yīng)運而生，尤其是近兩年Intel在AVX512初代型號上的降頻事件，進一步強化了『CPU就應(yīng)該做好CPU該做的事情』這一論調(diào)。但是單單從這一的視角來認識CPU上的SIMD指令又未免有些片面，容易忽視掉一些真正有意義的CPU上SIMD應(yīng)用場景。
對于一段程序來講，如果將每讀取單位數(shù)據(jù)，對應(yīng)的純計算復(fù)雜度大小定義為計算密度，而將算法在不同數(shù)據(jù)單元上執(zhí)行的計算流的相同程度定義為模式重復(fù)度，那么可以以此將程序劃分為4個象限。在大密度可重復(fù)的計算負載（典型的重型神經(jīng)網(wǎng)絡(luò)計算），和顯著小密度和非重復(fù)計算負載（例如HTML樹狀解析）場景下，業(yè)界在CPU和GPU的選取上其實是有相對明確“最優(yōu)解”的。不過對于過渡地帶，計算的重復(fù)特征沒有那么強， 或者運算密度沒有那么大的場景下，雙方的弱點都會被進一步放大。即便是規(guī)整可重復(fù)的計算負載，隨著計算本身強度減小，傳輸和啟動成本逐漸顯著。另一方面，即便是不太規(guī)整可重復(fù)的計算負載，隨著計算負荷加大，核心數(shù)不足也會逐漸成為瓶頸。這時候，引入SIMD的CPU和引入SIMT 的GPU間如何選擇和使用，就形成了沒有那么明確，見仁見智的權(quán)衡空間。
即使排除了重型神經(jīng)網(wǎng)絡(luò)，從程序的一般特性而言，具有一定規(guī)模的重復(fù)特性也是一種普遍現(xiàn)象。例如從概念上講，程序中的循環(huán)段落，都或多或少意味著批量/重復(fù)的計算負載。盡管因為摻雜著分支控制，導(dǎo)致重復(fù)得沒有那么純粹，但這種一定規(guī)模的細粒度重復(fù)，正是CPU上SIMD發(fā)揮獨特價值的地方。例如最常見的SIMD優(yōu)化其實就是memcpy，現(xiàn)代的memcpy實現(xiàn)會探測CPU所能支持的SIMD指令位寬，并盡力使用來加速內(nèi)存?zhèn)鬏?。另一方面現(xiàn)代編譯器也會利用SIMD指令來是優(yōu)化對象拷貝，進行簡單循環(huán)向量化等方式來進行加速。類似這樣的一類優(yōu)化方法偏『自動透明』，也是默默支撐著主頻不變情況下，性能稍有上升的重要推手。
可惜這類簡單的自動優(yōu)化能做到的事情還相當(dāng)有限，為了能夠充分利用CPU上的SIMD加速，現(xiàn)階段還非常依賴程序?qū)舆M行主動算法適應(yīng)性改造，有 目的地使用，換言之，就是主動實施這種單線程內(nèi)的并發(fā)改造。一個無法自動優(yōu)化的例子就是《內(nèi)存篇》中提到的字符串切分的優(yōu)化，現(xiàn)階段通過編譯器分析還很難從循環(huán) 判斷分支提取出數(shù)據(jù)并行pattern并轉(zhuǎn)換成SIMD化的match
下載文檔
