并行離散事件模擬系統容錯功能設計
2006-12-31 00:00:00王巖吳悅楊洪斌
計算機應用研究 2006年8期
(上海大學 計算機工程與科學學院， 上海 200072)
摘 要：基于時間偏差的并行離散事件模擬是提高模擬速度的有效手段，其通用系統實現結構是分布式邏輯進程模擬結構。提出了在并行離散事件模擬系統中實現容錯功能的基本框架，并針對系統本身特點對容錯框架各個方面的實現方案給予描述。
關鍵詞：并行離散事件模擬； Time Warp； 分布式邏輯進程模擬結構； 容錯
中圖法分類號：TP391．9文獻標識碼：A
文章編號：1001-3695(2006)08-0069-03
Design on Fault Tolerance of Parallel Discrete Event Simulation System
WANG Yan， WU Yue， YANG Hong bin
（School of Computer Engineering Science， Shanghai University， Shanghai 200072， China）
Abstract:Parallel discrete event simulation based on TW is an effect method to improve the speed of simulation， it’s common implementation structure is distributed logic process structure. This paper come up a fault tolerance framework within the parallel discrete event simulation system and give the implementation plan description of this framework.
Key words:Parallel Discrete Event Simulation; Time Warp; Distributed Logic Process Structure; Fault Tolerance
隨著模擬對象模型復雜性的日益增長，邏輯模擬對處理器時間和內存要求也越來越高。使用高性能計算機提高速度，用并行的方法實現模擬成為了一個嶄新的研究方向。采用時間偏差協議(Time Warp Protocol，TW)的并行離散事件模擬( Pa rallel Discrete Event Simulation)已經證明能夠在很大程度上提高模擬的速度，成為了并行模擬領域事實上的標準。然而在研究過程中發現，隨著模型規模和復雜性的日益提高，模擬過程常常需要幾小時甚至幾十小時才能完成。在沒有容錯功能的模擬系統中，一旦在模擬過程中出現故障，將不得不丟棄模擬得到的結果，從頭開始重新執行模擬，這將在時間和效率上帶來巨大的損失。本文將介紹基于時間偏差的并行離散事件模擬及其體系結構——分布式邏輯進程模擬結構，并在此基礎上提出容錯框架和實現方案的描述。
1 基于時間偏差的并行離散事件模擬
基于時間偏差的并行離散事件模擬是指將模型劃分為M個部分，每個部分被封裝進一個邏輯進程(LP)中，并分別在N（N≤M）個處理器上同時進行模擬，各邏輯進程之間依靠消息傳遞進行同步。在模擬過程中，如果一個邏輯進程推進得比較快，就可能接收到其他進程發來的一個遲到的消息（Stragglers），即該消息的時間戳小于當前邏輯進程正在執行的事件的時間戳，這將會導致模擬過程出現故障。為避免出現這種邏輯上的順序錯誤，并行模擬采取各種策略解決各邏輯進程之間的同步問題。作為一種樂觀協議，時間偏差協議TW利用回退策略解決同步問題，當某邏輯進程發生邏輯順序錯誤時，退回出錯處再進行模擬。回退包括兩步：①丟棄時間戳大于落后消息時間的狀態，恢復到比落后消息的時間標記值小的最近一個離散時間點上。②取消所有已錯誤發送出去的消息，這通常使用發送反消息來實現。在回退之后，LP以糾正好的路徑重新執行。
要實現回退，每個LP都需要將模擬過程中的信息記錄下來。為此，每個LP維護了各自的輸入隊列、狀態隊列和輸出隊列。輸入隊列維護LP處理的事件；輸出隊列維護LP的輸出消息；狀態隊列維護LP在各個離散時間點的狀態信息。
在模擬過程中，還必須考慮對內存的回收和對某些不可恢復操作（如I/O操作）的管理。為此，時間偏差模擬器定期地計算一個全局范圍內的“界”，稱為全局虛擬時間GVT。一旦GVT計算出來，任何一個LP都不可能再回退到GVT之前的時間點上，因此GVT之前的所有狀態信息都可以安全地刪除，所有事件都可以安全地執行。
如上所述，基于TW的離散事件模擬過程中不可避免地存在著大量信息的傳遞，消息的相互傳遞是整個系統得以同步和前進的基礎。而分布式邏輯進程模擬結構是離散事件模擬的通信架構，所以理解它就至關重要。我們的容錯模型，即構建于這個結構之上的。
2 分布式邏輯進程模擬體系結構
離散事件模擬模型通常使用基于邏輯進程LP的分布式結構。其結構如圖1所示。
在分布式LP模擬結構中，為了保證系統具有強大的并行能力，被模擬的模型會被劃分為許多區域。劃分的目的是使得在整個離散事件模擬過程中，每個劃分塊中間有相近數量的模擬對象在活動，以期達到并行性能的最大化。
一個模型域（R），一個模擬引擎（SE）和一個邏輯進程通信接口（LPCI）組成了一個邏輯進程LP。LP又被映射到處理節點（PE）上。這些處理節點可以是并行結構的處理器，也可以是局域網上的某些節點，甚至可以是通過Internet通信的計算機。其中邏輯進程通信接口（LPCI）是LP的通信中間層，同一個PE上的LP之間的通信由節點通信系統（PECS）加以處理，而位于不同PE上的LP之間的通信則通過PE通信接口PECI由節點間通信系統（IPECS）加以實現，以上幾個部分共同構成了一整套離散事件模擬的通信體系。一個模擬過程的完成，正是這些LP，PE之間彼此通信、相互協調、及時同步的結果。
容錯功能設計必須充分考慮這個通信系統本身的特點。
3 具有容錯功能的分布式離散事件模擬系統
具有容錯功能的分布式離散事件模擬系統的總體設計框架由以下三部分組成，即錯誤檢測，數據恢復和動態負載平衡。由于分布式離散事件模擬是典型的事件驅動系統，在其上加載容錯機制也必須結合該系統本身的特點。
3．1錯誤檢測模塊的設計
在模擬過程中存在兩種類型的故障，即Fail stop類型故障和拜占庭式故障。顧名思義，Fail stop類型故障是指如果有故障發生，整個模擬進程就會中止，不會有模擬結果產生；如果有模擬結果產生，我們就認定模擬過程正確。與之形成對比的拜占庭故障則是無論是否存在故障，都會運行到最終，但不保證模擬結果的正確性。目前我們的研究只涉及Fail stop類型的故障，拜占庭式故障將在后續工作中加以研究。
針對分布式離散事件模擬本身的特點（分布式、大量信息傳遞、LP是系統的主要參與者），采用如下方案來實現故障檢測：利用LP來作為故障檢測管理者，采用空消息來充當各個LP之間聯絡的橋梁——類似于分布式系統的心跳線(Heartbeats)。針對Fail stop類的邏輯進程出錯，處理節點失效以及通信線路故障三種故障，具體的檢測方法敘述如下：
（1）邏輯進程出錯。存在兩種可能：①同一個PE上的LP出錯；②不同PE上的LP出錯。針對①，在PE上的LP之間選擇一個充當故障檢測管理者，管理者與其他LP之間通過心跳線監控，如果一段時間內檢測不到某一個LP的心跳線則證明該LP故障。對于②，可以這樣處理，即每一個PE選出一個代表，建立虛擬令牌環，代表之間相互通信，如果一個代表檢測到自己PE上的某一個LP發生故障，就立即向其他的代表廣播消息，避免故障的進一步傳播。
（2）處理節點失效。將處理上述②的方法加以改進，使PE上代表的選擇更具有普遍性，即使得每一個LP都有可能在某種情況下成為代表，以確保非故障的PE上至少存在一個正常工作的LP。這樣，當一個PE上代表的心跳線不存在時，就是PE發生了故障。
（3）通信線路故障。我們考慮PE間通信系統存在故障的現象。這時候心跳線的丟失既有可能是PE故障，也有可能是通信線路在傳輸過程中造成的。解決方法如下：假使PEi上的代表LPi沒有接收到PEj的代表LPj的心跳線，則它向第三方PEk表LPi詢問是否收到PEJ的心跳線。如果PEk接收到PEj心跳線，則說明PEi和PEj之間的線路發生了故障。如果PEk也沒有收到PEj的心跳線，則PEi需要持續向其他的PE詢問，若所有的PE均沒有收到PEj的心跳線則證明PEj不可到達。
3．2數據恢復模塊的設計
在容錯機制中經常使用的數據恢復技術有兩種：檢查點和復制。檢查點技術需要穩定的存儲設備而復制技術的實現則需要大量的內存和計算能力。TW同步協議是樂觀同步協議，在實現模擬的過程中有大量的消息傳遞，并且當錯誤出現的時候還要進行回退。為了實現回退，就要保存變量狀態、事件列表、LP的虛擬時間、輸入輸出隊列和接收到的消息，這樣必然要消耗大量的系統資源，所以，在分布式離散事件模擬中，尤其是使用TW協議的模擬中，內存和計算能力是主要的瓶頸。針對TW本身的特點，選擇檢查點技術來實現數據恢復。
檢查點方案有非協作式和協作式。非協作式檢查點方案的實現思想是：各個進程獨立向前推進，并且獨立保存檢查點信息，而不管其他進程的進展情況。這種方案常常會造成這樣的后果——當出現故障的時候，形成級連式回退，也就是常說的多米諾現象，多米諾現象會造成大量計算的丟失，如圖2所示。
圖中菱形塊表示所取的檢查點，m表示所發送的消息。當p2進程發生故障的時候，將回退至它所保存的檢查點C，自然要取消它所發送的m6消息；p1要取消接收到的m6消息，就必須回退至檢查點B，同時取消m7;這樣又會導致p0回退至檢查點A，繼而使得p2再次回退到更前面的檢查點。這樣，逐級回退將會使所有的進程都回退到運行的初始點。這就是多米諾現象。
解決多米諾現象最簡單的方法就是采用協作式檢查點方案，即每個進程在記錄檢查點時兼顧其他的進程，大家相互協調，形成一個全局式檢查點，也常稱之為Recovery Line。在故障發生的時刻，涉及的相關進程回退至最近存儲的全局式檢查點，這樣就避免了各個進程的獨自回退而造成的多米諾現象。
針對分布式離散事件模擬本身的特點，我們選擇使用協作式檢查點方案。
根據上文的介紹，TW系統會階段性地保存各個LP的輸入隊列、狀態隊列和輸出隊列等信息。根據這個特點，我們對這些信息加以處理和提煉，形成用于容錯目的的Stable Checkpoints，并且使用協作式檢查點方案來生成全局性檢查點 Global Checkpoint。我們把全局性檢查點周期性地存儲到穩定存儲設備上，在系統出錯時用于數據恢復。假設在某時刻LPi發生了故障，所有與LPi相關聯的LP都可以回退至最近保存的Glo bal Checkpoint，從這點重新開始模擬進程。由全局性檢查點計算方法保證系統在此時刻狀態的正確性和完整性。選擇協作式檢查點方案的優點還在于：所有在全局性檢查點以前的模擬數據都可以丟掉，這樣可以大量地節省系統資源。此外，全局性檢查點的計算與系統本身GVT的計算相似，我們可以充分利用GVT計算來同時計算Global Checkpoint，這樣可以有效地減少系統運算開銷。
3．3動態負載平衡
在分布式計算系統中，存在著動態負載平衡問題。它是指在系統的負載不均衡的狀況下，把負擔較重節點的工作動態的調整到負擔較輕的節點上。在通常的負載均衡算法中涉及較多的是負載的監控，負載狀況的度量方法等。我們在設計容錯框架這部分功能的時候，充分考慮分布式離散事件模擬中的同步協議的特點（如TW的大量信息傳遞、大量的回退），以類似于分布式系統中動態負載平衡的處理辦法來實現系統的恢復。下面針對相對復雜的處理節點PE失效故障簡述恢復方法。
如前所述，在模擬進行之前，我們會把LP映射到PE上，以增加系統的并行性能。當PE發生故障時，我們自然考慮動態地將LP重新映射到工作正常的PE之上，以實現系統的恢復。其具體步驟如下：
（1）將失效的PE視之為處于完全過載狀態，把該PE上的LP遷移到合適的目標PE上。
（2）設定計數器來統計在系統運行過程中各個LP之間消息傳遞的次數，用來判斷LP之間的親密程度，結合系統的劃分算法，以此作為選擇目標PE的度量方法。
（3）修改整個系統中的活動PE表以及目標PE上的活動LP信息表，使之與實際情況相符合，避免其他部分和失效PE的進一步通信。
（4）取出數據保存階段在穩定存儲器上存儲的數據，恢復相應LP的各項隊列。
（5）由任意正常工作的PE發出信號使系統重新運行。
4結束語
隨著大規模集成電路模擬等應用對模擬性能要求的提高，分布式離散事件模擬變得日益重要。但在以往的分布式離散事件模擬系統中，完全沒有考慮容錯。而模擬對象模型的日益復雜化，將會對容錯機制提出迫切要求。本文提出一個針對分布式離散事件模擬系統的容錯功能框架，并給出框架各個部分實現的方案，可以有效地處理在模擬過程中出現的各種故障。
參考文獻：
[1]D Jefferson. Virtual Time[J]. ACM Transaction on Programming Languages and Systems， 1985，7(3):404-425.
[2]H Avril， C Tropper. Clustered Time Warp and Logic Simulation[C]. Proc.of the 9th Workshop on Parallel and Distributed Simulation， 1995.12-119.
[3]Avritzer A， Weyuker E J. Detecting Failed Processes Using Fault Signatures[C]. IEEE International Computer Performance and Depen dability Symposium， Urbana Champaign， Illinoise， 1996.302-311.
[4]A Gafni. Rollback Mechanisms for Optimistic Distributed Simulation Systems[J]. Proceedings of the SCS Multi conference on Distributed Simulation， 1988，19(3):61-67.
[5]D W Glazer， C Tropper. On Process Migration and Load Balancing in Time Warp[J]. IEEE Transaction on Parallel and Distributed Systems， 1993，14(3):318-327.
作者簡介：王巖（1976-），女，河南鄭州人，碩士研究生，研究方向為數字系統的并行邏輯模擬；吳悅（1960-），女，副教授，研究方向為計算機輔助設計和EDA技術；楊洪斌（1962-），男，副教授，研究方向為計算機系統結構。
注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
