異構可重構計算系統的Petri網模型

張娓娓，郭 軍

(1.西安思源學院，陜西 西安 710038； 2.西北大學，陜西 西安 710069)

0 引 言

隨著IC芯片制造工藝越來越接近物理極限，傳統的馮·諾依曼結構計算機的性能提高遇到了瓶頸?？芍貥嬘嬎?reconfigurable computing，RC)作為一種新的高性能計算模式，是解決性能瓶頸問題的有效方法?？芍貥嬘嬎阆到y將密集運算(intensive computation)任務交給可重構硬件實現，利用硬件運算的高速性和并行性,大幅度提高系統的運算能力。目前，可重構計算技術在圖像處理、生物計算、密碼算法、多媒體等高性能計算領域獲得了成功應用[1-6]。

由于可重構計算系統的功能是通過軟件和硬件共同實現的，其設計方法不同于傳統計算系統，需要采用軟硬件協同的設計方法。設計過程首先是根據系統規格說明建立系統功能在可重構平臺上的描述模型，確定計算任務和相應算法，然后將計算任務有效地映射到計算平臺的軟硬件組件上。因此，選擇合適的系統描述模型是可重構系統設計過程至關重要的一步。

目前，計算系統描述模型主要分為形式化模型和非形式化模型。非形式化模型一般無需嚴格定義，采用比較簡潔的符號表達，易于理解和實現。常用的非形式化模型主要有數據流/控制流圖、流程圖和時序狀態機等。文獻[7-8]采用有向無環圖(DAG)描述可重構系統任務，簡潔易懂，是一種常用的非形式化模型。文獻[9-11]采用非形式化模型來解決系統設計過程中的問題。但是，由于非形式化模型缺乏嚴謹的數學定義和理論支持，容易產生歧義，給模型分析驗證帶來了困難。與此相反，形式化模型通常有嚴格的數學定義和理論支持，建模方法具有無歧義、便于分析驗證等特點，在可重構計算系統的描述中比非形式化方法更有優勢。常用的形式化模型主要有圖靈機、Petri網、共代數(co-algebras)、π演算(π-calculus)、時間自動機和UML模型等。文獻[12]研究了共代數方法描述可重構計算系統，給出了相關定義，歸納出了基本的重構操作，但模型比較復雜，需要較好的代數知識才能理解應用。文獻[13]提出π演算的變形φ演算(φ-calculus)方法描述可重構計算系統，利用了π演算描述動態變化的優勢，但給出的模型定義比較抽象，也需要相關數學知識才能理解。共代數和φ演算模型涉及的數學知識比較復雜，實際應用不夠方便。文獻[14]在π演算的基礎上提出了一種π語言，能夠對可重構系統進行形式化描述，并產生實用代碼，但是該方法需要專門的編譯器，應用的便利性還需要實踐檢驗。文獻[15]采用自動機與UML結合的模型驗證方法，雖然UML模型能夠提供系統的多視圖描述模型，模型結構簡潔易懂，便于實現，但是，UML模型本身是半形式化模型，其描述符號定義不夠嚴謹，模型不支持動態運行，難以驗證系統的動態行為。

Petri網作為一種傳統的形式化建模工具，理論完善，尤其適合描述并發、異步、資源沖突的系統[16-17]，符合可重構計算系統的特點；Petri網模型又是一種可運行模型，具有動態分析系統資源分配、驗證系統功能的能力，這也是可重構計算系統設計關心的問題。盡管Petri網模型在軟硬件設計中已經得到成功應用，但是，Petri網模型應用于可重構計算系統建模分析時還存在數據流描述能力不足的問題。因此，針對傳統Petri網模型的不足進行擴展，提出一種數據流Petri網模型，使之滿足可重構計算系統建模需求，并討論相關的建模技術和動態分析技術。

1 可重構計算系統

實際應用的可重構計算系統多為異構系統，通常是由CPU(中央處理器)、GPU(圖形處理器)、FPGA(可編程門陣列)、DSP(數字信號處理器)等部件通過高速網絡或接口以一定的耦合方式組成的并行計算系統。針對不同應用，系統結構也不相同，典型的可重構計算系統如圖1所示，由CPU+FPGA等組成[1]。其中處理器可以是通用CPU，如Intel、AMD的處理器，或者是ARM、POWER PC等嵌入式處理器。處理器主要執行控制任務和一些非密集計算任務，FPGA主要完成密集計算任務，其中FPGA的作用更像是一個協處理器。著名的Cray XD1、SRC-6和SGI Altix等可重構計算機都采用類似的體系結構。

圖1 可重構計算系統結構

