PPTM:一種面向異構(gòu)系統(tǒng)的主動(dòng)式任務(wù)映射方法①

龔施俊 鄢貴海 李曉維

(*中國科學(xué)院計(jì)算技術(shù)研究所計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室 北京100190)

(**中國科學(xué)院大學(xué) 北京100049)

0 引言

隨著半導(dǎo)體芯片制程工藝發(fā)展,晶體管尺寸不斷逼近物理極限,摩爾定律逐步放緩[1-4],實(shí)現(xiàn)性能提升愈發(fā)依賴于新的體系結(jié)構(gòu)設(shè)計(jì)方法。領(lǐng)域?qū)Ｓ皿w系結(jié)構(gòu)(domain-specific architecture,DSA)針對(duì)特定問題域定制體系結(jié)構(gòu),具有顯著的性能和能效優(yōu)勢(shì)。DSA 通常被稱為“加速器”,因?yàn)榕c通用CPU上執(zhí)行整個(gè)應(yīng)用程序相比,它們只會(huì)加速某些應(yīng)用程序。典型加速器有GPU、TPU[4-5]和用于軟件定義網(wǎng)絡(luò)(software define network,SDN)的處理器[6]等。

類似于通用CPU 需要操作系統(tǒng)驅(qū)動(dòng),之前的工作中,針對(duì)不同的加速場(chǎng)景或加速器涌現(xiàn)了許多成熟高效的異構(gòu)加速系統(tǒng)或者框架,如OpenCL[7-8]、CUDA[9]、基于OpenVX[10]的AMDOVX[11]以及TensorFlow[12]等。這些系統(tǒng)運(yùn)行時(shí)將識(shí)別加速可行性并決定如何利用加速器的責(zé)任轉(zhuǎn)移給程序員,這對(duì)程序員提出了更高的要求,需要程序員熟悉加速器的底層實(shí)現(xiàn)細(xì)節(jié)。這導(dǎo)致程序員水平的個(gè)體差異對(duì)程序性能的影響巨大,差別甚至達(dá)到數(shù)千倍[1],其主要原因是異構(gòu)系統(tǒng)環(huán)境下的任務(wù)映射的差異。

為實(shí)現(xiàn)在異構(gòu)系統(tǒng)中高效的任務(wù)映射,之前的工作提出了很多基于任務(wù)在不同處理上的執(zhí)行性能和如何最小任務(wù)之間的通信開銷等的調(diào)度算法[13-18]。這些工作一般采用計(jì)算流圖來表示應(yīng)用,每個(gè)節(jié)點(diǎn)代表一個(gè)計(jì)算任務(wù),然后將這些任務(wù)在滿足某些限制條件下,如最小化通信開銷、最小化執(zhí)行時(shí)間等,將其調(diào)度到加速器上執(zhí)行。但是,我們發(fā)現(xiàn)針對(duì)某些應(yīng)用場(chǎng)景,基于執(zhí)行時(shí)間快慢來進(jìn)行任務(wù)調(diào)度無法攤銷計(jì)算節(jié)點(diǎn)之間的通信開銷,同時(shí)在特地處理數(shù)據(jù)規(guī)模時(shí),相比于CPU 加速器對(duì)計(jì)算核能帶來的加速比有限。在這種情況下,將計(jì)算節(jié)點(diǎn)映射到加速器上執(zhí)行帶來的性能增益將因整個(gè)應(yīng)用程序存在主機(jī)端(HOST)與加速器設(shè)備端的通信開銷而被部分抵消掉,大幅降低了預(yù)期的性能提升。

為了解決上述問題,本文提出了一種基于預(yù)測(cè)的主動(dòng)式任務(wù)映射算法(prediction-based proactive task mapping algorithm,PPTM)。首先,通過預(yù)測(cè)算法動(dòng)態(tài)調(diào)整計(jì)算節(jié)點(diǎn)的運(yùn)行時(shí)屬性,包括不同計(jì)算平臺(tái)的執(zhí)行時(shí)間和平臺(tái)之間的通信開銷等。然后,基于計(jì)算節(jié)點(diǎn)的性能增益和額外開銷數(shù)據(jù)來設(shè)計(jì)任務(wù)映射算法,完成計(jì)算流圖中任務(wù)節(jié)點(diǎn)在異構(gòu)平臺(tái)上的映射。最后,通過一個(gè)案例研究來驗(yàn)證該算法的有效性。

本文的主要貢獻(xiàn)包括以下4 個(gè)方面。

(1)提出了一種面向異構(gòu)加速系統(tǒng)的高效任務(wù)映射方法。該算法可以精確捕捉任務(wù)運(yùn)行時(shí)特征來完成應(yīng)用程序在異構(gòu)加速平臺(tái)上的任務(wù)映射,從而提高應(yīng)用整體性能。

(2)發(fā)現(xiàn)在一個(gè)應(yīng)用程序的計(jì)算流圖中,雖然將計(jì)算節(jié)點(diǎn)映射到加速器上執(zhí)行能帶來較大的加速比,但是需要根據(jù)整個(gè)應(yīng)用程序的計(jì)算流圖來考慮其映射行為,否則可能無法帶來性能增益。

(3)發(fā)現(xiàn)針對(duì)整個(gè)應(yīng)用程序,并不是降低的通信開銷越多,性能提升就越大,而是需要針對(duì)特定應(yīng)用以及運(yùn)行時(shí)數(shù)據(jù)來權(quán)衡。

(4)案例研究。本文以面向流式應(yīng)用的加速器為例,來評(píng)估PPTM 及其他映射算法的性能。這一案例研究的結(jié)論也可以推廣到面向其他應(yīng)用領(lǐng)域的加速器上。

1 相關(guān)工作

1.1 異構(gòu)加速系統(tǒng)與任務(wù)映射

