黃 姍 石晶林 蕭 放

(*中國科學院計算技術研究所無線通信技術研究中心 北京 100190)(**北京市移動計算與新型終端重點實驗室 北京 100190)(***中國科學院大學 北京 100049)

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

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

(*中國科學院計算技術研究所無線通信技術研究中心 北京 100190)(**北京市移動計算與新型終端重點實驗室 北京 100190)(***中國科學院大學 北京 100049)

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

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

0 引 言

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

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

1 OpenCL簡介

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

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

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

2 流式應用程序建模分析

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

2.1 流式應用程序的SDF模型

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

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

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

o×r1=i×r2

(1)

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

2.2 并行度的表征

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

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

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

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

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

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

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

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

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

3.1 數(shù)據(jù)流圖模型到異構平臺的映射

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

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

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

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

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

4 運行時系統(tǒng)

本節(jié)描述運行時系統(tǒng)對流式應用程序的調(diào)度，以及在線調(diào)整并行度進行動態(tài)調(diào)度的方法。

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

由于流式應用程序經(jīng)常需要重復執(zhí)行多次來處理源源不斷到達的數(shù)據(jù)，所以一個典型的流式應用程序的頂層有一個隱式的循環(huán)。根據(jù)這個特征，Gordon等人將軟流水技術調(diào)度應用在粗粒度的任務層次[10]，通過對整個流式應用程序頂層的隱式循環(huán)進行展開，來自不同循環(huán)迭代次數(shù)的任務就可以并行執(zhí)行，流式應用程序因為本身的特征可以很自然地從流水并行中獲得巨大的數(shù)據(jù)吞吐收益。

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

vi, vj∈V; mapvi, mapvj∈P

(2)

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

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

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

(vi,vj)∈E

(3)

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

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

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

4.2 運行時系統(tǒng)調(diào)度流程

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

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

4.3 在線并行度伸縮算法

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

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

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

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

(4)

圖7 運行時系統(tǒng)流程圖

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

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

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

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

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

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

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

5 實驗與結果分析

5.1 實驗平臺與基準程序

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

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

本文選擇StreamIT基準程序作為評估該編程框架和運行時系統(tǒng)的基準程序[13]。StreamIT是由美國麻省理工大學計算機系統(tǒng)實驗室研發(fā)的針對流式應用程序的高層編程語言，它同時收集了多個典型的流式應用程序作為基準測試程序集合。

5.2 實驗設計與結果分析

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

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

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

(a) 流水核心期性能

(b) 動態(tài)調(diào)度決策期時間開銷

(c) 動態(tài)調(diào)度切換期時間開銷

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

6 結 論

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

[ 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

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

2016-09-07)

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