Reducing Synchronization Overhead with Computation Replication in Parallel Agent-Based Road Traffic Simulation

摘要

Road traffic simulation is a useful tool for studying road traffic and evaluating solutions to traffic problems. Large-scale agent-based road traffic simulation is computationally intensive, which triggers the need for conducting parallel simulation. This paper deals with the synchronization problem in parallel agent-based road traffic simulation to reduce the overall simulation execution time. We aim to reduce synchronization operations by introducing some redundant computation to the simulation. There is a trade-off between the benefit of reduced synchronization operations and the overhead of redundant computation. The challenge is to minimize the total overhead of redundant computation and synchronization. First, to determine the amount of redundant computation, we proposed a way to define extended layers of partitions in the road network. The sizes of extended layers are determined by the behavior of agents and the topology of road networks. Second, due to the dynamic nature of road traffic, a heuristic was proposed to adjust the amount of redundant computation according to traffic conditions during simulation run-time to minimize the overall simulation execution time. The efficiency of the proposed method was investigated in a parallel agent-based road traffic simulator using real-world network and trip data. Results have shown that the method can reduce synchronization overhead and improve the overall performance of the parallel simulation significantly.