異構(gòu)多核處理器多發(fā)射動態(tài)調(diào)度技術(shù)研究

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

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

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

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

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

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

上述文獻(xiàn)未考慮系統(tǒng)的異構(gòu)特性、核間通信方式和存儲器的讀寫延遲等實際約束。本文在任務(wù)級并行自動提取技術(shù)、動態(tài)調(diào)度技術(shù)和亂序發(fā)射技術(shù)的基礎(chǔ)上,充分考慮系統(tǒng)的異構(gòu)特性、存儲器約束和核間通訊約束完成設(shè)計實現(xiàn),研究一種減少外部存儲器訪問開銷的方法,顯著提升了系統(tǒng)的性能。

1 多核計算系統(tǒng)整體結(jié)構(gòu)

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

圖1 異構(gòu)多核計算系統(tǒng)整體結(jié)構(gòu)

目標(biāo)異構(gòu)多核計算系統(tǒng)使用多層編程的方式完成預(yù)期的計算目標(biāo)。程序中的配置指令按照程序中確定的坐標(biāo)發(fā)送給對應(yīng)坐標(biāo)的計算單元,用于控制計算單元的計算方式,任務(wù)的發(fā)射過程嚴(yán)格遵從程序的預(yù)期設(shè)計,主控制器負(fù)責(zé)執(zhí)行控制指令,計算單元負(fù)責(zé)執(zhí)行計算指令進(jìn)行計算,由此實現(xiàn)多層編程。由于計算單元掛載在通信網(wǎng)絡(luò)上,也將計算單元稱為“計算節(jié)點”,下同。

三層網(wǎng)絡(luò)組成整個系統(tǒng)的控制、狀態(tài)、數(shù)據(jù)的交互通道。狀態(tài)網(wǎng)的作用是收集片上網(wǎng)絡(luò)中各個部件的工作狀態(tài),并反饋給主控制器。配置網(wǎng)的主要作用是負(fù)責(zé)傳送主控制器下發(fā)的各條配置信息給各個單元。數(shù)據(jù)網(wǎng)是片上各個單元之間大批量數(shù)據(jù)傳輸?shù)妮d體。數(shù)據(jù)網(wǎng)使用2D MESH的片上網(wǎng)絡(luò)(net on chip,NoC)作為拓?fù)浣Y(jié)構(gòu)。

2 多發(fā)射動態(tài)任務(wù)調(diào)度方案

2.1 任務(wù)的概念和分類

本文面向的目標(biāo)多核計算系統(tǒng)中,任務(wù)定義為一次計算過程,數(shù)據(jù)的起點是DDR存儲器,經(jīng)過運算單元運算,終點是DDR存儲器。本文將任務(wù)按照是否寫回DDR存儲器分為強寫回任務(wù)和弱寫回任務(wù)。

(1) 強寫回任務(wù)指必須將結(jié)果數(shù)據(jù)寫回DDR存儲器的任務(wù)。

(2) 弱寫回任務(wù)指結(jié)果數(shù)據(jù)可由調(diào)度器決策寫回DDR存儲器或者發(fā)射給下一個計算節(jié)點。

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

任務(wù)的編程規(guī)范舉例如下:

Task1

Configure FU cfg_info

Configure DDR.read address

Configure DDR dst=FU

Configure DDR.write address

Configure FU dst=DDR

Configure START

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

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

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

(3) 配置DDR存儲器的目的節(jié)點坐標(biāo)。

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

(5) 配置DDR存儲器的寫節(jié)點坐標(biāo)。

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

上述6條配置指令構(gòu)成了一個完整的從DDR存儲器取數(shù)、執(zhí)行、結(jié)果數(shù)據(jù)寫回DDR的運行流程。

2.2 任務(wù)依賴關(guān)系表

為了使調(diào)度控制器能夠準(zhǔn)確追蹤任務(wù)的數(shù)據(jù)相關(guān)性,以及在正確的時刻觸發(fā)任務(wù)的可執(zhí)行條件,需要在編程階段,預(yù)先記錄任務(wù)的數(shù)據(jù)相關(guān)性。同時為了讓調(diào)度控制器具有調(diào)度的基本依據(jù),需要新增任務(wù)依賴關(guān)系表,在任務(wù)依賴關(guān)系表中記錄任務(wù)的基本信息,并將任務(wù)依賴關(guān)系表中的內(nèi)容稱為任務(wù)標(biāo)簽。

