This article advocates the use of a formal framework for analyzing simulation performance. Simulation performance is characterized based on the three simulation development process boundaries: physical system, simulation model, and simulator implementation. First, the authors formalize simulation event ordering using partially ordered set theory. A simulator implements a simulation event ordering and incurs implementation overheads when enforcing event ordering at runtime. Second, they apply their formalism to extract and formalize the simulation event orderings of both sequential and parallel simulations. Third, they propose the relation stricter and a measure called strictness for comparing and quantifying the degree of event dependency of simulation event orderings, respectively. In contrast to the event parallelism measure, strictness is independent of time.
Fujimoto, R. M.2000. Parallel and distributed simulation systems. New York: John Wiley .
2.
Jefferson, D. A.1985. Virtual time . ACM Transactions on Programming Language System7 (3): 404-425 .
3.
Onggo, B. S. S. , and Y. M. Teo . 2002. Performance trade-off in distributed simulation . In Proceedings of the 6th IEEE International Workshop on Distributed Simulation and Real Time Applications, 77-84 . IEEE Computer Society Press.
4.
Teo, Y. M. , B. S. S. Onggo , and S. C. Tay . 2001. Effect of event orderings on memory requirement in parallel simulation . In Proceedings of the 9th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, 41-48 . IEEE Computer Society Press.
5.
Fujimoto, R. M.1990. Performance of time warp under synthetic workloads . Proceedings of SCS Multiconference on Distributed Simulation22 (1): 23-28 .
6.
Fujimoto, R. M. 1999. Exploiting temporal uncertainty in parallel and distributed simulations . In Proceedings of the 13th Workshop on Parallel and Distributed Simulation, pp. 46-53 .
7.
Zhou, S. P. , W. T. Cai , S. J. Turner , and B. S. Lee . 2002. Critical causality in distributed environment . In Proceedings of the 16th Workshop on Parallel and Distributed Simulation, pp. 53-59 .
8.
Lubachevsky, B. D.1989. Efficient distributed event-driven simulations of multiple-loop networks . Communications of the ACM32 (1): 111-123 .
9.
Turner, S. , and M. Xu. 1992. Performance evaluation of the bounded time warp algorithm . In Proceedings of the 6th Workshop on Parallel and Distributed Simulation, pp. 117-126 .
10.
Wieland, F. 1997. The threshold of event simultaneity . In Proceedings of the 11thWorkshop on Parallel and Distributed Simulation, pp. 56-59 .
11.
Culler, D. E. , J. P. Singh , and A. Gupta . 1999. Parallel computer architecture: A hardware/software approach. New York: Morgan Kaufmann .
12.
Gharachorloo, K.1995. Memory consistency models for shared-memory multiprocessors. Research Report 95/9, Western Research Laboratory .
13.
Attiya, H. , and J. Welch . 1998. Distributed computing: Fundamentals, simulations and advanced topics. New York: McGraw-Hill .
14.
Hadzilacos, V. , and S. Toueg . 1993. Fault-tolerant broadcasts and related problems. In Distributed systems, 2nd ed., edited by S. Mullender . Reading, MA: Addison-Wesley .
15.
Lamport, L.1979. How to make a multiprocessor that correctly executes multiprocess program . IEEE Transactions on Computers28 (9): 690-691 .
16.
Afek, Y. , J. Brown , and M. Merritt . 1989. A lazy cache algorithm . In Proceedings of the Symposium on Parallel Algorithms and Architectures, pp. 209-222 .
17.
Gharachorloo, K. , Gupta, A. and Hennesy, J.Two Techniques to Enhance the Performance of Memory Consistency Model . Proceedings of the International Conference on Parallel Processing, pp. 355-364 , 1991.
18.
Landin, A. , E. Hagerstein , and S. Haridi . 1991. Race-free interconnection networks and multiprocessor consistency . In Proceedings of the 18th Annual International Symposium on Computer Architecture, pp. 27-30 .
19.
Shasha, D. , and M. Snir . 1988. Efficient and correct execution of parallel programs that share memory . ACM Transactions on Programming Languages and Operating Systems10 (2): 282-312 .
20.
Berry, O. , and D. Jefferson . 1985. Critical path analysis of distributed simulation . In Proceedings of SCS Multiconference on Distributed Simulation, pp. 57-60 .
21.
Gambhire, P. , and A. D. Kshemkalyani . 2000. Evaluation of the optimal causal message ordering algorithm . In Proceedings of the High Performance Computing, LNCS no. 1970, 83-95 . New York: Springer-Verlag.
22.
Raynal, M. , A. Schiper , and S. Toueg . 1991. The causal ordering abstraction and a simple way to implement it . Information Processing Letter39 (6): 343-350 .
23.
Schiper, A. , J. Eggli , and A. Sandoz . 1989. A new algorithm to implement causal ordering . In Proceedings of the 3rd International Workshop on Distributed Algorithms, LNCS no. 392, 219-232 . New York: Springer-Verlag.
24.
Schwarz, R. , and F. Mattern . 1994. Detecting causal relationships in distributed computations: In search of the Holy Grail . Distributed Computing7 (3): 149-174 .
25.
Lamport, L.1978. Time, clocks, and the ordering of events in a distributed system . Communications of the ACM21 (7): 558-565 .
26.
Dushnik, B. , and E.W. Miller . 1941. Partially ordered sets . American Journal of Mathematics63: 600-610 .
27.
Fishburn, P. C.1988. Interval orders and circle orders . Order5: 225-234 .
28.
Chandy, K. M. , and J. Misra . 1979. Distributed simulation: A case study in design and verification of distributed Programs . IEEE Transactions on Software Engineering5 (5): 440-452 .
29.
Ronngren, R. , and M. Liljenstam . 1999. On event ordering in parallel discrete-event simulation . In Proceedings of the 13th Workshop on Parallel and Distributed Simulation, pp. 38-45 .
30.
Bain, W. L. , and D. S. Scott . 1988. An algorithm for time synchronization in distributed discrete-event simulation . In Proceedings of SCS Multiconference on Distributed Simulation19 (3): 30-33 .
31.
Teo, Y. M. , and S. C. Tay . 1994. Efficient algorithms for conservative parallel simulation of interconnection networks . In Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, 286-293 . Japan: IEEE Computer Society Press.
32.
Cai, W. , and S. J. Turner . 1990. An algorithm for distributed discrete-event simulation: The carrier null message approach . In Proceedings of the SCS Multiconference on Distributed Simulation, pp. 3-8 .