一個具體的應用在可重構平臺上的運行過程是配置硬件和運算操作的交替。即首先根據具體應用，將FPGA配置成特定功能的邏輯電路，通常是IP核，建立數據通路；其次是將數據輸入邏輯電路接口，由邏輯電路完成計算；最后，把運算結果保留到寄存器/緩存。如果經過一次配置，應用任務尚未完成，就需要再一次配置硬件進行運算，直到得到最終結果。對于復雜的應用，往往需要經過多次重復，如圖2所示。由圖可見，在可重構計算平臺上，應用是在時間和空間進行的。在時間方向，完成一次一次的運算，在x-y空間方向，完成一次一次的配置。因此，在可重構系統中，計算任務不僅在時間延續，而且在空間展開，由于空間展開，并行任務可以實現真正意義上的時間并行，從而大大提高了系統性能。

圖2 任務執行過程

從以上分析可以看出，不同的應用在可重構系統上的執行過程是配置操作和運算操作的交替往復。通過不同的硬件配置，到達優化的系統結構，在優化的配置下，進行高性能的運算。如果將每次配置定義為配置件(configure ware)，將每個配置下的數據運算稱為數據流件(dataflow ware)，那么，一個應用可以抽象為若干配置件和數據流件組成的有序序列，這個序列應該能夠滿足系統的硬件資源、運行時間等約束條件。對于相互獨立的并行的應用任務，可以同時提供硬件配置，實現硬件意義上的真并行。因此，系統的描述模型，應該能夠描述可重構系統這種資源約束、并行和有序的應用特征，Petri網模型就具備這些描述能力。

2 數據流Petri網

Petri網適合描述并發、異步、資源沖突的系統，可以圖形表示，直觀易懂，便于分析模擬。但是，一般Petri網以描述控制流見長，描述數據流的能力較弱，為此，提出了著色網和雙變遷網等擴展形式，以增強Petri網的數據處理能力。文中將根據可重構系統的特點，借鑒著色網和雙變遷網的思想，擴展定義一種簡明易用的數據流Petri網。

2.1 數據流Petri網基本定義

DPN可以用圖形符號直觀表示，圖3給出了圖形符號的基本表示形式。圖中，細圓圈表示配置庫所，圈中非負整數表示配置標識；粗圓圈表示數據庫所，其中的數字是數據標識；短線條表示配置變遷，矩形表示數據變遷；帶箭頭的弧線表示流關系，細弧表示配置流，粗弧表示數據流，權值標注在弧上。圖中初始標識為Mc(p1)=10，Md(s1)=1，Md(s2)=1，其余為0。

圖3 DPN圖形表示

以上給出的是Petri網的靜態結構，通過定義變遷激發條件，可以得到Petri網的動態執行特性，從而研究系統狀態的變化過程。

定義2：對于DPN，?x∈P∪T∪Q，則

?x={y|y∈P∪T∪Q∧(y,x)∈Fc}

x?={y|y∈P∪T∪Q∧(x,y)∈Fc}

稱?x為x的配置前集，x?為x的配置后集。

定義3：對于DPN，?x∈Q∪S，則

°x={y|y∈S∪Q∧(y,x)∈Fd}

x°={y|y∈S∪Q∧(x,y)∈Fd}

稱°x為x的數據前集，x°為x的數據后集。

定義4：數據變遷函數f(q):°q→q°,q∈Q,描述數據變遷完成的操作。

定義5：如果t∈T，?p∈?t，有Mc(p)≥W(p,t)，則配置變遷t使能或有發生權；如果q∈Q，?p∈?q，有Mc(p)≥W(p,q)，且?s∈°q，Md(s)=1，則數據變遷q使能或有發生權。

數據流Petri網擴展定義了數據庫所，數據可以有不同的類型，這一點類似于著色Petri網。但是，由于進一步定義了數據變遷，其數據處理能力強于著色網。而且，著色Petri網控制流與數據流是不加以區分的，而數據流Petri網將數據流與控制流明顯區分開，既是為了描述可重構計算系統的需要，也是不同于著色網的顯著特征。

2.2 數據流Petri網運行過程分析

對于圖3描述的系統，初始標識為Mc(p1)=10，這時，根據定義5，只有t1滿足使能條件，t1激發后，引起系統狀態變化，p2、p3各得到5個配置資源，即完成了一次配置，如圖4(a)；在該配置下，數據變遷q1、q2滿足使能條件，且數據庫所前集不為空，q1、q2可以并發執行，完成數據操作，如圖4(b)，需要注意的是，q1、q2不一定同時執行，可以不同步；激發后，配置資源全部釋放給p4，p4得到10個配置資源，如圖4(c)，從而完成了一次配置/計算任務；接下來，配置變遷t2滿足使能條件，激發后p5、p6分別得到4個和2個令牌資源，完成第2次配置，如圖4(d)，在該配置下，q3首先滿足使能條件，激發后釋放4個令牌資源給p7，并傳遞結果數據到s6，從而q4滿足使能條件激發，釋放2個令牌資源到p7，運算結果保留到s7，如圖4(e)；由于第二次配置資源并沒有使用完，剩余的資源通過變遷t3，傳遞給p8，變化結果如圖4(f)。

