二維RCA空域映射Petri網時間性能分析

陳乃金

安徽工程大學 計算機與信息學院，安徽 蕪湖 241000

二維RCA空域映射Petri網時間性能分析

陳乃金

安徽工程大學 計算機與信息學院，安徽 蕪湖 241000

1 引言

在傳統的計算系統中，計算機求解的實現主要是兩種方法[1]。其一是專用集成電路（Application Specific Integrated Circuit，ASIC）方法，該方法的優點是針對某一特定計算任務，可得到很高的計算速度及效率，但該方法缺點是不可編程的，靈活性差，計算任務一改變，就要改動硬件；其二是單核或多核通用處理器（General Purpose Processors，GPP）方法，通過選擇處理器的指令，根據某種算法構成一個新的指令序列，去完成特定的計算，該方法的優點是通過修改軟件可達到改變系統功能的目的，不需改動硬件，該方法具有可編程性，并且靈活性好。但缺點是這種可編程性是以犧牲系統的性能和速度為代價換來的。可重構計算恰好彌補上述兩種方法缺點[2]，它既具有ASIC高的計算速度及效率，又具有微處理器方法的可編程性和良好的靈活性，可重構系統在高性能計算領域已經顯示出了強大的數據處理能力，其中最具代表性的是美國超級計算機研究中心在1992年研制的Splash 2，在基因組的數據計算中比當時SPARC 10工作站的運算速度快2 500倍[3]，而且在實時嵌入式應用[4]等方面，已經展示了巨大的優勢。

作為通用可重構器件的FPGA路由結構復雜，一個邏輯塊周圍的可編程連接點可以達到上千個，提供這樣豐富的路由資源主要是為了能夠實現任意連接，提高通用性。但是，這帶來了系統重構時間和面積的增加、功耗消耗增大等缺陷，而且以FPGA為代表的細粒度可重構體系結構FGRAs（Fine Grained Reconfigurable Architectures）在進行位級運算時具有明顯的優勢，但是在處理規則和位數寬的字（Word）級算術和邏輯運算時效率較低，為了克服FGRAs的缺點，各種粗粒度可重構體系結構CGRAs（Coarse Grained Reconfigurable com-puter systems）被相繼提出，而且給予了相關研究[1-10]。本文針對通用的CGRAs系統芯片通用架構進行了研究，給出了CGRAs通用架構及其簡明的編譯流程，基于Petri網著重分析允許行有依賴空域映射（文獻[11]采用此方法）和行無依賴空域映射的時間特性，為了便于說明問題，本文以下映射均指空域映射。

2 CGRAs通用計算模型

2.1 CGRAs的設計目標

CGRAs的設計目標是針對計算密集型任務（如音視頻的編解碼、數字圖像處理、移動目標的識別、基因運算、解加密算法等）關鍵循環內核占用大量計算時間的事實，將其關鍵循環提取并通過不同的劃分映射方法，通過主處理器控制使其在RCA上被配置計算，這將大大加快關鍵循環任務的執行效率，從而獲得高的加速比。

2.2 CGRAs的結構及其工作原理

隨著高性能計算機體系結構的迅速發展，傳統的計算機在執行程序的過程中是按順序逐條地執行，即取指令→執行指令→……該執行方式效率較低，而且存儲器和I/O外設的速度與高速的CPU速度不匹配，這將使得計算機的計算速度大大下降。在這樣的背景下，各種追求運算高性能的計算平臺（如CGRAs等）被相繼提出，本文在結合文獻[1-2，9-10]等研究的基礎上給出了一種CGRAs較為通用計算模型[1，4-5，10]，其結構如圖 1 所示。

CGRAs是由一個主處理器（main processor）、主存儲器（main memory）、互連資源、DMA、RPU等構成高性能的混合計算機系統結構，其中RPU包括若干個可配置寄存器（context register，如控制、數據、RC（Reconfigurable Cell）寄存器等）、局部存儲器（local memory）、可重構單元陣列RCA（Reconfigurable Cell Array）等組件，為了緩解高速的主處理器、低速主存儲器、速度更低的RPU之間矛盾，一般在主處理器、主存儲器、RPU之間加一數據緩存（data cache）模塊，在主處理器和主存儲器之間加一指令緩存（instruction cache）模塊，目的是優化系統的運行。

