面向眾核系統的層次化柵欄同步機制*

臧照虎，李 晨，王耀華，陳小文，郭 陽

(國防科技大學計算機學院，湖南 長沙 410073)

1 引言

當前，在多核及眾核處理器中，大量并行應用程序和程序模型依賴于線程之間的同步來確保一致性和正確性[1,2]。因此，這類應用程序的性能受制于同步原語的延遲，隨著并行處理器或計算數據規模的增大，這種依賴性變得越來越大。柵欄同步是一個重要的同步原語，它會阻塞線程，直到所有線程都到達同步點，繼而恢復執行。柵欄通常用于將并行應用分離成不同的執行階段，以確保在對應階段所有線程完成之前,下一階段不會啟動。

為了實現柵欄同步，研究人員提出了許多基于軟件的方法[3,4]。通常，所有線程共享一個變量。當每個線程到達同步點時，訪問內存并修改該變量，使其值加1，然后進入等待狀態。當變量的值達到預設的同步線程數時，所有線程都將恢復執行。軟件柵欄同步方法仍然需要基于同步原語，如信號量和鎖[5,6]，利用這些同步原語，通過共享內存實現柵欄同步。由于共享變量存儲在內存中，每次修改共享變量都需要訪問內存,因此長內存訪問延遲可能成為系統的瓶頸。

利用共享內存實現的柵欄的開銷主要來自訪問共享內存的原子操作，因此可以利用Cache一致性協議來實現[7,8]。然而，一些多核處理器可能不支持硬件Cache一致性協議，因此這些系統無法采用這種方法[9]。為了降低這種軟件同步開銷，研究人員提出了幾種基于硬件實現的柵欄同步方法[10 - 14],典型的是在處理器上集成一個集中式硬件柵欄單元，用于處理來自所有內核的柵欄同步請求。與軟件柵欄同步相比，采用硬件設計的集中式柵欄同步方法效率更高。然而，當它運行在多核甚至眾核處理器系統上時，這種集中式柵欄同步方法可能會導致網絡擁塞[15]。陳小文[16]提出一種協同通信方法，用于在基于mesh的眾核處理器中實現高效和高擴展性的all-to-all柵欄同步機制，該方法使用片上網絡傳遞同步報文，但仍會占用片上網絡資源，可能在網絡中形成熱點。

因此，本文提出一種稱為HSync(Hierarchical Synchronization)的層次化硬件柵欄同步設計。HSync建立在分層網絡上，可以減少柵欄同步原語的同步流量，并且易于擴展以滿足眾核處理器的需求。實驗結果表明，與傳統的基于集中式硬件柵欄的柵欄同步相比，HSync實現了13%的性能提升和高達 74% 的同步報文減少。

2 背景

研究人員在過去的幾十年中已經提出了許多方法，例如在軟件中利用原子操作實現同步[17]。軟件同步方法雖然因其實現簡單而被廣泛使用，但是,構建于硬件共享內存系統之上的軟件實現的柵欄同步操作延遲很高,內核間通信的流量和延遲都隨著同步參與者數量的增加而呈指數增加[18]，這導致了同步數百個線程的效率極低。

當前已有研究人員使用專用硬件來提高柵欄同步性能，但這些方法也存在一些缺點，例如缺乏可擴展性或對并發柵欄的支持有限。從本質上來說，柵欄同步原語是一個與門，在硬件實現中，柵欄的實際性能受到芯片中連線延遲的限制。Hsu等[19]提出了一個多級隨機交換網絡，通過組合交換機中的數據包來有效處理軟件柵欄的同步流量，以緩解網絡中的熱點擁塞。Monchiero等[20]提出使用硬件模塊來減少CMP(Chip MultiProcessor)系統中核心的等待時間，該模塊集成在內存控制器中，稱為SOB(Synchronization Operation Buffer)。SOB管理本地核心對共享變量的輪詢，避免產生網絡流量及訪存。眾核系統中各核心也可以通過片上網絡進行同步信息的交換。Giannoula等[21]提出的SynCron(Synchronization)適用于NDP(Near-Data-Processing) 架構，此架構將處理核心置于數據附近，而不是將數據搬移至處理器中。該方法的優勢在于將信號量、鎖、柵欄及條件變量4種同步原語集中到一個硬件中，但是也因此帶來了更大的開銷，降低了靈活性，而且沒有應用到實際當中。本文方法依托于國防科技大學的眾核處理器項目，已應用于實際芯片，在減少網絡流量，降低時延，降低開銷的同時，擁有較強的擴展性。Hetland等[22]基于Intel的HARP(Hardware Accelerator Research Program)多芯片架構平臺提出了Harp Barrier的同步方法,此方法的優勢在于利用這種混合架構的FPGA及緩存一致性接口實現柵欄，但是其缺點在于難以適用于一般的眾核處理器。