在數(shù)據(jù)高速增長的背景下,異構(gòu)計(jì)算是滿足新興應(yīng)用不斷提高算力需求的有效途徑[19]。為了更好地發(fā)揮專用加速器的性能以及給用戶提供更加優(yōu)化的編程接口,涌現(xiàn)了很多成熟高效的異構(gòu)加速系統(tǒng)。OpenCL 提出了面向異構(gòu)設(shè)備上編程的行業(yè)標(biāo)準(zhǔn),通過它可以將應(yīng)用程序的計(jì)算密集型部分卸載到加速設(shè)備上從而提高應(yīng)用程序性能,它的目的是為異構(gòu)系統(tǒng)提供統(tǒng)一的開發(fā)平臺(tái)[20]。OpenCL 將主機(jī)與加速設(shè)備的交互方式進(jìn)行了統(tǒng)一的抽象,并提供統(tǒng)一的編程語言。用戶可以在程序池中選擇由設(shè)備商實(shí)現(xiàn)的kernel 程序來完成對(duì)加速設(shè)備的調(diào)用,然后在主機(jī)或設(shè)備上創(chuàng)建存儲(chǔ)單元,通過主機(jī)端與設(shè)備端的數(shù)據(jù)復(fù)制來完成設(shè)備端程序與主機(jī)端程序之間的數(shù)據(jù)交互,從而實(shí)現(xiàn)對(duì)底層加速器的透明化管理。CUDA 作為英偉達(dá)的商業(yè)化異構(gòu)加速系統(tǒng),其最終目的是支持面向通用計(jì)算的GPU(generalpurpose computing on graphics processing units,GPGPU)。CUDA 提供統(tǒng)一的開發(fā)套件,并封裝實(shí)現(xiàn)了很多高效計(jì)算庫(cuFFT、cuBLAS 等)以及提供了統(tǒng)一的高效成熟的NVCC 編譯器,相比于OpenCL 依賴于設(shè)備商的驅(qū)動(dòng)實(shí)現(xiàn),對(duì)用戶更加友好[9]。TensorFlow[21]作為Google 開源的數(shù)據(jù)流圖科學(xué)計(jì)算庫,主要用于機(jī)器學(xué)習(xí)等人工智能領(lǐng)域。通過提供眾多機(jī)器學(xué)習(xí)領(lǐng)域抽象核函數(shù)實(shí)現(xiàn),用戶可以選擇其構(gòu)建特定的機(jī)器學(xué)習(xí)算法,降低了機(jī)器學(xué)習(xí)算法的設(shè)計(jì)門檻。在底層可以對(duì)接CUDA 等加速器運(yùn)行時(shí)系統(tǒng),來支持異構(gòu)計(jì)算[15]。

在之前的異構(gòu)加速系統(tǒng)中,程序員的主要工作是將一個(gè)應(yīng)用程序劃分成不同的計(jì)算任務(wù),調(diào)用異構(gòu)加速系統(tǒng)提供的核函數(shù)來實(shí)現(xiàn)特定的計(jì)算任務(wù),并通過在加速器上執(zhí)行來提高整個(gè)應(yīng)用程序的性能。因此,一個(gè)應(yīng)用程序在異構(gòu)平臺(tái)上如何高效地進(jìn)行任務(wù)映射就顯得至關(guān)重要,這關(guān)系到整個(gè)應(yīng)用程序的實(shí)際性能,對(duì)程序員提出了更大的挑戰(zhàn)。

之前的工作中,涌現(xiàn)了諸多針對(duì)異構(gòu)多處理器的任務(wù)調(diào)度優(yōu)化算法。文獻(xiàn)[15]根據(jù)異構(gòu)處理器的任務(wù)執(zhí)行時(shí)間,提出了2 種啟發(fā)式算法來最小化應(yīng)用程序在異構(gòu)平臺(tái)上的執(zhí)行時(shí)間。而文獻(xiàn)[17]和[14]則為了能最小化任務(wù)之間的通信開銷提出了相關(guān)的任務(wù)映射算法。當(dāng)然,還有很多調(diào)度算法[16,22-29],但是這些工作通常是考慮不同應(yīng)用在加速器設(shè)備上的差異表現(xiàn)來決定最合適的任務(wù)映射方式,這與本文提出的在特定的應(yīng)用程序中有些任務(wù)被映射到加速器上會(huì)降低應(yīng)用程序整體性能還是有所差異的。

1.2 計(jì)算流圖

計(jì)算流圖通常是一個(gè)有向無環(huán)圖,其中的每一個(gè)節(jié)點(diǎn)都類似于一個(gè)函數(shù)調(diào)用,代表一個(gè)計(jì)算核,節(jié)點(diǎn)間的有向邊代表了數(shù)據(jù)的輸入輸出關(guān)系[2]。其定義如下:

定義1 計(jì)算流圖由二元組G=(V,E)表示,其中V為節(jié)點(diǎn)或頂點(diǎn)的有限集合,每個(gè)節(jié)點(diǎn)表示一個(gè)計(jì)算核;E為有向邊的有限集合,邊表示計(jì)算核之間通信或依賴關(guān)系。每條邊是一個(gè)有序二元組e=(v1,v2),其中v1,v2∈V。如果e=(v1,v2) ∈E,則邊e從v1指向v2,且稱v1是v2的依賴。

通過將應(yīng)用表達(dá)成計(jì)算流圖,可以方便地描述計(jì)算之間的依賴關(guān)系,然后通過合適的調(diào)度算法可以大幅減少加速器中的控制,還可以提高計(jì)算并行度。因此在之前的異構(gòu)多處理器任務(wù)映射算法研究中,基于計(jì)算流圖的計(jì)算任務(wù)表示方式被大量運(yùn)用。此外,在成熟的異構(gòu)加速系統(tǒng)TensorFlow 中也使用計(jì)算流圖作為計(jì)算任務(wù)的表達(dá)形式。在本文的算法設(shè)計(jì)中,將基于計(jì)算流圖來表達(dá)應(yīng)用程序中的計(jì)算任務(wù),并基于此來優(yōu)化調(diào)度。

2 問題描述

