分散式離散事件模擬的效能預估及對特定應用之調適

Abstract

當系統的行為不便以數學理論或實驗來探索時，模擬提供了另一個途徑. 在觀念上, 一個模擬器可分為兩大部分: 模擬引擎 (simulation engine) 和領域知識 (domain knowledge).前者用以控制模擬的進行;後 者用來描述被模擬系統的行為. 離散事件模擬 (discrete-event simulation) 是模擬引擎的一種, 它的應用受限於模擬時所需的時間.解 決的方法之一是將分散式計算的觀念引入模擬器的設計, 這就是所謂的分 散式離散事件模擬.過去這些年來有許多分散式模擬引擎的設計法被提 出. 這些法則 (strategy) 可略分為兩大類: 保守式 (conservative) 和樂觀式 (optimistic). 前者以 Chandy-Misra 法最為著名, 後者以 Time Warp法為代表. 這兩類技術根本的差異在於處理程序間同步的方 法. 事實上並沒有那一個法則是最好的, 選用的考量主要取決於不同的應 用. 因為實作分散式模擬器需要可觀的人力, 所以使用者需要有工具幫忙 在實作前找出模擬效能最佳的法則. 我們提出一個平行度分析器( parallelism analyzer),它可以針對特定的應用, 預測採用 Chandy- Misra 法時可獲得的 speedup; 同時我們也證明了這個演算法的正確性. 這個分析器可被擴充來預測別種保守式法則的效能, 我們也討論了利用這 個分析器來預測樂觀式法則時會遭遇的困難. 接著, 我們將分析器的觀念 延伸, 用以預估採取 Chandy-Misra 法來模擬時所需要的記憶體數量. 初 步結果顯示, 這種預測技術是可行的.接著我們討論另一個主題: 如何對 既有的一般用途之分散式模擬法則做調適, 使其面對特定的應用對象時能 有突出的效能. 相關文獻認為這是提昇模擬法則效能的一種途徑. 我們 以 Chandy-Misra 法則為藍圖 , 去除不必要的常務 (overhead),從而設 計出個人通信服務網路 (personal communication service (PCS) network) 專屬的模擬法則 . 我們選擇 PCS 網路是基於它的複雜度超 過了循序模擬所能負荷的範圍, 是一個適合分散式模擬的例子. 實驗結果 肯定了我們的法則對 high-tier PCS 網路的適用性.本論文使分散式模擬 中的效能預測及調適得到更進一步的瞭解. Discrete-event simulation provides a way to understand system behaviors over time, particularly when mathematical analysis and direct experimentation with the system are impractical. The power of discrete-event simulation is limited by its require- ment in computing resource, both time and space. Over the past years, parallel/distributed processing served as a means to improve the simulation performance. Distributed discrete-event simulation is a kind of event- driven distributed computing. Proposed distributed simulation strategies roughly fall into two classes, conservative and optimistic, both of which differ majorly in ways used to syn- chronize processes. The best strategies depends on application; no one strategy can outperform all the others in any case. Note that the cost for programming a distributed simulator is high. Therefore, before actually implementing the candidate simu- lation strategy for a particular application, it needs ways to predict the maximal speedup achievable. We provide such a tech- nique, called the parallelism analyzer, for the Chandy-Misra strategy, one of the well-known conservative approach. This technique can be tailored to other conservative strategies. We discuss the challenges encountered while extending this tech- nique to ptimistic strategies. Furthermore, we generalize the analyzer to predict the amount of memory consumed in a Chandy- Misra simulation. This technique is useful in resource allo- cation and simulator implementation verification. Preliminary empirical results show that predicting the memory utilization by the analyzer is feasible. We show customization of the general-purpose Chandy-Misra strategy to achieve impressive performance. We optimize the Chandy-Misra strategy by reducing the potential overhead, and, therefore, propose a domain- specific strategy for cell-level Personal Communication Service (PCS) networks simulation. PCS networks are selected because of the giant in system components and the rich in