蔡田田， 習(xí)偉， 郭曉斌， 姚浩， 黃凱

(1.南方電網(wǎng)科學(xué)研究院有限責(zé)任公司， 廣東 廣州 510080； 2. 浙江大學(xué) 信息與電子工程學(xué)院， 浙江 杭州 310027 )

多粒度通信優(yōu)化的MPSoC調(diào)度映射策略

蔡田田1， 習(xí)偉1， 郭曉斌1， 姚浩1， 黃凱2

(1.南方電網(wǎng)科學(xué)研究院有限責(zé)任公司， 廣東 廣州 510080； 2. 浙江大學(xué) 信息與電子工程學(xué)院， 浙江 杭州 310027 )

隨著嵌入式系統(tǒng)處理器核數(shù)的增加，映射與調(diào)度成為軟件開發(fā)的關(guān)鍵. 為了提升系統(tǒng)性能，需要格外關(guān)注映射與調(diào)度過程中的通信開銷.現(xiàn)有的粗粒度系統(tǒng)級或細(xì)粒度線程級通信優(yōu)化雖然能提升性能，但都各有缺陷.為此,提出了基于整數(shù)線性規(guī)劃的用于Simulink模型的多粒度通信優(yōu)化映射與調(diào)度策略，將不同粒度的通信優(yōu)化方法相結(jié)合，實現(xiàn)優(yōu)勢互補(bǔ).實驗結(jié)果表明，該方法能有效提高系統(tǒng)的整體性能.

整數(shù)線性規(guī)劃；映射與調(diào)度；多粒度通信優(yōu)化

0 引 言

隨著高性能嵌入式軟件應(yīng)用需求的日益增長，多核片上系統(tǒng)(multi-processor system on chip, MPSoC)成為研究的熱門領(lǐng)域.對于給定的應(yīng)用，如何將任務(wù)分配至不同的線程或處理器，即映射與調(diào)度問題，對于提升系統(tǒng)性能尤為關(guān)鍵.

自多核處理器問世以來，映射與調(diào)度問題因其復(fù)雜性與關(guān)鍵性而備受關(guān)注. 系統(tǒng)運(yùn)行過程中，許多影響性能的因素，諸如通信開銷、負(fù)載平衡、線程切換等都需要深入研究. 隨著處理器核數(shù)的增加，如何最小化多核處理器的通信開銷成為其中最為關(guān)鍵的問題.

針對通信開銷問題，一些文獻(xiàn)提出了映射與調(diào)度過程中降低通信開銷的方法. COTTON等[1]提出了通過多準(zhǔn)則優(yōu)化找到多核處理器映射的帕累托最優(yōu)解，使得多核處理器之間的通信開銷最小，同時保證負(fù)載平衡. FERRANDI等[2]針對映射與調(diào)度提出采用蟻群算法優(yōu)化系統(tǒng)性能. 黃凱等[3]基于整數(shù)線性規(guī)劃(ILP)提出的映射與調(diào)度策略定義了3層系統(tǒng)架構(gòu)，其中包含處理器內(nèi)部的通信優(yōu)化與處理器間的通信優(yōu)化. 然而，從圖1(a)所示的系統(tǒng)層次看，以上方法僅在粗粒度通信優(yōu)化條件下起作用，且都是通過控制線程或者處理器之間的通信信道進(jìn)行優(yōu)化，比如通過給各個處理器分配任務(wù)來減少占用的信道數(shù)量或減少每個信道的通信數(shù)據(jù)量.

圖1 粗粒度系統(tǒng)級對比細(xì)粒度線程級通信優(yōu)化Fig.1 Coarse-grained system level vs. fine-grained thread level communication optimization

另外，文獻(xiàn)[4-5]提出線程層次的細(xì)粒度通信優(yōu)化，如圖1(b)所示，主要通過對有依賴關(guān)系的線程之間通信任務(wù)的控制進(jìn)行優(yōu)化，比如在一個線程的運(yùn)算任務(wù)和通信發(fā)送任務(wù)執(zhí)行之前，提前執(zhí)行通信接收任務(wù)[4]，并合并有著相同源線程與目標(biāo)線程的通信發(fā)送與接收任務(wù). 這些優(yōu)化手段均在一定程度上降低了信道的啟動與傳輸時間，但從全局來看，可能會影響系統(tǒng)的整體性能，因為這些優(yōu)化手段無法在全局分配通信，可能會引入更多的系統(tǒng)延遲.

