Experience with concurrent simulation

ABSTRACT

We have successfully implemented a concurrent simulator and we report initial speedup measurements for this technique. Our algorithm requires a shared-memory multiprocessor and is appropriate to any discrete-event simulation model. In addition, our algorithm places no constraints on minimum service times or the presence of cycles in the simulation model. Our experimental simulator runs on an Encore Multimax computer and is applicable to closed product-form queueing networks. We have observed speedups of 2.3 for a central-server queueing model using our simulator.

REFERENCES

• 1: Bell, C. G. (1985) Multis: A New Class of Multiprocessor Computers. Science, 231, 462--467.
• 2: Brown, R. (1988) Calendar Queues: A Fast O(1) Priority Queue Implementation for the Simulation Event Set Problem. Communications of the ACM, 31, 1220--1227.
• 3: Bruell, S. C., Balbo, G., Ghanta S., and Afshari, P. V. (1984) A Mean Value Analysis Based Package for the Solution of Product-Form Queueing Network Models. International Conference on Modelling Techniques and Tools for Performance Analysis, Paris, France.
• 4: Chandy, K. M., and Misra J. (1979) Distributed Simulation: Case Study. IEEE Transactions on Software Engineering, SE-5, 440--452.
• 5: Chandy, K. M., and Misra J. (1981) Asynchronous Distributed Simulation via a Sequence of Parallel Computations. Communications of the ACM, 24, 198--206.
• 6: Jefferson, D. R. (1985) Virtual Time. ACM Transactions on Programming Languages and Systems, 7, 404--425.
• 7: Jones, D. W. (1986a) An Empirical Comparison of Priority-Queue and Event-Set Implementations. Communications of the ACM, 29, 300--311.
• 8: Jones, D. W. (1986b) Concurrent Simulation: An Alternative to Distributed Simulation. Proceedings of the 1986 Winter Simulation Conference, Arlington, Virginia, 417--423.
• 9: Jones, D. W., Henriksen, J. O., Pegden, C. D., et al. (1986) Implementations of Time (Panel). Proceedings of the 1986 Winter Simulation Conference, Arlington, Virginia 409--416.
• 10: Jones, D. W. (1989) Concurrent Operations on Priority Queues. Communications of the ACM, 32, 132--137.
• 11: Kingston, J. H. (1984) Analysis of Algorithms for the Simulation Event List. PhD Thesis, Basser Department of Computer Science, University of Sydney.
• 12: Kingston, J. H. (1985) Analysis of Tree Algorithms for the Simulation Event List. Acta Informatica, 22, 15--33.
• 13: Lubachevsky, B. D. (1988) Efficient Distributed Event-driven Simulations of Multiple-loop Networks. Proceeding of the 1988 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, 12--21.
• 14: Misra, J. (1986) Distributed Discrete-event Simulation, Computing Surveys, 18, 39--65.
• 15: Overstreet, C. M. (1982) Model Specification and Analysis for Discrete Event Simulation. PhD Thesis, Computer Science Department, Virginia Polytechnic Institute, Blacksburg, Virginia.
• 16: Overstreet, C. M. (1986) World View Based Discrete Event Model Simplification. Modelling and Simulation Methodology in the Artificial Intelligence Era. North Holland, Amsterdam.
• 17: Peacock, J. K., Wong, J. W., and Manning, E. G. (1979a) Distributed Simulation Using a Network of Processors. Computer Networks, 3, 44--56.
• 18: Peacock, J. K., Wong, J. W., and Manning, E. G. (1979b) A Distributed Approach to Queueing Network Simulation. 1979 Winter Simulation Conference, IEEE, 399--406.
• 19: Peacock, J. K., Wong, J. W. and Manning, E. G. (1979c) A Distributed Approach to Queueing Network Simulation. Proceedings 4th Berkeley Conference on Distributed Data Management and Computer Networks, Berkeley, CA, 237--259.
• 20: Rao, V. N., and Kumar, V. (1988) Concurrent Access of Priority Queues. IEEE Transactions on Computers, 37, 1657--1665.
• 21: Reed, D. A., Malony, A. D., and McCredie, B. D. (1988) Parallel Discrete Event Simulation Using Shared Memory. IEEE Transactions on Software Engineering, 14, 541--553.
• 22: Sauer, C. H., and Chandy K. M. (1981) Computer Systems Performance Modelling. Prentice-Hall, Englewood Cliffs, NJ.
• 23: Wagner, D. B., Lazowska, E. D., and Bershad, B. N. (1988) Techniques for Efficient Shared-Memory Parallel Simulation. Technical Report 88-04-05, Department of Computer Science, University of Washington, Seattle.
• 24: Wagner, D. B., and Lazowska, E. D., (1988) Parallel Simulation of Queueing Networks: Limitations and Potentials. Technical Report 88-09-05, Department of Computer Science, University of Washington, Seattle.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Abstract data types

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory
          Subjects: Types of simulation (continuous and discrete)*

General Terms:
Algorithms, Design, Performance