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

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

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

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

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

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

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

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

本文面向的異構(gòu)多核計(jì)算系統(tǒng)整體結(jié)構(gòu)如圖1所示,系統(tǒng)主要包括主控制器、計(jì)算單元、通信網(wǎng)絡(luò)和功能單元。計(jì)算單元包括可重構(gòu)計(jì)算單元(reconfigurable computing unit,RCU)、通用浮點(diǎn)計(jì)算單元(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)多核計(jì)算系統(tǒng)整體結(jié)構(gòu)

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

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

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

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

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

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

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

在編程階段,編程者需要根據(jù)實(shí)際的算法指定任務(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ā)送給各個(gè)單元,這些單元包括計(jì)算單元、DDR存儲器和數(shù)據(jù)網(wǎng)節(jié)點(diǎn)等;FU表示三類計(jì)算單元。上述任務(wù)5條配置信息的含義如下:

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

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

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

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

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

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

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

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

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

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

實(shí)現(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)。因?yàn)槿我鈺r(shí)刻計(jì)算單元只會被某一個(gè)任務(wù)唯一占用,所以通過監(jiān)控計(jì)算單元的狀態(tài)就可以得到相應(yīng)任務(wù)的狀態(tài),從而實(shí)現(xiàn)對任務(wù)完整流程的監(jiān)控。同時(shí),使用狀態(tài)網(wǎng)可以統(tǒng)計(jì)得出空閑的與繁忙的計(jì)算單元個(gè)數(shù)。

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

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

(3) 配置網(wǎng)下發(fā)配置指令。在某一個(gè)任務(wù)滿足發(fā)射條件后,調(diào)度控制器將主程序中該任務(wù)的計(jì)算配置信息通過配置網(wǎng)傳遞給選中的計(jì)算單元,從而完成一次完整的任務(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ā)射;另一方面,由于動(dòng)態(tài)任務(wù)調(diào)度缺少程序的全局信息,不具備使用靜態(tài)調(diào)度算法找出關(guān)鍵路徑,實(shí)現(xiàn)較優(yōu)的任務(wù)優(yōu)先級排序的能力[7]。因此,本文在粗粒度上使用任務(wù)的初始編程次序作為調(diào)度優(yōu)先級次序;在細(xì)粒度上分析任務(wù)的可發(fā)射條件,對任務(wù)的發(fā)射次序進(jìn)行精細(xì)調(diào)整,實(shí)現(xiàn)亂序發(fā)射。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1.2 控制單元

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

3.2 任務(wù)喚醒

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

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

3.3 發(fā)射單元

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

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

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

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

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

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

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

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

表1 FPGA資源消耗

4.1 實(shí)驗(yàn)測試方案

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

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

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

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

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

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

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

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

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

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

(1)

(7) 整體運(yùn)行時(shí)間加速比(speedup of whole run time,SPWRT)。計(jì)算公式為:

(2)

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

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

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

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

4.4 并行任務(wù)的亂序多發(fā)射實(shí)驗(yàn)

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

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

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

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

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

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

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

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

圖7 整體運(yùn)行時(shí)間加速比

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

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

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

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

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

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

4.4.2 任務(wù)粒度實(shí)驗(yàn)

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

表4 任務(wù)運(yùn)行時(shí)間(周期)

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

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

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

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

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

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

表5 DDR存儲器讀寫延遲

4.5 片上暫存實(shí)驗(yàn)

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

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

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

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

表7 片上暫存實(shí)驗(yàn)結(jié)果

5 結(jié) 論

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