通過對比粗粒度與細(xì)粒度通信優(yōu)化發(fā)現(xiàn)，粗粒度優(yōu)化可以全局分配通信得到最佳性能，但缺乏對信道的局部處理；而細(xì)粒度優(yōu)化能對信道進(jìn)行局部優(yōu)化，但沒法考慮系統(tǒng)全局的性能. 因此，可以將一種結(jié)合全局與局部處理的多粒度通信優(yōu)化應(yīng)用到映射與調(diào)度過程中.

本文提出一種基于整數(shù)線性規(guī)劃(integer linear programming, ILP)的多粒度靜態(tài)映射與調(diào)度策略，對Simulink模型進(jìn)行性能優(yōu)化. 在映射階段，根據(jù)負(fù)載平衡原理將任務(wù)分配至每個處理器的線程，并基于ILP粗粒度系統(tǒng)級進(jìn)行通信優(yōu)化. 在調(diào)度階段，確定所有任務(wù)的執(zhí)行順序，并引入細(xì)粒度線程級通信優(yōu)化，采用ILP方法分配通信流水線與消息聚合，以降低每個信道的通信開銷.

本文主要描述一種結(jié)合粗粒度和細(xì)粒度通信優(yōu)化的映射與調(diào)度策略，與以往大量的映射與調(diào)度策略相比，主要貢獻(xiàn)在于引入了針對細(xì)粒度Simulink模型的面向通信的優(yōu)化方法，首次引入多粒度通信優(yōu)化這一概念，并將其應(yīng)用于映射與調(diào)度過程中.

1 背景介紹

1.1 建 模

功能模型能夠體現(xiàn)具體應(yīng)用程序的并行性，并且容易轉(zhuǎn)化成如LESCEA[6]所支持的多線程代碼. 一些能夠建立功能模型的高級語言如KPN (Khan Process Network)[7]、dataflow[8]、Simulink[9]已被用于系統(tǒng)定義與代碼生成. 本文采用Simulink模型.

Simulink模型定義了目標(biāo)系統(tǒng)的軟硬件架構(gòu)，文獻(xiàn)[7，10-11]描述了其具體細(xì)節(jié). 通常Simulink模型包括圖2所示的3部分.

圖2 Simulink體系架構(gòu)Fig.2 A Simulink hierarchical structure

·Simulink模塊(block)代表一個包含輸入輸出的功能塊函數(shù).比如用戶自定義函數(shù)(S-function)、離散時間延遲、預(yù)定義塊等運(yùn)算操作. 本實驗采用了如圖2所示的功能模塊，代表系統(tǒng)運(yùn)行與收發(fā)消息的通信過程.

·Simulink鏈接(link)是相關(guān)模塊之間一對多的鏈接，其中一個輸出端口與多個輸入端口相對應(yīng). 如果一個鏈接從F0到F1，則稱F1依賴于F0，記作F0_>F1. 對于一個從發(fā)送模塊S到接收模塊R的鏈接，稱之為通信向量，記作S_>R.

·Simulink子系統(tǒng)包含若干Simulink模塊、Simulink鏈接以及其他子系統(tǒng)，表示層級結(jié)構(gòu)和條件語句，如for循環(huán)或if-then-else結(jié)構(gòu).

本文的設(shè)計如圖2所示，MPSoC Simulink模型的架構(gòu)可以分為系統(tǒng)層、子系統(tǒng)層、線程層3層. 其中系統(tǒng)層包括多個CPU子系統(tǒng)以及子系統(tǒng)間的通信信道；子系統(tǒng)層為一個CPU子系統(tǒng)架構(gòu)，包括一系列線程以及線程間的通信信道；線程層指包含Simulink模塊和Simulink鏈接的軟件線程.

1.2 通信流水線與消息聚合

分布式存儲架構(gòu)是一個普遍采用的處理器間通信的體系結(jié)構(gòu).其中分布式存儲服務(wù)器(distributed memory server, DMS)用于處理器間通信.DMS可在初始化之后自動傳輸數(shù)據(jù)而無須處理器干預(yù). 利用此特性，通信流水線能降低處理器之間數(shù)據(jù)傳輸?shù)耐ㄐ砰_銷. 為實現(xiàn)一個線程的并行計算和通信，所需的運(yùn)算數(shù)據(jù)必須在運(yùn)算前就緒，即要求在當(dāng)前周期(一個周期代表所有的線程均執(zhí)行一次[7，10])之前完成數(shù)據(jù)的傳輸與緩存，以便功能模塊能直接使用緩存數(shù)據(jù)進(jìn)行當(dāng)前周期的運(yùn)算. 因此，通信流水線可以最小化DMS的傳輸時間.

