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

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

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

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

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

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

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

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

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

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

圖2：將實時和工作指導與強分區架構相結合

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

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

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

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

區分并行編程的一個特征是，并行計算的單位通常可以小于前奏函數或過程的執行，但可以表示循環的一個或多個迭代，或對較大表達式的一部分進行求值。此外，編譯器和底層運行時系統更多地參與確定代碼的哪些部分可以實際并行運行。這與傳統的并發編程構造完全不同，傳統的并發編程構造依賴于顯式的程序員決策來確定線程邊界在哪里。

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

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