并行加入多核嵌入式計(jì)算的并發(fā)

對(duì)于我們?cè)S多人來(lái)說(shuō)，術(shù)語(yǔ)并行性 和并發(fā)性幾乎是同義詞，即使我們認(rèn)為它們代表的概念有所不同，我們也不完全同意使一個(gè)結(jié)構(gòu)并行而另一個(gè)并行的原因。但是，隨著我們進(jìn)入多核，多核和基于GPU的計(jì)算時(shí)代，區(qū)分這兩者，并觀察這些差異如何影響嵌入式程序員的世界是很有用的。

并發(fā)編程在嵌入式系統(tǒng)
中有著悠久的歷史，在這種情況下，它代表了使用單獨(dú)的控制線程來(lái)管理發(fā)生的多種活動(dòng)的方法。這些控制線程通常具有不同的相對(duì)優(yōu)先級(jí)，其中中斷處理程序搶占了非中斷代碼，而要求更高調(diào)用頻率或更早截止日期的代碼搶占了具有更低頻率或更晚截止時(shí)間的代碼。對(duì)于控制具有相同優(yōu)先級(jí)的活動(dòng)的控制線程，通常使用循環(huán)調(diào)度方法來(lái)確保沒(méi)有活動(dòng)被忽略太長(zhǎng)時(shí)間。所有這些都不需要多個(gè)物理處理器，并且可以將其總體上視為需要管理許多活動(dòng)時(shí)以適當(dāng)方式共享有限資源的一種方式。通過(guò)允許將任何給定的控制線程限制為管理單個(gè)活動(dòng)，它也可以看作是簡(jiǎn)化編程邏輯的一種方法。因?yàn)橐氩l(fā)的控制線程可以簡(jiǎn)化整個(gè)程序的邏輯，所以支持這種方法的語(yǔ)言結(jié)構(gòu)本身也較重就可以了。

與并發(fā)編程相反，并行編程通常更多地是通過(guò)使用整體分而治之策略將其分成多個(gè)部分來(lái)解決計(jì)算密集型問(wèn)題，以便更好地利用多種處理資源來(lái)解決單個(gè)問(wèn)題。引入并行編程而不是簡(jiǎn)化邏輯，通常會(huì)使邏輯變得更復(fù)雜，因此，重要的是，從語(yǔ)法上和運(yùn)行時(shí)，并行編程結(jié)構(gòu)的重量應(yīng)非常輕，否則，其復(fù)雜性和運(yùn)行時(shí)開銷可能會(huì)超過(guò)潛在的加速。

調(diào)度線程
對(duì)于并行編程和并行編程，物理處理器的實(shí)際數(shù)量可能在程序的一次運(yùn)行與下一次運(yùn)行之間有所不同，因此通常在物理處理器之上提供一個(gè)抽象級(jí)別，通常由調(diào)度程序提供。對(duì)于并發(fā)編程，調(diào)度程序通常使用搶占，其中一個(gè)線程在執(zhí)行過(guò)程中被中斷，以允許更高優(yōu)先級(jí)的線程接管共享的處理資源。對(duì)于并行編程，更多情況下，目標(biāo)只是在最短的時(shí)間內(nèi)完成所有工作，因此不經(jīng)常使用搶占，而總吞吐量則成為成功的關(guān)鍵標(biāo)準(zhǔn)。

對(duì)于用于管理具有不同關(guān)鍵程度的外部活動(dòng)的并發(fā)編程，實(shí)時(shí)調(diào)度程序通常依賴于使用某種速率單調(diào)或期限單調(diào)分析分配的優(yōu)先級(jí)，以確保所有線程都將滿足其期限[3]。相反，對(duì)于并行編程，一種稱為工作竊取的方法（圖1）作為一種平衡多個(gè)物理處理器上的負(fù)載的健壯方法而出現(xiàn)，同時(shí)為給定處理器提供了良好的引用局部性，并實(shí)現(xiàn)了處理器之間的良好訪問(wèn)分離。

圖1：使用雙端隊(duì)列的工作竊取方法