圖3直觀地描述了通信流水線，(a) (b) (c)分別為應(yīng)用模型、未采用通信流水線代碼、采用通信流水線代碼的示意圖，圖3(d)描述了(c)的執(zhí)行順序，其中R0、F1、S1在使用了通信流水線之后并行執(zhí)行.

圖3 通信流水線Fig.3 Communication pipeline

通信流水線通過將數(shù)據(jù)延遲一個周期使運(yùn)算與通信并行，若使用不當(dāng)，這一延遲會導(dǎo)致處理器阻塞，降低系統(tǒng)性能.

上述技術(shù)可以縮短通信的傳輸時間，其優(yōu)化時間取決于傳輸?shù)臄?shù)據(jù)量，但是每次通信的啟動時間無法優(yōu)化. 而消息聚合是將具有相同源線程和目的線程的消息合并傳輸，從而有效減少通信次數(shù)，節(jié)省啟動時的開銷.

圖4描述了一個消息聚合的例子，其中2條消息被合并傳輸，通信的啟動時間能節(jié)省50%.但是消息聚合有可能會造成發(fā)送延遲，進(jìn)而影響系統(tǒng)的性能.

圖4 消息聚合Fig.4 Message aggregation

2 基于ILP的多粒度通信優(yōu)化的映射與調(diào)度策略

首先，簡單起見，假定每個處理器線程數(shù)目為4，并與該處理器綁定. 映射階段決定了各任務(wù)、線程間的關(guān)系及其劃分結(jié)果，并權(quán)衡考慮了負(fù)載平衡與通信開銷最小化，其中粗粒度系統(tǒng)級通信優(yōu)化被用于最小化處理器內(nèi)部與處理器之間的通信開銷.

其次，基于映射的結(jié)果，利用通信流水線與消息聚合，進(jìn)行線程內(nèi)部與線程之間的任務(wù)調(diào)度，以降低通信開銷，優(yōu)化系統(tǒng)整體性能.

2.1 粗粒度系統(tǒng)級通信優(yōu)化映射

系統(tǒng)整體性能由所有處理器中最長的執(zhí)行時間決定，因此在映射過程中保持各處理器之間的負(fù)載平衡是提高性能的最基本要求，其中歸一化變量負(fù)載不均衡度(WG)指各處理器的負(fù)載與系統(tǒng)平均負(fù)載之差的總和，表示各處理器的負(fù)載平衡狀況.處理器間過多的通信將會延長其執(zhí)行過程中的阻塞時間，而處理器內(nèi)部過多的通信會延長處理器線程切換的時間. 處理器之間與處理器內(nèi)部的通信從系統(tǒng)層面可看作線程間的通信，因此需將這兩者的通信開銷最小化. 在映射過程中，從系統(tǒng)層面看，任務(wù)被劃分并分配到各線程，所以將粗粒度系統(tǒng)級通信優(yōu)化整合在ILP方程中，可以最小化所分配的信道數(shù)量.

在列舉ILP公式變量之前，先給出一些記號.

2.1.1 常 量

·P表示處理器數(shù)量.

·T表示任務(wù)數(shù)量.

·TH表示線程集合，線程thi∈TH與處理器pi/4∈P綁定.

·Nij為任務(wù)ti，tj之間的通信量大小.

·Dij為布爾型常量，表示任務(wù)ti與tj之間是否有依賴關(guān)系，當(dāng)tj依賴于ti時，該值為1.

·ETi為任務(wù)ti的執(zhí)行時間.

2.1.2 變 量

·Ai,m為布爾型變量，表示任務(wù)與線程之間的映射關(guān)系，當(dāng)任務(wù)ti被映射到線程thm時，該值為1.

·Sij,m為布爾型變量，表示任務(wù)之間的映射關(guān)系，當(dāng)任務(wù)ti、tj被分配至線程thm時，該值為1.

·Bij,k為布爾型變量，表示任務(wù)之間的映射關(guān)系，當(dāng)任務(wù)ti、tj被分配至處理器pk時，該值為1.

