Distributed simulation using hierarchical rollback

ABSTRACT

As the complexity of computer and communication systems increases, it becomes increasingly difficult to construct and evaluate models of these systems which can be used to study their performance under varying conditions. A modeling technique which is once again gaining in popularity due to its generality and ability to represent systems in varying degrees of detail is discrete event simulation.Constructing a simulation model of a real or proposed system is well understood and many tools are available. The major problem which arises is model evaluation. Due to the complexity and level of detail in a simulation model, it may require an excessive amount of time and computer resources to perform the evaluation. There is an area of current research, though, which is addressing these performance problems: distributed simulation.Distributed simulation has the potential to reduce the often lengthy run-time required for complex discrete event simulation by using multiple, cooperating processors instead of a single processor for model execution. Also, the computer resource requirements can more easily be satisfied by spreading the demand across a set of processors rather than depending on a single processor to furnish the required resources.In this paper a new technique for distributed simulation called hierarchical rollback is presented. Hierarchical rollback employs multiple processors for the evaluation of a single simulation model. Synchronization and coordination of the processors is based on a unique checkpoint/rollback mechanism. It will be shown how hierarchical rollback can be used to execute a hierarchical simulation model on a distributed set of processors.

REFERENCES

• 1: Chandy, K. M. and Misra, J. (1979), Distributed Simulation: A Case Study in Design and Verification of Distributed Programs, IEEE Transactions on Software Engineering, Vol. SE-5, No. 5, 440--452.
• 2: Chandy, K. M. and Misra, J. (1981), Asynchronous Distributed Simulation via a Sequence of Parallel Computations, Communications of the ACM, Vol. 24, No. 4, 198--205.
• 3: Gimarc, R. L. and Chandy, K. M. (1985), HSS: A Tool for Evaluating the Performance of Office Systems, Proceedings of the Computer Measurement Group International Conference.
• 4: Jefferson, D. (1985), Virtual Time, ACM Transactions on Programming Languages and Systems, Vol. 7, No. 3, 404--425.
• 5: Misra, J. (1986), Distributed Discrete-Event Simulation, ACM Computing Surveys, Vol. 18, No. 1, 39--65.
• 6: Peacock, J. K., Wong, J. W., and Manning, E. (1980), Distributed Simulation Using a Network of Processors, Computer Networks, Vol. 3, No. 1, 44--56.
• 7: Wirth, N. (1971), Program Development by Stepwise Refinement, Communications of the ACM, Vol. 14, No. 4.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

General Terms:
Algorithms, Design, Management, Performance