CGRAs的工作原理簡述如下：計算密集型任務通過加標記代碼級軟硬件劃分，將在RCA上執行效率低或者不能執行的代碼送到主處理器main processor上執行，將計算任務的循環代碼展開，并將其變為中間表示即數據流圖DFG（Data Flow Graph）的形式，通過某種劃分與映射算法依次將DFG放置到RCA上，然后對RCA中已經用到的重構單元RC（Reconfigurable Cell），若干個控制配置寄存器（several control context registers）組進行配置，控制配置寄存器組中的全局控制寄存器控制RCA的啟動，每個RC單元的連接關系及功能通過配置RC寄存器來實現，而且control context registers在main processor和循環控制器loop controller（一般用DMA控制器模塊）的控制下，完成基址存取和DMA配置等工作。數據緩沖器（data buffer）實際上為局部存儲器，與RCA進行數據的直接輸入與輸出，避免訪問外部的存儲器，從而節省通信成本。RCA組件可擴展為若干個RCA模塊，RCA的內部可以通過總線、路由、二維網格全互連形式等方式將若干個RC單元連接在一起，RCA是CGRAs加速的主要部件。

3 Petri網的基本概念

有限狀態自動機常用于單任務單狀態的轉換，對于活性、可達性、持續性等問題描述較難，針對實時多任務的復雜系統，系統的并發和動態性等因素均要考慮，Petri網等工具對其描述較為合適，Petri網是一種網狀信息流模型，包括庫所和變遷兩類節點，同時在庫所集上添加表示狀態信息的托肯分布（標識），可以較好地解決此類問題。相關Petri網的基本定義列舉如下：

圖1 CGRAs通用計算模型

定義1[12]三元組 N=(P，T;F)稱作網，必須滿足以下條件：

其中，dom(F)={x∈P∪T|?y∈P∪T:(x，y)∈F}，cod(F)= {x∈P∪T|?y∈P∪T:(y，x)∈F}，這里，P 表示庫所（Place）集合；T表示變遷（Transition）集合；F是網的流關系（Flow）。

定義2[12-14]四元組 N=(P，T;F，M0)稱作Petri網系統當且僅當

（1）N=(P，T;F)為一個網。

（2）映射 M:P→{0，1，2，…}（非負整數集）稱為網N的一個標識，其中，M0是初始標識。

（3）引發規則：

