根據美國國防部一九九五年十月頒佈的『模式與模擬發展計劃』內容所述，其計劃之首要目標乃為模式與模擬建構出一套完整的高階模擬架構(High Level Architecture, HLA)，此架構將成為美軍上下一貫之標準並廣泛運用於各類不同功能之軍事系統中。該技術架構之主要目的在於達成不同的模擬系統間之交流互動，並且提昇模擬系統和軟體元件之可重複使用率。而分散式模擬系統的各類需求是相當多元化的，HLA 可以提供較為一般性的骨幹架構以促成模擬系統的完整互動。
在真實世界中，軍事衝突是沿著一條時序(Time Line)來依序發生，因此在電腦兵棋的推演當中必須有效的模擬出相同的軍事衝突時序。而推演運行的方式就是指於推演中模擬真實世界時序的前進方式，推演所經過的時間必須精確地模擬，並確保物理法則以及推演之完整性/真實性。每一個演習訓練均有其推演模擬的起始日期與時間，電腦兵棋系統的推演方式通常使用連續式計時，必要時可以配合步階式計時以調快戰演比。因此在分散式模擬架構下的電腦兵棋系統，必須也能夠很精確的讓事件在正確的時序發生，並且要達到同步模擬的狀態。舉個例子：模擬演訓中，一連串的命令並不一定是依照執行先後順序下達的，所以，在分散環境下必須要確保較早時序的命令不會被忽略而時序較晚的命令反而先被執行，亦即必須保持正確之因果關係。而這些時序控制可以在兩種層面上實現，一個是在作業系統層面，稱為執行基礎(Run-Time Infrastructure – RTI) ，另一種是在應用程式的層面，稱為federate。
本論文所欲探討的即時時間管理服務即從此兩個層面來研究，也就是說，從執行基礎(RTI)的角度來研究如何設計即時時間管理模組，來改良現有之執行基礎(RTI)軟體的設計方式；另一個研究方向就是從federate角度來探討如何在現有執行基礎(RTI)軟體的限制下，提出federate的設計方式與運作規範以達即時性需求。
因此本論文所研究的議題為:
z 設計符合即時性需求的HLA Time Management 機制，以及滿足deadline 條件的LBTS
計算公式與演算法。
z 研究real-time 系統與lookahead 值之間的關係，以及探討降低「網路延遲」因素的
lookahead 值設定方式。
z 藉由實驗來提出對於不同網路環境、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:
z Design the LBTS equation and algorithm that could satisfy the hard deadline requirement.
z Research the relationship between real-time system and lookahead value.
z 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.