異構多核處理器多發射動態調度技術研究

唐 旭, 張多利, 王 杰, 宋宇鯤

(合肥工業大學 微電子學院,安徽 合肥 230601)

自第一款多核處理器誕生以來,關于多核處理器和計算并行化的研究從未停止[1-2]。其中多核調度問題是核心問題[3],調度方法的優劣直接決定了系統的性能高低。任務調度分為靜態調度和動態調度[4],靜態調度側重于任務執行之前,對所有任務的計算時間和任務間通信量進行整體分析[5-6],從而決定相對較優的任務發射執行順序[7];但是靜態任務調度通常是基于任務間通信無擁塞等多種理想化假設[8-9],且對于任務各項參數的預估往往不準確,因此在實際應用中,更多的是使用動態任務調度。動態任務調度的核心思想是實時監測計算資源的空閑情況等系統狀態[10],實時調整調度方案[4],發射滿足發射條件的任務,將空閑的計算資源利用起來。

此外,隨著處理器和外部存儲器間性能增速差的擴大,外部存儲器的讀寫延遲和帶寬成為限制系統性能的關鍵瓶頸[11-12]。由于任務級的計算數據粒度大,外部存儲器的讀寫延遲高,因此,減少非必須的外部存儲器讀寫次數,進而減少在外部存儲器讀寫上的時間消耗,是提升系統性能的關鍵問題之一[13]。

文獻[14]研究了一種多級計算體系結構的控制器設計,該控制器可自動提取粗粒度計算任務之間的并行性,并將這些任務分配到同構處理器上執行?？刂茩C制與超標量處理器類似,使用寄存器重命名、亂序執行和動態調度等技術實現調度任務執行的目標。文獻[14]的研究結果對粗粒度任務調度控制器的設計具有重要的參考價值,但未涉及對異構系統調度技術的研究。

文獻[15]指出顯式并行編程的復雜性極大地限制了編程人員從多處理器芯片上獲得更高性能的可能性。為簡化軟件編程,文獻[15]提出了一種任務級超標量微體系結構,作為多級計算體系結構的控制器,完成了調度控制器模型的計算機仿真和功能測試。

上述文獻未考慮系統的異構特性、核間通信方式和存儲器的讀寫延遲等實際約束。本文在任務級并行自動提取技術、動態調度技術和亂序發射技術的基礎上,充分考慮系統的異構特性、存儲器約束和核間通訊約束完成設計實現,研究一種減少外部存儲器訪問開銷的方法,顯著提升了系統的性能。

本文面向的異構多核計算系統整體結構如圖1所示,系統主要包括主控制器、計算單元、通信網絡和功能單元。計算單元包括可重構計算單元(reconfigurable computing unit,RCU)、通用浮點計算單元(general float processor,GFP)、快速傅里葉變換(fast Fourier transform,FFT)硬件加速器3類。功能單元包括雙倍數據速率(double data rate,DDR)存儲器等。通信網絡包括狀態網(status network,STAT-NET)、配置網(configure network,CFG-NET)、數據網(data network,DATA-NET)。

圖1 異構多核計算系統整體結構

目標異構多核計算系統使用多層編程的方式完成預期的計算目標。程序中的配置指令按照程序中確定的坐標發送給對應坐標的計算單元,用于控制計算單元的計算方式,任務的發射過程嚴格遵從程序的預期設計,主控制器負責執行控制指令,計算單元負責執行計算指令進行計算,由此實現多層編程。由于計算單元掛載在通信網絡上,也將計算單元稱為“計算節點”,下同。

三層網絡組成整個系統的控制、狀態、數據的交互通道。狀態網的作用是收集片上網絡中各個部件的工作狀態,并反饋給主控制器。配置網的主要作用是負責傳送主控制器下發的各條配置信息給各個單元。數據網是片上各個單元之間大批量數據傳輸的載體。數據網使用2D MESH的片上網絡(net on chip,NoC)作為拓撲結構。

2.1 任務的概念和分類

本文面向的目標多核計算系統中,任務定義為一次計算過程,數據的起點是DDR存儲器,經過運算單元運算,終點是DDR存儲器。本文將任務按照是否寫回DDR存儲器分為強寫回任務和弱寫回任務。

(1) 強寫回任務指必須將結果數據寫回DDR存儲器的任務。

(2) 弱寫回任務指結果數據可由調度器決策寫回DDR存儲器或者發射給下一個計算節點。

