組合計算模型實現系統設計與仿真

摘 要:在模塊化的系統設計中，適合各個模塊的最佳計算模型往往不盡相同，這些計算模型包括有窮狀態自動機、Petri網、離散事件和事件關系圖等。為了方便設計者和提高工作效率，有必要允許對模塊采用不同的計算模型，再運用組合計算模型的理論將這些模塊組合成完整的模型以用于仿真和系統的自動生成。作為應用實例，通過分層組合離散事件和事件關系圖，可以設計易于擴展、修改和維護的動態系統;同樣的原理也可以應用于其他計算模型，從而使它們在模塊化設計中發揮各自的優點。

關鍵詞:系統設計; 系統仿真; 計算模型; 離散事件; 事件關系圖

中圖分類號:TP311.5文獻標志碼:A

文章編號:1001-3695(2010)06-2116-03

doi:10.3969/j.issn.1001-3695.2010.06.035

System design and simulation with composing models of computation

FENG Huining

(Oracle Corporation， Redwood Shores， CA， USA)

Abstract: In a modular system design， the models of computation appropriate for the components usually vary. Those models of computation include finite state machine， Petri net， discrete events and event relationship graph. To provide flexibility for designers and to improve productivity， it is necessary to enable the use of different models of computations in the components， and to apply the theories of composing models of computation to construct complete models for simulation and automatic system generation. As an application， by hierarchically composing discrete events and event relationship graphs， dynamic systems that were easy to extend， modify and maintain could be created. The theories could also be applied to other models of computation， and thus exhibited their benefits in compositional designs.

Key words:system design; system dimulation; models of computation; discrete events; event relationship graph

0 引言

系統設計可以借助各種建模軟件。大型系統常常是通過組合模塊而成的，而對于不同功能的模塊，最佳的設計手段不盡相同。這些設計手段包括有窮狀態機FSM(finite state machine)、UML序列圖(sequence diagram)、同步數據流(synchronous dataflow， SDF)、進程網絡(process network， PN)、Petri網和離散事件(discrete events， DE)等。它們都被稱為計算模型(models of computation)。

最近研究發現，一種由傳統的有窮狀態機和活動圖演變而來的計算模型——事件關系圖(event relationship graph， ERG)[1]，適用于動態時序系統，并可與其他一些計算模型組合以實現更復雜的設計[2]。本文提出分層組合DE和ERG，并為組合而成的系統進行仿真以了解其實際性能。藉此為例，闡明使用組合計算模型在系統設計中的優點。

1 離散事件和事件關系圖

離散事件(DE)[3]和事件關系圖(ERG)均可用于設計和模擬隨時間改變狀態的系統，它們有各自的長處，適用于設計不同類型的模塊。雖然在一定程度上可以交換使用，但合適的選擇可以使得設計更簡便和更易于管理。

1.1 離散事件

在模型設計與仿真環境Ptolemy II[4]里，一個DE模型包含代表運算節點的方塊。這些方塊可帶有用三角形表示的輸入和輸出端口，即指向方塊本身的是輸入端口;指向外部的是輸出端口。輸入與輸出端口之間的連線代表事件流，即事件從發送端(輸出端口)傳遞到接收端(輸入端口)。仿真時，事件的傳遞被認為是瞬時的。事實上，除非執行了引起時間變化的運算，否則系統時間不變，這有利于驗證系統與實現環境無關的時序特性。如有需要，可引入額外的運算節點以產生延時。

圖1展示了一個簡單的DE模型。其中，cars1、cars2和servers將會在下文詳細討論;merge將來自cars1和cars2的事件流合并，產生單個合并后的事件流，它的輸入端口是空心的，代表可以接受多個連接，而實心的端口只能接受至多一個連接;plotter用于在一個仿真時彈出的窗口顯示結果圖表。

值得注意的是左上角名為DE director的方塊，它代表這個模型使用了DE計算模型。取決于實際需要，設計者可以放入不同的計算模型，如SDF和PN，這些計算模型為設計圖賦予運行的意義。