工作竊取[2]基于一些相對(duì)簡(jiǎn)單的概念，但通常需要對(duì)底層調(diào)度程序進(jìn)行非常仔細(xì)的編碼，以實(shí)現(xiàn)所需的低開銷?；舅枷胧?，編譯器將計(jì)算分解為非常輕量級(jí)的線程（我們將其稱為picothreads），并且在調(diào)度程序中，每個(gè)物理處理器都有一臺(tái)服務(wù)器，該服務(wù)器具有自己的雙端隊(duì)列（通常稱為雙端隊(duì)列）。微微線程（圖1）。
典型的微線程可能表示執(zhí)行循環(huán)的單個(gè)迭代，或評(píng)估單個(gè)子表達(dá)式。微微線程會(huì)自動(dòng)放置在生成雙微線程的服務(wù)器的雙端隊(duì)列的尾部，并且當(dāng)服務(wù)器完成給定微微線程的工作時(shí)，它將最近添加到自己雙端隊(duì)列的微微線程（從尾部）移除，并開始運(yùn)行一。后進(jìn)先出（LIFO）學(xué)科將雙端隊(duì)列有效地用作工作堆。
在某個(gè)時(shí)候，服務(wù)器的雙端隊(duì)列為空，它已經(jīng)完成了所執(zhí)行的總體計(jì)算。那時(shí)，服務(wù)器從其他服務(wù)器之一竊取了微微線程。但是在這種情況下，它將刪除其他服務(wù)器雙端隊(duì)列的最舊的微線程。也就是說(shuō)，為了進(jìn)行竊取，使用了先進(jìn)先出（FIFO）規(guī)則。這完成的是，當(dāng)服務(wù)自己的雙端隊(duì)列時(shí)，服務(wù)器正在拾取一個(gè)微微線程，該微微線程可能正在處理關(guān)聯(lián)處理器最近正在使用的數(shù)據(jù)，而當(dāng)從另一個(gè)雙端隊(duì)列中竊取時(shí)，它將選擇一個(gè)已經(jīng)微弱的微微線程。在其雙端隊(duì)列上，可能將處理不在任何處理器的緩存中的數(shù)據(jù)，并且可能與其他任何處理器所處理的數(shù)據(jù)在物理上不很接近。
單個(gè)微線程足夠小，因此通常無(wú)需在它們完成之前搶占它們，這意味著它們不需要自己的完整堆棧-它們可以共享服務(wù)器提供的堆棧。要過(guò)早終止總體并行計(jì)算，通常足以阻止新的微線程啟動(dòng)，而無(wú)需在執(zhí)行過(guò)程中中斷給定的微線程。實(shí)際上，它共享一個(gè)堆棧并使用運(yùn)行到完成的方法，這些方法使這些微微線程相對(duì)于并發(fā)編程中使用的典型的可搶占的較重線程而言如此輕巧。

工作竊取有許多微妙之處，這仍然是一個(gè)活躍的研究領(lǐng)域，包括確定要從哪個(gè)服務(wù)器竊取，確定一次要竊取多少微微線程，選擇有效的雙端隊(duì)列以支持一端的獨(dú)占訪問(wèn)。以及如何從其他線程共享訪問(wèn)權(quán)限，以及如何處理微微線程之間的任何同步等。盡管如此，工作竊取的基本方法已被廣泛采用，包括各種并行語(yǔ)言（Cilk +，Go，Rust，ParaSail等）。以及各種庫(kù)（Java fork / join庫(kù)，OpenMP，英特爾的線程構(gòu)建模塊等）。

那么，這一切與移動(dòng)和嵌入式編程世界有何關(guān)系？事實(shí)是，多核硬件也已進(jìn)入移動(dòng)和嵌入式
領(lǐng)域，部分原因是多核體系結(jié)構(gòu)通?？梢蕴峁┳罴训拿客咝阅?，而功率幾乎始終是這些資源受限環(huán)境中的主要問(wèn)題。但是，這些環(huán)境中的大多數(shù)仍將具有硬性或軟性的實(shí)時(shí)要求，因此僅靠竊取工作就無(wú)法提供這些要求。需要將更傳統(tǒng)的并發(fā)編程方法與基于工作竊取的調(diào)度的某些方面進(jìn)行仔細(xì)集成。