在異構(gòu)加速系統(tǒng)中,通過計(jì)算流圖表達(dá)的應(yīng)用程序,往往存在一些計(jì)算節(jié)點(diǎn)無法在加速器上執(zhí)行。因?yàn)榧铀倨魍ǔＪ穷I(lǐng)域?qū)Ｓ玫?只會(huì)加速整個(gè)應(yīng)用程序中的一部分。這導(dǎo)致在整個(gè)計(jì)算流圖中存在“柵欄”[30-31]節(jié)點(diǎn)。所謂柵欄節(jié)點(diǎn),就是在計(jì)算流圖中,當(dāng)前節(jié)點(diǎn)與其依賴節(jié)點(diǎn)支持運(yùn)行的平臺(tái)不同。這里只考慮主機(jī)(HOST)和加速器(設(shè)備)兩種計(jì)算平臺(tái),因此,柵欄節(jié)點(diǎn)表示這些計(jì)算核節(jié)點(diǎn)沒法在加速器上執(zhí)行,而其他節(jié)點(diǎn)表示既可以在CPU 上也可以在加速器上執(zhí)行。所以,柵欄節(jié)點(diǎn)致使HOST 和加速器設(shè)備被迫進(jìn)行數(shù)據(jù)交互,從而帶來通信開銷,導(dǎo)致整個(gè)應(yīng)用程序性能下降。在一些特殊應(yīng)用場(chǎng)景中,計(jì)算流圖中存在的柵欄節(jié)點(diǎn)可能會(huì)導(dǎo)致其依賴節(jié)點(diǎn)或者被依賴節(jié)點(diǎn)映射到加速器上執(zhí)行反而無法帶來性能增益。為了更清晰地說明這個(gè)問題,本文設(shè)計(jì)了如圖1 所示的計(jì)算流圖。

圖1 計(jì)算流圖示例

圖中給出了一個(gè)基于由10 個(gè)計(jì)算核節(jié)點(diǎn)組成的有向無環(huán)圖來表達(dá)的應(yīng)用程序,并用黑色標(biāo)識(shí)柵欄節(jié)點(diǎn)。如圖1 所示,v1和v5是柵欄節(jié)點(diǎn),并且將是任務(wù)映射時(shí)需要特別考慮的點(diǎn)。因?yàn)?柵欄節(jié)點(diǎn)與其依賴節(jié)點(diǎn)存在HOST 與加速器設(shè)備的數(shù)據(jù)交互,同時(shí)由于依賴關(guān)系,必須等待依賴節(jié)點(diǎn)執(zhí)行完成才能開始下一步的計(jì)算,這將帶來額外的通信開銷從而降低整個(gè)應(yīng)用程序的性能。為了降低柵欄節(jié)點(diǎn)對(duì)整個(gè)應(yīng)用帶來的性能影響,對(duì)其依賴節(jié)點(diǎn)完成高效的任務(wù)映射將是至關(guān)重要的。

用C表示計(jì)算流圖中2 個(gè)依賴節(jié)點(diǎn)之間的通信延遲的有限集合,如果c1∈C,則稱c1是計(jì)算核節(jié)點(diǎn)v1與被依賴節(jié)點(diǎn)之間的通信開銷。假設(shè),如果2 個(gè)依賴節(jié)點(diǎn)映射的計(jì)算平臺(tái)相同,則它們之間的通信延遲為零。用S表示計(jì)算核節(jié)點(diǎn)運(yùn)行在加速器上時(shí)相對(duì)于CPU 能夠帶來的性能增益的有限集合,如果s5∈S,則稱s5代表節(jié)點(diǎn)v5的性能增益。由于其無法在加速器上執(zhí)行,令其等于零,即無性能增益。在圖1 中,v9節(jié)點(diǎn)如果要調(diào)度到加速器上執(zhí)行,需要將結(jié)果數(shù)據(jù)從加速器上讀回(假設(shè)待處理數(shù)據(jù)已經(jīng)提前在平臺(tái)準(zhǔn)備好),這將帶來額外的通信開銷。很容易可以得出,如果s9＜c9,節(jié)點(diǎn)v9并不適合調(diào)度到加速器上執(zhí)行?；谝陨嫌^察,首先,假設(shè)在計(jì)算流圖中調(diào)度節(jié)點(diǎn)到加速器上執(zhí)行帶來的通信開銷用Φ表示,節(jié)點(diǎn)在加速器上執(zhí)行帶來的增益用X表示。然后,給出如下推論:

在計(jì)算流圖中,將節(jié)點(diǎn)映射到加速器上執(zhí)行并不總能帶來性能增益,假設(shè)只考慮通信開銷,需要滿足條件,即在加速器上執(zhí)行的增益能夠覆蓋通信開銷,即X≥Φ。

圖1 中,在處理特定數(shù)據(jù)大小時(shí),CPU 完全可以把處理數(shù)據(jù)全部放到內(nèi)存中,訪存不會(huì)成為CPU的性能瓶頸而導(dǎo)致CPU 處理性能降低。因此,在接下來的討論中,假設(shè)整個(gè)應(yīng)用程序處理的數(shù)據(jù)規(guī)模是能全部裝載到主機(jī)的內(nèi)存中的。計(jì)算核節(jié)點(diǎn)v9,由于其被依賴節(jié)點(diǎn)v5不能在加速器上執(zhí)行,如果整個(gè)通信開銷超過了加速器能夠帶來的性能增益,在執(zhí)行調(diào)度的時(shí)候,如果能將v9調(diào)度到CPU 上來執(zhí)行,對(duì)于提升應(yīng)用的整體性能將是更優(yōu)的調(diào)度策略。

