|
||||||||||||||||
|
Ph.D. ThesesPerformance Optimization of Parallel Discrete Event Simulation of Spatially Explicit Problems
By Ewa Deelman
The research presented in this thesis describes the simulation of spatially explicit problems using Parallel Discrete Event Simulation (PDES) with an optimistic protocol. Spatially explicit problems are characterized by continuous space in which objects reside and move freely. The space is heterogenous and the interactions between objects are frequent and localized. The space is discretized and partitioned among processes, each simulating an area of space. From the point of view of the parallel simulation processes, communications are frequent and take place between nearest-neighbors. These problem characteristics have an impact on three areas of Parallel Discrete Event Simulation: the Global Virtual Time (GVT) calculation overhead, the performance cost incurred by rollbacks, and load balance. Improvements are proposed for each of these performance issues. The bottleneck in PDES is memory. Since the simulation uses large amounts of memory, the GVT is used to synchronize processes and discard obsolete system information. In this work a new algorithm, the Continuously Monitored Global Virtual Time (CMGVT) is presented. Unlike other GVT algorithms, the CMGVT allows processes to calculate the GVT based on the local information constantly available to each process. System information, such as the Local Virtual Time of each process and information about messages in transit, is appended to simulation messages. Three variants of the CMGVT algorithm with progressively increasing overhead are described and their performance is compared. To address the issue of rollback overhead, a novel approach to rollback processing which limits the number of events rolled back as a result of a straggler or antimessage is described. The method, called Breadth-First Rollback (BFR), is suitable for spatially explicit problems where the space is discretized and distributed among processes and simulation objects move freely in the space. BFR uses incremental state saving, allowing the recovery of causal relationships between events during rollback. These relationships are then used to determine which events need to be rolled back. A dynamic load balancing algorithm based on the BFR processing method is described. Load predictions are determined based on the future events that are scheduled for a given Logical Process (LP). The information about the load of the processes is gathered and distributed during the Global Virtual Time calculation. Each LP calculates the new load distribution of the system. The load is balanced by moving spatial data between neighboring LPs in one round of communications. In the class of problems investigated in this thesis, the LPs can be described as being elements of a ring from the point of view of communication. Under these assumption, an algorithm that balances the load in a ring and achieves the smallest possible maximum after-balance load is presented.
|
||||||||||||||||
Research