綜上，軟件柵欄會帶來較高的時間開銷，而集中式硬件柵欄同步會占用片上網絡，可能造成網絡擁塞及熱點問題。因此，為了避免上述問題，本文設計了基于層次化網絡進行消息傳遞的方法。層次化網絡最大限度地減少了跨結點的通信報文，并在高并發場景下具有高性能。為了保證設計的正確性，參考驗證方法學[23,24]對HSync進行了模塊級完善和系統級驗證。

本文是基于國防科技大學自主研發的高性能通用DSP(Digital Signal Processor)提出的HSync。該款DSP具有24顆DSP核心，所有的核心被分為4個結點，6個核組合成1個結點。HSync在每個結點內設置一個本地柵欄單元LBU(Local Barrier Unit)，本結點的所有核都與之連接，由其負責本結點的柵欄同步請求。全局柵欄單元GBU(Global Barrier Unit)設置在結點之間，所有本地柵欄單元都與其相連，在完成本地柵欄同步后，再進行全局柵欄同步。

HSync使用獨立的柵欄網絡，網絡流量主要有2種類型，即本地柵欄同步流量和全局柵欄同步流量。如果沒有分層設計，即使是本地柵欄同步流量也需要跨全局柵欄網絡傳播，這大大增加了全局柵欄網絡的壓力，可能導致網絡擁塞和熱點問題。同時，隨著信息傳輸跳數的增加，本地柵欄同步的延遲會進一步增加。因此，分層柵欄結構可以顯著減少全局柵欄同步流量，降低本地柵欄同步延遲。

3 HSync設計

3.1 總體結構

HSync是多核處理器中柵欄同步的有效解決方案，可以提高并行程序性能，降低網絡開銷，簡化編程難度。該方案的設計主要是基于一定數量的計算核心組成一個基本單元，稱為結點，若干結點構成一個處理器。HSync的結構具有很強的可擴展性，便于應用在各種多核或眾核微處理器上。程序員在使用該裝置時只需要確定每個結點需要同步的核數及所有結點同步的總核數，并且使用同一個同步ID即可。

HSync使用了高度協作的兩級柵欄同步單元。如圖 1所示，柵欄同步單元包括結點內部的本地柵欄單元和結點之間的全局柵欄單元，本地柵欄單元連接全局柵欄單元。

Figure 1 Overall structure of HSync圖1 HSync的整體結構

在HSync柵欄同步操作中，單個核只能發起一個柵欄同步操作，但可以同時參與多個不同的柵欄同步。對于柵欄同步請求，每個結點內部的線程首先進行同步，然后全局柵欄單元收集所有結點的同步信息進行處理。這種分層處理方式匯集了同步信息，減少了網絡中的數據包數量，可以更快地完成結點內的柵欄同步。

本地柵欄單元 (LBU)由寄存器和相應的控制邏輯組成，位于每個結點內，負責處理結點內的柵欄同步請求。本文在LBU中設置了若干本地柵欄實例LBI(Local Barrier Instance)，每個硬件柵欄實例用于記錄一次柵欄同步的所有信息。LBU還包含了處理同步請求、分配LBI及向內核發送釋放信號的邏輯。LBU的結構如圖1所示，主要由柵欄同步請求分析模塊、柵欄實例調度模塊、柵欄實例分配模塊和一些LBI組成。