（3.1）變遷 t∈T 稱為使能的當且僅當：?p∈·t: M(p)≥1，記作 M[t＞ 。

（3.2）在M 下使能的變遷t可以引發，引發后得到一個新的標識 M′，記作 M[t＞M′，對 p∈P，有：

定義3可重構運算陣列的運行可形式化為一個十元組表示為含k種顏色時延Petri網，即CTdPN=(P，T; F，IC，M，W，H，OC，D，CON)，其中 (P，T;F)是一個網（其滿足的條件見定義1），IC是顏色的一個有限集合IC={ic1，ic2，…，ick}，顏色庫所輸入集 IC 表示每次輸入到RCA的數可以是實數，二進制數的原、反、補碼，定點或浮點數等；有色標識 M:P→L(C)；權函數W:F→L(C)+；顏色變遷H:T→L(C)+；L(C)表示定義在顏色集IC上的一個實數等類型數的線性函數，L(C)+表示系數不全為0的 L(C)，即 L(C)=a1c1+a2c2+…+akck；L(C)+= b1c1+b2c2+…+bkck；其中，ai，bi(i=1，2，…，k)均為非負整數，且b1+b2+…+bk≠0，初始標識為 M0，對?t∈T，如果 p∈·t→ M(p)≥W(p，t)，那么變遷 t在標識 M 有發生權(M[t＞)，在標識M 下發生變遷t，產生一個新的標識 M′(M[t＞ M′)：

顏色庫所輸出集 OC={oc1，oc2，…，ock1}表示任一運算任務DFG在RCA陣列所有輸出集合即有色庫所集IC表示每次輸入到RCA的數可以是實數，二進制數的原、反、補碼，定點或浮點數等，經過有色變遷集會產生相應的實數，進制數的原、反、補碼，定點或浮點數等輸出，OC=T′×P′，×為笛卡爾積，其中，P′為有色庫所集合，T′為有色變遷集合，T′=是定義在顏色變遷集T上的時間函數，即 D:T→R∪Ω1∪Ω2，R表示一個實數集，Ω1表示二進制數的原、反、補碼的集合，Ω2表示定點或浮點數的集合；D是定義在變遷集T上的時間函數，對于t∈T，D(t)=c表示變遷t的發生需要c個單位時間來完成。CON為任一DFG在RCA運行所耗費的配置時間。

為了便于比較行有依賴和無依賴映射完成后在RCA上的任一任務DFG的總執行時間，若RCA的互連方式相同，顏色庫所輸入集IC或輸出集OC的數據類型及輸入輸出次數均相同，配置時間也相同。在此條件下，定義3就退化為時延Petri網，具體見定義4。

定義4[12]時延Petri網是一個五元組TdPN=(P，T; F，M，D)，其中 (P，T;F，M)為一個原型Petri網，D 是定義在變遷集T上的時間函數，具體同定義3。

4 CGRAs的RCA內部最大運行并行度分析

4.1 CGRAs編譯流程

開發有效的SoC（System on Chip）芯片硬件任務編譯器是軟硬件邏輯高層綜合的一個重要方面，這項工作不但具有理論意義，而且具有重要的實際意義和應用價值。本節結合文獻[2]給出了一個通用CGRAs簡明編譯流程，如圖2所示。

圖2 通用CGRAs簡明編譯流程模型

由圖2可知計算任務的劃分與映射是CGRAs獲得高的加速比的一個重要方面，故對RCA映射結果的研究及其重要。

4.2 行無依賴空域映射

CGRAs中的RCA運算陣列可以看作一個通過不同互連資源互連的多指令流多數據流（MIMD）的并行計算系統，計算任務的調度是其設計關鍵要素之一，本節不對具體邏輯、時序、算術等運算帶抑止弧的增廣Petri網進行建模，而是研究基于RCA陣列運算，把計算任務直接分配給具體的RC單元，分析其運行機理，以便找到一個最佳調度并行執行方案使其計算任務總的執行時間盡可能達到最短。

一般而言，矩陣運算含有的循環次數較多，且較具代表性，所以本文矩陣運算為例，分析相關映射算法的性能。一個4×4矩陣運算的循環內核（共有16次循環）經過SUIF軟件展開并優化后[15-16]，可獲得4×4矩陣運算一次循環的任務子圖（見圖3（a）），各圓圈斜線上的英文字母表示任務的序號，橫線下的數字表示任務的執行時間。一個4×4矩陣運算的循環內核展開獲得16個任務子圖，將這16個任務子圖分8次依次映射到一個全互連的 RCA4×4上（RCA的互連形狀如圖3（a）所示），若要求一次循環必須在同一塊RCA上運行，則一塊RCA每次可配置運行兩個完整的任務子圖，行無和有依賴映射結果如圖3（c）（d）所示。

圖3 說明兩種映射方法的例子

為了便于說明問題，本文做出以下約定：有符號和無符號乘法任務的執行時間為2 cycle；其他算術與邏輯運算任務均為1 cycle。表1中的a，b，d的任務為乘法任務，故其執行時間為2 cycle，c，e，f，g為加法任務，故其執行時間為1 cycle。

表1 圖3（a）的順序關系表述

基本的CTdPN網的圖形單元建模工具如圖4所列。

圖4 CTdPN網的建?；締卧P系圖

4.3 基于時延Petri網的任務調度映射的時間特性分析

任務圖被劃分并映射到CGRAs中的RCA上時，就轉變為一個肯定型工程問題，下面用CTdPN網對此進行分析，因為本節主要關注RCA運行的時間特性，且沒有關注不同的資源（即用不同顏色的托肯（token）表示）使用問題，所以分析方法與文獻[12]關于任務調度肯定型問題類似。

下面本節可用CTdPN網對圖3兩種映射的時間特性進行分析，由圖3可知，RCA的互連方式相同，顏色庫所集合IC輸入次數均為16，集合OC的輸出次數均為2，并且兩種映射的輸入出的數據類型一樣，配置時間也一樣。在此條件下，CTdPN網簡化為時延Petri網即TdPN網，具體見定義4。所以為了便于說明問題，圖5和圖6中的網模型均采用時延Petri網對基于兩種映射方案的一個任務DFG運行的時間特性進行分析和驗證。

需要說明的是：全局時間不是Petri網的組成部分，因為全局時間對于大系統而言并非實時可知，也不能用于準確的控制。所以，用TdPN網分析得出的時間性能結論會有誤差，在此假設行無依賴映射和有依賴映射統一不考慮這個誤差。

圖5 行無依賴映射分析

表2 Σ1各個庫所 pi的 ASAP(pi)和 ALAP(pi)的值

圖3（c）的兩個映射成功的任務子圖可以按行流水線并行執行，采用的是行無依賴映射算法，對此可以將兩個子圖看作一個任務圖進行討論，其網模型和可達標識圖見圖5（a）和（b），網中每個庫所有兩個時間函數即最早發生時間ASAP(si)和最晚發生時間ALAP(si)，其值如表2所列。從Σ1網模型可知，在不改變任務工序之間的銜接關系的前提下，增加了零權庫所 p1和 p2，這樣就獲得行無依賴映射的Petri網模型。由圖5（a）和表2可得出的行無依賴映射主關鍵工序為（除去任務圖起點的虛庫所 p0和任務圖終點的虛庫所 pe）：a1→c1→e1→g1；b1→c1→e1→g1；a2→c2→e2→g2；b2→c2→e2→g2。依據圖3（b）RCA4×4硬件的實際，這四條主關鍵工序可以按行并行執行，同時考慮非關鍵工序的花費時間較長的任務 d1，d2，f1，f2可以得出行無依賴映射算法在 RCA4×4運行總的花費時間為7 cycle，由Σ1網可達標識圖可知，該Σ1網模型具有可達性、活性、持續性等性質。

對于圖3（d）的兩個映射成功的任務子圖僅可以部分按行并行執行（如 a1，b1，d1，f1的并行），故將其看作兩個獨立子圖討論（因為相同，所以只討論一個），其中一個任務子圖網模型和可達標識圖如圖6（a）（b）所示，網中每個庫所的ASAP(si)和ALAP(si)如表3所列。

表3 Σ2各個庫所 pi的 ASAP(pi)和 ALAP(pi)的值

由圖6（a）和表3可得出的行有依賴映射主關鍵工序為（除去任務圖起點的虛庫所 p0和任務圖終點的虛庫所 pe）：a1→ c1→e1→ g1；b1→ c1→e1→g1。依據圖3（b）RCA4×4硬件的實際，這兩條主關鍵工序不可以按行并行執行，僅是部分的關鍵工序和非關鍵工序部分任務按行執行，如 a1，b1，d1，f1等，從而可以得出一個子圖按行有依賴映射算法在RCA4×4運行總的花費時間為5 cycle，兩個子圖共需花費的時間為10 cycle，由 Σ2網可達標識圖可知，該Σ2網模型也是滿足可達性、活性等性質。

圖6 行依賴映射分析

一個4×4矩陣運算的循環內核展開共有16個的任務子圖，如果分8次在全互連的RCA4×4按行無依賴和行有依賴進行映射和運行，發現行無依賴映射執行完一個4×4矩陣運算總的耗時為56 cycle，而行有依賴映射執行耗時為80 cycle，相比較行有依賴映射而言，行無依賴映射的執行耗時少了24 cycle，所以行無依賴映射算法的優勢明顯。

5 結束語

本文結合Petri網通過實例對行無依賴映射和行有依賴映射的時間特性進行分析和比較，相比于文獻[11]提出的允許行有依賴映射算法而言，本文提出的行無依賴映射算法具有可行性和合理性。

[1]Compton K，Hauck S.Reconfigurable computing：a survey ofsystemsandsoftware[J].ACM ComputingSurveys，2002，34（2）：171-210.

[2]Cardoso J M P，Diniz P C，Weinhardt M.Compiling for reconfigurablecomputing：asurvey[J].ACM Computing Surveys，2010，42（4）：1301-1365.

[3]Arnold J M，Buell D A，Hoang D T，et al.The splash 2 processor and applications[C]//IEEE International Conference on Computer Design：VLSI in Computers and Processors，1993：482-485.

[4]Hasan M Z，Sotirios S G.Customized kernel execution on reconfigurable hardware for embedded applications[J]. Microprocessors and Microsystems，2009，33（3）：211-220.

[5]Giovanni A，Paolo B，Laura P.EGRA：a coarse grained reconfigurable architectural template[J].IEEE Transactions on Very Large Scale Integration Systems，2011，19（6）：1062-1074.

[6]Pranav V，John L J.A novel multicontext coarse-grained reconfigurable architecture for accelerating column-oriented databases[J].ACM Transactions on Reconfigurable Technology and Systems，2011，4（2）：1-30.

[7]Giovanni A，Kazuyuki T，Laura P，et al.Integrated kernel partitioning and scheduling for coarse-grained reconfigurable arrays[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2012，31（12）：1803-1816.

[8]Yongjoo K，Jongeun L，Toan X M.Improving performance ofnested loopson reconfigurable array processors[J]. ACM Transactions on Architecture and Code Optimization，2012，8（4）：1-22.

[9]Mei B F，Vernalde S，Verkest D，et al.ADRES：an architecture with tightly coupled VLIW processor and coarsegrained reconfigurable matrix[C]//Proceedings of the 13th InternationalConference on Field-Programmable Logic and Applications.Lisbon，Portugal：IEEE CS Press，2003：61-70.

[10]Singh H，Lee M H，Lu G M，et al.MorphoSys：an integrated reconfigurable system for data parallel and computation intensive applications[J].IEEE Transactions on Computers，2000，49（5）：465-481.

[11]Yoon J W，Shrivastava A，Park S，et al.A graph drawing based spatial algorithm for coarse-grained reconfigurable architectures[J].IEEE Transactions on Very Large Scale Integration Systems，2009，17（11）：1565-1578.

[12]吳哲輝.Petri網導論[M].北京：機械工業出版社，2006.

[13]曾慶田，吳哲輝.無界Petri網的進程表達式[J].計算機學報，2003，26（12）：1629-1636.

[14]蘇國軍，汪雄海.半導體制造系統改進Petri網模型的建立及優化調度[J].系統工程理論與實踐，2011，31（7）：1372-1377.

[15]Moon S，So B，Hall M W.Evaluating automatic parallelization in SUIF[J].IEEE Transactionson Paralleland Distributed Systems，2000，11（1）：36-49.

[16]Hall M W，Amarasinghe S P，Murphy B R，et al.Interprocedural parallelization analysis in SUIF[J].ACM Transactions on Programming Languages and Systems，2005，27（4）：662-731.

CHEN Naijin

College of Computer and Information Engineering,Anhui Polytechnic University,Wuhu,Anhui 241000,China

In order to more effectively optimize the mapping acceleration performance of coarse grained Reconfigurable Cell Array（RCA）,a method of row nodes no-dependency spatial mapping scheduling constraint is put forward.Timed Petri nets are used to analyse several data flow subgraphs which have been partitioned and mapped on RCA by constraint based on the same conditions.The running results of row nodes dependency mapping and row nodes no-dependency mapping are compared by an example.The experimental results show that this spatial mapping method is feasible.

Coarse Grained Reconfigurable computer systems（CGRAs）;Petri net;reconfigurable cell array;data flow graph

為了更有效地優化粗粒度可重構單元陣列映射加速性能，提出了一種行節點無依賴約束的空域映射調度方法，基于相同條件下，采用時延Petri網對若干個按約束已經被劃分映射到可重構單元陣列的數據流子圖的運行情況進行了分析，通過一個實例比較了行節點有依賴和無依賴的運行結果，結果表明該種空域映射方法具有可行性。

粗粒度可重構計算機系統；Petri網；可重構單元陣列；數據流圖

A

TP302

10.3778/j.issn.1002-8331.1302-0038

CHEN Naijin.Spatial mapping time performance analysis based on two dimension RCA and Petri net.Computer Engineering and Applications,2014,50（23）：41-46.

國家自然科學基金（No.61203034）；安徽省自然科學基金面上項目（No.1408085MF124）；安徽省高等學校省級自然科學基金（No.KJ2012B010）；蕪湖市科技計劃自然科學基金重點項目（No.蕪科計字[2012]95號）。

陳乃金（1972—），男，博士，副教授，研究領域為可重構計算、時空域劃分與映射等。E-mail：cnj@ahpu.edu.cn

2013-02-05

2013-05-03

1002-8331（2014）23-0041-06

CNKI網絡優先出版：2013-05-21,http://www.cnki.net/kcms/detail/11.2127.TP.20130521.1027.007.html