基于OpenCL的流式應(yīng)用程序在MPSoC上的動(dòng)態(tài)并行度伸縮調(diào)度①

黃 姍 石晶林 蕭 放

(*中國(guó)科學(xué)院計(jì)算技術(shù)研究所無(wú)線通信技術(shù)研究中心 北京 100190)(**北京市移動(dòng)計(jì)算與新型終端重點(diǎn)實(shí)驗(yàn)室 北京 100190)(***中國(guó)科學(xué)院大學(xué) 北京 100049)

基于OpenCL的流式應(yīng)用程序在MPSoC上的動(dòng)態(tài)并行度伸縮調(diào)度①

黃 姍②******石晶林******蕭 放***

(*中國(guó)科學(xué)院計(jì)算技術(shù)研究所無(wú)線通信技術(shù)研究中心 北京 100190)(**北京市移動(dòng)計(jì)算與新型終端重點(diǎn)實(shí)驗(yàn)室 北京 100190)(***中國(guó)科學(xué)院大學(xué) 北京 100049)

分析了嵌入式系統(tǒng)應(yīng)用程序的復(fù)雜化和多樣化趨勢(shì)，面向嵌入式系統(tǒng)常見的流式應(yīng)用程序，提出了基于開放運(yùn)算語(yǔ)言(OpenCL)的統(tǒng)一編程框架，并在此框架的基礎(chǔ)上設(shè)計(jì)一個(gè)運(yùn)行時(shí)系統(tǒng)，在應(yīng)用程序可用計(jì)算資源發(fā)生變化的場(chǎng)景下，該系統(tǒng)可在線調(diào)整應(yīng)用程序的并行度，并進(jìn)行動(dòng)態(tài)調(diào)度。實(shí)驗(yàn)結(jié)果顯示，與已有的Flextream動(dòng)態(tài)調(diào)度系統(tǒng)相比，該調(diào)度系統(tǒng)在性能上最高可以提升17%，在動(dòng)態(tài)調(diào)度的時(shí)間開銷上最多可以降低7%。

多處理器片上系統(tǒng)(MPSoC)， 開放運(yùn)算語(yǔ)言(OpenCL)， 編程框架， 并行度伸縮， 運(yùn)行時(shí)系統(tǒng)

0 引 言

近年來，嵌入式系統(tǒng)的應(yīng)用程序越來越復(fù)雜和多樣化[1-3]，多處理器片上系統(tǒng)(multiprocessor system on chip，MPSoC)因其靈活可編程的特點(diǎn)得到了廣泛的應(yīng)用。出于對(duì)性能、功耗效率的要求，MPSoC上集成了多種異構(gòu)的計(jì)算資源。因此，MPSoC上的軟件編程問題變得越來越復(fù)雜。程序員需要對(duì)不同類型的計(jì)算單元進(jìn)行編程，甚至需要了解微結(jié)構(gòu)信息從而充分地利用硬件資源的計(jì)算能力，提升程序的執(zhí)行效率。為了降低軟件編程的難度，為程序員提供統(tǒng)一的異構(gòu)計(jì)算資源編程接口，蘋果公司率先提出了開放運(yùn)算語(yǔ)言(open computing language，OpenCL)[4]編程框架，使用該編程框架的程序可以在任意的支持OpenCL編程框架的異構(gòu)平臺(tái)上編譯和執(zhí)行。另一方面，為了提升資源利用率，多個(gè)應(yīng)用程序會(huì)以一種動(dòng)態(tài)的方式共享一個(gè)MPSoC的計(jì)算資源。例如，一個(gè)視頻處理程序占據(jù)整個(gè)MPSoC的計(jì)算資源，當(dāng)另一個(gè)拍照程序被啟動(dòng)時(shí)，視頻處理程序不得不動(dòng)態(tài)地調(diào)整它的任務(wù)映射，因?yàn)橐徊糠钟?jì)算資源需要被分配給拍照程序。這意味著，系統(tǒng)需要在線地改變?nèi)蝿?wù)并行度以及任務(wù)映射，來適應(yīng)變化的計(jì)算資源。文獻(xiàn)[5]提出了一種半靜態(tài)的方法，準(zhǔn)備多個(gè)可能場(chǎng)景下的并行度和任務(wù)映射方案，然后運(yùn)行時(shí)系統(tǒng)根據(jù)實(shí)際情況進(jìn)行動(dòng)態(tài)的選擇。這種方法能適應(yīng)的場(chǎng)景會(huì)受到預(yù)先考慮的場(chǎng)景的限制，也會(huì)消耗大量的存儲(chǔ)資源去保存這些并行度和任務(wù)映射方案。文獻(xiàn)[6]提出了一種動(dòng)態(tài)調(diào)整數(shù)據(jù)級(jí)并行度的方法，但并沒有考慮其它類型的并行度調(diào)整。文獻(xiàn)[7]只考慮了動(dòng)態(tài)改變?nèi)蝿?wù)映射，但并沒有相應(yīng)的調(diào)整并行度。

綜合上述兩個(gè)方面的因素，本文提出了一種基于OpenCL編程框架的流式應(yīng)用程序在異構(gòu)多核片上系統(tǒng)的實(shí)現(xiàn)框架，并基于此實(shí)現(xiàn)了一個(gè)運(yùn)行時(shí)系統(tǒng)的框架設(shè)計(jì)，支持當(dāng)應(yīng)用程序在可用計(jì)算資源發(fā)生變化的場(chǎng)景下，在線調(diào)整應(yīng)用程序的并行度并動(dòng)態(tài)地調(diào)度應(yīng)用程序，主要貢獻(xiàn)在于：在流式應(yīng)用程序的同步數(shù)據(jù)流(synchronous data flow，SDF)模型基礎(chǔ)上，表征不同類型的并行度，給出局部調(diào)整并行度的方法；提出了一種根據(jù)可用的計(jì)算資源，動(dòng)態(tài)調(diào)整并行度，并重新分配計(jì)算資源的算法；提出了基于OpenCL編程框架的流式應(yīng)用程序在MPSoC平臺(tái)上進(jìn)行動(dòng)態(tài)調(diào)度的運(yùn)行時(shí)系統(tǒng)。

