基于Petri網(wǎng)多核映射任務(wù)分析及在torus架構(gòu)中的應(yīng)用

方 冉

(安徽工商職業(yè)學(xué)院電子信息系, 安徽 合肥 230041)

基于Petri網(wǎng)多核映射任務(wù)分析及在torus架構(gòu)中的應(yīng)用

方 冉

(安徽工商職業(yè)學(xué)院電子信息系, 安徽 合肥 230041)

多核任務(wù)映射是高性能計算領(lǐng)域的研究熱點(diǎn)?；趖orus互連的多核架構(gòu)，本文提出了行資源映射和行優(yōu)化資源映射兩種算法，行資源映射算法首先以torus的最左邊位置作為起點(diǎn)映射，然后按入度值從大到小的次序依次映射其后繼，每映射完一個后繼就映射其相應(yīng)的前驅(qū)，以此類推，映射完所有的節(jié)點(diǎn)。行優(yōu)化資源映射首先把出度最大的點(diǎn)放在torus最左邊位置，把入度最大的點(diǎn)放在torus同一行最右邊位置，然后映射出度最大的點(diǎn)的其他后繼和入度最大的點(diǎn)其他前驅(qū)，以此類推，映射完所有的節(jié)點(diǎn)。利用時延petri網(wǎng)軟件工具包對兩種映射方法進(jìn)行了分析和比較，實驗結(jié)果表明，基于相同的循環(huán)任務(wù)數(shù)據(jù)流圖和硬件架構(gòu)，行優(yōu)化資源映射算法獲得的吞吐量是行資源映射算法的2倍，并且每個映射塊運(yùn)行時間減少近似一半，行優(yōu)化資源映射算法具有合理性和可行性。

時延Petri網(wǎng); 多計算單元；任務(wù)調(diào)度；torus互連網(wǎng)絡(luò)

隨著國內(nèi)外高性能計算技術(shù)的迅速發(fā)展，傳統(tǒng)的單核、順序運(yùn)算已經(jīng)不能滿足計算密集型或計算規(guī)模大任務(wù)等的要求，在這樣的背景下，各種多核混合結(jié)構(gòu)的片上網(wǎng)絡(luò)系統(tǒng)被相繼提出，面對復(fù)雜的結(jié)構(gòu)，多核任務(wù)的調(diào)度問題顯得尤為重要，該類問題是優(yōu)化多核結(jié)構(gòu)性能的關(guān)鍵，相關(guān)的研究成果很多。典型的研究列舉如下：文獻(xiàn)[1] 對有向無環(huán)圖的并行實時調(diào)度進(jìn)行了研究，該文提出了一種通用無環(huán)圖任務(wù)分解轉(zhuǎn)換為順序圖的方法，通過該種方法，對于搶占式最早截止時間優(yōu)先算法而言，增加了4倍的資源成本，對于非搶占式最早截止時間優(yōu)先算法而言，增加了4倍以上的資源成本。文獻(xiàn)[2]研究了共享實時系統(tǒng)的調(diào)度邊界利用和映射問題，與已經(jīng)有的任務(wù)映射算法相比，該文提出的同步認(rèn)知任務(wù)映射算法(synchronization-cogniz ant task mapping algorithms SC-TMA) 獲得了較為優(yōu)化的調(diào)度率和平均系統(tǒng)負(fù)載。文獻(xiàn)[3]對可以同時利用線程級并行(thread-level parallelism TLP)和指令級并行(instruction-level parallelism ILP)自適應(yīng)多核架構(gòu)進(jìn)行了研究，構(gòu)建了離線和在線調(diào)度器，對內(nèi)核的應(yīng)用程序進(jìn)行了智能化配置和分配，相比較靜態(tài)和非對稱多核體系結(jié)構(gòu)，自適應(yīng)多核架構(gòu)減少了任務(wù)完成時間。文獻(xiàn)[4]研究了多核片上系統(tǒng)(multiprocessor system on chip MPSoC)的核與核之間互相通信問題，該文對運(yùn)算數(shù)據(jù)流圖進(jìn)行了數(shù)據(jù)依賴轉(zhuǎn)換，并提出了啟發(fā)式調(diào)度算法，該算法減少了任務(wù)調(diào)度長度，改進(jìn)了內(nèi)存的使用。文獻(xiàn)[5] 提出了一種溫度預(yù)報和任務(wù)分配同時進(jìn)行的解決方案，結(jié)果獲得了調(diào)度長度為5%～10%區(qū)間優(yōu)化的調(diào)度方案。但是上述工作均沒有對多核系統(tǒng)中映射成功的運(yùn)算節(jié)點(diǎn)進(jìn)行性能分析。如何對實際系統(tǒng)進(jìn)行建模?如何結(jié)合系統(tǒng)模型來分析片上多核系統(tǒng)的運(yùn)行機(jī)制顯得極為重要。Petri網(wǎng)具有并發(fā)性、可達(dá)性、活性等特征，適合多核系統(tǒng)的描述與分析。