2.3 動態(tài)任務(wù)調(diào)度和亂序發(fā)射的實現(xiàn)方案

實現(xiàn)方案是在系統(tǒng)原主控制器的基礎(chǔ)上新增調(diào)度控制器,控制任務(wù)調(diào)度和發(fā)射過程;狀態(tài)網(wǎng)負(fù)責(zé)檢測系統(tǒng)的狀態(tài),配置網(wǎng)負(fù)責(zé)下發(fā)配置信息。

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

(2) 調(diào)度控制器亂序多發(fā)射任務(wù)。通過監(jiān)測任務(wù)的執(zhí)行狀態(tài)和當(dāng)前時刻空閑的計算單元數(shù)量,再結(jié)合任務(wù)本身所需的計算單元的數(shù)量信息,可以判斷任務(wù)是否滿足可發(fā)射的條件:① 任務(wù)的所有前驅(qū)相關(guān)任務(wù)全部計算完成,結(jié)果數(shù)據(jù)已經(jīng)產(chǎn)生或者結(jié)果數(shù)據(jù)寫回DDR存儲器完成;② 當(dāng)前時刻系統(tǒng)上有足夠的計算資源。

滿足這2個條件的任務(wù)可以發(fā)射。調(diào)度控制器對每個任務(wù)的發(fā)射條件進(jìn)行嚴(yán)格檢查,保證了任務(wù)之間數(shù)據(jù)傳遞的安全性,為任務(wù)的亂序發(fā)射提供技術(shù)支撐。

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

2.4 任務(wù)調(diào)度優(yōu)先級策略

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

2.5 任務(wù)的寫回監(jiān)測和任務(wù)喚醒

對于強寫回類型的任務(wù),因為其計算結(jié)果數(shù)據(jù)必定寫回DDR存儲器,所以需要監(jiān)控其結(jié)果數(shù)據(jù)是否完成寫回DDR存儲器。

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

圖2 弱寫回任務(wù)不寫回DDR存儲器

對于弱寫回的任務(wù),對它的監(jiān)測分為如下2個階段:

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

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

2.6 動態(tài)任務(wù)鏈和啟用片上暫存

弱寫回任務(wù)組成動態(tài)任務(wù)鏈如圖3所示,將實際運行時不寫回DDR存儲器的弱寫回任務(wù)按照任務(wù)之間的數(shù)據(jù)相關(guān)性串聯(lián),組成動態(tài)任務(wù)鏈。

圖3 弱寫回任務(wù)組成動態(tài)任務(wù)鏈

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

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

完整的任務(wù)數(shù)據(jù)傳遞關(guān)系如圖4所示。

圖4 完整的任務(wù)數(shù)據(jù)傳遞關(guān)系

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

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

3 動態(tài)任務(wù)調(diào)度控制器架構(gòu)

3.1 動態(tài)調(diào)度控制器整體結(jié)構(gòu)

動態(tài)調(diào)度控制器整體結(jié)構(gòu)如圖5所示,控制器由取指仲裁模塊、任務(wù)標(biāo)簽緩存、任務(wù)標(biāo)簽隊列、配置信息緩存、任務(wù)配置信息隊列、控制單元、發(fā)射單元、狀態(tài)監(jiān)測單元組成,外圍集成到DDR存儲器的讀寫控制器、配置網(wǎng)和狀態(tài)網(wǎng)。

圖5 動態(tài)調(diào)度控制器整體結(jié)構(gòu)

3.1.1 狀態(tài)監(jiān)測單元

狀態(tài)監(jiān)測單元負(fù)責(zé)對任務(wù)的計算節(jié)點狀態(tài)和DDR存儲器的狀態(tài)進(jìn)行監(jiān)控,當(dāng)任務(wù)計算完成但數(shù)據(jù)未從節(jié)點發(fā)出,以及任務(wù)寫回DDR存儲器寫回完成時,任務(wù)狀態(tài)監(jiān)測單元能夠識別這2種狀態(tài),并將這2種狀態(tài)信息記錄在FIFO存儲器中,供控制單元讀取。

3.1.2 控制單元