1 OpenCL簡(jiǎn)介

OpenCL[4]是一個(gè)在異構(gòu)平臺(tái)下的編程框架，異構(gòu)平臺(tái)可以由通用處理器(central processing unit，CPU)、圖像處理器(graphic processing unit，GPU)、數(shù)字信號(hào)處理器(digital signal processor，DSP)、可編程門陣列(field programmable gate array，F(xiàn)PGA)以及應(yīng)用專用集成電路(application specific integrated circuit，ASIC)等組成。OpenCL一方面提供定義和控制異構(gòu)平臺(tái)的應(yīng)用編程接口(application programming interface，API)，另一方面提供基于C語(yǔ)言標(biāo)準(zhǔn)擴(kuò)展的對(duì)每個(gè)異構(gòu)處理單元進(jìn)行編程的OpenCL C語(yǔ)言。

OpenCL編程框架對(duì)異構(gòu)平臺(tái)上的計(jì)算資源進(jìn)行了層次化的抽象。一個(gè)異構(gòu)計(jì)算平臺(tái)由一個(gè)主控制單元(host)和多個(gè)計(jì)算設(shè)備(device)組成。一個(gè)異構(gòu)計(jì)算平臺(tái)的host通過API管理和控制各個(gè)device，每個(gè)device執(zhí)行一段特定的計(jì)算任務(wù)，被稱為核心(kernel)。一般而言，host實(shí)現(xiàn)在CPU上，kernel程序在device上執(zhí)行。一個(gè)多核心的CPU也可以同時(shí)作為device，即通過操作系統(tǒng)的多線程執(zhí)行具體的計(jì)算任務(wù)。

Host通過為每個(gè)device創(chuàng)建和維護(hù)任務(wù)隊(duì)列來決定device執(zhí)行哪些具體的計(jì)算任務(wù)，隊(duì)列里的命令可以是實(shí)例化一個(gè)kernel程序執(zhí)行的命令，也可以是一條同步命令，或者是數(shù)據(jù)傳輸命令。除了顯示的添加同步命令之外，host也可以通過定義任務(wù)隊(duì)列的執(zhí)行模型來控制隊(duì)列的執(zhí)行順序，命令隊(duì)列有兩種基本的執(zhí)行順序，一是串行執(zhí)行，即嚴(yán)格按照命令入隊(duì)列的順序執(zhí)行；另一種是亂序執(zhí)行，即當(dāng)前面的命令沒有滿足啟動(dòng)條件的情況下允許執(zhí)行已經(jīng)滿足啟動(dòng)條件的命令先執(zhí)行。

2 流式應(yīng)用程序建模分析

本節(jié)闡述流式應(yīng)用程序的圖建模，利用圖的節(jié)點(diǎn)來表示特定的計(jì)算任務(wù)，利用邊來表示任務(wù)之間的數(shù)據(jù)依賴關(guān)系。不同類型的并行度可以通過圖的結(jié)構(gòu)進(jìn)行表征，基于這個(gè)結(jié)構(gòu)，定義并行度調(diào)整的方法。

2.1 流式應(yīng)用程序的SDF模型

同步數(shù)據(jù)流[8](SDF)圖模型經(jīng)常用來對(duì)流式應(yīng)用程序進(jìn)行建模。在SDF模型中，兩個(gè)存在數(shù)據(jù)依賴關(guān)系的節(jié)點(diǎn)用有向邊相連，節(jié)點(diǎn)表示兩個(gè)特定的計(jì)算任務(wù)，有向邊表示數(shù)據(jù)的流動(dòng)方向，產(chǎn)生數(shù)據(jù)的節(jié)點(diǎn)被稱為生產(chǎn)者，使用數(shù)據(jù)的節(jié)點(diǎn)被稱為消費(fèi)者。圖1為流式應(yīng)用的數(shù)據(jù)流圖模型。

圖1 流式應(yīng)用程序的數(shù)據(jù)流圖模型

如圖 1(a) 所示，有向邊相連的兩個(gè)節(jié)點(diǎn)代表的計(jì)算任務(wù)T1和T2每一次被執(zhí)行都產(chǎn)生或消耗確定數(shù)據(jù)量，分別用o和i表示，被標(biāo)記在有向邊的起點(diǎn)和終點(diǎn)處。對(duì)于SDF模型，每對(duì)有向邊相連的節(jié)點(diǎn)，需要存在整數(shù)r1和r2滿足公式

o×r1=i×r2

(1)

后文將使用等效SDF模型所定義的數(shù)據(jù)流圖G=(V,E)來對(duì)流式應(yīng)用程序進(jìn)行刻畫，其中V表示節(jié)點(diǎn)的集合，E表示有向邊的集合。對(duì)于每一個(gè)節(jié)點(diǎn)v∈V，使用該節(jié)點(diǎn)對(duì)應(yīng)的計(jì)算任務(wù)的工作負(fù)載對(duì)其進(jìn)行量化，節(jié)點(diǎn)工作負(fù)載可以通過靜態(tài)分析或動(dòng)態(tài)評(píng)估得到；對(duì)于每一條邊e∈E，使用有向邊傳遞的數(shù)據(jù)量對(duì)其進(jìn)行量化，即等效模型中的d。