在現(xiàn)有的異構(gòu)加速系統(tǒng)中,運(yùn)行時(shí)系統(tǒng)將識(shí)別加速可行性和決定如何利用加速器的責(zé)任轉(zhuǎn)移給程序員,如OpenCL 需要實(shí)現(xiàn)專門的計(jì)算核,CUDA 和TensorFlow 提供了核函數(shù)庫供用戶調(diào)用,這對(duì)程序員提出了更高的要求。為了獲得更高的性能需要,程序員需要了解加速器的底層細(xì)節(jié),如加速器的存儲(chǔ)體系和處理性能等。除此之外,這些特性都會(huì)隨著應(yīng)用運(yùn)行時(shí)動(dòng)態(tài)地改變,這極大地增加了調(diào)度優(yōu)化的復(fù)雜度。

針對(duì)存在的問題,本文提出了基于預(yù)測(cè)的主動(dòng)式任務(wù)映射算法,即通過預(yù)測(cè)算法動(dòng)態(tài)調(diào)整計(jì)算節(jié)點(diǎn)的運(yùn)行時(shí)屬性,完成計(jì)算流圖中任務(wù)在異構(gòu)平臺(tái)的映射。

3 PPTM 算法設(shè)計(jì)

在之前的工作中,面向多處理器的計(jì)算流圖調(diào)度優(yōu)化通常會(huì)考慮任務(wù)在處理器上的執(zhí)行時(shí)間和通信開銷[14-15],如果是實(shí)時(shí)任務(wù)還會(huì)考慮如何滿足延遲要求,在此基礎(chǔ)上來最大化應(yīng)用程序性能。文算法設(shè)計(jì)只考慮計(jì)算核節(jié)點(diǎn)在加速器上執(zhí)行所能帶來的性能增益,用X表示,以及為此需要付出的額外開銷。這些開銷可以是數(shù)據(jù)通過PCIe 在主機(jī)端和設(shè)備端的傳輸延遲以及程序額外編譯時(shí)間等,統(tǒng)稱為通信開銷并用Φ表示。因此,PPTM 算法主要解決的問題可以抽象成,對(duì)于給定的應(yīng)用程序A所表達(dá)的計(jì)算流圖G=(V,E),根據(jù)節(jié)點(diǎn)在加速器上性能增益X和為了在加速器上執(zhí)行所帶來的通信開銷Φ,求得一個(gè)最優(yōu)的圖節(jié)點(diǎn)在異構(gòu)平臺(tái)上的映射方案G′,也即圖節(jié)點(diǎn)的最優(yōu)調(diào)度序列(v′1,v′2,…,v′n) ∈V,可以表示為

G′i=(v′i1,v′i2,…,v′in)=f(G,X,Φ),使得P(G′i)=max(P(G′i)),其中G′i∈G′i,在這里,使用P函數(shù)去表示求一個(gè)計(jì)算流圖的性能,f函數(shù)表示根據(jù)給定的限制條件獲得一個(gè)映射方案G′。

同時(shí),參考之前的工作,針對(duì)多處理器的任務(wù)映射問題通常是基于給定的處理器性能數(shù)據(jù)。然而,不管是處理器性能還是通信開銷,這些都會(huì)隨著任務(wù)的不同,而在運(yùn)行時(shí)動(dòng)態(tài)地變化。如果調(diào)度算法只根據(jù)歷史給定的數(shù)據(jù)來進(jìn)行任務(wù)映射,將無法適應(yīng)實(shí)際的應(yīng)用場(chǎng)景,如加速器性能在實(shí)際場(chǎng)景中沒法全部發(fā)揮、PCIe 帶寬實(shí)際上沒有那么高等。因此,本文基于一元線性回歸模型,針對(duì)計(jì)算節(jié)點(diǎn)在CPU 和加速器上的執(zhí)行時(shí)間以及節(jié)點(diǎn)之間的通信開銷,分別實(shí)現(xiàn)了對(duì)應(yīng)的預(yù)測(cè)模塊。首先通過線性擬合給定的歷史數(shù)據(jù)得到一個(gè)初步預(yù)測(cè)模型,然后會(huì)根據(jù)運(yùn)行時(shí)節(jié)點(diǎn)性能數(shù)據(jù),不斷調(diào)整整個(gè)預(yù)測(cè)模型。相關(guān)模型如下:

其中,CXi代表計(jì)算核節(jié)點(diǎn)i在CPU 上執(zhí)行時(shí)的預(yù)測(cè)時(shí)間。假設(shè)節(jié)點(diǎn)i能在加速器上執(zhí)行,則AXi代表其在加速器上執(zhí)行時(shí)的預(yù)測(cè)時(shí)間,相應(yīng)的cxi和axi表示實(shí)際的節(jié)點(diǎn)在CPU 和加速器上的執(zhí)行時(shí)間的測(cè)量值。I代表節(jié)點(diǎn)處理數(shù)據(jù)的規(guī)模。Ci則表示節(jié)點(diǎn)與依賴節(jié)點(diǎn)的通信開銷的預(yù)測(cè)值,對(duì)應(yīng)的ci則為實(shí)際測(cè)量值。因此,對(duì)于計(jì)算節(jié)點(diǎn)在加速器上的性能增益,可以簡(jiǎn)單地表示為Xi=AXi -CXi。

求解該問題的難點(diǎn)在于,修改某個(gè)節(jié)點(diǎn)的調(diào)度行為之后,會(huì)影響到其依賴與被依賴節(jié)點(diǎn)的性能,從而產(chǎn)生調(diào)度的傳播性影響,因此獲取一個(gè)最優(yōu)的任務(wù)映射方案,將是一個(gè)NP 問題。對(duì)此,本文給出一個(gè)基于性能增益?zhèn)鬟f的啟發(fā)式的求解算法,也就是在決定節(jié)點(diǎn)是否映射到加速器上執(zhí)行時(shí),不只是根據(jù)當(dāng)前節(jié)點(diǎn)的性能增益,而是累計(jì)其相關(guān)子節(jié)點(diǎn)的性能增益來判斷性能增益是否能覆蓋通信開銷。如果性能增益能覆蓋通信開銷則將其映射到加速器上執(zhí)行,否則映射到CPU 上執(zhí)行。如果將其映射到CPU 上執(zhí)行,則接著需要遞歸重新調(diào)度其相關(guān)子節(jié)點(diǎn)。當(dāng)然,如果在計(jì)算流圖中,節(jié)點(diǎn)的輸入是柵欄節(jié)點(diǎn),在計(jì)算性能增益時(shí)將會(huì)考慮相關(guān)的通信開銷。雖然,本文提出的求解算法是局部?jī)?yōu)化的,但是在考慮的應(yīng)用中,柵欄節(jié)點(diǎn)作為一個(gè)分界點(diǎn),柵欄節(jié)點(diǎn)上下游數(shù)據(jù)肯定來源于CPU。因此,只考慮其父節(jié)點(diǎn)是否是柵欄節(jié)點(diǎn),然后再來遞歸修改子節(jié)點(diǎn)的任務(wù)映射算法,也能求出一個(gè)比較全局優(yōu)化的映射方案。