(a)t1激發結果 (b)q1、q2操作結果 (c)t2激發結果

(d)q3操作結 (e)q4操作結果 (f)t3激發結果

圖4 模型運行過程

可見，圖3的模型描述了2次配置操作t1、t2，在完成t1配置后，進行2個可并行數據操作q1、q2；在完成t2配置后，進行2個串行數據操作q3、q4。不同配置下輸入的數據可以不相關，也可以相關。

模型對于數據操作采用批處理的概念，一次數據變遷處理一批數據，這樣可以避免因多次數據操作造成的復雜控制過程，而且，現有的硬件堆棧和DMA技術都能夠支持這種操作。

如果需要分析系統時間約束，可以進一步定義變遷激發時間，擴展成時間Petri網，但是，變遷激發條件需要重新定義；通過定義DPN的標識向量和關聯矩陣，分析可達路徑和標識變化，可以形式化表示和分析系統。鑒于篇幅所限，下面僅對模型的有界性、可達性和活性進行簡要說明。

有界性是指對于?p∈P，配置標識Mc(p)≤Mmax，Mmax是系統可提供的最大資源數量；對于?s∈S，數據標識Md(s)≤1；故DPN模型是有界的。對于模塊化可重構計算系統，可重構資源模塊是一定的，配置過程實際上就是把資源分配給不同的配置件，因此，無論何時，系統總的配置標識數量是不變的，資源數量是守恒的，這樣才能保障系統的安全性。利用DPN模型，可以很好地分析系統的有界性。

可達性描述了模型從狀態標識Mi，經過一個變遷系列，能夠到達新狀態標識Mj。就可重構系統應用而言，模型的可達性是至關重要的，決定了系統是否能夠實現某個配置，達到相應的系統狀態。由于大模型的狀態空間很大，分析可達狀態空間是一個困難的問題。通過模型運行，可以分析所關心的狀態是否可達，例如在圖4的模型分析中，兩次配置狀態都是可達的。

活性是指變遷t在某一標識下是否總能夠使能激發，也就是說，系統不會出現死鎖。這一點對可重構系統來說也是十分重要的，因為配置資源時，要避免資源競爭可能造成的死鎖。通過模型運行，可以分析發現系統可能出現的死鎖現象，圖4的分析表明示例模型不存在死鎖。

3 設計實例

乘加運算是矩陣運算的主要操作，而矩陣運算是一種典型的密集計算任務，在圖形圖像、信號處理中應用廣泛[18]。n階方陣乘法包含的乘法操作和加法操作數都在n3量級，而在圖像處理應用中，上百階的矩陣普遍存在，需要完成的乘法操作和加法操作數量十分巨大。這些運算操作大部分是可并行的，但是，在非并行體系結構上只能采用軟件技術實現串行操作，在可重構計算平臺上則可以實現并行運算。下面就以矩陣乘法為例，采用DPN模型描述任務的實現過程。

矩陣乘法運算的核心是乘法和加法操作，因此，配置任務主要是完成乘法器和加法器的配置。為了說明問題，這里僅以簡單的3×3矩陣為例，建立DPN描述模型。

矩陣乘法可以采用并行或串行算法。這里以并行乘、串行加為例，研究DPN描述不同結構的技術方法。如圖5所示，初始標識：Mc(p1)=6，Md(s1)=1，Mc(s2)=1，Mc(s3)=1，Mc(s4)=1，Mc(s5)=1，Mc(s6)=1，其他庫所標識均為0。通過分析模型的運行過程，可以得到系統狀態的變化情況，從而驗證是否滿足功能需求以及資源約束條件。模型運行時，t1變遷首先使能激發，分配給庫所p2、p3、p4各2個資源，配置3個并行乘法器，由數據變遷q1、q2、q3表示；第2次配置由t2實現，配置兩個串行加法器q4和q5，第2次配置與第1次配置存在數據相關，即s8和s9中上次配置運算結果先行計算，中間結果再與s7中數據相加，最終結果存入s11，資源全部釋放到p8。

圖5 乘加運算的DPN描述模型

4 結束語

采用Petri網等形式化方法描述可重構計算系統，有助于設計者較早地分析系統的功能和發現設計存在的問題，同時，也為各個設計階段提供了一個統一的系統級抽象模型，保證模型的一致性。通過定義數據流Petri網，文中提出一種針對可重構計算系統的建模方法，描述可重構計算中存在的配置流和數據流；實際建模表明，該方法所建模型結構簡單，分析過程直觀易懂，理論方法容易掌握，能夠描述資源約束下可重構計算系統中的主要特征參數，是一種實用性的可重構計算系統建模方法。