Contact Us

Use the form on the right to contact us.

You can edit the text in this area, and change where the contact form on the right submits to, by entering edit mode using the modes on the bottom right. 

1 Create Way
Singapore, 138602
Singapore

Research project within TUM CREATE. Focussing on modelling and optimisation of architecture and infrastructure, urban systems simulation like traffic and power are the main research interests. Apart from that, a cognitive systems group deal with human computer interaction. 

Relaxation of Synchronization in Parallel Agent-based Traffic Simulation

Blog

Relaxation of Synchronization in Parallel Agent-based Traffic Simulation

Vaisagh Viswanathan

As introduced in the previous article, parallel and distributed computing is necessary to simulate the complex infrastructure of electro-mobility of a mega-city at a high level of detail in real-time. To make the parallel simulation efficient, new synchronization algorithms and load-balancing algorithms that consider the characteristics of traffic simulation are required. This article talks about one method to improve the synchronization between processes.

Generally, models and simulations are abstraction of the real world. They mimic the behavior of the simulated system, but never duplicate the simulated system. Uncertainty and error exist throughout the process of modelling and simulation; this is also true for traffic simulation. This uncertainty can originate from both error in the developed models and incomplete knowledge about the input data (Jong et al., 2007). Recall that synchronization between processes is required to maintain the correctness of the parallel simulation. However, uncertainty makes the “correctness” difficult to define, since there is no single “correct” simulation. For some experiments, the simulation needs to be run multiple times to obtain a statistically meaningful result. Therefore, it would be more accurate to say that a parallel simulation does not need to produce an identical result as the sequential simulation, but a “correct” one for the purpose of the study.  We can make use of this fact to relax the synchronization and improve performance. A similar idea of relaxing the simulation has previously been studied (Cicirelli et al., 2005).

To give an example, when the velocity and position of the vehicles near the boundary of partitions do not change much, even if synchronization is skipped for a few update cycles, it is highly likely that result of the simulation is not impacted. This can reduce the overhead of synchronization, thus reducing the total running time of the parallel simulation. An illustration of the relaxed synchronization is shown below. The processes are represented as workers at a meeting. Synchronization is represented as information exchange between the workers. If there is any information owned by a worker that is of interest to another worker, the two workers need to communicate to keep the information up to date. For example, worker Kai and Joe usually communicate with each other every 10 minutes to exchange information (10 minutes is the update cycle of the information.).  Now Kai and Joe discover that the information they are interested in does not change much in the period of 10 minutes; rather the change is only obvious every 20 minutes. Thus they decide to communicate every 20 minutes in spite of the risk of discrepancy. 

An interesting research question with regard to this relaxation of the synchronization is the criteria of measuring the correctness of the simulation. Must the exact same result be produced by the relaxed parallel simulation? Or is a certain percentage of error permissible? The answers to these questions may necessitate different statistical measures. The amount of relaxation allowed is influenced by many factors. For example, if the vehicle models are not sensitive, more relaxation can be introduced. In another example, the amount of relaxation that can be introduced differs for different traffic conditions (as explained in example above). Lastly, the parameter of interest for a simulation is also an important factor. For example, if the average trip time of vehicles is being considered, then the parallel simulation should produce a statistically equal average trip time. This topic is discussed in more detail here