Performance Improvements for Large-Scale Traffic Simulation in MATSim - Computational Approaches for Urban Environments - page 212

to temporary wrong results at modules processing events, e.g., wrong traffic counts.
For this reason, the JDEQSim approach to avoid gridlock is implemented.
Besides the re-implementation and extension of DEQSim in Java, an attempt is
also made to parallelize JDEQSim, which is described in the next section.

9.3.2 Parallelization of JDEQSim

In Charypar et al. ( 2007b ), the parallelization of DEQSim is described. This is
achieved by partitioning the traffic network into several pieces, which are assigned
to separate CPUs of a shared memory machine. The message passing interface
(MPI, Snir et al. 1995 ) is used for communication between CPUs. When an agent
travels from the network area assigned to one CPU to a different one, MPI is used
for passing the agent's data between CPUs. This operation includes periodically
synchronizing the state of links at the border of each network partition.
In Java, threads are used as a basis for parallel programming (Lea 1999 ), where
such instructions which need to be executed in parallel are distributed to different
threads. In order to pass data between two threads, the synchronized keyword is
used. The advantage of the Java synchronized keyword compared to MPI in C CC is
that no explicit data structures have to be built for transferring data between threads.
This means that all data within the Java virtual machine (JVM, Lindholm and Yellin
1999 ) are accessible to all threads. But in the context of parallelizing JDEQSim,
this turns out to be a major disadvantage; whereas MPI allows to explicitly specify
which data to transfer between CPUs, it is not always obvious what data will be
exchanged due to a synchronized statement in Java. While many elements of data
transfer between threads are hidden and handled by the JVM, which simplifies
programming, this also means that the programmer has little control over them for
performance optimization.
Before describing a successful implementation of the parallelization of JDE-
QSim, two straightforward, but failed, attempts in this regard are described. This
helps to better understand the path taken and the various issues involved.

9.3.2.1 Failed Attempt 1: Single Scheduler Queue

As mentioned earlier, in Java each thread can access all data within the JVM. A
simple parallelization solution is therefore to maintain a single scheduler queue
within the JVM. The network links are assigned to different threads, e.g., using a
network partitioning algorithm as used in DEQSim, such that most collocated links
are assigned to the same thread.
In order to keep the state of the scheduler queue synchronized between threads,
each access of the queue needs to be synchronized. Unfortunately, this leads to
too many synchronizations between the threads, thus deteriorating performance. An