Horst Mehl
Skip Abstract Section
Abstract
Although users may want to employ shared variables when they program distributed simulation applications, almost none of the currently existing distributed simulation systems does offer this facility. In this paper, we systematically present new algorithms which provide consistent shared variables for distributed simulation applications. Basically, our approach combines known techniques to realize distributed shared memory with simulation algorithms. As there are essentially two classes of distributed simulation algorithms---conservative and optimistic---we study shared variable algorithms for both of them and propose five new algorithms. Initial performance measurements of a prototype implementation are described. Potential performance degradation by the usage of shared variables is expected to depend to a high degree on the access behavior of the simulation application. Having the abstraction of shared variables available provides the user with a simple concept to design distributed simulation applications in the presence of inherent global data.
- H. E. Bal and M. F. Kaashoek. Data distribution in ORCA through compiler optimization. Technical Report IR254, University of Amsterdam, 1991.Google Scholar
- S. Bellenot. State skipping performance with the time warp operating system. Proceedings of the 6th Workshop on Parallel and Distributed Simulation (PADS92), (Newport Beach, California, January 20-22), SCS, pp. 53--61, 1992.Google Scholar
- J. B. Carter, J. K. Bennett, and W. Zwaenepoel. Implementation and performance of MUNIN. Technical Report TR91-150, Department of Computer Science, Rice University, 1991.Google ScholarDigital Library
- K. M. Chandy and J. Misra. Distributed simulation: A case study in design and verification of distributed programs. IEEE Transactions on Software Engineering SE 5:5, pp. 440--452, 1979.Google ScholarDigital Library
- D. Conklin, J. Cleary, and B. Unger. The sharks world--a study in distributed simulation design. Proceedings of the SCS Multiconference on Distributed Simulation, (San Diego, California, January I7-19), pp. 157--160, 1990.Google Scholar
- R. M. Fujimoto. Lookahead in parallel discrete event simulation. Proceedings of the International Conference on Parallel Processing, pp. 34--41, 1988.Google Scholar
- R. M. Fujimoto. The virtual time machine. University of Utah, Salt Lake City, Technical Report UUCS-88-019, 1989.Google Scholar
- R. M. Fujimoto. Parallel discrete event simulation. Communications of the ACM 33:10, pp. 30--53, 1990. Google ScholarDigital Library
- R. M. Fujimoto, J. J. Tsai, and G. C. Gopalakrishnan. Design and evaluation of the rollback chip: Special purpose hardware for time warp. Technical Report UUCS-88-011, Department of Computer Science, University of Utah, 1988.Google Scholar
- A. Gafni. Rollback mechanisms for optimistic distributed simulation systems. Proceedings of the 1988 Distributed Simulation Conference, (San Diego, California, February 3-5), SCS, pp. 61--67, 1988.Google Scholar
- B. Gates and J. Marti. An empirical study of time warp request mechanisms. Proceedings of the Distributed Simulation Conference (San Diego, California, Feb. 3-5), SCS, pp. 73--80, 1988.Google Scholar
- K. Ghosh and R. M. Fujimoto. Parallel discrete event simulation using space-time memory. International Conference on Parallel Processing, pp. III:201--208, 1991.Google Scholar
- J. B. Gilmer and J. P. Hong. Replicated state space approach for parallel simulation. Proceedings of the Winter Simulation Conference, pp. 430--434, 1986. Google ScholarDigital Library
- D. Jefferson. Virtual time. ACM Transactions on Programming Languages and Systems 7:3, pp. 404--425, 1985. Google ScholarDigital Library
- D. Jefferson. Virtual time II: Storage management in distributed simulation. Proceedings of the Annual Symposium on Principles of Distributed Computing, (Quebec, Canada, August 22-24), pp. 75--89, 1989. Google ScholarDigital Library
- D. R. Jefferson, B. Beckmann, F. Wieland, L. Blume, M. Diloreto, P. Houtalas, P. Laroche, K. Sturedevant, J. Typman, L. Van Warren, J. Wedel, H. Younger, and S. Bellenot. Distributed simulation and the time warp operating system. Proceedings of the 11th ACM Symposium on Operating Systems Principles, pp. 77--93, 1987. Google ScholarDigital Library
- D. W. Jones. Concurrent simulation: An alternative to distributed simulation. Proceedings of the Winter Simulation Conference, pp. 417--423, 1986. Google ScholarDigital Library
- D. W. Jones, C. C. Chou, D. Renk, and S. C. Bruell. Experience with concurrent simulation. Proceedings of the Winter Simulation Conference, pp. 756--764, 1989. Google ScholarDigital Library
- J. I. Leivent and R. J. Watro. Mathematical foundations for time warp systems. ACM Transactions on Programming Languages and Systems 15:5, pp. 771-794, 1993. Google ScholarDigital Library
- Y. Lin and B. Preiss. Optimal memory management for time warp parallel simulation. ACM Transactions on Modeling and Computer Simulation, 1:4, pp. 283--307, 1991. Google ScholarDigital Library
- Y. B. Lin and E. D. Lazowska. Reducing the state saving overhead for time warp parallel simulation. Technical Report 90-02-03, University of Washington, Seattle, 1990.Google Scholar
- B. Lubachevsky. Simulating colliding rigid disks in parallel using bounded lag without time warp. Proceedings of the SCS Multiconference on Distributed Simulation, (San Diego, California, January 17-19), pp. 194--202, 1990.Google Scholar
- B. Lubachevsky, A. Weiss, and A. Shwartz. An analysis of rollback-based simulation. ACM Transactions on Modeling and Computer Simulation 1:2, pp. 154--193, 1991. Google ScholarDigital Library
- B. D. Lubachevsky. Simulating billiards: Serially and in parallel. International Jounal in Computer Simulation 2:4, pp. 373--411, 1992.Google Scholar
- V. K. Madisetti, D. A. Hardaker, and R. M. Fujimoto. The MIMDIX operating system for parallel simulation. Proceedings of the 6th Workshop on Parallel and Distributed Simulation (PADS92), (Newport Beach, California, January 20-22), SCS, pp. 65--74, 1992.Google Scholar
- F. Mattern. Efficient algorithms for distributed snapshots and global virtual time approximation. Journal of Parallel and Distributed Computing 18, pp. 423--434, 1993. Google ScholarDigital Library
- H. Mehl. Breaking ties deterministically in distributed simulation schemes. Technical Report 217/91, Department of Computer Science, University of Kaiserslautern, Fed. Rep. of Germany (December), 1991.Google Scholar
- H. Mehl. Speed-up of conservative distributed discrete event simulation methods by speculative computing. Proceedings of the SCS Multiconference on Advances in Parallel and Distributed Simulation, (Anaheim, California, January 23-25), Simulation Series 23:1, Eds.: V. Madisetti, D. Nicol, R. Fujimoto, pp. 163--166, 1991.Google Scholar
- H. Mehl. Distributed shared memory: A survey. Technical Report SFB124-33/92, Department of Computer Science, University of Kaiserslautern, Fed. Rep. of Germany, 1992.Google Scholar
- H. Mehl. The distributed simulation language DSL---language description (in German). In Preparation: Technical Report, Department of Computer Science, University of Kaiserslautern, 1994.Google Scholar
- H. Mehl. Distributed simulation methods (in German). Vieweg-Verlag, Wiesbaden, Germany, 1994.Google Scholar
- H. Mehl and S. Hammes. How to integrate shared variables in distributed simulation. Technical Report SFB124-32/92, Department of Computer Science, University of Kaiserslautern, Fed. Rep. of Germany, 1992.Google Scholar
- J. Misra. Distributed discrete-event simulation. Computing Surveys 18:1, pp. 39--65, 1986. Google ScholarDigital Library
- D. M. Nicol and S. E. Riffe. A "conservative" approach to parallelizing the sharks world simulation. Proceedings of the Winter Simulation Conference, (New Orleans, Louisiana, December 9-12), pp. 186--190, 1990. Google ScholarDigital Library
- B. Nitzberg and V. Lo. Distributed shared memory: A survey of issues and algorithms. IEEE Computer, (August), pp. 52--60, 1991. Google ScholarDigital Library
- A. Prakash and R. Subramanian. An efficient optimistic distributed simulation scheme based on conditional knowledge. Proceedings of the 6th Workshop on Parallel and Distributed Simulation (PADS92), (Newport Beach, California, January 20-22), SCS, pp. 85--94, 1992.Google Scholar
- B. R. Preiss, D. I. MacIntyre, and W. M. Loucks. On the trade-off between time and space in optimistic parallel discrete-event simulation. Proceedings of the 6th Workshop on Parallel and Distributed Simulation (PADS92), (Newport Beach, California, January 20-22), SCS, pp. 33--42, 1992.Google Scholar
- P. Reiher. Private communication. 1993.Google Scholar
- P. L. Reiher, R. M. Fujimoto, S. Bellenot, and D. R. Jefferson. Cancellation strategies in optimistic execution systems. Proceedings of the SCS Multiconference on Distributed Simulation 22:1, pp. 112--121, 1990.Google Scholar
- R. Righter and J. Walrand. Distributed simulation of discrete event systems. Proceedings of the IEEE, 77:1, pp. 99--113, 1989.Google ScholarCross Ref
- L. Sokol, B. K. Stucky, and V. S. Hwang. MTW: A control mechanism for parallel discrete simulation. International Conference on Parallel Processing, pp. 250--254, 1989.Google Scholar
- L. M. Sokol, J. B. Weissman, and P. A. Mutchler. MTW: An empirical performance study. Technical Report, The MITRE Corporation, Washington AI Center, McLean VA 22102, 1990.Google Scholar
- M. Stumm and S. Zhou. Algorithms implementing distributed shared memory. IEEE Computer (May), pp. 54--64, 1990. Google ScholarDigital Library
- F. Wieland, L. Hawley, and L. Blume. An empirical study of data partitioning and replication in parallel simulation. Proceedings of the Distributed Memory Computing Conference, (Charleston, SC, April 8-12), pp. 915--921, 1990.Google ScholarCross Ref
- F. Wieland and D. Jefferson. Case studies in serial and parallel simulation. International Conference on Parallel Processing, pp. 255--258, 1989.Google Scholar
Index Terms
- How to integrate shared variables in distributed simulation
Recommendations
Efficiently unifying parallel simulation techniques
ACM-SE 44: Proceedings of the 44th annual Southeast regional conferenceThis paper introduces a unifying technique that is able to combine the advantages of synchronous, conservative and optimistic simulations. The unifying framework is based on optimistic simulation. The optimized optimistic simulation exploits synchronous ...
An Empirical Evaluation of Techniques for Parallel Discrete-Event Simulation of Interconnection Networks
PDP '96: Proceedings of the 4th Euromicro Workshop on Parallel and Distributed Processing (PDP '96)Abstract: Three parallel discrete-event simulators-synchronous, conservative and optimistic-implemented on an Intel Paragon multicomputer are comparatively evaluated. Parallelism is achieved by model decomposition, distributing the simulation among a ...
Distributed Simulation of ECATNets: A Conservative Approach
PDP '96: Proceedings of the 4th Euromicro Workshop on Parallel and Distributed Processing (PDP '96)Abstract: ECATNets (Extended Concurrent Algebraic Term Nets) are a kind of high-level algebraic net used for specifying various aspects of distributed and parallel systems. We address the problem of developing parallel simulation techniques to analyze ...
Comments