圖2 給出了PPTM 算法的流程圖,圖中使用的性能數(shù)據(jù)來自于預(yù)測(cè)模塊,為簡(jiǎn)潔起見圖中沒有畫出預(yù)測(cè)模塊。

圖2 PPTM 算法流程圖

如圖2 所示,從應(yīng)用程序計(jì)算流圖的非柵欄節(jié)點(diǎn)的加速器可執(zhí)行的葉子節(jié)點(diǎn)開始遍歷整個(gè)圖節(jié)點(diǎn)。首先判斷節(jié)點(diǎn)是否有父節(jié)點(diǎn),如果沒有,則說明調(diào)度來到了根節(jié)點(diǎn),進(jìn)入調(diào)度流程。否則,判斷其父節(jié)點(diǎn)是否是柵欄節(jié)點(diǎn),如果不是柵欄節(jié)點(diǎn),將根據(jù)預(yù)測(cè)得到的加速器性能增益累加到其父節(jié)點(diǎn)的性能增益上,然后接著遍歷圖節(jié)點(diǎn)。否則,接著判斷節(jié)點(diǎn)與父節(jié)點(diǎn)的通信開銷是否高于性能增益,如果是,將節(jié)點(diǎn)映射到CPU 上執(zhí)行,并將其相關(guān)的子節(jié)點(diǎn)重新加入到節(jié)點(diǎn)遍歷池中進(jìn)行重新映射。否則,將節(jié)點(diǎn)映射到加速器上執(zhí)行,接著判斷是否整個(gè)圖已經(jīng)遍歷完成,如果遍歷完成則結(jié)束算法,否則繼續(xù)算法執(zhí)行。算法1 給出了PPTM的偽代碼實(shí)現(xiàn)。

4 示例研究

為了驗(yàn)證算法設(shè)計(jì)的有效性,并為將來面向加速器的運(yùn)行時(shí)系統(tǒng)設(shè)計(jì)提供參考,本文將針對(duì)之前的工作,面向流式應(yīng)用的加速器平臺(tái)ShuntFlow[3],也即面向計(jì)算核的處理器(kernel processing unit,KPU),設(shè)計(jì)和實(shí)現(xiàn)運(yùn)行時(shí)系統(tǒng)(kernel operating system,KOS),并實(shí)現(xiàn)本文提出的任務(wù)映射方法。首先介紹ShuntFlow 加速器的硬件結(jié)構(gòu),然后介紹整個(gè)KOS的架構(gòu)以及相關(guān)實(shí)現(xiàn)細(xì)節(jié)。

4.1 核處理器KPU

圖3 給出了ShuntFlow(KPU)架構(gòu)圖[32]。KPU加速器主要加速實(shí)現(xiàn)了一系列流式應(yīng)用中的聚合算子,這些算子在流式數(shù)據(jù)挖掘、金融風(fēng)控等領(lǐng)域被廣泛應(yīng)用[33],可以被看成是多個(gè)計(jì)算核,從而可以將KPU 抽象成由多個(gè)計(jì)算核組成的加速器平臺(tái)。表1給出了一個(gè)KPU 加速器實(shí)現(xiàn)的計(jì)算核的相關(guān)信息。

圖3 ShuntFlow(KPU)加速器架構(gòu)圖

表1 KPU 計(jì)算核實(shí)現(xiàn)信息

在本文的實(shí)例中,KPU 總共實(shí)現(xiàn)了6 類計(jì)算核,其中加速比是對(duì)比CPU 不考慮數(shù)據(jù)傳輸延遲時(shí),KPU 能夠帶來性能的提升,同時(shí)可以看出不同計(jì)算核能夠?qū)崿F(xiàn)的加速比是不一樣的。輸入數(shù)代表計(jì)算核需要幾個(gè)輸入數(shù)據(jù),包括參數(shù)在內(nèi)。

4.2 KOS 實(shí)現(xiàn)

首先,給出KOS 針對(duì)KPU 加速器的架構(gòu),在這里只給出支持KPU 和CPU 兩個(gè)平臺(tái)的實(shí)現(xiàn),多平臺(tái)的實(shí)現(xiàn)可以很方便地進(jìn)行擴(kuò)展。然后,將詳細(xì)介紹針對(duì)KPU 加速器怎么實(shí)現(xiàn)PPTM 算法進(jìn)行性能優(yōu)化。最后,介紹了一些應(yīng)用,用于下一節(jié)的測(cè)評(píng)。

圖4 給出了KOS 針對(duì)KPU的架構(gòu)圖,接下來,將簡(jiǎn)單介紹一些模塊的功能。

圖4 KOS 架構(gòu)圖

KOS API主要包括計(jì)算流圖構(gòu)建、數(shù)據(jù)注冊(cè)、計(jì)算核注冊(cè)以及加速器相關(guān)屬性注冊(cè)等接口。針對(duì)KPU 需要注冊(cè)的硬件屬性,包括特定數(shù)據(jù)大小傳輸開銷和硬件上計(jì)算核實(shí)現(xiàn)信息(見表1)等。