為了支持多個線程并發的柵欄請求，本文在每個LBU中設置了多個LBI，并可根據系統規模進行調整。LBI主要包括以下功能：(1)同步ID區分不同的同步請求;(2)記錄結點內需要同步的線程總數;(3)記錄整個處理器中需要同步的線程總數;(4)使用進程向量寄存器記錄已經到達的線程;(5)一些配置功能，例如超時寄存器為同步請求預留了最長的保持時間。

HSync中為每個柵欄實例提供了一些配置寄存器，用戶可以通過設置這些寄存器來控制每個 LBI。比如，通過設置柵欄超時寄存器，可以調整LBI的最長占用時間，以適應不同的工作環境。如果確定不需要配置LBI，可以去掉部分配置寄存器，以減少設計的面積開銷。

全局柵欄單元 (GBU)用于處理結點間的柵欄同步請求。與LBU的主要區別在于其內部有多個FIFO，用于臨時存儲來自 LBU 的消息。GBU包含多個全局柵欄實例GBI(Global Barrier Instance)，GBI與LBI的組成類似。GBU首先接收來自 LBU的消息，對其進行解碼以跟蹤全局柵欄同步,并在所有線程到達時向LBU發送釋放信號。GBU 的具體結構如圖2所示。

Figure 2 Structure of GBU圖2 全局柵欄單元的結構

為了增強本文柵欄設計方案的可配置性，以及協助程序員在出現問題時定位錯誤，本文添加了一些用于觀察和控制柵欄的寄存器，包括狀態寄存器組和配置寄存器組。狀態寄存器用來存儲柵欄機制的當前狀態，程序員可以通過讀取這些寄存器的值來檢查機制的運行狀態；柵欄的配置信息存儲在配置寄存器中，程序員將特定值寫入這些寄存器以配置柵欄。

全局柵欄映射寄存器：該寄存器存儲了全局柵欄實例與柵欄同步請求ID的映射關系。每個柵欄同步請求ID對應一個全局柵欄實例。這個映射關系是由硬件根據空閑柵欄實例自動建立的，程序員可以通過讀該寄存器來獲取該柵欄請求所訪問的柵欄實例。全局柵欄實例有效寄存器：默認所有位均為1。當使用柵欄實例時，其對應值設置為0。當柵欄同步完成后，柵欄實例被釋放，寄存器恢復為全1。全局錯誤寄存器：當該寄存器設置為1時，表示柵欄處理發生異常，例如超時錯誤，將發送中斷信號通知系統；設置為 0 時，則中斷關閉。軟復位寄存器：對該寄存器的低位寫1將復位對應結點的柵欄單元。閾值控制寄存器：該寄存器的值表示該結點發送的同步請求存在于緩沖區頭部的時間。超時后，頭部請求將放置在緩沖區的末尾。本地柵欄單元中的寄存器組與全局柵欄單元中的類似，但沒有閾值控制寄存器。

全局柵欄實例和本地柵欄實例也包含狀態寄存器和配置寄存器。柵欄狀態寄存器：該寄存器存儲了柵欄同步請求的相關信息，包括同步請求ID、參與同步的總核數等。本地柵欄實例還包含參與同步的內核總數。柵欄實例狀態向量寄存器：表示當前到達的核心向量。超時寄存器：表示一個柵欄請求可以等待的最長時間，超時后此柵欄實例將被釋放。超時計數寄存器：當一個柵欄請求被分配給一個柵欄實例時，此寄存器會開始計數，記錄此同步請求的等待時間，當超過超時寄存器的值時，會釋放柵欄，以避免長時間等待。柵欄實例錯誤使能寄存器：將此寄存器設置為1后，如果對應LBI在處理柵欄請求中發生錯誤，將通知系統處理錯誤并做出其他響應。柵欄實例錯誤寄存器：用于記錄發生錯誤時到達的核心向量，以方便于系統查詢和定位錯誤。