在編程階段,編程者需要根據實際的算法指定任務的不同類型。

任務的編程規范舉例如下:

Task1

Configure FU cfg_info

Configure DDR.read address

Configure DDR dst=FU

Configure DDR.write address

Configure FU dst=DDR

Configure START

其中:Configure表示配置指令,配置指令經系統主控制器譯碼后通過配置網發送給各個單元,這些單元包括計算單元、DDR存儲器和數據網節點等;FU表示三類計算單元。上述任務5條配置信息的含義如下:

(1) 配置計算單元的計算信息。

(2) 配置DDR存儲器的讀地址和數據量。

(3) 配置DDR存儲器的目的節點坐標。

(4) 配置DDR存儲器的寫地址和數據量。

(5) 配置DDR存儲器的寫節點坐標。

(6) 主控制器發出命令,啟動DDR存儲器,建立數據網傳輸鏈路,完成計算過程。

上述6條配置指令構成了一個完整的從DDR存儲器取數、執行、結果數據寫回DDR的運行流程。

2.2 任務依賴關系表

為了使調度控制器能夠準確追蹤任務的數據相關性,以及在正確的時刻觸發任務的可執行條件,需要在編程階段,預先記錄任務的數據相關性。同時為了讓調度控制器具有調度的基本依據,需要新增任務依賴關系表,在任務依賴關系表中記錄任務的基本信息,并將任務依賴關系表中的內容稱為任務標簽。

2.3 動態任務調度和亂序發射的實現方案

實現方案是在系統原主控制器的基礎上新增調度控制器,控制任務調度和發射過程;狀態網負責檢測系統的狀態,配置網負責下發配置信息。

(1) 狀態網監測系統狀態。因為任意時刻計算單元只會被某一個任務唯一占用,所以通過監控計算單元的狀態就可以得到相應任務的狀態,從而實現對任務完整流程的監控。同時,使用狀態網可以統計得出空閑的與繁忙的計算單元個數。

(2) 調度控制器亂序多發射任務。通過監測任務的執行狀態和當前時刻空閑的計算單元數量,再結合任務本身所需的計算單元的數量信息,可以判斷任務是否滿足可發射的條件:① 任務的所有前驅相關任務全部計算完成,結果數據已經產生或者結果數據寫回DDR存儲器完成;② 當前時刻系統上有足夠的計算資源。

滿足這2個條件的任務可以發射。調度控制器對每個任務的發射條件進行嚴格檢查,保證了任務之間數據傳遞的安全性,為任務的亂序發射提供技術支撐。

(3) 配置網下發配置指令。在某一個任務滿足發射條件后,調度控制器將主程序中該任務的計算配置信息通過配置網傳遞給選中的計算單元,從而完成一次完整的任務喚醒、調度、發射的控制流程。

2.4 任務調度優先級策略

最簡單的調度優先級策略是使用任務的初始編程次序作為任務發射次序。一方面,由于程序中前面的任務與后面的任務相比,往往具有更多的與其他任務之間的間接相關性[14],優先發射程序中前面的任務,原則上能夠使得更多存在相關性的任務達成發射條件而發射;另一方面,由于動態任務調度缺少程序的全局信息,不具備使用靜態調度算法找出關鍵路徑,實現較優的任務優先級排序的能力[7]。因此,本文在粗粒度上使用任務的初始編程次序作為調度優先級次序;在細粒度上分析任務的可發射條件,對任務的發射次序進行精細調整,實現亂序發射。

2.5 任務的寫回監測和任務喚醒

對于強寫回類型的任務,因為其計算結果數據必定寫回DDR存儲器,所以需要監控其結果數據是否完成寫回DDR存儲器。

弱寫回任務不寫回DDR存儲器如圖2所示。

圖2 弱寫回任務不寫回DDR存儲器

對于弱寫回的任務,對它的監測分為如下2個階段:

(1) 第1階段。計算完成時刻調度控制器實時決策任務的結果數據是否寫回DDR存儲器,如果后繼任務滿足發射的條件,或者片上有足夠的暫存節點,那么結果數據不必寫回DDR存儲器;同時,將所有后繼任務的狀態刷新成可發射的,并指示其源數據的位置位于片上計算單元中或者暫存節點之中。

(2) 第2階段。如果第1階段的決策是寫回DDR存儲器,那么需要采取與強寫回類型的任務相同的方法,監控任務的結果數據是否寫回DDR存儲器完成,在寫回完成后,刷新所有后繼任務的狀態成可發射狀態,且標識其源數據位于DDR存儲器。