Memory Master采用BFC 算法來完成KOS內(nèi)存管理,統(tǒng)一管理KOS 中的內(nèi)存分配,回收內(nèi)存碎片,降低內(nèi)存分配開銷。

Kernel Master主要負(fù)責(zé)接收注冊(cè)的計(jì)算核信息,并提供給計(jì)算流圖構(gòu)建模塊計(jì)算流圖,并對(duì)節(jié)點(diǎn)進(jìn)行標(biāo)識(shí)。

Graph Master主要負(fù)責(zé)計(jì)算核節(jié)點(diǎn)的創(chuàng)建和釋放,并根據(jù)計(jì)算核節(jié)點(diǎn)負(fù)責(zé)管理計(jì)算流圖。

Hardware Resource Master提供加速器資源以及性能數(shù)據(jù)配置接口,并負(fù)責(zé)對(duì)加速器資源的分配和釋放以及為性能預(yù)測(cè)器提供性能數(shù)據(jù)。

Data Master負(fù)責(zé)管理源數(shù)據(jù)和結(jié)果數(shù)據(jù),同時(shí)提供接口,可以在不同節(jié)點(diǎn)或者平臺(tái)之間完成數(shù)據(jù)格式的轉(zhuǎn)換。

Distributed Manager主要負(fù)責(zé)根據(jù)平臺(tái)信息等完成計(jì)算流圖的調(diào)度,同時(shí)為了優(yōu)化調(diào)度實(shí)現(xiàn)性能預(yù)測(cè)器。針對(duì)KPU,需要滿足KPU 能夠支持的最大計(jì)算核并行執(zhí)行的資源限制,同時(shí)能夠根據(jù)注冊(cè)的通信開銷、計(jì)算核加速比等信息,針對(duì)應(yīng)用不同的數(shù)據(jù)大小等完成性能預(yù)測(cè)。

Dataflow Executor實(shí)現(xiàn)記分板算法,完成最小調(diào)度單位,計(jì)算流子圖在不同平臺(tái)的執(zhí)行。

CPU&GPU Executor負(fù)責(zé)針對(duì)特定的平臺(tái)完成子圖的解析,然后根據(jù)子圖的依賴關(guān)系,并行或者串行調(diào)度計(jì)算核節(jié)點(diǎn)到特定平臺(tái)完成計(jì)算并返回計(jì)算結(jié)果。

YCC&CFD針對(duì)特定加速器平臺(tái)KPU 實(shí)現(xiàn)的編譯器和驅(qū)動(dòng)層,主要負(fù)責(zé)將計(jì)算核節(jié)點(diǎn)解析成平臺(tái)二進(jìn)制指令,然后通過特定的傳輸協(xié)議完成與加速器的交互。

4.2.1 性能優(yōu)化——PPTM 算法實(shí)現(xiàn)

如前面PPTM 算法的設(shè)計(jì)所述,PPTM 算法要完成計(jì)算節(jié)點(diǎn)的執(zhí)行時(shí)間預(yù)測(cè),不僅需要初始的性能配置數(shù)據(jù),同時(shí)還需要獲取任務(wù)的特定屬性,如輸入輸出數(shù)據(jù)大小等,然后根據(jù)任務(wù)的運(yùn)行時(shí)數(shù)據(jù),才能提高性能預(yù)測(cè)的精度。因此,本文首先根據(jù)任務(wù)的輸入數(shù)據(jù)大小,通過最小二乘法在初始的性能數(shù)據(jù)上,訓(xùn)練得到一個(gè)初始的節(jié)點(diǎn)性能預(yù)測(cè)模型。類似于執(zhí)行時(shí)間預(yù)測(cè),根據(jù)節(jié)點(diǎn)輸出數(shù)據(jù)大小,在初始的通信開銷數(shù)據(jù)上,訓(xùn)練得到一個(gè)初始的節(jié)點(diǎn)通信開銷預(yù)測(cè)模型。然后,這些模型會(huì)在運(yùn)行時(shí),根據(jù)實(shí)際預(yù)測(cè)的測(cè)量值,不斷調(diào)整整個(gè)模型來提高預(yù)測(cè)的精度。

基于以上獲取的執(zhí)行時(shí)間,根據(jù)之前描述的性能增益求取模型,可以很容易計(jì)算出計(jì)算節(jié)點(diǎn)的性能增益數(shù)據(jù)。然后,基于性能增益和通信延遲數(shù)據(jù),KOS 將很容易實(shí)現(xiàn)PPTM 算法,完成任務(wù)映射。首先,基于深度優(yōu)先遍歷獲得一個(gè)節(jié)點(diǎn)棧,方便從計(jì)算流圖中的葉子節(jié)點(diǎn)開始遍歷整個(gè)圖。然后,得到應(yīng)用程序的計(jì)算流圖G的一份拷貝G′,作為映射算法的輸入。最后,實(shí)現(xiàn)之前給出的PPTM 算法的偽代碼,得到優(yōu)化的計(jì)算流圖G″。

4.2.2 應(yīng)用示例

本文選取金融量化投資領(lǐng)域的一些實(shí)際應(yīng)用作為示例應(yīng)用程序,當(dāng)然這些計(jì)算核在風(fēng)險(xiǎn)控制以及流式數(shù)據(jù)聚合中也被廣泛使用[34]。同時(shí),使用現(xiàn)實(shí)世界的股票的股價(jià)(price)、每日開盤價(jià)(open)、收盤價(jià)(close)、交易量(volume)以及回報(bào)率(returns)作為數(shù)據(jù)源,通過調(diào)用相關(guān)計(jì)算核可以實(shí)現(xiàn)對(duì)股票的量化交易因子挖掘。參考量化投資領(lǐng)域中因子挖掘算法[32],構(gòu)造了如下5 個(gè)應(yīng)用。

