ＰＤＥＳ時間推進中樂觀算法的研究與實現(xiàn)

摘要：介紹了PDES時間推進中的樂觀算法，給出了樂觀策略，從本地控制機制、消息回滾機制和全局控制機制三個方面分析了時間彎曲機制，最后對算法進行了實現(xiàn)。

關(guān)鍵詞：PDES；樂觀算法；時間彎曲

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044(2009)05-1185-03

Research and Realization of the Optimistic Arithmetic in PDES Time Advancing

MIAO Qing， DING Jing，KONG Jian-xing

(Artillery Academy， Hefei 230031，China)

Abstract: It introduces the optimistic arithmetic in PDES time advancing， giving the optimistic strategy， analyzing the Time Wrap from the local control mechanism、message rollback mechanism and global control mechanism. In the end， it realizes the arithmetic.

Key words: PDES; optimistic arithmetic; Time Wrap

1 引言

并行離散事件仿真（Parallel Discrete Event Simulation，PDES），是指在多處理器系統(tǒng)或網(wǎng)絡(luò)工作站上并行執(zhí)行離散事件仿真程序。如何將不同類型的仿真系統(tǒng)的內(nèi)部時間協(xié)調(diào)一致，是保證仿真正確運行的基本前提條件，這也正是PDES過去20年努力解決的問題。隨著近年來計算機仿真技術(shù)中高層體系結(jié)構(gòu)（High Level Architecture，HLA）的飛速發(fā)展，作為HLA時間管理算法直接來源的PDES中的時間推進算法，對其的研究又掀起了新的高潮。

PDES中關(guān)鍵的時間推進同步算法始終是仿真界公認的重點和難點問題。目前PDES主要采取兩類同步算法。保守算法嚴格禁止發(fā)生因果關(guān)系錯誤，確保不會失序地處理非獨立事件，也就是保證依據(jù)時間的邏輯先后順序在并行機上處理事件，但可能發(fā)生死鎖。樂觀算法充分利用系統(tǒng)平臺的并行計算能力，設(shè)定分布在每個處理機上的邏輯進程可以按任意順序在空閑的處理機上執(zhí)行，一旦出現(xiàn)任何一個關(guān)系錯誤即發(fā)生同步錯誤，則及時進行回退，并且恢復(fù)系統(tǒng)上一時刻的狀態(tài)。本文重點研究PDES時間推進中的樂觀算法。

2 PDES時間推進中樂觀算法的研究

2.1 樂觀（Optimistic）策略

與保守策略相反，樂觀策略并不遵守本地因果約束條件，不需要確定可以安全處理事件的時間，它規(guī)定邏輯進程可以按任何順序執(zhí)行事件，盡可能快地向前推進，不嚴格地避免因果錯誤的發(fā)生，一旦進程收到一個時戳值小于正在處理的消息時戳的消息，則認為因果錯誤發(fā)生了，此時探測因果錯誤，并使用回滾機制糾正錯誤。這種方法的好處之一是可以充分利用可能發(fā)生，但實際上并不會發(fā)生因果錯誤的幾率。

2.2 時間彎曲機制（Time Wrap）

最著名的PDES樂觀算法是由Jefferson 提出的基于虛擬時間的時間彎曲機制（Time Wrap）。時間彎曲是把“超前——回滾”作為基本的同步機制，每個進程運行時，并不考慮是否會和其他進程發(fā)生同步?jīng)_突。一旦發(fā)生沖突，不管冒進的進程運行到什么時刻，都必須回滾到發(fā)生沖突前的時間點處，再按照己修正的路徑繼續(xù)運行。

可以用非常簡單的一句話描述出實現(xiàn)虛擬時間的主要約束條件，即如果事件A產(chǎn)生事件B，則在執(zhí)行A和B時，必須保證在B開始執(zhí)行前，A事實上已經(jīng)執(zhí)行完畢。但是實際上，如果A和B之間沒有因果關(guān)系，即使事件A具有比事件B較早的虛擬時間，也不需要在執(zhí)行事件B之前執(zhí)行事件A，可以并行執(zhí)行A和B，或者是執(zhí)行A后，立即執(zhí)行B，均可獲得更高的性能。如果A和B具有完全相同的虛擬時間坐標，那么在事件調(diào)度上就更沒有約束和限制條件，它們甚至可以交叉執(zhí)行。