2.6 動態任務鏈和啟用片上暫存

弱寫回任務組成動態任務鏈如圖3所示,將實際運行時不寫回DDR存儲器的弱寫回任務按照任務之間的數據相關性串聯,組成動態任務鏈。

圖3 弱寫回任務組成動態任務鏈

4個弱寫回任務不寫回DDR存儲器將減少總共6次DDR存儲器的讀寫,只需保留頭任務讀DDR存儲器和尾任務寫DDR存儲器,該方法明顯減少了DDR存儲器的讀寫次數,節省了DDR存儲器的讀寫時間消耗。

除了使用動態任務鏈條減少任務的結果數據寫回DDR存儲器以外,還可以使用片上空閑計算單元的本地隨機存取存儲器(random access memory,RAM)作為暫存區,片上計算單元及其暫存區的數據進入等待狀態,待后繼任務的發射條件滿足時,再將數據發送給后繼任務所映射的計算單元,減少數據寫回。

完整的任務數據傳遞關系如圖4所示。

圖4 完整的任務數據傳遞關系

2條舊路徑分別是計算完成的任務節點將結果數據寫回DDR存儲器和后繼任務節點讀DDR存儲器獲得計算所需的源數據。新路徑1是多核計算系統運行的當前時刻,系統上有足夠的空閑計算節點,因此直接發射后繼任務,數據直接在數據網上從計算完成節點傳輸到后繼任務節點。新路徑2是在系統的計算資源不夠充足時,后繼任務未能獲得發射,因此將數據寫入到片上暫存節點。新路徑3是在系統的計算資源充足時,發射后繼任務,將計算源數據通過數據網從片上暫存節點發送到后繼任務計算節點。

使用上述任務結果數據重新定向的方法,減少了用戶對任務結果數據流向的人工干預。調度控制器將弱寫回任務自動組成任務鏈條以及自動亂序發射任務,在保證數據安全性的前提下,實現了對任務計算過程的硬件自動化控制,編程友好度顯著提高。

3.1 動態調度控制器整體結構

動態調度控制器整體結構如圖5所示,控制器由取指仲裁模塊、任務標簽緩存、任務標簽隊列、配置信息緩存、任務配置信息隊列、控制單元、發射單元、狀態監測單元組成,外圍集成到DDR存儲器的讀寫控制器、配置網和狀態網。

圖5 動態調度控制器整體結構

3.1.1 狀態監測單元

狀態監測單元負責對任務的計算節點狀態和DDR存儲器的狀態進行監控,當任務計算完成但數據未從節點發出,以及任務寫回DDR存儲器寫回完成時,任務狀態監測單元能夠識別這2種狀態,并將這2種狀態信息記錄在FIFO存儲器中,供控制單元讀取。

3.1.2 控制單元

控制單元負責動態調度控制器主狀態機的控制,同時通過任務標簽信息、任務計算節點狀態信息以及DDR存儲器的狀態信息,對任務的喚醒、發射和寫回過程進行決策,在確定待發射任務的編號后,向發射單元發送任務的基本信息和任務發射的啟動命令。

3.2 任務喚醒

在異構多核計算系統中,任務計算完成、DDR存儲器的寫完成以及任務節點間數據傳輸完成,分別對應著任務的寫回、DDR的釋放和計算單元的釋放。它們觸發了任務的可發射條件,因此,任務喚醒的時機是任務計算完成、空閑計算單元數量的增加和DDR存儲器寫回完成。

調度器的控制單元根據狀態監測單元輸出的信息和空閑的計算資源數量,確定計算完成或者結果數據寫回DDR存儲器完成的任務編號,然后訪問任務標簽隊列RAM,獲取任務的后繼輸出任務ID,將任務列表中后繼任務的狀態刷新成可發射。

3.3 發射單元

發射單元具有如下2類功能:① 按照控制單元的命令發射任務的計算配置信息;② 按照控制單元的命令發射任務的寫回配置信息,實現任務寫回。

發射單元的發射工作大體分為如下3個步驟:

(1) 讀取原始配置信息。

(2) 按照控制單元的調度決策對原始配置信息進行相應修改,或者生成新的配置信息。

(3) 將修改后的配置信息或者新生成的配置信息傳輸到配置網上。