1 相關(guān)定義與網(wǎng)建模轉(zhuǎn)換

為了便于問題研究，下面給出時延Petri網(wǎng)等相關(guān)定義。

定義1[6]四元組N=(P，T，F(xiàn)，M0)稱作Petri網(wǎng)系統(tǒng)的引發(fā)規(guī)則為：

1) 變遷t.∈T稱為使能的當(dāng)且僅當(dāng)

?p∈·t：M(p)≥1，記作M[t>；

2) 在M下使能的變遷t可以引發(fā)，引發(fā)后得到一個新的標(biāo)識M′，記作M[t>M′，對p∈P，

定義2 多核互連背景下的時延petri網(wǎng)TPN(timedpetrinet)可表示為一個七元組，具體包括以下兩種情況：

1) 執(zhí)行延遲TPN1：TPN1=(P，T，F(xiàn)，M，I，O，D1)，P∪T≠Φ，P∩T=Φ，F(xiàn)?(P×T)∪(T×P)，庫所P為一個有限集合，表示可以存放運(yùn)算操作輸入或輸出值的單元集合；變遷T為一個有限集合，表示計算執(zhí)行的單元集合；F表示P和T數(shù)據(jù)傳輸?shù)牧麝P(guān)系；I是j種顏色輸入的一個有限集合I={i1，i2，…，ij}；D1是定義在某個t∈T，在變遷集合T上的執(zhí)行延遲函數(shù)，D1(x)表示當(dāng)M[t>發(fā)生時，變遷t就觸發(fā)了，并且執(zhí)行延遲為x個時間單位，O={o1，o2，…，ok}表示任一運(yùn)算任務(wù)在多核陣列所有輸出集合。

2) 等待延遲TPN2：TPN2=(P，T，F(xiàn)，M，I，O，D2)，其他說明同3.1，唯一不同的是D2是定義在某個t∈T，在變遷集合T上的等待延遲函數(shù)，D2(y)表示當(dāng)M[t>發(fā)生時，變遷t就觸發(fā)了，并且等待延遲為y個時間單位，TPN2包括不同步和過渡等待延遲。本文涉及的其他相關(guān)理論詳見文獻(xiàn)[6-8]。

2.2 任務(wù)數(shù)據(jù)流圖與時延petri網(wǎng)TPN之間的轉(zhuǎn)換

2.2.1TPN網(wǎng)的建模基本單元圖 為了便于問題的討論，乘法運(yùn)算的執(zhí)行時延約定為2cycles，其他算術(shù)邏輯運(yùn)算的執(zhí)行時延約定為1cycle。圖1給出了TPN網(wǎng)建模所用的基本單元關(guān)系圖。

由圖1(d)可知，約定來自庫所pi的同一數(shù)據(jù)可被兩個變遷共享被同時使用，由圖1(e)可知，來自庫所pi和pi+1的數(shù)據(jù)如果具有同步性，那么可以進(jìn)行融合計算；若不具有同步性，則要進(jìn)行轉(zhuǎn)換。

2.2.2 相關(guān)轉(zhuǎn)換

1) 不同步轉(zhuǎn)換。在多處理器系統(tǒng)中，變遷執(zhí)行數(shù)據(jù)的不同步情況常常發(fā)生，在這種情況下，要用到存取轉(zhuǎn)換變遷，一個變遷需要耗時2cycles。以二目運(yùn)算為例，運(yùn)算的輸入放在兩個庫所里，因為兩個庫所的數(shù)據(jù)來源具有不同步性，所以要有一個存儲等待ti1變遷和一個庫所pi配合完成，具體如圖2所示。