將實(shí)時(shí)與竊取工作相結(jié)合是一個(gè)新的研究領(lǐng)域，只有很少的學(xué)術(shù)論文關(guān)注此問(wèn)題。盡管如此，它顯然變得越來(lái)越重要。正在更新諸如ARINC 653之類的標(biāo)準(zhǔn)，該標(biāo)準(zhǔn)定義了用于混合關(guān)鍵性系統(tǒng)的強(qiáng)分區(qū)體系結(jié)構(gòu)，以適應(yīng)多核硬件。由于擔(dān)心共享單個(gè)芯片的處理器不像強(qiáng)分區(qū)所要求的那樣獨(dú)立，因此采用的一種方法涉及將多個(gè)內(nèi)核分配給單個(gè)分區(qū)用于其時(shí)間片，然后在完成時(shí)間片后將它們?nèi)恐匦路峙浣o不同的分區(qū)。這將允許使用混合工作竊取方法，其中每個(gè)分區(qū)都有自己的服務(wù)器進(jìn)程集，每個(gè)服務(wù)器進(jìn)程都有自己的雙端隊(duì)列（圖2）。分割的時(shí)間片結(jié)束后，與該分區(qū)關(guān)聯(lián)的所有服務(wù)器進(jìn)程都將被掛起，并繼續(xù)執(zhí)行下一個(gè)分區(qū)的服務(wù)器進(jìn)程。因此，這里我們搶占了服務(wù)器進(jìn)程，而各個(gè)微微線程仍然可以通過(guò)將服務(wù)器進(jìn)程視為一種虛擬處理器來(lái)使用運(yùn)行完成模型。

圖2：將實(shí)時(shí)和工作指導(dǎo)與強(qiáng)分區(qū)架構(gòu)相結(jié)合

通過(guò)為每個(gè)實(shí)時(shí)優(yōu)先級(jí)創(chuàng)建單獨(dú)的服務(wù)器進(jìn)程，可以采用類似的方式安排優(yōu)先級(jí)調(diào)度。每個(gè)服務(wù)器都有自己的專用堆棧，只有當(dāng)內(nèi)核上所有優(yōu)先級(jí)較高的服務(wù)器進(jìn)程無(wú)關(guān)時(shí)，才會(huì)在內(nèi)核上運(yùn)行優(yōu)先級(jí)較低的服務(wù)器進(jìn)程。當(dāng)實(shí)時(shí)需求較弱時(shí)，另一種選擇是每個(gè)核心僅使用一個(gè)服務(wù)器進(jìn)程，但對(duì)于不同的優(yōu)先級(jí)使用單獨(dú)的設(shè)備。使用這種方法，不會(huì)發(fā)生搶占picothread的搶占。但是，當(dāng)服務(wù)器進(jìn)程選擇要執(zhí)行的新微微線程時(shí)，將遵循優(yōu)先級(jí)：服務(wù)器將首先從其自己的最高優(yōu)先級(jí)非空雙端隊(duì)列中選擇，但是如果另一臺(tái)服務(wù)器具有比任何其他服務(wù)器更高優(yōu)先級(jí)的非空雙端隊(duì)列，則從另一臺(tái)服務(wù)器進(jìn)行竊取。服務(wù)器自己的非空雙端隊(duì)列。

并發(fā)和并行的編程語(yǔ)言構(gòu)造
許多編程語(yǔ)言都包含一些并發(fā)線程，互斥鎖以及同步信號(hào)和等待的概念。PerBrinch Hansen的并發(fā)Pascal [1]是將許多這些概念整合到語(yǔ)言本身的最早的語(yǔ)言之一。Ada和Java從一開始就也包含并發(fā)編程概念，現(xiàn)在許多其他語(yǔ)言也包含這些概念。通常，并發(fā)線程的執(zhí)行對(duì)應(yīng)于近似執(zhí)行命名函數(shù)或過(guò)程的異步執(zhí)行。在InAda中，這是關(guān)聯(lián)任務(wù)的任務(wù)主體。在Java中，它是關(guān)聯(lián)的Runnable對(duì)象的run方法。鎖通常與某種同步對(duì)象（通常稱為監(jiān)視器）相關(guān)聯(lián)，對(duì)象上的某些或全部操作會(huì)在啟動(dòng)操作時(shí)自動(dòng)獲得鎖，并在完成時(shí)自動(dòng)釋放鎖，從而確保始終保持平衡。在Ada中，這些稱為受保護(hù)的對(duì)象和操作，而在Java中，它們是類的同步方法。