本文設計的動態任務調度控制器在完成Verilog RTL級設計后,在Xilinx公司的XCVU440-FLGA2892-1-C型號的現場可編程門陣列(field programmable gate array,FPGA)芯片上綜合和實現,使用Xilinx公司的Vivado EDA工具鏈,對設計的Verilog RTL級電路進行綜合、映射和布局布線。

實現后最高電路主頻為166.058 MHz,動態調度器對FPGA的資源消耗見表1所列。

表1 FPGA資源消耗

4.1 實驗測試方案

本文從并行任務路徑數量、系統布局、任務的粒度、在計算資源發生競爭時的處理方法等維度,制定實驗方案,對調度控制器的功能和性能進行測試。

在測試中,對比的對象是現有的異構多核計算系統,系統上不啟用新設計的調度控制器,但系統上仍然可使用手動并行編程的技術。在控制層,僅有系統主控制器順序發射配置指令。NoC網絡上掛載了3類計算單元,每個計算單元各有8個,總共24個計算核。

4.2 系統并行計算性能參數

本文參考文獻[14]選用下述參數反映計算系統運行的不同特征和任務調度控制器的性能指標。設任務的總數為N。

(1) 任務調度時間,指從前驅任務計算完成或者寫回DDR完成,到后繼任務發射所消耗的周期數。

(2) 整體運行時間(whole run time,WRT),是從第1個任務發射到最后1個任務寫回DDR存儲器寫回完成,消耗的周期數。

(3) 執行時間(execute time,ET),是配置信息發射到任務寫回完成消耗的周期數。

(4) 執行時間總和(sum of execute time, SET),是所有任務的執行時間之和。

(5) 平均并行度(average of parallelism, AP),是同時運行任務的數量。

(6) 平均執行時間(average of execute time, AET),是執行時間總和除以任務的個數,即

(1)

(7) 整體運行時間加速比(speedup of whole run time,SPWRT)。計算公式為:

(2)

其中:new表示系統啟用調度控制器;old表示系統不啟用調度控制器。

4.3 任務平均調度時間隨任務數量變化實驗

任務平均調度時間見表2所列,任務的平均調度時間隨著任務的個數逐漸上升,但是逐漸趨向于一個穩定的值,即26個周期,相比于任務級計算102～104數量級的執行周期,調度控制器花費的時間代價較小。

表2 任務平均調度時間

4.4 并行任務的亂序多發射實驗

現有的異構多核計算系統控制器無調度功能,為了提升效率,在控制過程上使用類似單指令多數據流的方法,將一個粒度較大的任務展開到若干個相同類型的計算單元上執行,現有系統能實現編程者手動的并行編程,并行展開任務。但是,這種方法局限性較大,無法充分發掘客觀存在卻又不易被編程者察覺的任務并行性[15]。

4.4.1 并行任務路徑數量實驗

1條任務路徑是指數據從DDR存儲器出發,經過若干個任務計算單元,最后回到DDR存儲器。計算單元之間的相關性數據是否寫回DDR存儲器取決于控制器的控制。1個計算單元上運行1個任務。兩路并行任務路徑如圖6所示,圖6中有2條并行的任務路徑,總共有6個任務。

圖6 兩路并行任務路徑示意

此外,對目標異構多核計算系統采用2種布局方式:一種是規整布局,同類的計算單元位置處于一條直線上;另一種是分散布局,不同種類的計算單元混合零散排布在NoC網絡上,每個計算單元周圍都分布著不同種類的計算單元。

不同并行任務路徑數量下的整體運行時間見表3所列,其中,所有任務數據粒度均為256,每條任務路徑上有3個任務。

表3 不同并行任務路徑數量下的整體運行時間(周期)

整體運行時間加速比如圖7所示,相較于不啟用調度控制器,啟用調度器的計算系統整體運行時間加速比在1.310～1.900之間,且隨著并行任務路徑數量的增加,加速比呈現上升趨勢。動態調度控制器減少了任務數據讀寫DDR的時間消耗,因而獲得運行時間的加速。使用調度器后,規整布局與分散布局下的運行時間相差不大,原因是調度器設計時考慮到了布局的變化,設定了調整系統布局后調度器性能基本穩定的目標。

圖7 整體運行時間加速比

平均并行度如圖8所示,平均并行度與理論并行度有一定的差距。

圖8 平均并行度-任務路徑數量實驗結果

未能達到理論并行度的原因如下:

(1) 動態任務調度器需要花費額外的調度時間,調度控制器一次僅能調度發射一個任務,因此總共的調度時間是每個任務的調度時間的總和。

