DISTRIBUTED SIMULATION, ALGORITHMS AND PERFORMANCE ANALYSIS (LOAD BALANCING, DISTRIBUTED PROCESSING)

摘要

Simulation is one example of an application that shows great potential benefits from distributed processing. The conventional approach to simulation, that of sequentially processing the events, does not exploit the natural parallelism existing in some simulation models. This is particularly true in large models, where submodels often interact weakly and can be simulated in parallel. The decreasing cost of multiprocessor systems also suggests that a distributed approach to simulation can be workable. Moreover, such an approach can be very attractive, since time and memory limitations, often major constraints with simulation programs, may be alleviated by distributing the load among several processors.;Distributed simulation requires a set of processors that can communicate by sending messages along the links of a communication network or via a shared memory. The processors each simulate a submodel of the overall model and interact when necessary. Submodel interactions produce the interprocessor communication in the simulator.;Two methods for distributed simulation are studied in this thesis. Both methods are applicable to discrete time simulation models and are fully distributed in the sense that they require no central control. In one method, each processor can simulate independently as long as it is certain that no events will arrive that belongs to the past of the simulation process. In the second method, processors are not concerned about future arriving events. They simulate independently and roll back if an event arrives that belongs to the past.;The thesis consists of two parts. The first presents some centralized and distributed algorithms for efficient utilization of the second method. The issue of load balancing is also discussed in this part and some heuristic algorithms are presented.;The second part of the work consists of mathematical modeling and analysis of models of both methods. The analysis gives some insight into the effects of different system parameters on the performance. The performance of each method is compared with the other and also with single processor simulation. The mathematical models are then confirmed and complemented with the simulation results. Finally, results of the implementation of the second method are presented.