·Interi,m為布爾型變量，當(dāng)處理器間通信任務(wù)ti被映射至線程thm時，該值為1.

2.1.3 目 標(biāo)

以下目標(biāo)函數(shù)可實現(xiàn)線程間通信量(CS)、負(fù)載不均衡度(WG)最小化，在保證k1+k2=1的情況下通過調(diào)節(jié)目標(biāo)函數(shù)中的權(quán)重k1，k2實現(xiàn)兩者的均衡.

min(k1×CS+k2×WG)，

(1)

(2)

(3)

2.1.4 約束條件

·每個任務(wù)必須被分配到一個線程.

(4)

·若任務(wù)ti或tj未被分配到線程thm，則Sij,m為0.

Sij,m≤(Ai,m+Aj,m)/2.

(5)

·若任務(wù)ti或tj未被分配到處理器pk，則Bij,k為0.

(6)

·若互相依賴的任務(wù)ti和tj被映射到不同處理器，則他們之間存在處理器間通信.

(7)

·每個線程至少包含1個跨處理器通信任務(wù).

(8)

式(7)、(8)中MAX是一個足夠大的正整數(shù). 由以上公式，可得到一一對應(yīng)的任務(wù)線程和負(fù)載不均衡度和通信開銷最小的映射最優(yōu)解.

2.2 細(xì)粒度線程級通信優(yōu)化調(diào)度

調(diào)度過程決定了線程內(nèi)和線程間任務(wù)的執(zhí)行順序. 不合理的調(diào)度會延長處理器同步等待時間，從而降低動態(tài)性能.

在這個階段，建立了另一組ILP方程，并基于上述映射結(jié)果決定調(diào)度過程. 在映射階段后，處理器內(nèi)與處理器間的通信任務(wù)被添加到各個線程. 在線程與處理器內(nèi)所有任務(wù)的調(diào)度過程中，通信任務(wù)將影響系統(tǒng)性能. 因此，需要用細(xì)粒度線程級通信優(yōu)化，包括采用通信流水線和消息聚合技術(shù)來提高系統(tǒng)性能. 對于一個確定的映射，通信流水線僅可應(yīng)用于處理器間的通信任務(wù)，而消息聚合可應(yīng)用于處理器內(nèi)和處理器間.

在引入基于ILP方法的通信優(yōu)化之前，首先須對2項優(yōu)化技術(shù)進(jìn)行量化，并分析其對調(diào)度結(jié)果和性能的影響. 為便于從細(xì)粒度Simulink模型角度分析，在下文的描述中用模塊代表前文提到的任務(wù)(兩者屬同一概念). 如圖3所示，當(dāng)通信流水線被應(yīng)用于一對互相通信的任務(wù)中時，通信向量S_>R中的數(shù)據(jù)在當(dāng)前周期被R接收并在下個周期被使用，這將導(dǎo)致nb_R0，F(xiàn)1，S1，即一個線程周期的執(zhí)行時間產(chǎn)生延遲. 從線程T1看，通信流水線僅提前1個周期執(zhí)行接收任務(wù)，不會改變此線程任務(wù)執(zhí)行的順序.

消息聚合，將相同源線程和目的線程中對應(yīng)的通信任務(wù)聚合到一起，導(dǎo)致模塊數(shù)量和執(zhí)行順序發(fā)生改變. 為保持模塊間數(shù)據(jù)的相關(guān)性，由消息聚合得到的模塊其執(zhí)行順序應(yīng)遵守以下規(guī)則：

·在發(fā)送線程，聚合模塊間的模塊應(yīng)先于新模塊.當(dāng)發(fā)送模塊S0和S1被聚合成S01時，原本位于S0和S1之間的功能模塊S3，應(yīng)移至S01之前，如圖4(d)中T1的代碼所示.

·在接收線程，聚合模塊間的模塊應(yīng)晚于新模塊.當(dāng)接收模塊R0和R1被聚合成R01時，原本位于R0和R1之間的功能模塊F1，應(yīng)移至R01之后， 如圖4(d)中T0的代碼所示.

基于以上分析，建立了一組ILP方程來決定調(diào)度策略. 同時，為了提升性能，通信流水線和消息聚合應(yīng)被合理分配到通信向量中，以最優(yōu)化細(xì)粒度通信.

2.2.1ILP方程各量

2.2.1.1 常 量

·B表示模塊的集合，包括功能模塊和通信模塊.