(2) 從任務計算完成到調度器響應,期間有額外的延遲,這包括任務狀態監測模塊內部的延遲和調度器響應任務狀態監測模塊的延遲。

(3) 在異構多核計算系統上,隨著任務數量增多,計算資源的利用率提升,導致數據網負載加大,任務間數據傳輸延遲增大。

4.4.2 任務粒度實驗

任務運行時間見表4所列,其中,任務路徑數量為8,每條路徑上有3個任務,共24個任務,均采用規整布局。

表4 任務運行時間(周期)

整體運行時間加速比如圖9所示,有調度器的目標計算系統能夠維持至少為1.000的整體運行時間加速比,這表明調度器不會造成系統性能的損失,且在任務粒度小于等于4×103時,展現出較高的加速比。

圖9 整體運行時間加速比-任務粒度實驗結果

在任務粒度為8×103、16×103的情況下,加速比降低是由于任務結果數據不寫回DDR存儲器,數據網上存在大規模的數據搬運行為,產生了鏈路擁塞,造成額外的鏈路延遲。相對應地,用戶在系統不啟用動態調度器的情況下手動映射計算單元位置,規避了鏈路擁塞問題,因此,在任務粒度為8×103、16×103的情況下,有調度器的計算系統加速比下降。任務粒度超過16×103的情形下,因為計算單元本地的緩存只有16×103,所以任務節點之間傳遞的數據被強制寫回DDR存儲器,在數據流動過程與無調度器的計算系統保持一致,任務的整體運行時間非常接近,因而整體運行時間加速比接近于1.000。

平均并行度-任務粒度實驗結果如圖10所示,在任務粒度從0.256×103增加到4×103過程中,平均并行度逐漸逼近理論并行度,這是由于隨著任務粒度的增加,任務的調度時間和發射時間占任務執行時間的比例降低。任務粒度為8×103、16×103的情況下,產生了鏈路的擁塞,存在鏈路擁塞的任務路徑執行時間增加,但是其余無擁塞的路徑沒有額外延遲,因此,系統的平均并行度下降。

圖10 平均并行度-任務粒度實驗結果

DDR存儲器讀寫延遲見表5所列,數據網延遲見表6所列。DDR存儲器的讀寫延遲被調度控制器節省,數據網上數據的傳輸延遲是調度器所增加的時間消耗。結果表明,在無擁塞的情況下,數據網上數據傳輸的時間與一次DDR存儲器的讀或者寫的延遲接近,而存在擁塞的情況下,數據網擁塞的時間與一次DDR存儲器的讀或者寫的延遲接近。從整體運行時間加速比和平均并行度的實驗中分析得到,發生鏈路擁塞時,系統的整體性能會發生明顯下降,無法達到預期的性能,因此,減少數據網的擁塞將是下一步優化性能的關鍵。

表5 DDR存儲器讀寫延遲

4.5 片上暫存實驗

為了檢測調度控制器在發生計算資源競爭導致后繼任務無法發射時,是否啟用片上暫存節點作為結果數據的暫存,設計如下實驗。任務流圖如圖11所示,圖中計算單元左上角的標號表示任務的ID編號。

圖11 任務流圖-發生計算資源競爭

任務1～任務8將8個RCU計算資源全部占用,且這8個任務的粒度均為2×103,任務9的粒度為0.256×103,因此任務9計算完成時,任務1～任務8還未結束,RCU單元仍被占用,其后繼任務(任務18,粒度0.256×103)將無法獲得足夠的計算資源,發生計算資源競爭。

片上暫存的實驗結果見表7所列,調度控制器按照預期的設想將任務9的結果數據寫入到暫存節點之中,且大幅節省了整體運行時間,這表明使用暫存節點技術能夠明顯提升系統整體性能。

表7 片上暫存實驗結果

本文從優化目標系統性能的角度出發,設計了一種面向異構多核處理器的多發射動態調度控制器。實驗測試結果表明,調度控制器在提升計算系統的整體性能、降低存儲器延遲等方面展現了良好的效果,并且調度控制器的功能正確,達到了預期動態任務調度和任務亂序多發射的目標。在任務粒度實驗中,結果表明數據網的擁塞是限制系統性能的關鍵要素,因此,在任務調度和任務的計算單元映射環節新增數據網擁塞的約束,并研究減少擁塞的方法,是下一步需要研究的重點。