New synchronization algorithms to improve the efficiency of large-scale high-fidelity traffic simulations in the cloud
Modeling and Simulation will play a key role in understanding and preparing for a large scale transition to electro-mobility. Road traffic models are made up of driver-vehicle-units (DVUs) that have certain driving behaviors and internal vehicle models. Calculating the movement of hundreds of thousands of these DVUs at a reasonable speed and fidelity requires significant computational resources. Is it even possible to simulate such complex infrastructure of a mega-city at a high level of detail in real-time? At the scale of a mega-city, parallel and distributed computing is necessary. However, new algorithms which incorporate the specific characteristics of road traffic need to be designed.
As is well-known in the parallel and distributed computing community, to improve the speed of a program is not simply a matter of adding more processors; this is because parallel computing comes with a price. For example, there is an overhead in distributing the work load to processes, and managing the data of processes. In parallel agent-based traffic simulation, the road network is usually decomposed into multiple sub-regions (Nagel &Rickert, 2001; Cameron & Duncan, 1996; Barcelo et al., 1998 ). A sub-region is a collection of road segments. Processes execute the agent models contained by each sub-region. Each process is usually assigned to a different physical processing unit.
Due to the interaction of agents, there are usually data read and write dependencies between processes. A process should not progress its part of the simulation over the simulation time when there are read or write dependencies until synchronization is performed by the processes that need to exchange data. Processors incur communication costs during synchronization. Conventionally, agent-based simulations use global barriers to synchronize processes. Global barriers block all processes from execution periodically; processes exchange messages during this time. However, this is inefficient as all processes need to wait at the global barriers. Depending on the ratio between the computational load and the speed of message passing between processes, the overhead of barriers can be so significant that the simulation itself slows down! Thus, more efficient synchronization algorithms need to be designed for agent-based traffic simulation.
In order to handle these issues more efficiently, we developed a new synchronization protocol which takes advantage of the characteristics of agent-based traffic simulation. We use a peer-to-peer synchronization approach. A process negotiates the time of synchronization with the other processes that require synchronization. Synchronization events are scheduled as mutually agreed appointments; communication only happens between those peers. These remove the global barrier and reduce the communication overhead mentioned previously. The processes communicate through exchanging messages, therefore, the processes can run on supercomputers or even the cloud. An illustration of the process is shown in the figure below.
Each individual workers at the table corresponds to a process. With the global barrier method, all workers periodically talk or communicate with other relevant workers; this results in unnecessary waiting. With the mutual appointment strategy, workers negotiate with relevant workers when they should perform the next talk or communication. Only point-to-point communication is required; irrelevant workers do not have to wait during communication. Experiments have shown that this approach is able to produce an improvement of up to 10 percent.
We have also developed and utilized other parallel and distributed computing techniques to reduce the number of interacting processes during synchronization and the frequency of synchronization. For more details please refer to the paper. More details on the other techniques used and the real world validation experiments carried out will be discussed in subsequent blog posts.