信令和等待用于處理并發(fā)線程需要進(jìn)行通信或以其他方式合作的情況，并且一個(gè)線程必須等待一個(gè)或多個(gè)其他線程采取某種操作或發(fā)生某些外部事件，然后才能進(jìn)一步進(jìn)行處理。信號(hào)發(fā)送和等待通常也由異步對(duì)象來(lái)實(shí)現(xiàn)，線程正在等待對(duì)象狀態(tài)的某些變化，信號(hào)被用來(lái)指示狀態(tài)已更改，并且一些等待線程應(yīng)該重新檢查以查看同步對(duì)象是否現(xiàn)在處于所需的狀態(tài)。Hoare和Brinch Hansen提出的條件臨界區(qū)代表了第一種語(yǔ)言構(gòu)造之一，它基于布爾表達(dá)式隱式提供了這種等待和信號(hào)傳遞。通常，這是通過(guò)對(duì)對(duì)象或條件隊(duì)列的顯式Wait和Signal操作提供的（在Java中，信令使用notify或notifyAll）。Ada結(jié)合了條件關(guān)鍵區(qū)域的概念，并通過(guò)將帶有入口屏障的條目合并到受保護(hù)的對(duì)象構(gòu)造中來(lái)進(jìn)行監(jiān)視，從而無(wú)需顯式的Signal和Wait調(diào)用。所有這些概念都代表了并發(fā)編程結(jié)構(gòu)的含義。

相比之下，盡管正在迅速變化，但數(shù)量較少的語(yǔ)言卻沒(méi)有包含可以被認(rèn)為是并行編程結(jié)構(gòu)的語(yǔ)言。與并發(fā)編程一樣，并行編程可以由顯式語(yǔ)言擴(kuò)展，標(biāo)準(zhǔn)庫(kù)或二者的某種混合來(lái)支持。并行編程的第三個(gè)選項(xiàng)是使用程序注釋，例如編譯指示，向編譯器提供方向，以允許編譯器自動(dòng)并行化原始順序算法。

區(qū)分并行編程的一個(gè)特征是，并行計(jì)算的單位通常可以小于前奏函數(shù)或過(guò)程的執(zhí)行，但可以表示循環(huán)的一個(gè)或多個(gè)迭代，或?qū)^大表達(dá)式的一部分進(jìn)行求值。此外，編譯器和底層運(yùn)行時(shí)系統(tǒng)更多地參與確定代碼的哪些部分可以實(shí)際并行運(yùn)行。這與傳統(tǒng)的并發(fā)編程構(gòu)造完全不同，傳統(tǒng)的并發(fā)編程構(gòu)造依賴于顯式的程序員決策來(lái)確定線程邊界在哪里。

Cilk是最早使用的具有通用并行編程結(jié)構(gòu)的語(yǔ)言，它是由MIT的Charles Leiserson [3]設(shè)計(jì)的，現(xiàn)在由Intel作為其Intel Parallel Studio的一部分提供支持。Cilk允許程序員 在算法的戰(zhàn)略要點(diǎn)插入諸如cilk_spawn 和cilk_sync之類的指令，其中_spawn 導(dǎo)致將表達(dá)式的評(píng)估分叉到單獨(dú)的輕量級(jí)線程中，而_sync導(dǎo)致程序等待本地產(chǎn)生的并行線程，因此可以使用它們執(zhí)行的結(jié)果。此外，Cilk還提供了使用cilk_for的功能 而不是簡(jiǎn)單地表示給定的for循環(huán)的迭代是并行執(zhí)行的候選對(duì)象?，F(xiàn)在提供類似功能的其他語(yǔ)言包括OpenMP，它使用編譯指示而不是語(yǔ)言擴(kuò)展來(lái)指導(dǎo)并行執(zhí)行的插入； Google的languageGo，它包括用于具有通信通道的并行執(zhí)行的輕量級(jí)goroutine，以及Mozilla Research的Rust，它支持大量輕量級(jí)的語(yǔ)言。使用所有權(quán)轉(zhuǎn)移來(lái)避免競(jìng)爭(zhēng)情況的任務(wù)通信，以及AdaCore的ParaSail語(yǔ)言使用基于無(wú)指針，無(wú)別名方法的安全自動(dòng)并行化，該方法簡(jiǎn)化了分而治之的算法。

所有這些并行語(yǔ)言或擴(kuò)展都采用了某種形式的竊取工作來(lái)調(diào)度其輕量級(jí)線程。所有這些語(yǔ)言使從順序?qū)虻乃季S方式轉(zhuǎn)換為并行導(dǎo)向的思維方式變得更加容易。嵌入式和移動(dòng)程序員現(xiàn)在應(yīng)該開始使用這些語(yǔ)言進(jìn)行實(shí)驗(yàn)，以準(zhǔn)備將實(shí)時(shí)優(yōu)先級(jí)功能與偷竊計(jì)劃程序合并在一起，以提供先進(jìn)的嵌入式和移動(dòng)應(yīng)用程序在繪圖板上所需的反應(yīng)性和吞吐量的結(jié)合，從而為未來(lái)的將來(lái)做好準(zhǔn)備。lw