淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0806200622132700
中文論文名稱 分散式連網模擬環境之即時協調機制設計
英文論文名稱 Design of the real-time synchronization mechanism under distributive networked simulation environment
校院名稱 淡江大學
系所名稱(中) 資訊工程學系博士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 94
學期 2
出版年 95
研究生中文姓名 惠霖
研究生英文姓名 Lin Hui
學號 891190075
學位類別 博士
語文別 英文
口試日期 2006-06-01
論文頁數 81頁
口試委員 指導教授-葛煥昭
委員-王亦凡
委員-葛煥昭
委員-蔣定安
委員-施國琛
委員-黃俊堯
中文關鍵字 高階模擬架構  執行基礎  時限  同步 
英文關鍵字 High Level Architecture (HLA)  Run-Time Infrastructure (RTI)  Deadline  Synchronization 
學科別分類 學科別應用科學資訊工程
中文摘要 根據美國國防部一九九五年十月頒佈的『模式與模擬發展計劃』內容所述,其計劃之首要目標乃為模式與模擬建構出一套完整的高階模擬架構(High Level Architecture, HLA),此架構將成為美軍上下一貫之標準並廣泛運用於各類不同功能之軍事系統中。該技術架構之主要目的在於達成不同的模擬系統間之交流互動,並且提昇模擬系統和軟體元件之可重複使用率。而分散式模擬系統的各類需求是相當多元化的,HLA 可以提供較為一般性的骨幹架構以促成模擬系統的完整互動。
在真實世界中,軍事衝突是沿著一條時序(Time Line)來依序發生,因此在電腦兵棋的推演當中必須有效的模擬出相同的軍事衝突時序。而推演運行的方式就是指於推演中模擬真實世界時序的前進方式,推演所經過的時間必須精確地模擬,並確保物理法則以及推演之完整性/真實性。每一個演習訓練均有其推演模擬的起始日期與時間,電腦兵棋系統的推演方式通常使用連續式計時,必要時可以配合步階式計時以調快戰演比。因此在分散式模擬架構下的電腦兵棋系統,必須也能夠很精確的讓事件在正確的時序發生,並且要達到同步模擬的狀態。舉個例子:模擬演訓中,一連串的命令並不一定是依照執行先後順序下達的,所以,在分散環境下必須要確保較早時序的命令不會被忽略而時序較晚的命令反而先被執行,亦即必須保持正確之因果關係。而這些時序控制可以在兩種層面上實現,一個是在作業系統層面,稱為執行基礎(Run-Time Infrastructure – RTI) ,另一種是在應用程式的層面,稱為federate。
本論文所欲探討的即時時間管理服務即從此兩個層面來研究,也就是說,從執行基礎(RTI)的角度來研究如何設計即時時間管理模組,來改良現有之執行基礎(RTI)軟體的設計方式;另一個研究方向就是從federate角度來探討如何在現有執行基礎(RTI)軟體的限制下,提出federate的設計方式與運作規範以達即時性需求。
因此本論文所研究的議題為:
􀁺 設計符合即時性需求的HLA Time Management 機制,以及滿足deadline 條件的LBTS
計算公式與演算法。
􀁺 研究real-time 系統與lookahead 值之間的關係,以及探討降低「網路延遲」因素的
lookahead 值設定方式。
􀁺 藉由實驗來提出對於不同網路環境、real-time 系統與lookahead 值三者之間的關係
式,以利日後建構即時性模擬環境的依據。

英文摘要 In the real world scenario, the military conflicts have been taking place along the timeline. Hence, in order to realistically simulate the conflicts, the model of the software needs to effectively advance the simulation time in the same sequence. In other words, the software has to progress the events in the same order to ensure the causal and physical accuracies. Since simulation has the initial and ended time, the software is usually a successive time-stepping through the simulation. The time scale may also be changed during this period to coordinate with the time-step simulation. Hence, the time synchronization among distributive war game softwares is essential for the causal correctness of the simulated scenario. Time synchronization can be carried out in two levels. One is in the operating system level, called RTI in HLA terminology, and the other is the application level, called federate in HLA terminology.
This dissertation attempts to have an in-depth research on the time management of the distributed simulation from these two levels. First, this research will study the real-time management issue from the perspective of the RTI. This study plans to ameliorate the time management mechanism of the existing commercializes RTI software. On the other hand, this research will also discuss the federate’s design issue in the real-time simulation. That is, the issue of how to design a real-time federate under the constraint of existing RTI software.
In all, this dissertation would have some research issues as follows:
􀁺 Design the LBTS equation and algorithm that could satisfy the hard deadline requirement.
􀁺 Research the relationship between real-time system and lookahead value.
􀁺 Use experiments to study the relationship among the different network environments,
real-time systems and lookaheads. The relationship is valuable in the design and development
of future real-time simulation environment.

論文目次 Contents