2.2 并行度的表征

在數(shù)據(jù)流圖模型G上添加特殊節(jié)點(diǎn)可以顯式地表征并行度，如圖2(a)所示。進(jìn)一步地，圖2(b)表示數(shù)據(jù)并行，圖2(c) 表示任務(wù)并行，圖2(d)表示流水并行。數(shù)據(jù)并行是指同時(shí)對(duì)不同的輸入數(shù)據(jù)進(jìn)行相同計(jì)算任務(wù)，任務(wù)并行是指同時(shí)執(zhí)行了兩個(gè)或多個(gè)相互獨(dú)立的沒有數(shù)據(jù)依賴關(guān)系的任務(wù)。數(shù)據(jù)并行和任務(wù)并行是通過添加拆分節(jié)點(diǎn)S和合并節(jié)點(diǎn)J顯示的表現(xiàn)在任務(wù)流圖中，通常被形象化地表現(xiàn)為一種水平并列的模式，本文使用水平并行(horizontalparallelism，HP)來描述。

圖2 數(shù)據(jù)流圖模型及其并行度表征

由于流式應(yīng)用程序會(huì)迭代執(zhí)行多次來處理源源不斷到達(dá)的需要處理的數(shù)據(jù)，所以數(shù)據(jù)流圖G實(shí)際上被一個(gè)隱式的外部循環(huán)所包含。這個(gè)特征使得流式應(yīng)用程序得以非常自然地利用流水線的實(shí)現(xiàn)方式。通過將外層隱式的循環(huán)進(jìn)行展開，原本屬于不同迭代周期的任務(wù)節(jié)點(diǎn)就可以并行執(zhí)行。這種通過循環(huán)展開獲得流水并行的技術(shù)最早被應(yīng)用在指令層次，稱為軟流水技術(shù)[9]。Gordon等人將這種軟流水技術(shù)應(yīng)用在粗粒度的任務(wù)層次，挖掘了任務(wù)級(jí)的流水并行[10]。如圖 2(d) 所示，兩個(gè)級(jí)聯(lián)的任務(wù)節(jié)點(diǎn)通過循環(huán)展開即可構(gòu)成流水并行的結(jié)構(gòu)，本文使用垂直并行(verticalparallelism，VP)來描述。

2.3 并行度調(diào)整方法

基于流式應(yīng)用程序的圖建模和對(duì)不同并行類型的表征，本節(jié)闡述并行度調(diào)整的方法。在應(yīng)用程序執(zhí)行的過程中，分配給該應(yīng)用程序的硬件資源有可能發(fā)生變化，這就需要在線動(dòng)態(tài)調(diào)整應(yīng)用程序的并行度。靜態(tài)編譯階段可以使用復(fù)雜度較高的分析優(yōu)化算法，獲得最優(yōu)或接近最優(yōu)的結(jié)果，而動(dòng)態(tài)并行度調(diào)整由于占用運(yùn)行時(shí)的時(shí)間，不能使用復(fù)雜度太高的算法。以一個(gè)優(yōu)化的靜態(tài)分析優(yōu)化的結(jié)果作為動(dòng)態(tài)調(diào)整的起點(diǎn)，一方面可以降低動(dòng)態(tài)調(diào)整算法的復(fù)雜度，另一方面也可以保證性能的損失在可接受的范圍內(nèi)。本文提出的動(dòng)態(tài)并行度調(diào)整是基于一個(gè)應(yīng)用程序能夠使用異構(gòu)平臺(tái)上所有的計(jì)算資源的場(chǎng)景下的靜態(tài)分析結(jié)果。因此，本文的并行度調(diào)整根據(jù)不同的并行度類型，對(duì)流圖模型進(jìn)行局部節(jié)點(diǎn)合并。

圖3是通過局部的節(jié)點(diǎn)合并進(jìn)行并行度調(diào)整的API定義，分為水平并行度調(diào)整和垂直并行度調(diào)整兩種類型。水平并行度調(diào)整是將包含在同一對(duì)S-J節(jié)點(diǎn)對(duì)vsp和vjo中的兩個(gè)節(jié)點(diǎn)vi和vj合并成一個(gè)行的節(jié)點(diǎn)vk，并通過置vk的前驅(qū)節(jié)點(diǎn)In(vk)和后繼節(jié)點(diǎn)Out(vk)分別為S-J節(jié)點(diǎn)對(duì)的vsp和vjo將新節(jié)點(diǎn)vk連接到圖中。垂直并行度調(diào)整的API將有向邊相連的兩個(gè)節(jié)點(diǎn)vi和vj合并成新的節(jié)點(diǎn)vk，并通過置vk的前驅(qū)節(jié)點(diǎn)In(vk)和后繼節(jié)點(diǎn)Out(vk)分別為原vi的前驅(qū)節(jié)點(diǎn)和原vj的后繼節(jié)點(diǎn)將新節(jié)點(diǎn)vk連接到圖中。

圖3 并行度調(diào)整API

3 基于OpenCL的實(shí)現(xiàn)框架

本節(jié)闡述基于OpenCL編程框架的流式應(yīng)用程序的實(shí)現(xiàn)框架。首先需要確定經(jīng)過數(shù)據(jù)流圖建模的應(yīng)用程序和異構(gòu)平臺(tái)的計(jì)算資源之間的映射關(guān)系，然后根據(jù)這個(gè)映射關(guān)系通過主控單元host的邏輯管理和調(diào)度各個(gè)device執(zhí)行所承載的計(jì)算任務(wù)。

3.1 數(shù)據(jù)流圖模型到異構(gòu)平臺(tái)的映射