為正確實現(xiàn)虛擬時間，必須使每個進程按時戳順序處理消息。但因為消息并不總是按時戳順序到達的，對于某個進程來說，僅僅依靠自身的信息，是不可能知道那個消息是具有“下一”時戳的消息的。不管哪個消息被推測為“下一”個，總可能有更早時戳的消息在較晚時刻到達。因此，即使具有“下一”時戳的消息到達，進程也不能確定它是這樣的消息。這是用時間彎曲機制實現(xiàn)虛擬時間的核心問題。

時間彎曲有三個主要組成部分：

1）本地控制機制（local control mechanism），利用本地虛擬時鐘（LVT：Local Virtual Time）負責(zé)按Lamport時鐘條件進行消息的接收、執(zhí)行和發(fā)送；

2）消息回滾機制，當(dāng)沖突發(fā)生時，負責(zé)回收已執(zhí)行的所有“錯誤”消息；

3）全局控制機制（global control mechanism），利用全局虛擬時鐘（GVT：Global Virtual Time）負責(zé)全局問題，如空間管理、流控制、輸出到外設(shè)的事件提交、錯誤句柄管理、仿真結(jié)束探測等。

2.2.1 本地控制機制（local control mechanism）

本地虛擬時鐘：每個進程都有自己的本地虛擬時鐘LVT，用于記錄局部仿真時間，其值等于進程輸入隊列中下一消息的時戳值，該值在事件處理過程中并不改變，只在事件之間變化。

每個進程只有一個輸入隊列，所有到達的消息按虛擬接收時間遞增的順序存儲在隊列中。理想情況是，進程循環(huán)運行，不斷地接收消息，按虛擬時間順序執(zhí)行事件，產(chǎn)生新的事件，并發(fā)送消息。只要沒有收到“過去的”的消息，這個理想的進程就能一直運行下去。但是如果由于各個進程的計算速率不同，或網(wǎng)絡(luò)傳輸延遲等原因，使進程收到了“過去的”的消息，不管是何種原因，接收方解決此問題的唯一方法是，回滾到該“遲到”消息時戳的虛擬時間上，先執(zhí)行該“遲到的”消息，再執(zhí)行時間戳大于該“遲到”消息的消息，取消所有已造成的錯誤的影響，然后再向前推進，這樣這個消息就能處于正確的位置了。

當(dāng)進程處理完輸入隊列中所有的消息時，它的LVT被設(shè)為+inf，或者說，進程運行暫時結(jié)束了，但并不是被刪除了，一旦重新接收到消息，進程繼續(xù)運行，它的LVT被置為該消息的時戳。

由于每個進程不可能等待“下一”消息，因此進程一直連續(xù)運行，按虛擬接收時間遞增的順序處理那些已到的消息。但是由于無法保證將來是否會有“遲到的”消息，因此所有進程的運行都是暫時的，這有點類似于賭博，一旦賭博成功，進程就能順利運行，但是一旦賭博失敗，進程必須被“處罰”，回滾到它應(yīng)該接收這條“遲到”的消息的虛擬時間。下面給出進程循環(huán)時的處理方式：

初始化T：=0

while不滿足仿真結(jié)束條件do

接收消息，即進行消息排隊；

If輸入隊列中有消息then

取出隊列中第一個消息；

if該消息的時戳t＜當(dāng)前虛擬時鐘Tthen

回滾；

else

處理該消息； //如果需要，發(fā)送消息

T：= t；

保存進程狀態(tài)；

End if

Else

T：= inf；

End if

End while

