A Graph Partitioning Algorithm for Parallel Agent-Based Road Traffic Simulation

摘要

A common approach of parallelising an agent-based road traffic simulation is to partition the road network into sub- regions and assign computations for each subregion to a logical process (LP). Inter-process communication for synchronisation between the LPs is one of the major factors that affect the performance of parallel agent-based road traffic simulation in a distributed memory environment. Synchronisation overhead, i.e., the number of messages and the communication data volume exchanged between LPs, is heavily dependent on the employed road network partitioning algorithm. In this paper, we propose Neighbour-Restricting Graph-Growing (NRGG), a partitioning algorithm which tries to reduce the required communication between LPs by minimising the number of neighbouring partitions. Based on a road traffic simulation of the city of Singapore, we show that our method not only outperforms graph partitioning methods such as METIS and Buffoon, for the synchronisation protocol used, but also is more resilient than stripe spatial partitioning when partitions are cut more finely.