圖4展示了一個(gè)流式應(yīng)用程序的數(shù)據(jù)流圖模型G映射到一個(gè)異構(gòu)平臺(tái)的方法，模型的節(jié)點(diǎn)被映射到異構(gòu)平臺(tái)的device處理資源上(虛線),例如GPU和DSP；圖模型的邊實(shí)例化為先入先出(FIFO)的數(shù)據(jù)結(jié)構(gòu)，映射到異構(gòu)平臺(tái)的不同存儲(chǔ)資源上(點(diǎn)劃線)。

圖4 數(shù)據(jù)流圖模型到計(jì)算平臺(tái)的映射

3.2 基于OpenCL的實(shí)現(xiàn)框架

圖5是流式應(yīng)用程序基于OpenCL的實(shí)現(xiàn)框架圖。主控制的功能主要包括根據(jù)應(yīng)用程序模型和任務(wù)映射，調(diào)用OpenCL的API庫(kù)函數(shù)控制和調(diào)度各個(gè)device完成相應(yīng)的計(jì)算任務(wù)。在線的并行度調(diào)整和動(dòng)態(tài)任務(wù)調(diào)度需要主控單元調(diào)用并行度調(diào)整的API函數(shù)(2.3節(jié))來完成。各個(gè)device上執(zhí)行的計(jì)算任務(wù)用OpenCL C語(yǔ)言實(shí)現(xiàn)，通過OpenCL C編譯器產(chǎn)生對(duì)應(yīng)的可執(zhí)行文件。這個(gè)過程可以靜態(tài)地完成，也可以由主控單元?jiǎng)討B(tài)地調(diào)用編譯組件完成，如圖 5中的虛線箭頭和虛線框所示。

圖5 實(shí)現(xiàn)框架圖

4 運(yùn)行時(shí)系統(tǒng)

本節(jié)描述運(yùn)行時(shí)系統(tǒng)對(duì)流式應(yīng)用程序的調(diào)度，以及在線調(diào)整并行度進(jìn)行動(dòng)態(tài)調(diào)度的方法。

4.1 流水線調(diào)度的基本方法

由于流式應(yīng)用程序經(jīng)常需要重復(fù)執(zhí)行多次來處理源源不斷到達(dá)的數(shù)據(jù)，所以一個(gè)典型的流式應(yīng)用程序的頂層有一個(gè)隱式的循環(huán)。根據(jù)這個(gè)特征，Gordon等人將軟流水技術(shù)調(diào)度應(yīng)用在粗粒度的任務(wù)層次[10]，通過對(duì)整個(gè)流式應(yīng)用程序頂層的隱式循環(huán)進(jìn)行展開，來自不同循環(huán)迭代次數(shù)的任務(wù)就可以并行執(zhí)行，流式應(yīng)用程序因?yàn)楸旧淼奶卣骺梢院茏匀坏貜牧魉⑿兄蝎@得巨大的數(shù)據(jù)吞吐收益。

流水線調(diào)度首先根據(jù)計(jì)算任務(wù)到處理資源的映射計(jì)算每個(gè)任務(wù)的所屬于的迭代周期，如公式

vi, vj∈V; mapvi, mapvj∈P

(2)

所示。數(shù)據(jù)流圖源節(jié)點(diǎn)的迭代周期為0，其余對(duì)于數(shù)據(jù)流圖模型的每一條邊(vi,vj)∈E，vj的迭代周期取決于其所有前驅(qū)節(jié)點(diǎn)vi中迭代周期最大的一個(gè)，如果節(jié)點(diǎn)vi和vj的任務(wù)被分配在不同的處理資源上，那么就需要在最大迭代周期的基礎(chǔ)上加一個(gè)迭代距離D，mapvi和mapvj分別表示任務(wù)vi和vj映射的處理資源，P表示計(jì)算平臺(tái)上所有處理資源的集合。如果計(jì)算處理資源支持任務(wù)計(jì)算和數(shù)據(jù)傳輸并行執(zhí)行，即一個(gè)處理器在啟動(dòng)了DMA數(shù)據(jù)傳輸任務(wù)之后可以不等待數(shù)據(jù)傳輸任務(wù)結(jié)束即開始執(zhí)行后續(xù)的計(jì)算任務(wù)，則D為2，否則D為1。如果節(jié)點(diǎn)vi和vj的任務(wù)被分配在相同的處理資源上，那么vj的迭代周期就等于vi的迭代周期的最大值。

根據(jù)已經(jīng)計(jì)算好的每個(gè)節(jié)點(diǎn)所屬于的迭代周期，根據(jù)公式

Buf(vi,vj)=(Ivj-Ivi+1)×weight(vi,vj)

(vi,vj)∈E

(3)

可以計(jì)算出每條有向邊所需要的存儲(chǔ)空間，用以進(jìn)行數(shù)據(jù)傳遞，其中weight(vi,vj)每條有向邊傳遞的數(shù)據(jù)量，即圖模型中的d。

一個(gè)典型的流水線調(diào)度需要三個(gè)階段，分別為流水的建立期(Prologue)、核心期(SteadyState)和退出期(Epilogue)。在流水的建立期，通過逐步添加各個(gè)迭代周期的計(jì)算任務(wù)到各個(gè)device的任務(wù)隊(duì)列，在每?jī)蓚€(gè)存在數(shù)據(jù)依賴的任務(wù)之間添加足夠的緩存空間，使得數(shù)據(jù)的消費(fèi)者節(jié)點(diǎn)并不直接依賴于其生產(chǎn)者當(dāng)前產(chǎn)生的數(shù)據(jù)，而是使用生產(chǎn)者上一次產(chǎn)生的緩存數(shù)據(jù)。流水調(diào)度進(jìn)入核心期后，分配在不同計(jì)算資源上的任務(wù)都可以彼此獨(dú)立地執(zhí)行，不等待其它計(jì)算資源完成任何的任務(wù)計(jì)算，由此便獲得了流水并行。退出期即當(dāng)沒有新數(shù)據(jù)到達(dá)時(shí)，逐步釋放掉已經(jīng)完成的計(jì)算任務(wù)。圖 6是一個(gè)簡(jiǎn)單的流水線調(diào)度不同時(shí)期的示意圖。

