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

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

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

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

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

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

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

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

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

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

圖2：將實時和工作指導與強分區(qū)架構(gòu)相結(jié)合

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

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

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

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

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

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

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