2) 過渡轉(zhuǎn)換。受限于多處理器系統(tǒng)的不同的互連方式，兩個處理器之間的數(shù)據(jù)傳輸如果不可達(dá)，這時需要插入過渡節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸，這時處理器節(jié)點(diǎn)功能為數(shù)據(jù)過渡傳輸，tn+1變遷和pi+3配合完成數(shù)據(jù)過渡傳輸，需要耗時2cycles(見圖3)。

混合異構(gòu)多核系統(tǒng)主要處理對象之一是循環(huán)任務(wù)子圖，本文采用petri網(wǎng)工具對已經(jīng)被映射到torus網(wǎng)絡(luò)處理器系統(tǒng)的任務(wù)子圖進(jìn)行TPN網(wǎng)的轉(zhuǎn)換，并進(jìn)行相關(guān)的性能分析和討論。

3 二維torus多核互連網(wǎng)絡(luò)可調(diào)度性分析

3.1 二維torus網(wǎng)絡(luò)簡介

二維torus網(wǎng)絡(luò)是一種常用的片上系統(tǒng)，這種結(jié)構(gòu)的網(wǎng)絡(luò)克服了共享介質(zhì)網(wǎng)絡(luò)的可擴(kuò)展性難題，文中給出torus網(wǎng)絡(luò)節(jié)點(diǎn)均可編譯程序。torus網(wǎng)絡(luò)節(jié)點(diǎn)之間的互連形式如圖4所示，每個節(jié)點(diǎn)包含一個路由器網(wǎng)絡(luò)接口模塊和一個可計算和存儲的IP 內(nèi)核，路由器網(wǎng)絡(luò)接口信道可以是輸入類型，輸出類型，雙向類型。圖4給出了二維torus網(wǎng)絡(luò)的互連方式，torus在主處理器的控制下完成映射成功任務(wù)的編譯與傳輸，主存儲器來存儲運(yùn)算的中間和最后結(jié)果數(shù)據(jù)。

一個展開循環(huán)任務(wù)子圖含有六種計算任務(wù)(見圖5)，任務(wù)a的執(zhí)行時間為2cycles，任務(wù)b、c的執(zhí)行時間均為4cycles，任務(wù)d、e、f的執(zhí)行時間均為1cycle。

3.2 torus多核互連結(jié)構(gòu)的任務(wù)映射

一個循環(huán)任務(wù)子圖(見圖5)任務(wù)間的關(guān)系描述見表1，說明本文只討論最大出(入)度為4的情形。

表1 循環(huán)任務(wù)子圖間順序關(guān)系描述

采用按行資源映射RRM (row resource mapping)和行優(yōu)化資源映射RORM(row optimum resource mapping)兩種方法對圖5的循環(huán)子任務(wù)進(jìn)行了映射。

RRM算法流程：

輸入：一個任務(wù)子圖

輸出：一個任務(wù)子圖執(zhí)行周期和坐標(biāo)

約束：4×4 torus；任務(wù)節(jié)點(diǎn)入(出)度最大值為3

Step1讀入數(shù)據(jù)表。

Step2按行掃描數(shù)據(jù)表獲得任務(wù)子圖第一層的第一個節(jié)點(diǎn)，獲得入度為0且節(jié)點(diǎn)號最小的點(diǎn)，以此點(diǎn)作為起點(diǎn)，并把該點(diǎn)調(diào)度映射到torus第一行最左邊位置，其坐標(biāo)為 (0，0)。

Step3比較已經(jīng)映射成功的當(dāng)前點(diǎn)直接后繼的入度，可分為三種情況：