·T表示線程的集合.

·P表示處理器的集合.

·exei為功能模塊bi∈B的執(zhí)行時間.

·commi為通信模塊bi∈B的傳輸時間.

·commstratup為任意通信模塊的啟動時間.

·interi為布爾型常量，當(dāng)通信模塊bi∈B是處理器間通信模塊時，該值為1，即bi和相關(guān)的通信模塊位于不同的處理器上.

·Dij為布爾型常量，表示模塊bi∈B和bj∈B間的依賴關(guān)系，當(dāng)bj依賴于bi時該值為1.

·switch為線程切換時間.

·cyc為每個模塊總的執(zhí)行周期數(shù).

2.2.1.2 變 量

·eij為布爾型變量，表示模塊間的執(zhí)行順序，當(dāng)相同線程內(nèi)的模塊bi∈B先于bj∈B執(zhí)行時該值為1.

·toverall為一個應(yīng)用程序總的執(zhí)行時間.

·si,k為第k周期模塊bi∈B的調(diào)用時間.

·Mij為布爾型變量，表示消息聚合是否被用于包含相同源線程和目的線程的通信模塊，當(dāng)這種模塊bi∈B和bj∈B被聚合在一起時，該值為1.

·CPi為布爾型變量，表示通信流水線是否被用于通信模塊bi∈B，當(dāng)bi被通信流水線化時，該值為1.

·COMMi為消息聚合后，通信模塊bi∈B的傳輸時間.

2.2.1.3 目 標(biāo)

·為了最大化提升性能，應(yīng)最小化系統(tǒng)總執(zhí)行時間：

min(toverall).

(9)

2.2.1.4 約束條件

·同一線程內(nèi)模塊的執(zhí)行順序應(yīng)滿足原始數(shù)據(jù)的相關(guān)性：

eij≥Dij,i,j≤|B|.

(10)

·消息聚合可能影響模塊的執(zhí)行順序以及通信時間.

對于相同線程內(nèi)的模塊bi∈B和bj∈B，假設(shè)bi早于bj執(zhí)行：

eik+(1-Mij)×MAX≥ejk,

eik+(Mij-1)×MAX≤ejk,k≤|B|.

(11)

其中，MAX是一個足夠大的正整數(shù).

聚合后新模塊的通信傳輸時間為原模塊時間之和：

COMMi=Mij×commj+commi,

COMMj=(1-Mij)×commj-Mij×commstartup.

(12)

·相同線程內(nèi)的模塊依據(jù)eij執(zhí)行. 假設(shè)bi∈B和bj∈B被映射到相同的線程，并且bi先于bj執(zhí)行，在第k周期bi的結(jié)束時間應(yīng)該早于第k周期bj的調(diào)用時間，且第(k+1)周期bi的調(diào)用時間應(yīng)該晚于第k周期bj的結(jié)束時間：

(13)

timei和timej分別表示完成bi和bj的時間. 如果bi(bj)是一個功能模塊，那么

timei=exei(or timej=exej)，

(14)

否則，

timei=commstartup+COMMi

or

timej=commstartup+COMMj.

(15)

考慮通信流水線的影響，

(16)

如果bi(bj)是一個通信模塊，則

timei=commstartup+(1-CPi)×COMMi

or

timej=commstartup+(1-CPj)×COMMj.

(17)

·對于一對通信模塊bi∈B和bj∈B，假設(shè)bi是發(fā)送模塊，bj是接收模塊，第k周期bi的結(jié)束時間應(yīng)該早于第k周期bj的調(diào)用時間，且第(k+1)周期bi的調(diào)用時間應(yīng)該晚于第k周期bj的結(jié)束時間.進(jìn)一步，如果bi和bj位于相同的處理器上，在bi執(zhí)行完畢后，需要線程切換來執(zhí)行bj:

si,k+commstartup+COMMi+(1-interi)×switch≤

sj,k,sj,k+commstartup+COMMj+(1-interj)×

switch≤si,k+1.

(18)

·同一處理器不能同時執(zhí)行2個模塊，即同一處理器上任意2個模塊的執(zhí)行時間不能重疊. 假設(shè)模塊bi∈B和bj∈B被分配到相同處理器的不同線程，第k周期bi的執(zhí)行時間不能與第k′周期bj的執(zhí)行時間重疊：

(19)