圖6 流水線調(diào)度時(shí)期示意圖

4.2 運(yùn)行時(shí)系統(tǒng)調(diào)度流程

圖7為運(yùn)行時(shí)系統(tǒng)工作的全流程，系統(tǒng)啟動(dòng)之后初始化device設(shè)備，根據(jù)任務(wù)映射關(guān)系計(jì)算圖模型中每個(gè)節(jié)點(diǎn)的迭代周期，并為每個(gè)有向邊分配存儲(chǔ)空間。初始化設(shè)備同時(shí)置變量resChange為FALSE，表示系統(tǒng)初次啟動(dòng)，隨后進(jìn)入流水線調(diào)度的建立期。在建立期中，host根據(jù)每個(gè)計(jì)算節(jié)點(diǎn)的迭代周期，向device的任務(wù)隊(duì)列中添加新的迭代周期的任務(wù)并執(zhí)行整個(gè)任務(wù)隊(duì)列，直到所有迭代周期的節(jié)點(diǎn)都添加到任務(wù)隊(duì)列中，并在任務(wù)隊(duì)列的末尾添加?xùn)耪贤矫?。之后，流水進(jìn)入核心期，device的任務(wù)隊(duì)列不再添加新的任務(wù)，只要還有新數(shù)據(jù)到來并且計(jì)算資源不變(!dataEnd && !resChange)，任務(wù)隊(duì)列的任務(wù)就被循環(huán)執(zhí)行。如果不再有新數(shù)據(jù)(dataEnd)需要處理，則進(jìn)入流水的退出期。在流水的退出期中，主控host根據(jù)每個(gè)計(jì)算節(jié)點(diǎn)的迭代周期，從device的任務(wù)隊(duì)列中刪除某個(gè)迭代周期的任務(wù)并重新執(zhí)行任務(wù)隊(duì)列，直到任務(wù)隊(duì)列為空。最后調(diào)用OpenCL提供的API接口函數(shù)，釋放相關(guān)任務(wù)隊(duì)列、存儲(chǔ)資源以及device，結(jié)束整個(gè)應(yīng)用程序的執(zhí)行。

當(dāng)應(yīng)用程序處于核心期時(shí)，如果計(jì)算資源有所變化，則運(yùn)行時(shí)系統(tǒng)進(jìn)入動(dòng)態(tài)并行度伸縮調(diào)度的工作流程。首先進(jìn)入并行度伸縮調(diào)度的決策期，如圖7的點(diǎn)劃線框所包含的流程所示，包括調(diào)用并行度伸縮的算法，之后重新計(jì)算圖模型中每個(gè)節(jié)點(diǎn)的迭代周期和分配每條有向邊的存儲(chǔ)資源，并置變量resChange為TRUE。隨后，運(yùn)行時(shí)系統(tǒng)進(jìn)入并行度伸縮調(diào)度的切換期，切換期分別由流水的退出期和建立期組成，完成從上一個(gè)核心期到下一個(gè)核心期的轉(zhuǎn)換工作。

4.3 在線并行度伸縮算法

本小節(jié)詳述在線并行度伸縮的算法細(xì)節(jié)，即圖7中的灰色標(biāo)記的內(nèi)容。

流式應(yīng)用程序使用2.1節(jié)中的圖模型G=(V,E)來表示，集合P是異構(gòu)平臺(tái)上所有處理資源的集合，初始的任務(wù)映射用數(shù)組Map表示，如下式所示：

Map={mapv1,…,mapv|V|}

v1,…,v|V|∈V,mapv1,…,mapv|V|∈P

(4)

圖7 運(yùn)行時(shí)系統(tǒng)流程圖

Nr表示處理資源變化后仍然可用的計(jì)算單元個(gè)數(shù)，滿足Nr≤|P|。圖8為并行度調(diào)整的算法流程，為了清晰起見，整個(gè)算法流程分成4個(gè)步驟，下面將逐步闡述。

步驟1：決定哪些處理單元被保留繼續(xù)執(zhí)行該應(yīng)用程序。通過對(duì)初始任務(wù)映射中的處理器按照每個(gè)處理器承載的計(jì)算任務(wù)個(gè)數(shù)做升序排列，序列前Nr個(gè)處理資源被保留，并組成集合Preserve。因?yàn)殪o態(tài)任務(wù)的映射結(jié)果是最優(yōu)解或者近優(yōu)解，每個(gè)處理資源的任務(wù)負(fù)載總和是趨近于平衡的，保留承載任務(wù)個(gè)數(shù)少的處理器即保留了單個(gè)任務(wù)負(fù)載較高的任務(wù)，通過重新分配多個(gè)負(fù)載較低的任務(wù)更有利于新的任務(wù)映射達(dá)到負(fù)載均衡。與此同時(shí)，在靜態(tài)任務(wù)映射中被分配到集合Preserve上執(zhí)行的節(jié)點(diǎn)任務(wù)組成集合Vreserve,其余組成集合Vvictim。