3.2 HSync工作流程

一般來說，可以將來自核心的同步請求分為2類：(1)本地同步：指只有結點內的處理器核上的線程參與的柵欄同步。當一個線程發送柵欄請求時，LBU接收請求并選擇一個空閑的LBU來記錄此柵欄同步的詳細信息。當LBU收到來自其他參與同步的內核的請求時，它會更新之前選擇的 LBI。直到所有的核都到達，LBI將被LBU復位，并向參與同步的核發送釋放信號。如果參與本地同步的核數為1，則直接將請求發送給GBU進行處理。(2)全局同步：指參與同一次同步的線程位于不同結點。不同結點的核首先完成本地柵欄同步，然后將相應的同步信息發送給GBU。與LBU流程類似，GBU會為此請求分配一個空閑的GBI記錄同步信息。當所有參與同步的核到達時，GBU將重置GBI，并向LBU 發送釋放信號。LBU將發布信息轉發給每個內核，所有線程恢復執行。

柵欄同步請求分為本地和全局，可以減少本地同步報文在網絡中的傳輸時間。同時，層次化的多級設計減少了全局同步的報文數量。一次完整柵欄同步的基本流程如圖 3所示。本文假設所有內核同時參與相同的柵欄同步。

Figure 3 Flow chart of barrier synchronization request圖3 柵欄同步請求流程

3.3 編程接口

HSync使用體系結構中已有的load指令(訪問特定范圍的地址)訪問柵欄空間的方式發出同步請求，線程阻塞在此指令，直到所有線程都到達柵欄。這種方法的優點是不需要添加新指令或修改指令集。柵欄同步請求的具體信息編碼在load指令的地址參數中。柵欄空間地址包含3個字段：SyncID(同步請求ID)、LocalNum(本地線程數)和GlobalNum(全局線程數),它們各自的字段寬度根據實際系統配置確定。

下面給出了柵欄操作以及訪問柵欄內部寄存器的軟件接口:

intbar_req(unsigned intSyncID，unsigned intLocalNum，unsigned intGlobalNum);

在《中關村筆記》中，資料的完備性、敘事的詳盡性是毋庸置疑的，這使得它在根本上作為“非虛構文學”的參與者，遵循了客觀紀實性的要求，并由于藝術水準的高超為這一題材的發展增添了更多可能性。

intset_bar_reg(unsigned intRegName，unsigned intValue);

intget_bar_reg(unsigned intRegName);

程序員需要向發起柵欄請求的函數傳遞3個參數：表示柵欄同步請求的ID的SyncID、存儲本地結點參與同步的線程數LocalNum和存儲參與此同步的全局線程總數GlobalNum。當柵欄同步正確完成時，該函數返回一個大于零的值。整個同步機制對程序員是透明的。當內核發送同步請求時，該機制自動分配空閑的 LBI 和 GBI，無需程序員指定。

為了提高方案設計的靈活性和穩定性，本文還在HSync內部設置了一些配置寄存器供程序員訪問。設置內部寄存器的系統調用需要提供2個參數：RegName(目標寄存器的名稱)和Value(要設置的值)。獲取狀態寄存器值的函數只需要提供寄存器地址。

3.4 可擴展性

本節討論如何對本文提出的方案進行擴展，以適用于更大規模的系統，便于HSync應用到不同的場景中。HSync可以通過2種方式應用于更大的系統。第1種方式是增加LBU中LBI的個數和GBU中GBI的個數。這種方法比較簡單容易實現，但是在系統規模巨大時會造成很大的硬件開銷，且在實際程序中很少會有并發柵欄請求占滿LBI或GBI的情況。在實際測試中發現確實如此，每個結點通常不會同時有大量不同ID的同步請求，因此大多時候有一部分LBI或GBI并未被使用。第2種方式使用固定數量的LBI和GBI，當同步請求數超過LBI或GBI數量時，在同步裝置中增加FIFO來緩存同步請求。