以上的5 個(gè)應(yīng)用,是本文通過抽取量化投資領(lǐng)域中因子挖掘算法[32]的常見操作,然后抽象成計(jì)算核,最后對(duì)計(jì)算核進(jìn)行隨機(jī)組合而成。其中AVG 是求平均數(shù),在加速器上沒有實(shí)現(xiàn),本文會(huì)在CPU 上給出其實(shí)現(xiàn),因而其是柵欄節(jié)點(diǎn)。根據(jù)KOS 計(jì)算流圖的定義,圖5 和圖6 給出了應(yīng)用(4)和應(yīng)用(5)的計(jì)算流圖形式,其他應(yīng)用的計(jì)算流圖可以很容易類比得到。

圖5 應(yīng)用(4)KOS 計(jì)算流圖

圖6 應(yīng)用(5)計(jì)算流圖

如圖中所示,由于AVG 無法在加速器上加速,顯示為黑色節(jié)點(diǎn)。限于篇幅,這里只給出了5 個(gè)應(yīng)用示例,來證明本文系統(tǒng)的高效性。具體的分析將在下一節(jié)進(jìn)行詳細(xì)描述,其結(jié)論可以簡(jiǎn)單地推廣到其他應(yīng)用中。

5 測(cè)評(píng)與分析

5.1 測(cè)試環(huán)境與測(cè)試方案

5.1.1 測(cè)試環(huán)境

KOS的測(cè)試是在一臺(tái)服務(wù)器上完成的,加速器KPU 通過PCIex8 接口連接。加速器實(shí)現(xiàn)在DE5a-Net的FPGA 板卡上,綜合頻率為150 MHz。服務(wù)器的配置如表2 所示。KOS的測(cè)試用例采用前面描述的5 個(gè)應(yīng)用。

表2 測(cè)試環(huán)境參數(shù)表

5.1.2 測(cè)試方案

PPTM的設(shè)計(jì)目的是通過運(yùn)用提出的主動(dòng)式任務(wù)映射算法,能夠根據(jù)系統(tǒng)的運(yùn)行時(shí)數(shù)據(jù)動(dòng)態(tài)地調(diào)整計(jì)算流圖中計(jì)算節(jié)點(diǎn)的映射關(guān)系,從而提高整個(gè)應(yīng)用程序在異構(gòu)加速系統(tǒng)中的性能。因此,本文總共實(shí)現(xiàn)了3 種執(zhí)行模式,如下所述。

Accelerator-Free(A-Free)模式應(yīng)用程序不使用加速器進(jìn)行加速,而是直接將計(jì)算流圖中的所有節(jié)點(diǎn)全部映射到CPU 上執(zhí)行,做為基礎(chǔ)的對(duì)比數(shù)據(jù)。

DirectMapping(D-Map)模式采用傳統(tǒng)的任務(wù)映射方法,即在映射應(yīng)用程序計(jì)算流圖中節(jié)點(diǎn)時(shí)采用加速器優(yōu)先映射,也就是只要加速器支持的計(jì)算節(jié)點(diǎn)都映射到加速器上執(zhí)行,來做為主要的對(duì)比算法實(shí)現(xiàn)。

PPTM 模式將運(yùn)用提出的任務(wù)映射算法,來調(diào)度計(jì)算流圖在異構(gòu)加速系統(tǒng)中的執(zhí)行方式。

基于以上的3 種執(zhí)行模式,在不同的浮點(diǎn)數(shù)據(jù)集(data1-32M,data2-320M)上對(duì)不同的應(yīng)用進(jìn)行了多次實(shí)驗(yàn),并統(tǒng)計(jì)了相關(guān)性能數(shù)據(jù)。

5.2 數(shù)據(jù)分析

5.2.1 性能分析

表3 和表4 分別給出了在不同數(shù)據(jù)集上,5 個(gè)應(yīng)用在不同執(zhí)行模式下的性能數(shù)據(jù)。

表3 數(shù)據(jù)集1 下應(yīng)用性能數(shù)據(jù)

表4 數(shù)據(jù)集2 下應(yīng)用性能數(shù)據(jù)

從表中可以看出,在數(shù)據(jù)集1 上,通過D-Map映射方式,將計(jì)算流圖中的節(jié)點(diǎn)調(diào)度到加速器上執(zhí)行可以帶來巨大的性能增益,5 個(gè)應(yīng)用平均性能提升了26.41%。但是在數(shù)據(jù)集2 上時(shí),隨著數(shù)據(jù)規(guī)模的加大,主機(jī)與加速設(shè)備的通信開銷變大,采用D-Map的任務(wù)映射方法,對(duì)某些應(yīng)用,帶來性能增益有所下降,特別是對(duì)應(yīng)用(5)。從圖5 中可以看到,應(yīng)用(5)中左子樹上的柵欄節(jié)點(diǎn)AVG 所依賴的子節(jié)點(diǎn),將其映射到加速器上執(zhí)行,根據(jù)提出的算法,其累積的性能收益相比于其他柵欄節(jié)點(diǎn)偏少,如果將其調(diào)度到加速器上執(zhí)行,帶來的性能增益甚至不能抵消通信開銷,從而導(dǎo)致整個(gè)應(yīng)用程序性能增益下降。本文實(shí)驗(yàn)中,在數(shù)據(jù)集2 上,5 個(gè)應(yīng)用通過DMap 映射方法在異構(gòu)加速平臺(tái)上帶來的平均性能增益不足7%。