在該約束下，timei和timej由式(14)和(17)定義.m是一個布爾型變量，當(dāng)?shù)趉周期bi的結(jié)束時間早于第k′周期bj的調(diào)用時間時，該值為1.

·應(yīng)用程序總的執(zhí)行時間取決于第cyc周期每個模塊的調(diào)用時間.對于任意模塊bi∈B，

toverall≥si,cyc+timei，

(20)

timei由式(14)和(17)定義.

解決了上述規(guī)劃問題，可得到所有任務(wù)的執(zhí)行順序，并且可在通信任務(wù)間引入通信流水線和消息聚合. 由于任務(wù)已經(jīng)映射到確定的處理器線程，故線程間和線程內(nèi)的調(diào)度也將確定.

縱觀整個多粒度通信優(yōu)化流程，在映射階段，以粗粒度通信優(yōu)化為主導(dǎo)，通過最小化線程間和線程內(nèi)的通信開銷，為細(xì)粒度通信優(yōu)化構(gòu)建一個更加輕量級的通信網(wǎng)絡(luò). 在調(diào)度階段，加入細(xì)粒度通信優(yōu)化，進(jìn)一步減小信道分配開銷，從而全面降低系統(tǒng)的通信開銷.

3 實現(xiàn)平臺與實驗結(jié)果

3.1 實現(xiàn)平臺

借助LESCEA(light and efficient simulink compiler for embedded application)多線程代碼生成器，在基于Simulink的MPSoC設(shè)計平臺[7，10-11]上實現(xiàn). 以Simulink為模型，輸入并生成一系列能被目標(biāo)硬件架構(gòu)執(zhí)行的軟件代碼. 多線程代碼生成的整體流程如圖5所示，共包含4個步驟：1) 映射：每個任務(wù)被分配到一個處理器的一個線程，并加入粗粒度系統(tǒng)級通信優(yōu)化，得到一個系統(tǒng)模型作為LESCEA的起始點. 2) 調(diào)度:在考慮細(xì)粒度線程級通信優(yōu)化的同時，決定每個線程內(nèi)任務(wù)的執(zhí)行順序以及每個處理器內(nèi)線程的執(zhí)行順序. 3) 線程代碼生成:對于每個線程，生成一組包含內(nèi)存聲明和一系列函數(shù)調(diào)用的C語言代碼. 4) 依賴于硬件的軟件庫(hardware dependent software)適應(yīng):為每個處理器產(chǎn)生一份主代碼，以及一份將線程鏈接到HdS庫的Makefile文件.

圖5 多線程代碼生成流程Fig.5 Multithreaded code generation flow

實驗所用的硬件平臺如圖6所示. 該平臺是一個靈活性較高的MPSoC，其中包含用作處理器擴(kuò)展的高效互聯(lián)網(wǎng)絡(luò). 包括8個CPU子系統(tǒng)，1個全局內(nèi)存子系統(tǒng)，以及1個將CPU和內(nèi)存子系統(tǒng)橋接在一起的互聯(lián)網(wǎng)絡(luò). 每個CPU子系統(tǒng)包含1個基于CK Core的32位7級流水線RISC(reduced instruction set computer)處理器[12]及本地組件，通過內(nèi)存服務(wù)訪問點(memory service access point, MSAP)[13]與外部互聯(lián)網(wǎng)絡(luò)連接.內(nèi)存子系統(tǒng)包含8個CPU子系統(tǒng)私有的內(nèi)存模塊和1個全局共享內(nèi)存. 在實驗中，采用一個簡單的MJPEG(motion joint photographic experts group)譯碼器和一個復(fù)雜的MPEG2(moving picture experts group 2)譯碼器作為應(yīng)用程序模型.

圖6 MPSoC硬件平臺架構(gòu)Fig.6 MPSoC hardware platform architecture

為了驗證所提出的多粒度通信優(yōu)化方法的效果，依次使用不同的通信優(yōu)化粒度進(jìn)行4組對比實驗，如表1所示.

表1 實驗設(shè)置

3.2 實驗結(jié)果

3.2.1 MJPEG譯碼器

MJPEG譯碼器有7個S函數(shù)，7個延遲，26條數(shù)據(jù)鏈路和4個IAS(if-action subsystem). 由于其規(guī)模很小，在2/3-CPU平臺上進(jìn)行實驗. 實驗使用10幀QVGA(quarter video graphics array)格式的數(shù)據(jù)流作為輸入.