為了減少資源浪費，LBI和GBI的數量可設置為比核數更小的值，因此如果 LBI 或 GBI 被全部占用，則來自內核的新同步請求可能會阻塞暫存于同步請求的FIFO。在這種情況下，會產生死鎖。為了解決這個問題，本文修改了傳統的FIFO，增加了一些控制邏輯。當 FIFO 中的數據在一定時間內沒有被移除時，后續的請求將首先對FIFO 頭進行處理。這種方法不僅減少了LBI和GBI的數量，而且對本文設計的性能沒有顯著影響，大大增強了設計的可擴展性，減少了資源浪費。

4 實驗

為了衡量柵欄同步操作對于并行應用程序的影響，本文使用2個計算核進行實驗。如圖 4所示，隨著核數的增加，軟件同步方法引起的同步開銷迅速增加。當有32個內核在運行矩陣乘法運算時，接近66% 的執行時間是消耗在各進程同步上的，對于需要多核柵欄同步的運算，隨著核數增加，柵欄同步操作占比會更大。對于不同運算，柵欄同步操作所占比例不同，但隨著核數增多，占比增大的趨勢是相同的。

Figure 4 Proportion of time cost for software synchronization operation under different core scales圖4 不同核心規模下軟件同步占總執行時間比例

本文采用Verilog硬件描述語言實現了HSync硬件柵欄設計，并通過將此設計集成到系統級環境中得到實驗結果。本文在 Linux系統上使用仿真軟件平臺對HSync進行了測試。實驗中使用的24核系統，一共4個結點，每個結點具有6個核心。

為了全面地評估HSync，本文使用了幾種不同的測試方案，包括理論性能測試、隨機激勵測試和實際應用測試。為了測試本文方案的理論性能，首先建立了一個合成流量模型。主要做法是調整本地同步請求在全體同步請求中所占的比例。在此測試中，分別選取了5個典型值：0,25%,50%,75%和100%。基于這個條件，隨機產生相應的柵欄同步請求，并不斷地發送到同步單元，同時監測網絡中的流量并記錄同步消耗的時間。本文還選擇了幾種常用的并行計算核，如FFT、一般線性遞推方程等。本文評估中所使用的計算核如表1所示。

Table 1 Computational kernels used in this experiment

本文使用合成流量模型和一些并行計算核對HSync進行了全面測試。為了清楚地了解柵欄同步所占用的處理器執行時間，在實驗平臺上測量了1次柵欄同步的時間。圖 5表明，硬件柵欄同步相比軟件實現耗時明顯減少了，本文的層次化柵欄設計耗時相比集中式也有明顯降低。

Figure 5 Average time spent in one barrier synchronization圖5 1次柵欄同步的平均耗時

4.1 不同柵欄對程序執行時間的影響

從圖 6可以看出，隨著本地柵欄同步請求比例的增加，由于本地的網絡延遲更低，因此性能提升更加明顯。圖7為以集中式柵欄為基準不同柵欄方案下各并行計算核的性能。橫坐標代表使用的計算核，縱坐標代表歸一化的執行時間。由于降低了本地柵欄的同步延遲，HSync在實際應用中相對于無層次硬件柵欄方案也有一定的改進。

Figure 6 Performance of different barrier schemes in synthetic traffic models圖6 合成流量模型中不同柵欄方案的性能

Figure 7 Performance of different barrier schemes in parallel computing kernels圖7 并行計算核中不同柵欄方案的性能

4.2 不同柵欄對網絡流量的影響

受益于層次化的設計，結點內的柵欄同步不會在結點之間的網絡中產生報文。對于全局同步，柵欄請求會被結點中的本地柵欄單元處理，合成一條報文，然后在結點間的網絡中傳輸。因此，柵欄同步的網絡流量得到了很大的減少。圖 8 描述了合成流量模型網絡中的歸一化報文數量。橫坐標表示本地柵欄同步在所有同步請求中的比例。正如預期的那樣，隨著本地柵欄同步所占比例逐步增加，結點間網絡中傳輸的數據包總數則逐步減少。當所有數據包都是本地柵欄同步請求生成時，數據包數量最少。得益于層次化的結構設計，可以看到圖9中實際的并行計算核中網絡流量顯著減少，因為網絡中數據包合并后大大減少了報文數量。