List of The Figures III
1. Introduction 1
1.1. Motivation 1
1.2. Research goal 4
1.3. Research Procedure 6
2. Synchronization of the parallel / Distributed Simulation 8
2.1. Synchronization Problem Statement 9
2.2. Lookahead and Simulation Model 13
2.3. Synchronous Execution 14
2.3.1. Centralized Barriers 16
2.3.2. Tree Barrier 17
2.3.3. Butterfly Barrier 18
2.3.4. Transient Messages 20
2.3.5. A simple Synchronous Protocol 25
2.3.6. Distance between logical Process 27
2.4. Hard deadline and Soft deadline 33
3. HLA Time Management 36
3.1. The Role of Time 36
3.2. Message Order and Time Stamps 38
3.3. Advancing Logical Time 38
3.4. Lower Bound Timestamp Computation 40
3.5. Hard deadline Simulation Using HLA 41
4. The Service Performance for Time Management of RTI 43
4.1. The Time Advance Request Service 43
4.2. The Experiments 47
4.2.1. First Stage Test 50
4.2.2. Second Stage Test 53
4.3. Results and Discussion 58
4.4. Summary 64
5. The improvement of the time management service of HLA 66
5.1. The real time system’s modeling and scheduling 66
5.2. The Interactive Coordination of Hard deadline and Soft deadline Systems 75
6. Conclusion 77
7. Bibliography 79



List of The Figures
Figure1.1 HLA Architecture. 1
Figure1.2 Execution scenarios. (a) Time stepped federate using Time Advance Request. (b) Event driven federate using Next Event Request. 4
Figure1.3 Lookahead Description. 5

Figure2.1 Scenario illustrating the need for time management. 8
Figure2.2 Event E10 affect E20 by scheduling a third event E15 which modified a state variable used by E20. This necessitates sequential execution of all three events. 10
Figure2.3 Deadlock situation 12
Figure2.4 Sample execution of processors entering a barrier. 15
Figure2.5 Parallel simulation program using barrier synchronizations 16
Figure2.6 Processors organized into a tree to implement the barrier primitive. 18
Figure2.7 Eight-processor Butterfly barrier. (a) Communications pattern, and illustration of barrier from the perspective of processor 3; (b) tree abstraction of barrier mechanism. 19
Figure2.8 Notation for detecting transient messages in the butterfly barrier. 23
Figure2.9 A simple synchronous protocol. 26
Figure2.10 Synchronous simulation protocol. 26
Figure2.11 (a) Network of logical processes indicating lookahead on each arc. The boxes represent events with time stamp 11, 13, and 15; (b) distance matrix for this network of LPs. 29
Figure2.12 Computation for computing LBTS values. 31

Figure3.1 Logical view of Time Management service in HLA 36
Figure3.2 Delays among the communication of federates in HLA 42

Figure 4.1 Time Advance Request Simulation Procedure 45
Figure 4.2 Offset-Epoch method 47
Figure 4.3 Simulation program procedure diagram in HLA specification 48
Figure 4.4 TAR Benchmark program procedure diagram 50
Figure 4.5 The number of computer and execution time corresponding diagram 53
Figure 4.6 Chariot Software Testing Diagram 55
Figure 4.7 Chariot Software Testing Frame 56
Figure 4.8 TAR-TAG Service Time(1) 59
Figure 4.9 TAR-TAG Service Time(2) 60
Figure 4.10 TAR-TAG Service Time(3) 61
Figure 4.11 TAR-TAG Service Time(4) 62
Figure 4.12 TAR-TAG Service Time(5) 63

Figure5.1 Use of time-value function and precision-value function to create Real-time task model: (a) proposed real-time task model; (b) conventional hard deadline task 69
Figure 5.2 Combined hard deadline and soft deadline federations with message gateway 75