每組實驗總的執(zhí)行周期數(shù)如圖7所示. 相較于在映射階段只考慮負(fù)載平衡、在調(diào)度階段只使用先入先出(first in first out, FIFO)調(diào)度方法的基礎(chǔ)組E1，本文方法在2-CPU平臺上性能提升了10%，在3-CPU平臺性能提升接近20%.由于2-CPU平臺中應(yīng)用程序簡單，且使用了2個處理器，帶粗粒度通信優(yōu)化的ILP映射(E2)的結(jié)果與不帶優(yōu)化的ILP映射(E1)的結(jié)果相同，說明該2種條件下性能相同. 當(dāng)處理器數(shù)量增加時，在3-CPU平臺上，其性能提升明顯，這是因為使用了一個額外的處理器并且減少了更多的通信開銷.

圖7 各實驗組的總執(zhí)行周期數(shù)Fig.7 Total execution cycles of each set

為了進(jìn)一步分析性能提升的原因，將處理器的狀態(tài)劃分成3類：計算狀態(tài)(COMP)、通信狀態(tài)(COMM)和空閑狀態(tài)(IDLE). 計算/通信狀態(tài)指處理器在執(zhí)行功能模塊/通信模塊的狀態(tài)，而空閑狀態(tài)指處理器切換線程或等待線程同步的狀態(tài).

圖8顯示了處理器內(nèi)IDLE和COMM狀態(tài)組件的百分比，并以各處理器的平均值為衡量依據(jù).其中E4的通信開銷減小至只有2%～3%，并且IDLE狀態(tài)也減至7%內(nèi). 說明性能提升的主要原因是通信開銷的減少. 此外，如圖8所示，調(diào)度的結(jié)果也同步縮短了時間.

圖8 IDLE和COMM CPU狀態(tài)組件的百分比Fig.8 Percentage of IDLE and COMM CPU state component

3.2.2 MPEG2譯碼器

MPEG2視頻譯碼器的Simulink功能模型更加復(fù)雜，包含49個S函數(shù)，18個延遲，186條數(shù)據(jù)鏈路，28個IAS，4個FIS(for-iteration subsystems)，以及72個預(yù)定義Simulink模塊. 實驗基于不同的CPU平臺進(jìn)行，并采用一個10幀CIF MPEG2(common intermediate format MPEG2)視頻比特流作為輸入.

如圖9所示，在4、5、6、8-CPU平臺上，性能提升18.4%～26%，同時發(fā)現(xiàn)，性能的提升量隨著處理器數(shù)量的增加而增加. 為了進(jìn)一步分析結(jié)果，統(tǒng)計了不同平臺上通信和空閑狀態(tài)的處理器利用率.相較于E1，在采用粗粒度通信優(yōu)化后，E2平均減少了30.4%的通信狀態(tài)和18.5%的空閑狀態(tài).同時由于調(diào)度策略優(yōu)化，E3分別減少了36.5%的通信狀態(tài)及34.2%的空閑狀態(tài). 相較于E3，在使用細(xì)粒度通信優(yōu)化后，E4減少了85.4%的通信狀態(tài)和48.8%的空閑狀態(tài). 說明每一種通信優(yōu)化粒度都能通過減少通信和空閑狀態(tài)提高處理器的利用率，有效提升性能. 更重要的是，本文提出的基于ILP方法的多粒度通信優(yōu)化的映射與調(diào)度策略(E4)，能夠同時利用粗粒度和細(xì)粒度通信優(yōu)化，減少通信開銷及空閑時間，從而顯著提升系統(tǒng)性能.

圖9 MPEG2各實驗組的總執(zhí)行周期數(shù)Fig.9 Total execution cycles of each set in experiment of MPEG2

4 結(jié)束語

為了提升MPSoC應(yīng)用程序的性能，提出了一種新穎的映射和調(diào)度策略，實現(xiàn)Simulink模型的最小化通信開銷. 該策略采用ILP方法，結(jié)合不同粒度的通信優(yōu)化特點，減少了通信時間和空閑時間的通信開銷. 基于MJEPG和MPEG2解碼器的實驗結(jié)果，驗證了該策略的有效性.在未來的工作中，將探索更為復(fù)雜的環(huán)圖應(yīng)用模型的高效通信優(yōu)化技術(shù).

[1] COTTON S, MALER O, LEGRIEL J, et al. Multi-criteria optimization for mapping programs to multi-processors[C]∥IEEE International Symposium on Industrial&Embedded Systems.Vasteras: IEEE Computer Society, 2011：9-17.