步驟2：檢測(cè)并行度。通過函數(shù)DetectParallel檢測(cè)集合Vvictim中的每個(gè)任務(wù)是否存在并行度。遍歷集合Vvictim中的每個(gè)節(jié)點(diǎn)v，首先將v添加集合Vscale中，判斷如果v屬于一對(duì)S-J節(jié)點(diǎn)對(duì)中，那么v是水平平行度的一部分，那么則遍歷與它同屬于這個(gè)S-J結(jié)構(gòu)的每個(gè)兄弟節(jié)點(diǎn)vs，如果vs∈Vreserve，那么節(jié)點(diǎn)vs和承載其執(zhí)行的計(jì)算單元mapvs組成一個(gè)節(jié)點(diǎn)資源對(duì)(vs,mapvs)，進(jìn)而構(gòu)成節(jié)點(diǎn)資源對(duì)集合VPneighbor={(vs,mapvs)},vs∈Vreserve；如果vs∈Vvictim，則節(jié)點(diǎn)vs構(gòu)成集合Vscale。同理的，判斷如果v不屬于S-J結(jié)構(gòu)中，那么v只可能是垂直并行度的一部分，那么則遍歷它的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)，如果其前驅(qū)或者后繼節(jié)點(diǎn)屬于集合Vreserve，那么前驅(qū)或者后繼節(jié)點(diǎn)則與其映射的處理資源構(gòu)成節(jié)點(diǎn)資源對(duì)集合VPneighbor。在本步驟中，輸出的集合Vscale表示的是需要調(diào)整并行度并重新分配計(jì)算資源的節(jié)點(diǎn)的集合。

步驟3：調(diào)整并行度。函數(shù)ScaleParallel將上一個(gè)步驟中形成的集合Vscale中的任務(wù)節(jié)點(diǎn)和集合VPneighbor中的節(jié)點(diǎn)進(jìn)行合并，達(dá)到局部的調(diào)整水平或垂直并行度的效果，合并的節(jié)點(diǎn)將由對(duì)應(yīng)節(jié)點(diǎn)資源對(duì)的計(jì)算資源承載執(zhí)行。方法是首先將集合Vscale根據(jù)任務(wù)復(fù)雜度進(jìn)行降序排列，依次考慮排序后的每個(gè)計(jì)算節(jié)點(diǎn)vi，同時(shí)選擇當(dāng)前VPneighbor中任務(wù)負(fù)載最小的處理資源p所對(duì)應(yīng)的節(jié)點(diǎn)資源對(duì)(vj,p)，將vi與vj進(jìn)行節(jié)點(diǎn)合并，同時(shí)保證合并之后處理資源p的任務(wù)負(fù)載不能超過閾值(Th)的10%。這個(gè)閾值Th表示了一種理想的情況，即所有的任務(wù)在剩余的Nr個(gè)處理資源上絕對(duì)平均的分配。設(shè)置這樣一個(gè)約束的原因是局部的調(diào)整并行度可以降低同步以及通信的開銷從而提升性能，但仍然需要兼顧全局的負(fù)載均衡。此外，在進(jìn)行了節(jié)點(diǎn)合并之后，需要檢查并刪除無(wú)用的S-J節(jié)點(diǎn)對(duì)。

步驟4：為不能調(diào)整并行度的節(jié)點(diǎn)分配處理資源。算法進(jìn)行到這里，集合Vvictim中還余下一些沒有進(jìn)行合并的計(jì)算節(jié)點(diǎn)，這里采取貪心算法將剩余節(jié)點(diǎn)分配給計(jì)算資源集合Preserve。

圖8 并行度調(diào)整算法

該算法的復(fù)雜度主要對(duì)于集合Vvictim中的每個(gè)節(jié)點(diǎn)，DetectParallel函數(shù)需要遍歷其水平或者垂直的鄰居節(jié)點(diǎn)，ScaleParallel函數(shù)需要通過排序算法選擇一個(gè)鄰居節(jié)點(diǎn)進(jìn)行合并。然而這個(gè)過程被限制在了數(shù)據(jù)流圖模型的一個(gè)局部結(jié)構(gòu)，所以涉及到的節(jié)點(diǎn)個(gè)數(shù)有限，使得該算法能夠在有效的時(shí)間內(nèi)完成。而全局的排序算法主要集中在第4步，出于復(fù)雜度的考慮，步驟4使用了貪心算法，保證算法整體可行。

5 實(shí)驗(yàn)與結(jié)果分析

5.1 實(shí)驗(yàn)平臺(tái)與基準(zhǔn)程序

本文選擇parallella開發(fā)板[11]作為實(shí)驗(yàn)平臺(tái)。Parallella開發(fā)板上集成了一個(gè)ARMA9中央處理器，和一個(gè)Epiphany的協(xié)處理器，包含16個(gè)計(jì)算單元，每個(gè)計(jì)算單元包含一個(gè)緊耦合的32KB的SRAM存儲(chǔ)器。Parallella板上集成集成了1GB大小的DDR3存儲(chǔ)器作為內(nèi)存，其中的32MB的存儲(chǔ)空間作為被主控制單元ARMA9處理器和協(xié)處理器Epiphany共享。

Parallella平臺(tái)支持OpenCL的編程框架，主控制處理器ARMA9上搭載Linux的操作系統(tǒng)，其中OpenCL的API基于Epiphany提供的軟件開發(fā)包[12](epiphanysoftwaredevelopmentkit,eSDK)實(shí)現(xiàn)。Host處理器ARMA9通過API函數(shù)管理和控制Epiphany的每個(gè)計(jì)算單元執(zhí)行特定的計(jì)算任務(wù)。

