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

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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)部時(shí)間協(xié)調(diào)一致，是保證仿真正確運(yùn)行的基本前提條件，這也正是PDES過去20年努力解決的問題。隨著近年來計(jì)算機(jī)仿真技術(shù)中高層體系結(jié)構(gòu)（High Level Architecture，HLA）的飛速發(fā)展，作為HLA時(shí)間管理算法直接來源的PDES中的時(shí)間推進(jìn)算法，對(duì)其的研究又掀起了新的高潮。

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

2 PDES時(shí)間推進(jìn)中樂觀算法的研究

2.1 樂觀（Optimistic）策略

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

2.2 時(shí)間彎曲機(jī)制（Time Wrap）

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

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

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

時(shí)間彎曲有三個(gè)主要組成部分：

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

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

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

2.2.1 本地控制機(jī)制（local control mechanism）

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

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

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

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

初始化T：=0

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

接收消息，即進(jìn)行消息排隊(duì)；

If輸入隊(duì)列中有消息then

取出隊(duì)列中第一個(gè)消息；

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

回滾；

else

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

T：= t；

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

End if

Else

T：= inf；

End if

End while

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

2.2.2 消息回滾機(jī)制

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

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

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

2.2.3 全局控制機(jī)制（global control mechanism）

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

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

3 算法實(shí)現(xiàn)

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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