[2] FERRANDI F, LANZI P L, PILATO C, et al. Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems[J]. IEEE Trans Comput-Aided Des Integ Circuits & Syst,2010,29(6):911-924.

[3] HUANG K, YU M, ZHANG X M, et al. ILP based multithreaded code generation for Simulink model[J]. IEICE Trans Inf & Syst,2014,97(12):3072-3082.

[4] YAN R J, HUANG K, YU M, et al. Communication pipelining for code generation from Simulink models[C]∥IEEE International Conference on Trust. Melbourne: IEEE Computer Society,2013,8(1):1893-1900.

[5] BRISOLARA L, HAN S, GUERIN X L,et al. Reducing finegrain communication overhead in multithread code generation for heterogeneous MPSoC[C]∥SCOPES’07. Nice:ACM,2007,11(1):81-89.

[6] HAN S, CHAE S, BRISOLARA L, et al. Memory-efficient multithreaded code generation from Simulink for heterogeneous MPSoC[J]. Des Autom Embed Syst,2007,11(4):249-283.

[7] KAHN G, MACQUEEEN D. Coroutines and networks of parallel processors[C]∥Proceedings of the IFIP Congress 77. Toronto: North-Holland Publishing Company,1977:993-998.

[8] LEE E A, PARKS T M. Dataflow Process Networks[M]. Norwell: Kluwer Academic Publishers,2001,83(5):59-85.

[9] MATHWORKS. Math works 發(fā)布包含MATLAB和Simulink 產(chǎn)品系列的Release2016b[ER/OL].http://www.mathworks.com/products/simulink.html.

[10] HAN S I, CHAE S I, JERRAYA A A. Functional modeling techniques for efficient SW code generation of video codec applications[C]∥ASP-DAC’06. Yokohama:ACM,2006,13(13):935-940.

[11] HAN S I, CHAE S I, BRISOLARA L, et al. Simulink?-based heterogeneous multiprocessor SoC design flow for mixed hardware/software refinement and simulation[J].Integ VLSI J, 2009,42(2):227-245.

[12] C-SKY, Inc. C-Sky IP authorization,2016[EB/OL] http:∥www.csky.com/solution/CPU-IP-shou-quan.htm.

[13] HAN S I, BAGHDADI A, BONACIU M, et al. An efficient scalable and flexible data transfer architecture for multiprocessor SoC with massive distributed memory[C]∥DAC’04.SanDiego:IEEE,2004:250-255.

MPSoC mapping and scheduling approach with multi-grained communication optimizations.

CAI Tiantian1, XI Wei1, GUO Xiaobin1, YAO Hao1, HUANG Kai2

(1.ElectricPowerResearchInstitute,CSG,Guangzhou510080,China; 2.CollegeofInformationScience&ElectronicEngineering,ZhejiangUniversity,Hangzhou310027,China)

As the number of processors in an embedded system increases, mapping and scheduling become key challenges of system software designers. To achieve high performance, communication overheads should be addressed during mapping and scheduling process. Most existing mapping and scheduling approaches exploit coarse-grained system level communication optimizations from a global view, and standalone communication optimization techniques adopt fine-grained thread level communication optimizations from a local view. While these communication optimization techniques can improve performance, they still face problems. In this work, an integer linear programming (ILP)-based mapping and scheduling approach is proposed with multi-grained communication optimizations for Simulink models, which can efficiently exploit the advantages of different granularities of communication optimizations and complement their disadvantages. It conducts coarse-grained communication optimization during the mapping process and fine-grained communication optimization during the scheduling process. Experimental results show that the proposed approach can improve the overall system performance significantly.

integer linear programming; mapping and scheduling; multi-grained communication optimizations

2016-10-24.

南方電網(wǎng)科學(xué)研究院“電力二次設(shè)備芯片研制方案研究項目”.

蔡田田(1982-)，ORCID:http//orcid.org/0000-0001-9475-1654,女，碩士，高級工程師，主要從事智能電網(wǎng)技術(shù)、電力電子技術(shù)及SoC芯片相關(guān)技術(shù)研究，E-mail：caitt@csg.cn.

10.3785/j.issn.1008-9497.2017.04.008

TP 36

A

1008-9497(2017)04-429-08

Journal of Zhejiang University(Science Edition), 2017,44(4):429-436