Utilising innovative partitioning algorithms to parallelise large-scale microscopic and nanoscopic road traffic.
Microscopic and nanoscopic traffic simulations abstract road traffic at a very high level of detail. They help to analyse how the behaviour of individual drivers and vehicles affect traffic as a whole. Simulating a megacity with millions of driver-vehicle-units at a reasonable speed requires a lot of computational resources. We can use parallel computing techniques to allow traffic simulations to leverage on more computational resources such as compute clusters or supercomputers.
As is well-known in the parallel and distributed computing community, adding more processors does not always improve the speed of a program. This is due to the inherent parallelism of the simulated system and parallelization overhead. In parallel agent-based traffic simulation, the road network is usually decomposed into multiple sub-regions. The agent models contained by each sub-region are executed by Logical Processes (LPs). The LPs are usually assigned to different physical processing units. Due to the interaction of agents, there are usually data read and write dependencies between LPs. An LP should not progress the simulation over the point in the simulation when a read or write dependency occurs until the dependency is fulfilled by the messages exchanged between the LPs. Due to the dependencies between LPs, the whole simulation can only progress as fast as the slowest LP. Thus, distributing the computational workload to LPs evenly plays an important role in the efficiency of the parallel simulation.
There is a large amount of existing work on partitioning and load balancing. The most straightforward way of partitioning is to cut the road network into stripes or grids with equal sizes (Lee & Chandrasekar, 2010). Also, recursive coordinate bisection (RCB) can also be used which recursively cuts the road network into two equal halves (Berger & Bokhari, 1987). However, these methods ignore another essential factor that influences the efficiency of parallelisation: synchronisation. Partitioning into stripes and grids and RCB may incur high synchronisation overhead.
Another approach of partitioning that considers the minimisation of synchronisation overhead is graph partitioning (Karypis & Kumar, 1998). However, the objective of the minimisation is only on the data volume of the communication. This is insufficient since data volume is not an accurate indicator for the total synchronisation overhead for parallel applications. The number of messages is also critical. Even with the same amount of data, there is more overhead if the data is sent as a larger number of smaller messages.
An example of the Singapore road network being partitioned into 16 partitions is shown below with RCB (left) and graph partitioning (right). Different colors denote different partitions. The figure demonstrates the irregular shapes generated by different graph partitioning agorithms. The irregular shapes do not promise a good optimisation on the number of synchronisation messages.
Another factor that needs to be considered is the load balancing that needs to be performed dynamically during the simulation run. This needs to be done because the workload in the road network changes dynamically. This in turn implies that the run-time dynamics of the workload should be considered. Thus, load balancing is challenging since there are mutiple objectives to be optimised at the same time.
We are developing an innovative partitioning algorithm that performs dynamic load-balancing for parallel agent-based traffic simulation and at the same time minimises synchronisation overhead. When we say minimising synchronisation overheads, we not only minimise the total data volume sent during communication but also the number of synchronisation messages. Traffic density and flow are tracked during the simulation. They are used to guide the partitioning to balance the work load of LPs and minimise the data volume. Furthermore, the topology and geographical information of the road network is used to minimise the number of messages.