控制單元負(fù)責(zé)動態(tài)調(diào)度控制器主狀態(tài)機的控制,同時通過任務(wù)標(biāo)簽信息、任務(wù)計算節(jié)點狀態(tài)信息以及DDR存儲器的狀態(tài)信息,對任務(wù)的喚醒、發(fā)射和寫回過程進(jìn)行決策,在確定待發(fā)射任務(wù)的編號后,向發(fā)射單元發(fā)送任務(wù)的基本信息和任務(wù)發(fā)射的啟動命令。

3.2 任務(wù)喚醒

在異構(gòu)多核計算系統(tǒng)中,任務(wù)計算完成、DDR存儲器的寫完成以及任務(wù)節(jié)點間數(shù)據(jù)傳輸完成,分別對應(yīng)著任務(wù)的寫回、DDR的釋放和計算單元的釋放。它們觸發(fā)了任務(wù)的可發(fā)射條件,因此,任務(wù)喚醒的時機是任務(wù)計算完成、空閑計算單元數(shù)量的增加和DDR存儲器寫回完成。

調(diào)度器的控制單元根據(jù)狀態(tài)監(jiān)測單元輸出的信息和空閑的計算資源數(shù)量,確定計算完成或者結(jié)果數(shù)據(jù)寫回DDR存儲器完成的任務(wù)編號,然后訪問任務(wù)標(biāo)簽隊列RAM,獲取任務(wù)的后繼輸出任務(wù)ID,將任務(wù)列表中后繼任務(wù)的狀態(tài)刷新成可發(fā)射。

3.3 發(fā)射單元

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

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

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

(2) 按照控制單元的調(diào)度決策對原始配置信息進(jìn)行相應(yīng)修改,或者生成新的配置信息。

(3) 將修改后的配置信息或者新生成的配置信息傳輸?shù)脚渲镁W(wǎng)上。

4 硬件設(shè)計實現(xiàn)和實驗測試

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

實現(xiàn)后最高電路主頻為166.058 MHz,動態(tài)調(diào)度器對FPGA的資源消耗見表1所列。

表1 FPGA資源消耗

4.1 實驗測試方案

本文從并行任務(wù)路徑數(shù)量、系統(tǒng)布局、任務(wù)的粒度、在計算資源發(fā)生競爭時的處理方法等維度,制定實驗方案,對調(diào)度控制器的功能和性能進(jìn)行測試。

在測試中,對比的對象是現(xiàn)有的異構(gòu)多核計算系統(tǒng),系統(tǒng)上不啟用新設(shè)計的調(diào)度控制器,但系統(tǒng)上仍然可使用手動并行編程的技術(shù)。在控制層,僅有系統(tǒng)主控制器順序發(fā)射配置指令。NoC網(wǎng)絡(luò)上掛載了3類計算單元,每個計算單元各有8個,總共24個計算核。

4.2 系統(tǒng)并行計算性能參數(shù)

本文參考文獻(xiàn)[14]選用下述參數(shù)反映計算系統(tǒng)運行的不同特征和任務(wù)調(diào)度控制器的性能指標(biāo)。設(shè)任務(wù)的總數(shù)為N。

(1) 任務(wù)調(diào)度時間,指從前驅(qū)任務(wù)計算完成或者寫回DDR完成,到后繼任務(wù)發(fā)射所消耗的周期數(shù)。

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

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

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

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

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

(1)

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

(2)

其中:new表示系統(tǒng)啟用調(diào)度控制器;old表示系統(tǒng)不啟用調(diào)度控制器。

4.3 任務(wù)平均調(diào)度時間隨任務(wù)數(shù)量變化實驗

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

表2 任務(wù)平均調(diào)度時間

4.4 并行任務(wù)的亂序多發(fā)射實驗

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

4.4.1 并行任務(wù)路徑數(shù)量實驗

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

圖6 兩路并行任務(wù)路徑示意

此外,對目標(biāo)異構(gòu)多核計算系統(tǒng)采用2種布局方式:一種是規(guī)整布局,同類的計算單元位置處于一條直線上;另一種是分散布局,不同種類的計算單元混合零散排布在NoC網(wǎng)絡(luò)上,每個計算單元周圍都分布著不同種類的計算單元。

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

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

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

圖7 整體運行時間加速比

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

