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

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

0 引 言

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

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

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

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

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

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

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

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

1 背景介紹

1.1 建 模

功能模型能夠體現(xiàn)具體應(yīng)用程序的并行性，并且容易轉(zhuǎn)化成如LESCEA[6]所支持的多線(xiàn)程代碼. 一些能夠建立功能模型的高級(jí)語(yǔ)言如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)代表一個(gè)包含輸入輸出的功能塊函數(shù).比如用戶(hù)自定義函數(shù)(S-function)、離散時(shí)間延遲、預(yù)定義塊等運(yùn)算操作. 本實(shí)驗(yàn)采用了如圖2所示的功能模塊，代表系統(tǒng)運(yùn)行與收發(fā)消息的通信過(guò)程.

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

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

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

1.2 通信流水線(xiàn)與消息聚合

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

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

圖3 通信流水線(xiàn)Fig.3 Communication pipeline

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

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

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

圖4 消息聚合Fig.4 Message aggregation

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

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

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

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

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

在列舉ILP公式變量之前，先給出一些記號(hào).

2.1.1 常 量

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

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

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

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

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

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

2.1.2 變 量

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

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

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

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

2.1.3 目 標(biāo)

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

min(k1×CS+k2×WG)，

(1)

(2)

(3)

2.1.4 約束條件

·每個(gè)任務(wù)必須被分配到一個(gè)線(xiàn)程.

(4)

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

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

(5)

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

(6)

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

(7)

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

(8)

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

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

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

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

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

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

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

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

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

2.2.1ILP方程各量

2.2.1.1 常 量

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

·T表示線(xiàn)程的集合.

·P表示處理器的集合.

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

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

·commstratup為任意通信模塊的啟動(dòng)時(shí)間.

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

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

·switch為線(xiàn)程切換時(shí)間.

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

2.2.1.2 變 量

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

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

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

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

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

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

2.2.1.3 目 標(biāo)

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

min(toverall).

(9)

2.2.1.4 約束條件

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

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

(10)

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

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

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

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

(11)

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

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

COMMi=Mij×commj+commi,

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

(12)

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

(13)

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

timei=exei(or timej=exej)，

(14)

否則，

timei=commstartup+COMMi

or

timej=commstartup+COMMj.

(15)

考慮通信流水線(xiàn)的影響，

(16)

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

timei=commstartup+(1-CPi)×COMMi

or

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

(17)

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

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

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

switch≤si,k+1.

(18)

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

(19)

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

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

toverall≥si,cyc+timei，

(20)

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

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

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

3 實(shí)現(xiàn)平臺(tái)與實(shí)驗(yàn)結(jié)果

3.1 實(shí)現(xiàn)平臺(tái)

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

圖5 多線(xiàn)程代碼生成流程Fig.5 Multithreaded code generation flow

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

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

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

表1 實(shí)驗(yàn)設(shè)置

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 MJPEG譯碼器

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

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

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

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

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

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

3.2.2 MPEG2譯碼器

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

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

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

4 結(jié)束語(yǔ)

為了提升MPSoC應(yīng)用程序的性能，提出了一種新穎的映射和調(diào)度策略，實(shí)現(xiàn)Simulink模型的最小化通信開(kāi)銷(xiāo). 該策略采用ILP方法，結(jié)合不同粒度的通信優(yōu)化特點(diǎn)，減少了通信時(shí)間和空閑時(shí)間的通信開(kāi)銷(xiāo). 基于MJEPG和MPEG2解碼器的實(shí)驗(yàn)結(jié)果，驗(yàn)證了該策略的有效性.在未來(lái)的工作中，將探索更為復(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è)備芯片研制方案研究項(xiàng)目”.

蔡田田(1982-)，ORCID:http//orcid.org/0000-0001-9475-1654,女，碩士，高級(jí)工程師，主要從事智能電網(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