由于這是一個DE模型，事件的處理必須按照它們所附帶的時間戳為序。舉例來說，如果cars1產生如圖2(a)的事件流，cars2產生如圖2(b)的事件流，則merge產生如圖2(c)的事件流。

圖2中每個事件表示為(時間戳，數據)的二元組。每一個事件流中，前面事件的時間戳不大于后面事件的時間戳。為便于討論，在此將時間戳簡化為小數，并且不考慮多個事件恰好發生在同一時間的情況。這些細節在文獻[3]中有詳細的論述。至于事件的數據，上例中使用連續的整數，而在實際應用中可以是任意數據類型。

1.2 事件關系圖

ERG同樣可用于設計動態系統。它與DE的異同將在第1.3節中討論。

圖3是一個模擬自動汽車清洗系統運作的ERG模型，這個系統有一個隊列供已到達但尚未開始接受清洗的汽車排隊等候。洗車機的數目取決于servers變量(圖中表示為小圓點緊跟著變量名和初始值);在任一洗車機空閑時，隊列中最先到達的汽車可以開始清洗。

與DE模型不同，ERG中的方塊并不代表運算節點，而是事件和事件發生時執行的操作。這與有窮狀態自動機也不同，因為后者中的方塊代表狀態，而不是瞬時發生的事件和操作。Init是初始事件，用填充和加粗邊框表示;該事件在仿真開始時間(一般是0.0)發生，發生時所執行的操作設為servers=3，queue=0。

Enter事件每次發生代表一輛汽車進入隊列等候清洗，它所對應的操作是遞增queue變量，代表等候的汽車數目增加1。汽車到達的間隔由一個隨機過程產生，在模型中，這些間隔由表達式3.0 + 5.0×random()計算。Random()是Ptolemy II內部函數，用于產生[0.0， 1.0)間的隨機數值。Start事件代表一輛排隊中的汽車開始接受清洗，并因此占用一臺洗車機。Leave事件代表一輛汽車清洗完畢，而它原來占用的洗車機變成空閑。

模型中的連接表示事件的因果關系，它們可以帶有條件(guard)和延遲(δ)，如條件或延遲省略則分別默認為true和0.0。例如，在init和enter之間的連接表示init事件發生后將觸發enter事件，而該enter事件將比init延遲上述表達式所設定的時間;又如，在enter與start之間的連接表示enter發生后，如果條件servers>0滿足，那么start將立即在當前時間發生。另一個從enter到其自身的連接表示enter發生后，經過一定的時間將會出現下一次enter事件。可見，ERG模型中一個事件可以觸發多個事件，這一點與有窮狀態機從一個狀態只能轉移到下一個狀態不同。

ERG的運行理論上需要一個無限空間的事件隊列。為討論方便，暫假設隨機函數random()恒返回0.0。圖4從上至下顯示系統運行時事件隊列的變化。事件隊列中的每個記錄表示為(發生時間，事件名稱)的二元組。

關于多個事件同時發生的討論可參閱文獻[2]的3.1.4小節。

1.3 關系和比較

DE和ERG適用于不同的系統或一個系統內不同類型的模塊。從定義上，DE并沒有惟一確定事件處理的先后順序，它僅確定了事件間的一個偏序關系。如果事件e1直接或者間接(通過引起其他事件)產生e2，表示成e1≤e2，那么e1必須在e2之前由運算節點處理完畢。然而，如果e1與e2無關，即既非e1≤e2，亦非e2≤e1，那么它們可以以任意次序處理，甚至同步處理[5]。這一特性允許采取不同的策略運行，從而達到充分利用硬件資源和滿足特定實時要求的目的;同時，節點的運算也是可以并行的。如圖1中，cars1和cars2之間沒有任何依賴關系，它們分別輸出事件到merge，因此它們可以同步執行。這對于在多核處理器上加快運行速度有很大幫助[6]。

