|
ABSTRACT
Traditional discrete-event simulations employ an inherently sequential algorithm. In practice, simulations of large systems are limited by this sequentiality, because only a modest number of events can be simulated. Distributed discrete-event simulation (carried out on a network of processors with asynchronous message-communicating capabilities) is proposed as an alternative; it may provide better performance by partitioning the simulation among the component processors. The basic distributed simulation scheme, which uses time encoding, is described. Its major shortcoming is a possibility of deadlock. Several techniques for deadlock avoidance and deadlock detection are suggested. The focus of this work is on the theory of distributed discrete-event simulation.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
| |
2
|
BEZIVIN, J., AND IMBERT, H. 1983. Adapting a simulation language to a distributed environment. In Proceedings of the 3rd International Conference on Distributed Computing Systems (Ft. Lauderdale, Fla.), IEEE, New York, pp. 596-603.
|
| |
3
|
|
| |
4
|
|
| |
5
|
|
| |
6
|
CHANDY, K. M., AND MISRA, J. 1979. Distributed simulation: A case study in design and verification of distributed programs. IEEE Trans. Softw. Eng. SE-5, 5, 440-452.
|
 |
7
|
|
 |
8
|
|
| |
9
|
CHANDY, K. M., MISRA, J., ANO HOLMES, V. 1979. Distributed simulation of networks. Comput. Netw. 3, 105-113.
|
 |
10
|
|
| |
11
|
CHRISTOPHER, T., EVENS, M., GARGEYA, R. R., AND LEONHARDT, T. 1983. Structure of a distributed simulation system. In Proceedings of the 3rd International Conference on Distributed Computing Systems (Ft. Lauderdale, Fla.). IEEE, New York, pp. 584-589.
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
| |
15
|
|
 |
16
|
|
| |
17
|
KUMAR, D. 1986. Ph.D dissertation (in preparation). Computer Science Dept., Univ. Texas at Austin, Austin, Tex.
|
| |
18
|
|
| |
19
|
|
 |
20
|
|
| |
21
|
PEACOCK, J. K., WONG, J. W., AND MANNING, E. G. 1979a. Distributed simulation using a network of processors. Comput. Netw. 3, 1, 44-56.
|
| |
22
|
J. Kent Peacock , J. W. Wong , Eric Manning, A distributed approach to queueing network simulation, Proceedings of the 11th conference on Winter simulation, p.399-406, December 03-05, 1979, San Diego, CA, United States
|
| |
23
|
QUINLIVAN, B. 1981. Deadlock resolution in distributed simulation. Master's thesis, Computer Science Dept., Univ. Texas at Austin, Austin, Tex.
|
 |