換種說法，每個進程不斷“提前”處理輸入隊列中的“未來”消息。但是不管采用哪種超前調(diào)度，有一點可以肯定，回滾并不是經(jīng)常發(fā)生的。如果通過偶然的回滾而大幅度的提高系統(tǒng)運行的性能，那么可以說“超前處理”是成功的。

2.2.2 消息回滾機制

一個進程在仿真系統(tǒng)中有唯一的一個進程名，有它自己的狀態(tài)，包括它的所有的數(shù)據(jù)空間。進程有一專門的狀態(tài)隊列，作為進程狀態(tài)的備份，為防止進程發(fā)生回滾，時間彎曲機制必須定期保存進程狀態(tài)。最簡單的方法是處理完每個事件后，都保存狀態(tài)，當(dāng)然根據(jù)需要，也可以減少或增加保存頻率，比較好的方法是每過一段時間保存一次進程狀態(tài)。每個進程有唯一的輸入隊列，包括所有最近到達的消息，消息按虛擬接收時間存儲。小于本地虛擬時鐘的消息己經(jīng)過處理了，但并沒有從隊列中刪除它們，因為一旦發(fā)生回滾，還需要重新處理它們。虛擬接收時間大于本地虛擬時鐘的消息還未處理。每個進程有唯一的輸出隊列，包括進程最近發(fā)送的所有消息及其備份，消息按虛擬發(fā)送時間存儲。保存這些消息的目的是發(fā)生回滾時，可以“取消發(fā)送”它們。

在時間彎曲的消息回滾機制中，涉及一個概念，即反消息，專門用來回滾發(fā)生錯誤的消息。當(dāng)進程發(fā)送消息時，實際上發(fā)送的是正消息，而反消息保留在發(fā)送方的輸出隊列中，以防止發(fā)生回滾。對正、負消息的操作方法是對稱的，并遵守隊列原則，即一旦正消息和反消息出現(xiàn)在同一個隊列中，它們立即互相消除，并且不用考慮先到的是正消息還是反消息，只要第二個消息到達，立即發(fā)生消除。正消息和反消息一般是成對產(chǎn)生，成對消除的，并且在時間彎曲系統(tǒng)中，任何時刻，消息的代數(shù)和總是為0。

如果一個進程的LVT為T，收到一個虛擬接收時間為t（t ＜T）的消息，此時該進程需要回滾。回滾機制的第一步是搜索該進程的狀態(tài)隊列中小于t的最后一個狀態(tài)，然后恢復(fù)該狀態(tài)，同時恢復(fù)時間t為該進程的LVT。完成這些工作后，拋棄狀態(tài)隊列中大于t的所有狀態(tài)，重新啟動該進程，從t開始繼續(xù)向前推進。并且還要“糾正”t到T之間的工作，取消該進程向其他進程發(fā)送的消息，即發(fā)出這些消息的反消息。一個進程的回滾可能引起多個進程回滾，甚至可能形成回路，但由于沒有進程阻塞，因此不可能發(fā)生死鎖。

2.2.3 全局控制機制（global control mechanism）

在使用上述兩個機制前，還有兩個問題需要解決。第一，某些操作（如I/O操作），不能重新執(zhí)行；第二，即使重新執(zhí)行沒有發(fā)生，一些歷史的事件信息記錄必須被保存起來，這樣會占用越來越多的存貯空間。這兩個問題都可以用全局虛擬時間 GVT來解決。

可以將GVT當(dāng)作整個系統(tǒng)的虛擬時鐘，表示系統(tǒng)的運行進度。還可以把GVT看成提交下限，即任何時戳小于GVT的事件都不會被回滾，因此可以安全提交時戳小于GVT的事件。

3 算法實現(xiàn)

基于樂觀算法，我們采用C#.net編寫程序，構(gòu)建了采用時間彎曲機制來實現(xiàn)樂觀時間推進策略的系統(tǒng)。