從表中可以看到,通過PPTM 任務(wù)映射算法,在不同的數(shù)據(jù)規(guī)模時(shí),對(duì)比D-Map 映射方式都能帶來性能增益。在數(shù)據(jù)集1 上,通信延遲還比較小,因此對(duì)于大多數(shù)應(yīng)用通過D-Map 映射方法就能夠帶來很好的性能增益。本文提出的PPTM 算法,相比于D-Map 模式,帶來了2.37%～14.06%的性能提升。而在數(shù)據(jù)集2 時(shí),隨著通信延遲的增加,PPTM 任務(wù)映射算法,相比于D-Map 映射方式,平均能夠帶來13.8%的性能提升。特別是針對(duì)應(yīng)用(4),從圖4可以看到,柵欄節(jié)點(diǎn)存在于葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的關(guān)鍵路徑上,尤其是最下面的2 個(gè)柵欄節(jié)點(diǎn)之間只隔了1 個(gè)節(jié)點(diǎn)。如果按照D-Map的任務(wù)映射方法,將這個(gè)節(jié)點(diǎn)調(diào)度到加速器上執(zhí)行,將導(dǎo)致主機(jī)與加速設(shè)備之間反復(fù)進(jìn)行數(shù)據(jù)通信,從而帶來嚴(yán)重的通信開銷。因此,通過PPTM 任務(wù)映射算法,將其映射到CPU 上執(zhí)行,反而帶來了24.85%的性能提升。

通過以上的數(shù)據(jù)分析可以看出,針對(duì)不同的應(yīng)用程序,并不是將其計(jì)算流圖中加速器支持的所有節(jié)點(diǎn)全部調(diào)度到加速器上執(zhí)行,就一定能獲得最佳的性能。因?yàn)獒槍?duì)某些應(yīng)用,如果直接把節(jié)點(diǎn)映射到加速器上,會(huì)導(dǎo)致無法攤銷的主機(jī)與加速設(shè)備之間的數(shù)據(jù)交互,從而帶來嚴(yán)重的通信開銷,反而無法提升整個(gè)應(yīng)用程序的性能。因此,需要根據(jù)特定性能數(shù)據(jù),合理地進(jìn)行任務(wù)映射,才能最大化應(yīng)用程序在異構(gòu)加速系統(tǒng)上的性能。為了進(jìn)一步分析通信開銷對(duì)性能的影響,接下來,將對(duì)應(yīng)用在不同的數(shù)據(jù)集上的通信開銷數(shù)據(jù)進(jìn)行分析。

5.2.2 通信延遲分析

圖7 和圖8 分別給出了D-Map 模式和PPTM 模式在不同的數(shù)據(jù)集下,應(yīng)用由于存在主機(jī)和加速器端的數(shù)據(jù)交互而帶來的通信開銷數(shù)據(jù)。圖中,D-Map-C代表應(yīng)用在D-Map 模式下的通信開銷,PPTM-C 則代表應(yīng)用在PPTM 模式下的通信開銷。

圖7 數(shù)據(jù)集1 下應(yīng)用通信開銷數(shù)據(jù)對(duì)比

圖8 數(shù)據(jù)集2 下應(yīng)用通信開銷數(shù)據(jù)對(duì)比

從圖中可以看到,PPTM 任務(wù)映射算法,在不同的數(shù)據(jù)集上,其通信開銷相比于D-Map 映射方法都要低。而在本文的假設(shè)中,通信開銷只存在于柵欄節(jié)點(diǎn)的上下節(jié)點(diǎn)需要數(shù)據(jù)交互時(shí)。因此,必然是PPTM 任務(wù)映射算法改變了與柵欄節(jié)點(diǎn)相連的某些節(jié)點(diǎn)的映射方式。

從圖7 中可以看到,在數(shù)據(jù)集1 上,PPTM 算法相比于D-Map,平均降低了24.9%的通信開銷。但是,從之前的性能分析可知,其帶來的性能增益平均不到6%。因?yàn)镻PTM 雖然降低了應(yīng)用程序的整體通信開銷,但同時(shí)也會(huì)失去將某些節(jié)點(diǎn)映射到加速器上執(zhí)行帶來的性能增益,這需要根據(jù)應(yīng)用的運(yùn)行時(shí)數(shù)據(jù)做出權(quán)衡。

從圖8 可以看出,當(dāng)在數(shù)據(jù)集2 上時(shí),PPTM 算法相比于D-Map,平均降低了53.3%的通信開銷。同時(shí),之前的性能分析表明,PPTM 帶來了平均13.8%的性能增益,特別是應(yīng)用(4),帶來了24.85%的性能提升。從圖7 中可以看到,針對(duì)應(yīng)用(4),PPTM 算法對(duì)比于D-Map,降低了將近83%的通信開銷。然而,對(duì)于應(yīng)用(3),PPTM 算法降低了66.67%的通信開銷,但性能增益微乎其微。

通過上面的分析可以看到,PPTM 算法通過改變柵欄節(jié)點(diǎn)子節(jié)點(diǎn)的映射方式必然會(huì)降低整個(gè)應(yīng)用程序的通信開銷,但并不是通信開銷降低得越多帶來的性能增益越高。除了因?yàn)楦淖児?jié)點(diǎn)映射方式后無法受益于加速器帶來的性能增益,性能增益還跟具體的應(yīng)用存在很強(qiáng)的關(guān)聯(lián)性。

6 結(jié)論

現(xiàn)有異構(gòu)加速系統(tǒng)中,將計(jì)算通過加速設(shè)備來加速,在需要與主機(jī)端進(jìn)行交互的應(yīng)用場(chǎng)景中會(huì)帶來相應(yīng)的通信開銷。如果無法合理地?cái)備N主機(jī)與設(shè)備端的通信開銷,在特定的數(shù)據(jù)規(guī)模時(shí)(CPU 性能瓶頸不在訪存時(shí)),針對(duì)不同的應(yīng)用,并不是將其計(jì)算流圖中的加速器支持的所有節(jié)點(diǎn)全部調(diào)度到加速器上執(zhí)行,就一定能獲得最佳的性能。通過引入PPTM 算法,在運(yùn)行時(shí)動(dòng)態(tài)地感知應(yīng)用中計(jì)算節(jié)點(diǎn)的性能變化,實(shí)現(xiàn)更加高效的任務(wù)映射,能夠提高應(yīng)用程序的整體性能。最終測(cè)試充分驗(yàn)證了,針對(duì)不同的應(yīng)用程序,本文提出的任務(wù)映射算法,能夠?qū)崿F(xiàn)更加高效的任務(wù)調(diào)度,從而提高應(yīng)用程序性能。