本文選擇StreamIT基準(zhǔn)程序作為評(píng)估該編程框架和運(yùn)行時(shí)系統(tǒng)的基準(zhǔn)程序[13]。StreamIT是由美國(guó)麻省理工大學(xué)計(jì)算機(jī)系統(tǒng)實(shí)驗(yàn)室研發(fā)的針對(duì)流式應(yīng)用程序的高層編程語(yǔ)言，它同時(shí)收集了多個(gè)典型的流式應(yīng)用程序作為基準(zhǔn)測(cè)試程序集合。

5.2 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

本文假設(shè)16個(gè)計(jì)算單元全部可用的場(chǎng)景為靜態(tài)任務(wù)映射起點(diǎn)[10]作為動(dòng)態(tài)并行度伸縮的起點(diǎn)。為了說明本文方法的有效性，本文將與Flextream[7]的結(jié)果進(jìn)行對(duì)比，為了保證對(duì)比的公平性，我們將Flextream[7]的算法在Parallella的開發(fā)板上進(jìn)行了實(shí)現(xiàn)，對(duì)比將從流水核心期性能、動(dòng)態(tài)伸縮調(diào)度時(shí)間開銷和運(yùn)行時(shí)系統(tǒng)整體性能及吞吐能力三個(gè)方面展開。流水核心期的性能是評(píng)估的首要指標(biāo)，因?yàn)橐粋€(gè)基于流水調(diào)度方法實(shí)現(xiàn)的系統(tǒng)的性能主要取決于流水核心期的性能。本文提出了動(dòng)態(tài)的并行度伸縮和調(diào)度的方法，動(dòng)態(tài)變化的時(shí)間開銷也是衡量該運(yùn)行時(shí)系統(tǒng)的一個(gè)關(guān)鍵因素。本文以一個(gè)連續(xù)變化的場(chǎng)景來評(píng)估系統(tǒng)整體的性能和吞吐能力。

(1) 流水核心期性能。圖 9(a) 表示了基準(zhǔn)程序的流水核心期在12/8/4個(gè)處理單元上執(zhí)行相對(duì)于在1個(gè)處理單元上執(zhí)行的加速比，它們都是從16個(gè)處理單元的場(chǎng)景動(dòng)態(tài)調(diào)整過來的，與Flextream[7]相比，本文可以獲得最多17%的核心期性能提升。這是因?yàn)楸疚脑跊Q策期采用的算法首先考慮了適當(dāng)?shù)恼{(diào)整并行度，避免了在處理資源減少的情況下過度并行導(dǎo)致的不必要通信和同步的開銷，從而提升了性能。

(2) 動(dòng)態(tài)伸縮調(diào)度時(shí)間開銷。除了核心期的性能之外，完成一次動(dòng)態(tài)調(diào)整切換的時(shí)間開銷也是衡量系統(tǒng)性能的重要指標(biāo)，此處選擇基準(zhǔn)程序MPEG2作為基準(zhǔn)程序。根據(jù)第4節(jié)的闡述，運(yùn)行時(shí)系統(tǒng)通過決策期和切換期兩個(gè)階段完成對(duì)應(yīng)用程序的動(dòng)態(tài)調(diào)度。決策期如圖 7中點(diǎn)劃線包含的框所示，包含并行度調(diào)整、迭代周期和緩存需求計(jì)算等。圖 9(b) 展示了決策期從16個(gè)可用計(jì)算單元的場(chǎng)景分別到1～15個(gè)可用計(jì)算單元的場(chǎng)景所需的時(shí)間開銷。因?yàn)殪o態(tài)任務(wù)映射是基于16個(gè)可用計(jì)算單元的，所以越接近16個(gè)計(jì)算單元的變化場(chǎng)景，所需的時(shí)間開銷越小。同樣的，本文與Flextream[7]的算法的時(shí)間開銷進(jìn)行對(duì)比。在場(chǎng)景變化比較大的情況下，例如從16個(gè)計(jì)算單元到4個(gè)可用計(jì)算單元場(chǎng)景變化，本文的時(shí)間開銷更小。這是因?yàn)椴⑿卸日{(diào)整算法(圖 8)中步驟2和步驟3局部合并了一些節(jié)點(diǎn)，從而降低了步驟4中的排序算法的時(shí)間復(fù)雜度。然而當(dāng)場(chǎng)景變化比較小時(shí)，例如從16個(gè)計(jì)算單元到1個(gè)計(jì)算單元的場(chǎng)景變化，本文的算法帶來的局部搜索和比較的復(fù)雜度超過了全局排序降低的復(fù)雜度，則會(huì)消耗更多的時(shí)間。圖 9(c) 展示了切換期的時(shí)間開銷，從16個(gè)可用計(jì)算單元到1到15個(gè)可用資源15個(gè)場(chǎng)景變化。切換期的調(diào)度分為流水退出期和流水建立期兩個(gè)階段，圖 9(c) 進(jìn)行了分別的比較。退出期的時(shí)間開銷主要取決于前一個(gè)場(chǎng)景的資源分配和流水階段總數(shù)，因?yàn)楸緦?shí)驗(yàn)所設(shè)計(jì)的15個(gè)場(chǎng)景的起點(diǎn)都是基于16個(gè)可用計(jì)算單元，所以退出期調(diào)度的時(shí)間開銷和Flextream的算法基本一致。然而由于本文的動(dòng)態(tài)伸縮算法建立新場(chǎng)景時(shí)減少了不必要的并行度帶來的開銷，所以在流水建立期上與Flextream相比可最多減小7%的時(shí)間開銷。

(a) 流水核心期性能

(b) 動(dòng)態(tài)調(diào)度決策期時(shí)間開銷

(c) 動(dòng)態(tài)調(diào)度切換期時(shí)間開銷