(1) 若當(dāng)前點(diǎn)有多個后繼，且后繼的入度值不等

選擇當(dāng)前點(diǎn)入度值最大的直接后繼，按行增加一路由點(diǎn)，映射該直接后繼點(diǎn)；按節(jié)點(diǎn)號從大到小的次序掃描已經(jīng)映射成功后繼點(diǎn)的直接前驅(qū)點(diǎn)，把節(jié)點(diǎn)號大的點(diǎn)放入當(dāng)前行；torus的行row+1；直接映射節(jié)點(diǎn)號小的前驅(qū)；若節(jié)點(diǎn)號大前驅(qū)的后繼入度為1直接映射；若節(jié)點(diǎn)號大前驅(qū)的后繼入度大于1加路由節(jié)點(diǎn)映射。選擇入度值較大的直接后繼，轉(zhuǎn)(1)，以此類推。

(2) 若當(dāng)前點(diǎn)有多個后繼，且后繼的入度值相等，優(yōu)先選擇節(jié)點(diǎn)號進(jìn)行映射，其他同(1)。

(3) 若當(dāng)前點(diǎn)只有一個后繼，直接映射，其他同(1)。

所有的任務(wù)點(diǎn)全部映射完成轉(zhuǎn)Step4。

Step4 End RRM。

RORM算法流程：

輸入：一個任務(wù)子圖

輸出：一個任務(wù)子圖執(zhí)行周期和坐標(biāo)

約束： 4×4 torus；任務(wù)節(jié)點(diǎn)入(出)度最大值為4

Step1讀入數(shù)據(jù)表。

Step2按行掃描數(shù)據(jù)表獲得任務(wù)子圖第一層的第一個節(jié)點(diǎn)，首先獲取出度最大的點(diǎn)放在torus互連網(wǎng)絡(luò)第一行最左邊位置，其坐標(biāo)為 (0，0)；然后獲取入度最大的點(diǎn)放在torus互連網(wǎng)絡(luò)第一行最右邊位置，依次映射。

Step3 處理出度最大的點(diǎn)其他后繼：

若有一個后繼，直接映射到當(dāng)前行緊鄰位置；若有兩個后繼，一個直接映射到當(dāng)前行緊鄰位置，torus的行row+1，映射放入另外一個后繼。

Step4 處理入度最大的點(diǎn)其他前驅(qū)：

若有一個前驅(qū)，直接映射到當(dāng)前行緊鄰位置；若有兩個前驅(qū)，一個直接映射到當(dāng)前行緊鄰位置，torus的行row+1，映射放入另外一個前驅(qū)。

所有的任務(wù)點(diǎn)全部映射完成轉(zhuǎn)Step5

Step5 End RORM

分別采用RRM和RORM兩種算法獲得了圖5的一個循環(huán)子圖映射結(jié)果，具體如圖6～圖7所示。

3.3 基于TPN網(wǎng)的任務(wù)映射時間性能特性分析

圖6和圖7(a)是針對同一個任務(wù)子圖映射成功的結(jié)果，RRM執(zhí)行時間次序圖和映射的網(wǎng)模型∑1具體如圖8～圖9所示。

RORM執(zhí)行時間次序圖和映射的網(wǎng)模型∑2具體如圖10和圖11所示，其中tw1和w1用來表示一次不同步轉(zhuǎn)換。

由上述分析可知，RORM執(zhí)行一塊的時間為5cycles，RRM執(zhí)行一塊的時間為9cycles，更為重要的是采用RORM算法一次可以映射2個圖5形狀的循環(huán)子圖，然而RRM只能映射一個子圖，并且增加了6個路由節(jié)點(diǎn)，產(chǎn)生6次數(shù)據(jù)過渡延遲，同時產(chǎn)生3次不同步數(shù)據(jù)延遲，但是RORM算法只有1次不同步數(shù)據(jù)延遲，RORM算法優(yōu)勢明顯。

4 結(jié)語

