多粒度通信優化的MPSoC調度映射策略

蔡田田， 習偉， 郭曉斌， 姚浩， 黃凱

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

多粒度通信優化的MPSoC調度映射策略

蔡田田1， 習偉1， 郭曉斌1， 姚浩1， 黃凱2

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

隨著嵌入式系統處理器核數的增加，映射與調度成為軟件開發的關鍵. 為了提升系統性能，需要格外關注映射與調度過程中的通信開銷.現有的粗粒度系統級或細粒度線程級通信優化雖然能提升性能，但都各有缺陷.為此,提出了基于整數線性規劃的用于Simulink模型的多粒度通信優化映射與調度策略，將不同粒度的通信優化方法相結合，實現優勢互補.實驗結果表明，該方法能有效提高系統的整體性能.

整數線性規劃；映射與調度；多粒度通信優化

0 引 言

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

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

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

圖1 粗粒度系統級對比細粒度線程級通信優化Fig.1 Coarse-grained system level vs. fine-grained thread level communication optimization

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

通過對比粗粒度與細粒度通信優化發現，粗粒度優化可以全局分配通信得到最佳性能，但缺乏對信道的局部處理；而細粒度優化能對信道進行局部優化，但沒法考慮系統全局的性能. 因此，可以將一種結合全局與局部處理的多粒度通信優化應用到映射與調度過程中.

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

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

1 背景介紹

1.1 建 模

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

Simulink模型定義了目標系統的軟硬件架構，文獻[7，10-11]描述了其具體細節. 通常Simulink模型包括圖2所示的3部分.

圖2 Simulink體系架構Fig.2 A Simulink hierarchical structure

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

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

·Simulink子系統包含若干Simulink模塊、Simulink鏈接以及其他子系統，表示層級結構和條件語句，如for循環或if-then-else結構.

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

1.2 通信流水線與消息聚合

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

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

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

通信流水線通過將數據延遲一個周期使運算與通信并行，若使用不當，這一延遲會導致處理器阻塞，降低系統性能.

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

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

圖4 消息聚合Fig.4 Message aggregation

2 基于ILP的多粒度通信優化的映射與調度策略

首先，簡單起見，假定每個處理器線程數目為4，并與該處理器綁定. 映射階段決定了各任務、線程間的關系及其劃分結果，并權衡考慮了負載平衡與通信開銷最小化，其中粗粒度系統級通信優化被用于最小化處理器內部與處理器之間的通信開銷.

其次，基于映射的結果，利用通信流水線與消息聚合，進行線程內部與線程之間的任務調度，以降低通信開銷，優化系統整體性能.

2.1 粗粒度系統級通信優化映射

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

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

2.1.1 常 量

·P表示處理器數量.

·T表示任務數量.

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

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

·Dij為布爾型常量，表示任務ti與tj之間是否有依賴關系，當tj依賴于ti時，該值為1.

·ETi為任務ti的執行時間.

2.1.2 變 量

·Ai,m為布爾型變量，表示任務與線程之間的映射關系，當任務ti被映射到線程thm時，該值為1.

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

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

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

2.1.3 目 標

以下目標函數可實現線程間通信量(CS)、負載不均衡度(WG)最小化，在保證k1+k2=1的情況下通過調節目標函數中的權重k1，k2實現兩者的均衡.

min(k1×CS+k2×WG)，

(1)

(2)

(3)

2.1.4 約束條件

·每個任務必須被分配到一個線程.

(4)

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

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

(5)

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

(6)

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

(7)

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

(8)

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

2.2 細粒度線程級通信優化調度

調度過程決定了線程內和線程間任務的執行順序. 不合理的調度會延長處理器同步等待時間，從而降低動態性能.

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

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

消息聚合，將相同源線程和目的線程中對應的通信任務聚合到一起，導致模塊數量和執行順序發生改變. 為保持模塊間數據的相關性，由消息聚合得到的模塊其執行順序應遵守以下規則：

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

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

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

2.2.1ILP方程各量

2.2.1.1 常 量

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

·T表示線程的集合.

·P表示處理器的集合.

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

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

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

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

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

·switch為線程切換時間.

·cyc為每個模塊總的執行周期數.

2.2.1.2 變 量

·eij為布爾型變量，表示模塊間的執行順序，當相同線程內的模塊bi∈B先于bj∈B執行時該值為1.

·toverall為一個應用程序總的執行時間.

·si,k為第k周期模塊bi∈B的調用時間.

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

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

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

2.2.1.3 目 標

·為了最大化提升性能，應最小化系統總執行時間：

min(toverall).

(9)

2.2.1.4 約束條件

·同一線程內模塊的執行順序應滿足原始數據的相關性：

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

(10)

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

對于相同線程內的模塊bi∈B和bj∈B，假設bi早于bj執行：

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

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

(11)

其中，MAX是一個足夠大的正整數.

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

COMMi=Mij×commj+commi,

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

(12)

·相同線程內的模塊依據eij執行. 假設bi∈B和bj∈B被映射到相同的線程，并且bi先于bj執行，在第k周期bi的結束時間應該早于第k周期bj的調用時間，且第(k+1)周期bi的調用時間應該晚于第k周期bj的結束時間：

(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，假設bi是發送模塊，bj是接收模塊，第k周期bi的結束時間應該早于第k周期bj的調用時間，且第(k+1)周期bi的調用時間應該晚于第k周期bj的結束時間.進一步，如果bi和bj位于相同的處理器上，在bi執行完畢后，需要線程切換來執行bj:

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

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

switch≤si,k+1.

(18)

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

(19)

在該約束下，timei和timej由式(14)和(17)定義.m是一個布爾型變量，當第k周期bi的結束時間早于第k′周期bj的調用時間時，該值為1.

·應用程序總的執行時間取決于第cyc周期每個模塊的調用時間.對于任意模塊bi∈B，

toverall≥si,cyc+timei，

(20)

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

解決了上述規劃問題，可得到所有任務的執行順序，并且可在通信任務間引入通信流水線和消息聚合. 由于任務已經映射到確定的處理器線程，故線程間和線程內的調度也將確定.

縱觀整個多粒度通信優化流程，在映射階段，以粗粒度通信優化為主導，通過最小化線程間和線程內的通信開銷，為細粒度通信優化構建一個更加輕量級的通信網絡. 在調度階段，加入細粒度通信優化，進一步減小信道分配開銷，從而全面降低系統的通信開銷.

3 實現平臺與實驗結果

3.1 實現平臺

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

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

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

圖6 MPSoC硬件平臺架構Fig.6 MPSoC hardware platform architecture

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

表1 實驗設置

3.2 實驗結果

3.2.1 MJPEG譯碼器

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

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

圖7 各實驗組的總執行周期數Fig.7 Total execution cycles of each set

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

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

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

3.2.2 MPEG2譯碼器

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

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

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

4 結束語

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

[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 發布包含MATLAB和Simulink 產品系列的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.

南方電網科學研究院“電力二次設備芯片研制方案研究項目”.

蔡田田(1982-)，ORCID:http//orcid.org/0000-0001-9475-1654,女，碩士，高級工程師，主要從事智能電網技術、電力電子技術及SoC芯片相關技術研究，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