圖8 平均并行度-任務(wù)路徑數(shù)量實驗結(jié)果

未能達(dá)到理論并行度的原因如下:

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

(2) 從任務(wù)計算完成到調(diào)度器響應(yīng),期間有額外的延遲,這包括任務(wù)狀態(tài)監(jiān)測模塊內(nèi)部的延遲和調(diào)度器響應(yīng)任務(wù)狀態(tài)監(jiān)測模塊的延遲。

(3) 在異構(gòu)多核計算系統(tǒng)上,隨著任務(wù)數(shù)量增多,計算資源的利用率提升,導(dǎo)致數(shù)據(jù)網(wǎng)負(fù)載加大,任務(wù)間數(shù)據(jù)傳輸延遲增大。

4.4.2 任務(wù)粒度實驗

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

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

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

圖9 整體運行時間加速比-任務(wù)粒度實驗結(jié)果

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

平均并行度-任務(wù)粒度實驗結(jié)果如圖10所示,在任務(wù)粒度從0.256×103增加到4×103過程中,平均并行度逐漸逼近理論并行度,這是由于隨著任務(wù)粒度的增加,任務(wù)的調(diào)度時間和發(fā)射時間占任務(wù)執(zhí)行時間的比例降低。任務(wù)粒度為8×103、16×103的情況下,產(chǎn)生了鏈路的擁塞,存在鏈路擁塞的任務(wù)路徑執(zhí)行時間增加,但是其余無擁塞的路徑?jīng)]有額外延遲,因此,系統(tǒng)的平均并行度下降。

圖10 平均并行度-任務(wù)粒度實驗結(jié)果

DDR存儲器讀寫延遲見表5所列,數(shù)據(jù)網(wǎng)延遲見表6所列。DDR存儲器的讀寫延遲被調(diào)度控制器節(jié)省,數(shù)據(jù)網(wǎng)上數(shù)據(jù)的傳輸延遲是調(diào)度器所增加的時間消耗。結(jié)果表明,在無擁塞的情況下,數(shù)據(jù)網(wǎng)上數(shù)據(jù)傳輸?shù)臅r間與一次DDR存儲器的讀或者寫的延遲接近,而存在擁塞的情況下,數(shù)據(jù)網(wǎng)擁塞的時間與一次DDR存儲器的讀或者寫的延遲接近。從整體運行時間加速比和平均并行度的實驗中分析得到,發(fā)生鏈路擁塞時,系統(tǒng)的整體性能會發(fā)生明顯下降,無法達(dá)到預(yù)期的性能,因此,減少數(shù)據(jù)網(wǎng)的擁塞將是下一步優(yōu)化性能的關(guān)鍵。

表5 DDR存儲器讀寫延遲

4.5 片上暫存實驗

為了檢測調(diào)度控制器在發(fā)生計算資源競爭導(dǎo)致后繼任務(wù)無法發(fā)射時,是否啟用片上暫存節(jié)點作為結(jié)果數(shù)據(jù)的暫存,設(shè)計如下實驗。任務(wù)流圖如圖11所示,圖中計算單元左上角的標(biāo)號表示任務(wù)的ID編號。

圖11 任務(wù)流圖-發(fā)生計算資源競爭

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

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

表7 片上暫存實驗結(jié)果

5 結(jié) 論

本文從優(yōu)化目標(biāo)系統(tǒng)性能的角度出發(fā),設(shè)計了一種面向異構(gòu)多核處理器的多發(fā)射動態(tài)調(diào)度控制器。實驗測試結(jié)果表明,調(diào)度控制器在提升計算系統(tǒng)的整體性能、降低存儲器延遲等方面展現(xiàn)了良好的效果,并且調(diào)度控制器的功能正確,達(dá)到了預(yù)期動態(tài)任務(wù)調(diào)度和任務(wù)亂序多發(fā)射的目標(biāo)。在任務(wù)粒度實驗中,結(jié)果表明數(shù)據(jù)網(wǎng)的擁塞是限制系統(tǒng)性能的關(guān)鍵要素,因此,在任務(wù)調(diào)度和任務(wù)的計算單元映射環(huán)節(jié)新增數(shù)據(jù)網(wǎng)擁塞的約束,并研究減少擁塞的方法,是下一步需要研究的重點。