對于二維多核torus互連網(wǎng)絡(luò)及類似結(jié)構(gòu)而言，要充分利用其互連資源，特別是任務(wù)圖出入度數(shù)較大情況。運(yùn)用petri網(wǎng)工具包對RRM和RORM分析可知，對于具有圖5性質(zhì)的及類似的循環(huán)子圖，相比較RRM， RORM在一個4*4結(jié)構(gòu)的torus互連多核結(jié)構(gòu)可以映射兩個子圖，且運(yùn)行時間為5cycles，而RRM只能映射一個子圖，且運(yùn)行時間為9cycles，假設(shè)任務(wù)圖按塊執(zhí)行，且任務(wù)圖不能被分割(理由是考慮通信成本的較小化)，RORM算法任務(wù)的吞吐量是RRM算法的2倍，且每個映射塊運(yùn)行時間減少近似一半，RORM算法具有可行性。

[1] SAIFULLAH A，F(xiàn)ERRY D，LI J， et al. Parallel real-time scheduling of DAGs[J]. IEEE Transactions on Parallel and Distributed Systems， 2014， 25(12)： 3 242-3 252.

[2] HAN J J， ZHU D K，WU X D，et al. Multiprocessor Real-Time Systems with Shared Resources： Utilization Bound and Mapping[J]. IEEE Transactions on Parallel and Distributed Systems，2014，25(11)：2 981-2 991.

[3] PRICOPI M， MITRA T.Task Scheduling on Adaptive Multi-Core[J].IEEE Transactions on Computers， 2014，63(10)： 2 590-2 603.

[4] WANG Y， SHAO Z L， CHAN H C B， et al. Memory-Aware Task Scheduling with Communication Overhead Minimization for Streaming Applications on Bus-Based Multiprocessor System-on-Chips[J]IEEE Transactions on Parallel and Distributed Systems， 2014，25(7)： 1 797-1 807.

[5] GANESHPURE K， KUNDU S.Performance-Driven Dynamic Thermal Management of MPSoC Based on Task Rescheduling[J]ACM Transactions on Design Automation of electronic Systems， 2014，19(2)：11：1-11：33.

[6] 吳哲輝.Petri網(wǎng)導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2006：.

[7] 蔣昌俊.Petri網(wǎng)的行為理論及其應(yīng)用[M].北京：高等教育出版社，2003：.

[8] 袁崇義.Petri網(wǎng)原理及應(yīng)用[M].北京：電子工業(yè)出版社，2005：.

(責(zé)任編輯：李 麗，范 君)

Multi-core Task Mapping Analysis Based on Petri Net and Torus Architecture Applications

FANG Ran

( Department of Electronic Information, Anhui Vocational College of Commerce and Industry, Hefei Anhui 230041, China)

Multi-core task mapping is a hot research topic in the field of high performance computing tasks. Based on torus interconnect multi-core architecture, the RRM (row resource mapping) algorithm and RORM (row optimum resource mapping) algorithm were proposed. The mapping starting point of RRM is the leftmost position in torus at first. Then its successors are mapped in the order of indegree values. Corresponding predecessors are mapped after mapping a successor and so on. Finally, all of the nodes are mapped completely. The maximum outdegree node is the mapping starting point of RORM, and it is mapped onto the leftmost position of torus at first, and the maximum indegree node is mapped onto the rightmost position of torus. Then the other successors of the maximum outdegree node and the other predecessors of the maximum indegree node are mapped onto torus. Finally, all of the nodes are mapped completely. Two mapping methods were analyzed and compared by time petri net software tool kits. Based on the same cyclic data flow graph and hardware architecture, the results of experiment showed that the throughput of RORM is 2 times of RRM. Compared with RRM, the running time of each mapping blocks by RORM reduced approximately 50%. RORM is rational and feasible.

time petri net; multi-computing units; task schedule; torus interconnection network

2015-03-22

安徽省自然科學(xué)基金項目( 1408085MF124)

方冉(1983-)，男，安徽蕪湖人,講師，碩士，研究方向：控制工程及原理。

TP301

A

1672-1098(2015)03-0030-06