ERG從定義上要求模型順序執行，每次只處理在事件隊列中的第一個事件;在該事件結束前，不能處理后續事件。這一思想在圖4中反映出來。此規定限制了多核處理器的優勢，但也方便設計者明確安排事件發生的順序，簡化多個事件對同一變量的操作。試想如果事件的順序并非惟一確定，那么變量的最終結果有可能因不同的運行策略而異。

將來對ERG的一個研究方向是用算法自動找出同步處理事件的策略，而保證系統的正確性不受影響。

2 組合計算模型

計算模型的組合是Ptolemy項目的研究重點，目的在于充分發揮不同計算模型在模塊化設計中的長處，最大限度地方便設計者。研究發現，某些組合在實踐中十分常用，如DE與ERG(在分層結構中，前者位于后者的上層，下同)、DE與FSM、SDF與FSM等;某些組合雖然可行，但并不十分常用，如PN與DE、ERG與SDF等;還有一些組合在理論上還沒有得到支持，如DE與PN、SDF與PN、SDF與DE、SDF與ERG等[7]。

2.1 設計考慮

由于上述DE和ERG間的區別，在實際應用中，ERG通常用于實現系統中較低層的模塊，如與硬件設備或終端用戶交互的模塊;DE則多用于控制這些模塊間的通信。

在一個比圖3稍為復雜的汽車清洗系統中，設想將汽車到達的邏輯設計成一個模塊，而將處理隊列和清洗汽車的部分設計成另一個模塊。這樣可以達到更好的關注分離(separation of concerns)，確保對汽車到達邏輯的修改不影響清洗模塊，反之亦然。通過修改或者更換指定模塊，還可以測試不同的實現方式對系統性能的影響。一個可行的辦法是用ERG分別實現這兩個模塊，它們可以獨立地使用內部變量而不受外界干擾。它們與外界的信息交互通過端口實現。

另一方面，組合這兩個模塊也需要選用一個計算模型。首先，ERG模塊是有時序的，因此要組合它們并讓它們對時間有統一的認知就必須選用一個能處理時間的計算模型。這樣，一個模塊所發送事件的時間戳在傳遞到另一個模塊后仍然有意義。很明顯不能采用SDF和PN等，因為它們并不能處理時間。嚴格意義上FSM也不可選，但經過擴展以后的模態模型(modal model)卻可以。其次，雖然兩個模塊互相傳遞信息，但希望它們可以相對獨立地運行，這樣就不須精確定義模塊內部的事件順序。對于事件e1和e2，如果它們屬于不同的模塊，那么僅當它們都參與信息交互時才關注它們的先后。最后，希望可以為以后增刪模塊提供一定的自由度，如增加一個汽車隊列，或者將一個汽車隊列按單雙號分成兩個。出于以上考慮，一個較好的選擇是將DE作為在ERG上層控制信息傳遞的計算模型。

2.2 計算模型組合示例

圖5通過組合DE和ERG來實現上述較復雜的汽車清洗系統。它運用了Ptolemy II提供的分層組合手段。用標號①表示的頂層是一個類似圖1的DE模型。這一模型沒有輸入和輸出端口，可以獨立仿真與運行。

Cars1和cars2是標號②模塊的兩個復件。它們有名為output的輸出端口，對應頂層模型中cars1和cars2右邊的輸出端口。每個復件簡單地重復輸出一個代表汽車到達的事件。由于cars1和cars2的輸出均被連接到merge，它們輸出的事件流如圖2所示，經過合并以后發送到servers的輸入端口。

Servers由標號③的模塊完成。它與圖3主要有以下區別:

a)CarInput端口輸入汽車到達事件;serversOutput和queueOutput端口輸出servers和queue變量每次更新后的數值。

b)指向enter的兩個連接的延遲設定為infinity，triggers屬性設定為carInput。這表示每個enter事件比上一次該事件無限延遲，直至carInput端口從外部接收到事件。

c)每當servers或queue變量更新，兩個變量的最新值通過輸出端口輸出到外部。這一操作由對應輸出端口的賦值語句實現。

用Ptolemy II仿真可以得到如圖6的輸出。這是plotter將接收到的兩個事件流(servers和queue)以系統時間為橫軸輸出到一個窗口的結果。居上的曲線為等待中的汽車數目。居下的曲線為空閑洗車機的數目。