(3) 運(yùn)行時(shí)系統(tǒng)整體性能和吞吐能力。盡管動(dòng)態(tài)調(diào)度的決策是基于一個(gè)靜態(tài)的任務(wù)映射結(jié)果，但系統(tǒng)仍然可以從任意的一個(gè)場(chǎng)景遷移到另一個(gè)。本文評(píng)估了MPEG2基準(zhǔn)程序在一個(gè)連續(xù)變化的場(chǎng)景下的運(yùn)行效率，可用的計(jì)算單元數(shù)按照16、13、9、5、7依次變化，每個(gè)場(chǎng)景持續(xù)200s時(shí)間。在整個(gè)變化過程中，本文的運(yùn)行時(shí)系統(tǒng)可以完成432000次完整的執(zhí)行，F(xiàn)lextream可以完成374000次。由于流式應(yīng)用程序每一次完整地執(zhí)行消耗和產(chǎn)生等量的數(shù)據(jù)，所以本文在整體上提供了更高的數(shù)據(jù)吞吐率。

6 結(jié) 論

本文首先提出了流式應(yīng)用程序基于OpenCL編程框架的實(shí)現(xiàn)方法，并基于此設(shè)計(jì)了動(dòng)態(tài)調(diào)度的運(yùn)行時(shí)系統(tǒng)。當(dāng)計(jì)算資源發(fā)生變化時(shí)，運(yùn)行時(shí)系統(tǒng)通過決策期合理的調(diào)整并行度和任務(wù)分配，隨后通過流水線調(diào)度的退出期和建立期完成動(dòng)態(tài)切換。實(shí)驗(yàn)表明，相較于已有的Flextream，本文可以最多提升17%的核心期性能，并降低7%的切換時(shí)間開銷。

[ 1] Liu L, Zhou Y, Tian L, et al. CPC-based backward compatible network access for LTE cognitive radio cellular networks.IEEECommunicationMagazine, 2015, 53(7): 93-99

[ 2] Zhou Y, Liu L, Pan Z, et al. Two-stage cooperative multicast transmission with optimized power consumption and guranteed coverage.IEEEJSAConSEED, 2014, 32(2):274-284

[ 3] Garcia V, Zhou Y, Shi J. Coordinated multipoint transmission in dense cellular networks with user-centric adaptive clustering.IEEETransWirelessComm, 2014, 13(8):4297-4308

[ 4] The OpenCL Specification, Khronos OpenCL Working Group, https: //www.khronos.org/opencl/. 2016

[ 5] Schor L, Bacivarov L, Yang H, et al. Expandable process networks to efficiently specify and explore task, data, and pipeline parallelism. In: Proceedings of the 2014 International Conference on Compilers, Architecture and Sythesis for Embedded Systems, New Dehli, India, 2014

[ 6] Choi Y, Li C, Silva D, et al. Adaptive task duplication using online bottleneck dectection for streaming applications for heterogeneous architecture. In: Proceedings of the 9th Conference on Computing Frontiers, NY, USA, 2012. 163-172

[ 7] Hormati A, Choi Y, Kudlur M, et al. Flextream: Adaptive compilation of streaming applications for heterogeneous architectures. In: Proceedings of the 18th International Conference on Parallel Architecture and Compilation Techniques, Raleigh, USA. 214-223

[ 8] Lee E A, Messerschmitt D G. Synchronous data flow.ProceedingsoftheIEEE, 1987, 75: 1235-1245

[ 9] Allan V, Jones R, Lee R, et al. Software pipelining.ACMComputingSurveys, 1995, 27: 367-432

[10] Gordon M, Thies W, Amarasinghe S. Exploiting coarse-grained task, data, pipeline parallelism in stream programs. In: Proceedings of the 12th International Conference on Architecture Support for Programming Languages and Operating Systems, San Jose, USA, 2006. 151-162

[11] E16g301 epiphany 16-core microprocessor. http://adapteva.com/docs/e16g301 datasheet.pdf

[12] Epiphany sdk reference. http://adapteva.com/docs/epiphany sdk ref.pdf

[13] StremI T. http://groups.csail.mit.edu/cag/streamit/shtml/benchmarks.shtml

An openCL based streaming applications program’s dynamic parallelism scaling scheduling on MPSoC

Huang Shan******, Shi Jinglin******, Xiao Fang***

(*Wireless Communication Research Center, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190)(**Beijing Key Laboratory of Mobile Computing and Pervasive Device, Beijing 100190)(***University of Chinese Academy of Sciences, Beijing 100049)

The complex and diversity trends of the application programs for embedded computing systems were analyzed. Then, a unified programming framework based on the open computing language (OpenCL) was proposed for embedded computing systems’ common streaming application programs, and on the basis of the framework, a runtime system was designed. Under the variation of application programs’ computing resources, the system on-line regulates programs’ parallelism, and conducts dynamic parallelism scaling scheduling. The experimental results showed that, compared with the existing dynamic scheduling system of Flextream, the proposed scheduling system’s performance was improved by 17%, and the runtime overhead of the dynamic scheduling was reduced by 7%.

multiprocessor system on chip (MPSoC), open computing language (OpenCL), programming framework, parallelism scaling, runtime system

10.3772/j.issn.1002-0470.2016.12.001

①國(guó)家自然科學(xué)基金(61431001)和北京市青年拔尖人才(2015000021223ZK31)資助項(xiàng)目。

2016-09-07)

②女，1988年生，博士生；研究方向：通信基帶芯片設(shè)計(jì)，專用矢量DSP處理器設(shè)計(jì)，片上多核調(diào)度系統(tǒng)設(shè)計(jì)；聯(lián)系人，E-mail: huangshan@ict.ac.cn