24
|
|
| |
25
|
SEETHALAKSHMI, M. 1979. A study and analysis of performance of distributed simulation. Master's thesis, Computer Science Dept., Univ. of Texas at Austin, Austin, Tex.
|
| |
26
|
U.S. DOD 1982. Reference Manual for the ADA Programming Language. U.S. Department of Defense.
|
CITED BY 195
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rajive Bagrodia , Zheng Li , Vikas Jha , Yuan Chen , Jason Cong, Parallel logic level simulation of VLSI circuits, Proceedings of the 26th conference on Winter simulation, p.1354-1361, December 11-14, 1994, Orlando, Florida, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Karim Djemame , Mohamed Bettaz , Dennis C. Gilles , Lewis M. Mackenzie, Performance comparison of high-level algebraic nets distributed simulation protocols, Proceedings of the 28th conference on Winter simulation, p.621-628, December 08-11, 1996, Coronado, California, United States
|
|
|
|
|
|
|
|
|
Albert G. Greenberg , Boris D. Lubachevsky , Isi Mitrani, Unboundedly parallel simulations via recurrence relations for network and reliability problems, Proceedings of the 22nd conference on Winter simulation, p.731-733, December 09-12, 1990, New Orleans, Louisiana, United States
|
|
|
|
|
|
Steven K. Reinhardt , Mark D. Hill , James R. Larus , Alvin R. Lebeck , James C. Lewis , David A. Wood, The Wisconsin Wind Tunnel: virtual prototyping of parallel computers, ACM SIGMETRICS Performance Evaluation Review, v.21 n.1, p.48-60, June 1993
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sibabrata Ray , Hong Jiang , Jitender S. Deogun, A parallel algorithm for mapping a special class of task graphs onto linear array multiprocessors, Proceedings of the 1994 ACM symposium on Applied computing, p.473-477, March 06-08, 1994, Phoenix, Arizona, United States
|
|
|
Bruno R. Preiss , Wayne M. Loucks , V. Carl Hamacher, A unified modeling methodology for performance evaluation of distributed discrete event simulation mechanisms, Proceedings of the 20th conference on Winter simulation, p.315-324, December 12-14, 1988, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D. Jefferson , B. Beckman , L. Blume , M. Diloreto , P. Hontalas , P. Reiher , K. Sturdevant , J. Tupman , J. Wedel , F. Wieland , H. Younger, The status of the time warp operating system, Proceedings of the third conference on Hypercube concurrent computers and applications: Architecture, software, computer systems, and general issues, p.738-744, January 19-20, 1988, Pasadena, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Lokesh Bajaj , Rajive Bargrodia , Richard Meyer, Case study: parallelizing a sequential simulation model, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.29-36, May 01-04, 1999, Atlanta, Georgia, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Winston W. Liu , Ching-Chuan Chiang , Hsiao-Kuang Wu , Vikas Jha , Mario Gerla , Rajive L. Bagrodia, Parallel simulation environment for mobile wireless networks, Proceedings of the 28th conference on Winter simulation, p.605-612, December 08-11, 1996, Coronado, California, United States
|
|
|
|
|
|
|
|
|
Christopher D. Carothers , Yi-Bing Lin , Richard M. Fujimoto, Simulating population dependent PCS network models using time warp, Proceedings of the 27th conference on Winter simulation, p.555-562, December 03-06, 1995, Arlington, Virginia, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Enver Yücesan , Chun Hung Chen , Insup Lee, Web-based simulation experiments, Proceedings of the 30th conference on Winter simulation, p.1649-1654, December 13-16, 1998, Washington, D.C., United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Lisa M. Sokol , Jon B. Weissman , Paula A. Mutchler, MTW: an empirical performance study, Proceedings of the 23rd conference on Winter simulation, p.557-563, December 08-11, 1991, Phoenix, Arizona, United States
|
|
|
|
|
|
Felipe Knop , Edward Mascarenhas , Vernon Rego , V. S. Sunderam, An introduction to fault tolerant parallel simulation with EcliPSe, Proceedings of the 26th conference on Winter simulation, p.700-707, December 11-14, 1994, Orlando, Florida, United States
|
|
|
Dhananjai Madhava Rao , Narayanan V. Thondugulam , Radharamanan Radhakrishnan , Philip A. Wilsey, Unsynchronized parallel discrete event simulation, Proceedings of the 30th conference on Winter simulation, p.1563-1570, December 13-16, 1998, Washington, D.C., United States
|
|
|
|
|
|
|
|
|
Dale E. Martin , Radharamanan Radhakrishnan , Dhananjai M. Rao , Malolan Chetlur , Krishnan Subramani , Philip A. Wilsey, Analysis and simulation of mixed-technology VLSI Systems, Journal of Parallel and Distributed Computing, v.62 n.3, p.468-493, March 2002
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Vijay Balakrishnan , Peter Frey , Nael B. Abu-Ghazaleh , Philip A. Wilsey, A framework for performance analysis of parallel discrete event simulators, Proceedings of the 29th conference on Winter simulation, p.429-436, December 07-10, 1997, Atlanta, Georgia, United States
|
|
|
Meng-Lin Yu , Sumit Ghosh , Erik DeBenedictis, A provably correct, non-deadlocking parallel event simulation algorithm, Proceedings of the 24th annual symposium on Simulation, p.100-111, April 1991, New Orleans, Louisiana, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Vijay A. Saraswat , Kenneth Kahn , David Weinbaum, Detecting stable properties of networks in concurrent logic programming languages, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.210-222, August 15-17, 1988, Toronto, Ontario, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rajive Bagrodia , Richard Meyer , Mineo Takai , Yu-an Chen , Xiang Zeng , Jay Martin , Ha Yoon Song, Parsec: A Parallel Simulation Environment for Complex Systems, Computer, v.31 n.10, p.77-85, October 1998
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Cássio M. M. Pereira , Daniel C. Lobato , César A. C. Teixeira , Maria G. Pimentel, Achieving causal and total ordering in publish/subscribe middleware with DSM, Proceedings of the 3rd workshop on Middleware for service oriented computing, p.61-66, December 01-05, 2008, Leuven, Belgium
|
|
|
Milind Kulkarni , Martin Burtscher , Rajeshkar Inkulu , Keshav Pingali , Calin Casçaval, How much parallelism is there in irregular applications?, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
REVIEW
"Osman Balci : Reviewer"
This paper introduces some basic concepts of distributed simulation and
discusses several techniques for deadlock avoidance and deadlock detection.
The paper starts with an overview of system simulation. The introduction to the
basic
more...
|