參考文獻 [ABBO88] R. Abbott and H. Garcia-Molina, “Scheduling Real-Time Transactions,” SIGMOD RECORD, vol. 17, no. 1 (March 1988), pp. 71-81.
[ABKL05] Azzedine Boukerche, and Kaiyuan Lu, A Novel Approach to Real-Time RTI based Distributed Simulation System. Proceedings of the 38th Annual Simulation Symposium (ANSS’05) IEEE.
[CLIU73] C.L. Liu and J.W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard Real Time Environment,” Journal of the ACM, vol. 20, no. 1 (January 73), pp. 4661.
[DMSO02] Defense Modeling and Simulation Office, Department of Defense, RTI 1.3 – Next Generation Programmer’s Guide Version 5, High Level Architecture, Runtime Infrastructure, Feb. 2002. http://www.dmso.mil/
[DMSO98] Defense Modeling and Simulation Office, “HLA glossary”, 5 Feb., 1998.
[DUWA03] B. Al-Duwairi and G. Manimaran, "Combined Scheduling of Hard and Soft Real-Time Tasks in Multiprocessor Systems," In Proc. of International conference on High Performance Computing (HiPC 2003), Hyderabad, India, pp.279-289, Dec. 2003.
[FISH95] Fishwick, P. A., Simulation Model Design and Execution, Prentice Hall, New Jersey, 1995.
[FUJI96-1] Fujimoto, R. M., HLA Time Management: Design Document 1.0, August 15, 1996. http://www.cc.gatech.edu/computing/pads/papers.html
[FUJI96-2] Fujimoto, R. M., Weathly, R. M., Time Management in the DoD High Level Architecture, Proceedings of the tenth workshop on Parallel and distributed simulation, Philadelphia, Pennsylvania, United States, May 22 - 24, 1996, pp. 60-67.
[FUJI98-1] R. M. Fujimoto, Time Management in The High Level Architecture, SIMULATION, 71:6, pp.388-400, December 1998.
[FUJI98-2] R.M. Fujimoto and P. Hoare, “HLA RTI Performance in High Speed LAN Environments”, In: 1998 Fall Simulation Interoperability Workshop, September, 1998.
[FUJI99] Fujimoto, R. M., Parallel and Distributed Simulation Systems, John Wiley & Sons, inc. A Wiley Interscience Publication, 1999.
[FUJI00] R.M. Fujimoto, Chapter 3. Conservative Synchronization Algorithms, Parallel and Distributed Simulation Systems, John Willy & Sons, Inc., NY, 2000.
[HLA] “High Level Architecture”, available at http://www.dmso.mil/.
[HODU01] Hodum, F., Edwards, D., Time Management Services in the RTI-NG, 2001 Fall Simulation Interoperability Workshop, Sep. 9-14, 2001, Orlando. Paper Number: 01F-SIW-090.
[IEEE00-1] IEEE Std 1516-2000, IEEE standard for modeling and simulation (M&S) High Level Architecture (HLA) - framework and rules, 2000.
[IEEE00-2] IEEE Std 1516.1-2000, IEEE Standard for Modeling and Simulation [M and S] High Level Architecture [HLA] - Federate Interface Specification, 2000.
[IEEE00-3] IEEE Std 1516.2-2000, IEEE Standard for Modeling and Simulation [M and S] High Level Architecture [HLA] - Object Model Template, 2000.
[IEEE00-4] IEEE Std 1516.3-2003, IEEE Standard for Modeling and Simulation [M and S] High Level Architecture [HLA] - Recommended Practice for High Level Architecture (HLA) Federation Development and Execution Process (FEDEP) , 2003.
[KANE96] H. Kaneko, J.A. Stankovic, S. Sen, and K. Ramamritham, “Integrated Scheduling of Multimedia and Hard Real-Time Tasks”, Proceedings of Real-Time Systems Symposium, pp. 206-217, 1996.
[KUHL00] F. Kuhl, “Creating computer simulation systems—An introduction to the high level architecture”.
[LOCK86] C.D. Locke, Best-Effort Decision Making for Real-Time Scheduling, PhD dissertation, Computer Science Department, Carnegie Mellon University, 1986.
[MOII92] H. Moiin, Scheduling Algorithms for Real-Time Systems, PhD dissertation, Department of Electrical aud Computer Engineering, University of California, Santa Barbara, 1992.
[MOII93] H. Moiin, P. M. Melliar-Smith and L. E. Moser, “Better Late Than Never”, Proceedings of the 1993 ACM conference on Computer science, Indianapolis, Indiana, United States, pp.44-51.
[MP] “Master Plan”, available at http://www.dmso.mil/dmso/docslib/mspolicy/msmp/.
[SHIH91] W.K. Shih, J.W.S. Liu and J.Y. Chung, “Algorithms for Scheduling Imprecise Computations with Timing Constraints,” SIAM Journal of Computing, vol. 20, no. 3 (June 1991), pp. 537-552.
[STEI92] Steinman, J. S., SPEEDES: A multiple-synchronization environment for parallel discrete event simulation, The International Journal for Computer Simulation, Vol. 2, No. 3, 1992, pp 251-286.
[STEI93] Steinman, J. S., Breathing Time Warp, Proceeding 7th Workshop an Parallel and Distributed Simulation, Vol. 23, No. 1, 1993, pp 109-118.
[THOM01] Thom McLean, Hard Real-Time Simulation using HLA, 01F-SIW-093.
[VARD00] Vardânega, F., Maziero, C., A generic rollback manager for optimistic HLA simulations, Fourth IEEE International Workshop on Distributed Simulation and Real-Time Applications (DS-RT 2000) Proceedings, 2000, Page(s): 79 -85.
[VARD01] Vardânega, F., Maziero, C., A generic rollback manager for optimistic HLA simulations, Simulation: Transactions of the Society for Computer Simulation International, v.18, n.2, June, 2001, pp.110 - 115.
[ZEIL00] Zeilger, B. P., Praehofer, H., Kim, T. G., Theory of Modeling and Simulation, 2nd edition, Academic Press, New York, 2000.

論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2006-06-13公開。
  • 同意授權瀏覽/列印電子全文服務,於2006-06-13起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信