系統(tǒng)的初始界面如圖1所示，界面左邊三欄分別顯示三個進程通道中的當(dāng)前狀態(tài)，主要是收發(fā)和處理消息及回滾的過程，右邊一欄顯示的是各個進程當(dāng)前的進程時鐘和當(dāng)前接收通道中接收其他進程發(fā)送的消息時戳。點擊“Start”鍵系統(tǒng)開始運行，點擊“Reset”鍵系統(tǒng)重啟。

仿真開始時，各個進程時鐘取值為零。進程查詢自己的輸入通道的消息隊列，按照接收順序依次處理消息，并把進程時鐘推進到消息所帶時戳處。如圖2，當(dāng)系統(tǒng)運行時，帶有“message”字樣的消息表示消息的發(fā)送，括號里的數(shù)字表示該消息的時戳。消息被處理后，系統(tǒng)對該消息打上“handled”標記。系統(tǒng)當(dāng)前狀態(tài)為：進程A，B，C按照接收順序依次處理消息，并且分別推進各自的進程時鐘到“4”，“9”，“8”。

在發(fā)送時戳為“7”，“9”的消息給進程B且進程B依次處理并推進進程時鐘到“9”后，進程A向進程B發(fā)送一時戳為“6”的消息，進程B的輸入通道的消息隊列中增加了一個時戳為“6”的消息，此時發(fā)生了沖突。如圖3所示。

進程B回收已執(zhí)行的所有“錯誤”消息，即時戳為“7”和“9”的消息，取消這期間的消息發(fā)送，即取消向進程C發(fā)送的時戳為“8”的消息，并回滾到發(fā)生沖突前的時間點處，此時進程A，B，C的進程時鐘分別回滾回“4”，“5”，“2”。如圖4所示。

各進程再按照己修正的路徑重新處理消息，繼續(xù)運行。進程B依次處理消息“6”，“7”，“9”，進程C重新處理消息“8”。最終各進程分別推進自己的進程時鐘到“4”，“9”，“8”，完成了一次消息的“超前——回滾”。如圖5所示。

4 結(jié)束語

實現(xiàn)的具體代碼在此就不一一列出了，有需要的同仁可直接向作者索取。雖然樂觀算法充分利用系統(tǒng)平臺的并行計算能力，各個進程能夠盡可能快地向前推進，但樂觀算法也存在著不足之處：

1）需要周期性地保存每個邏輯進程的狀態(tài)，這可能是時間彎曲機制的最主要的問題。狀態(tài)保存的開銷會嚴重降低算法性能，限制時間彎曲的效率，很難獲得好的性能。

2）內(nèi)存開銷大。與保守方法相比，由于樂觀算法需要保存進程狀態(tài)、輸入隊列、輸出隊列，因此需要大量的內(nèi)存，這是樂觀方法無法逃避的一個問題。

3）從實現(xiàn)上看，樂觀方法比保守方法復(fù)雜。實際的時間彎曲的代碼并不復(fù)雜，但是細微的設(shè)計失誤，可能會嚴重影響性能，甚至得出錯誤的計算結(jié)果。

參考文獻：

[1] Richard Fujimoto.Parallel Discrete Event Simulation [J].Communications of the ACM，1990，33(10).

[2] 歐陽伶俐.并行離散事件仿真算法及其在HLA時間管理中的應(yīng)用[D].北京:航天二院，1999.

[3] 歐陽伶俐，宋星，卿杜政，等.HLA時間管理與PDES仿真算法研究[J].系統(tǒng)仿真學(xué)報，2000，12(3)：237-240.

[4] 王學(xué)慧，邱曉剛，李革，等.PDES中樂觀時間同步的時空損耗研究[J].計算機仿真，2006，23（2）：86-89.

[5] 張耀程，喬海泉，李革，等.并行離散事件仿真中的回退和持續(xù)機制的研究[J].系統(tǒng)仿真學(xué)報，2007，19（1）：67-70.

[6] 李俊紅，楊洪斌，吳悅.基于樂觀策略的并行離散事件模擬研究[J].計算機工程與設(shè)計，2006，27（1）：12-14.