[發明專利]多核處理器的核間通信方法

有效

• 申請號: 201110452294.8
• 申請日: 2011-12-30
• 公開（公告）號: CN102591843A
• 公開（公告）日: 2012-07-18
• 發明（設計）人: 王俊昌;張凱;華蓓;周影影;肖月振
• 申請（專利權）人: 中國科學技術大學蘇州研究院
• 主分類號: G06F15/167
• 分類號: G06F15/167;G06F5/08
• 代理公司: 蘇州創元專利商標事務所有限公司 32103
• 代理人: 范晴

技術領域

本發明涉及一種無鎖先進先出隊列(lock-free?FIFO)，并特別地涉及一種簡單，高效，易于實現的單生產者/單消費者模式無鎖先進先出隊列(single-producer-single-consumer?lock-free?FIFO)的方法和裝置，該無鎖先進先出隊列被構造為用來在共享存儲器環境下提供簡單，高效，易于實現的通信方法。

背景技術

單生產者/單消費者模式的先進先出隊列是計算機科學中一種重要的數據結構，特別地，單生產者/單消費者模式的無鎖先進先出隊列一直被用來構造快速，高效的通信機制。如無特殊說明，本專利申請文件提及的無鎖先進先出隊列均指單生產者/單消費者模式的無鎖先進先出隊列。例如，隨著處理器指令集并行化空間的日益減少，再加上對能耗關注程度的增加，單處理器的發展速度正在逐步減慢，這最終導致多核處理器系統時代的到來。為充分發掘多核處理器系統的性能，運行在多核系統上的工作任務需要采用適當的并行化方法并行化。基本的并行化方法包括：任務級并行(Task?Parallelism)，數據級并行(Data?Parallelism)，流水線并行(Pipeline?Parallelism)。下面以流水線并行的方法為例子來說明無鎖先進先出隊列在軟件并行化領域的重要性。

以下結合圖1對流水線并行化方法進行描述。假設工作A在并行化的過程中被分割為依次相連的三個部分，分別為工作1，工作2，工作3，通過適當的綁定映射，可以讓工作1運行在處理核1上，工作2運行在處理核2上，工作3運行在處理核3上。當一個任務到來時，運行在處理核1上的工作1首先對該任務進行處理，然后將該任務通過一條先進先出隊列傳遞給工作2，運行在處理核2上的工作2對該任務進行處理，然后將該任務通過一條先進先出隊列傳遞給工作3，處理核3完成對該任務的處理。處理核3的工作完成后，該任務被全部完成。

參照圖1所描述的，在流水線并行方法中，處理核之間通過單生產者/單消費者模式先進先出隊列依次相連，一方面，該些隊列將多個處理核有效地組織在了一起，充分利用了硬件資源，另外一方面，在流水線并行方法中，單生產者/單消費者模式先進先出隊列處于數據處理的關鍵路徑上，該隊列的性能直接影響到流水線并行化方法的性能，從而影響應用軟件運行在多核體系結構上的性能。

下面結合圖2所示傳統無鎖先進先出隊列示例來闡述傳統無鎖先進先出隊列的方法：該些無鎖先進先出隊列通常是駐留在共享存儲器中的一塊內存區域。多個處理核或設備共享該內存區域，特別地，生產者2生產數據，并將該些數據依次放入到共享內存區域3，消費者1依次將共享內存區域中的數據取出，從而達到通訊的目的。

對傳統的單生產者/單消費者模式隊列的操作可通過以下代碼進行描述：

在該無鎖先進先出隊列的例子中，生產者2運行在第一個處理核上，產生新數據，使用enqueue函數進行入隊列操作；消費者1運行在第二個處理核上，消耗數據，使用dequeue函數進行出隊列操作；buffer為共享內存區域3。在廣泛使用的多核處理器系統中(例如X86架構)，由于該些處理器支持順序一致性訪存協議(sequential?consistency)，以上代碼進行描述的單生產者/單消費者模式隊列可以在不加鎖定的情況下安全地被生產者及消費者并發訪問。由于不需要鎖定操作，該些先進先出無鎖隊列在性能上優于傳統的基于鎖定的先進先出隊列。

具體地，傳統先進先出無鎖隊列的工作方式如下：生產者首先判斷隊列是否已滿，如果隊列未滿，那么生產者做入隊操作，將數據寫入隊列中，然后，生產者指向隊列的下一元素位置，作為一個例子，可以使用偽代碼：head＝(head+1)％size，其中size為隊列的大小，使用取模運算來確定隊列頭部的值。消費者首先判斷隊列是否為空，如果隊列不空，那么消費者做出隊操作，將數據從隊列中讀出，然后，消費者指向隊列的下一元素位置，作為一個例子，可以使用偽代碼：tail＝(tail+1)％size。

下面結合圖3闡述廣泛使用的多核處理器的系統結構的特點并指出傳統無鎖先進先出隊列中存在的重要缺陷。如圖3所示，多核處理器系統中，多個處理核通過同一條系統總線共享一個物理儲存器，在處理核與物理儲存器間是多層次的處理核緩存(cache)。處理核緩存的引入，一方面減少了處理核對數據的平均訪問時間和處理核對存儲器帶寬的需求；另外一方面，由于同一數據可能同時存在于多個處理核緩存中，多核處理器系統需要運行緩存一致性協議(cache?coherence?protocols)來維護多個數據副本的一致性。