從結果可以看出，這一系統是過載的，即等待的汽車數目無限增大。通過調整汽車到達間隔和清洗時間再次仿真或線性規劃可以獲得一個更優化的系統[8];增加洗車機的個數也可以達到相同的目的。

2.3 組合計算模型的特點

模塊化設計便于重用，減少工作。組合計算模型則允許設計者對不同模塊運用合適的計算模型，這樣可以提高設計的靈活性。以上述分層設計的汽車清洗系統為例，下層的模塊可以單獨開發。它們使用獨立的變量，內部狀態不受外界環境影響，它們與外界的信息交互由協議所規范，協議包括輸入輸出端口和數據類型。在外面，管理這些模塊的計算模型單純地為模塊傳遞信息，確保事件到達輸入端口順序的正確性，而無須關心模塊內部對數據的操作。整個系統還可以作為一個模塊在更大的系統中使用。

與軟件工程中常用的UML相比，組合計算模型理論的不同點在于涵蓋了更多面向不同類型系統工程師的計算模型，并允許采用不同的計算模型設計系統的各個組成部分。UML雖然提供了多種建模手段，但不同的計算模型如類圖、狀態圖和序列圖并不能輕易地組合成一個系統整體。它們通常僅僅反映系統的不同側面，而如何維護這些不同側面之間的一致性則常常成為棘手的問題[9]。與此不同的是，組合計算模型著眼于運用各種手段設計模塊，并將它們分層組合成用戶所需的系統。

3 結束語

使用合適的計算模型可以簡化設計和減少錯誤，對于設計與維護大型系統十分重要。組合設計模型使設計者可以對系統各個模塊選用不同設計模型，并將模塊組合成為整體進行仿真。

本文提出結合離散事件和事件關系圖構建模型，并以此為例闡明了分層組合計算模型的原理。實際應用反映出，靈活運用多種計算模型可以簡化設計，方便對模型的重用、修改與維護，從而降低開發成本。

對組合計算模型，未來的研究方向包括理論化更多類型的組合、簡化對常用組合的定義，以及將現有理論應用到實時系統、分布式系統和計算物理系統(cyberphysical systems)中。對事件關系圖的研究則主要在于將其應用范圍從原來的統計和運籌擴展到作為一種系統設計語言，用于仿真和生成實際系統中的控制模塊。另一研究方向則是在不改變語義的前提下并行運行事件關系圖，提高運行效率。

參考文獻:

[1]SCHRUBEN L. Simulation modeling with event graphs[J]. Communications of the ACM， 1983，26(11): 957-963.

[2]FENG Huining. Model transformation with hierarchical discreteevent control[D]. Berkeley: EECS at UC Berkeley， 2009.

[3]LEE E A. Modeling concurrent realtime processes using discrete events[J]. Annals of Software Engineering， 1999，7(1-4): 25-45.

[4]EKER J， JANNECK J W，LEE E A， et al. Taming heterogeneity: the ptolemy approach[J]. Proceedings of the IEEE， 2003，91(1): 127-144.

[5]LAMPORT L. Time， clocks， and the ordering of events in a distributed system[J]. Communications of the ACM，1978， 21(7): 558-565.

[6]ZHAO Yang， LIU Jie， LEE E A. A programming model for timesynchronized distributed realtime systems[C]//Proc of the 13th IEEE Realtime and Embedded Technology and Applications Symposium. Washingtoin DC: IEEE Computer Society，2007:259-268.

[7]GODERIS A， BROOKS C， ALTINTAS L， et al. Composing different models of computation in kepler and ptolemy Ⅱ[C]//Proc of the 7th International Conference on Computational Science. Berlin: SpringerVerlay，2007:182-190.

[8]CHAN W K， Schruben L W. Optimization models of discreteevent system dynamics[J]. Operations Research， 2008， 56(5): 1218-1237.

[9]張龍祥. UML與系統分析設計[M]. 北京:人民郵電出版社， 2001.