Figure 8 Network traffic of different barrier schemes in synthetic traffic models圖8 合成流量模型中不同柵欄方案網絡流量

Figure 9 Network traffic of different barrier schemes in different computing kernels圖9 并行計算核中不同柵欄方案網絡流量

4.3 LBI和GBI數量對設計的影響

在本文的設計中，LBU和GBU分別用于分析并處理本地同步請求和全局同步請求，它們包含的LBI和GBI的數量可能會影響HSync執行柵欄同步的性能。因此，為了分析不同數量的LBI和GBI對HSync性能的影響，設計了幾組實驗。實驗基本配置由4個結點組成，每個結點包含8個核。通過在不同的LBU和GBU 配置下執行相同的應用程序，比較實際執行時間得到實驗結果。圖 10 顯示了在每個結點中設置不同LBU數量對性能的影響。結果表明，當LBU數量為3時，HSync對柵欄同步的加速比達到較高值。圖 10表明，GBU的數量在4～6時達到較高的加速比。根據此實驗結果，可以確定HSync中LBI和GBI的最佳數量，以實現性能和硬件開銷之間的平衡。

Figure 10 Effect of the number of GBIs and LBIs on performance圖10 GBI和LBI數量對性能的影響

4.4 硬件開銷

對HSync進行了功能驗證并確認結果正確后，使用28 nm工藝庫在典型條件下(常溫常壓(1 V，25 ℃))進行了綜合，綜合頻率達到了1.56 GHz。綜合結果表明，HSync所占用面積為401 979.38 μm2,相比于集中式的FlatBar減少了36%，其中本地柵欄單元約占66%，全局柵欄單元約占34%。FlatBar因為缺乏FIFO調度機制，在結點之間需要設置24個柵欄實例，而且與結點內的柵欄同步單元沒有協同工作，解碼器及相應的狀態寄存器更多，而HSync只需要12個全局柵欄實例且邏輯更加簡單，因此面積更小。HSync功耗為29.46 mW，比FlatBar減少了55.4%，由于HSync相比于非層次化FlatBar減少了很多重復的解碼單元、狀態寄存器及控制邏輯，因此降低了功耗。

5 結束語

具有共享內存的多核系統或眾核系統中的同步問題需要高效可靠的解決方案。一種簡單的方法是利用共享內存實現。然而，事實證明這不是一種高效的方法，且依賴于其他的同步原語。本文提出的設計方案對處理器存儲系統沒有任何影響,且大大減少了網絡中傳輸的數據包數量；另一方面，由于本地結點內部的同步請求由LBU處理，減少了整體同步延遲，提高了系統性能。

柵欄同步使用層次化方式實現的目的在于減少網絡內的柵欄同步報文數量，同時減少柵欄同步操作的平均延遲。隨著處理器核數的增加，使用FlatBar實現的柵欄會將大量同步報文集中到網絡的一個結點，造成擁塞等問題，層次化的方式將報文分別在不同結點上進行處理匯集，減少了報文數量，進而降低了對網絡的壓力，且對于結點內的核可以更快完成同步操作。隨著結點數增加及每個結點的核數增加，層次化結構優勢更加突出，平均網絡延遲也會降低更多。

通過實驗結果體現出了層次化硬件柵欄的優勢：降低了平均延遲，減少了網絡流量，降低了網絡開銷。本文的實驗結果表明，與集中式硬件柵欄FlatBar相比，使用層次化柵欄的HSync的處理器總執行時間平均減少了13%,網絡流量減少了74%；與軟件柵欄同步方法相比，總執行時間平均減少了82%。此外，HSync滿足硬件設計的簡單性和編程接口的易用性，是一種行之有效的硬件柵欄同步機制。