As mentioned above, micro-simulation of traffic, that is, the individual simulation of each vehicle, has been done for quite some time (e.g. [16]). A prominent example is NETSIM [14, 32], which was developed in the 70s. Newer models are, e.g., the Wiedemann-model [45], AIMSUN [15], INTEGRATION [31], MITSIM [12], HUTSIM [20], or VISSIM [44].
NETSIM was even tried on a vector supercomputer [22], without a real break-through in computing speeds. But, as pointed out earlier, ultimately the inherent structure of agent-based micro-simulation is at odds with the computer architecture of vector supercomputers, and so not much progress was made on the supercomputing end of micro-simulations until the parallel supercomputers became available. One should note that the programming model behind so-called Single Instruction Multiple Data (SIMD) parallel computers is very similar to the one of vector supercomputers and thus also problematic for agent-based simulations. In this paper, when we talk about parallel computers, we mean in all cases Multiple Instruction Multiple Data (MIMD) machines.
Early use of parallel computing in the transportation community includes parallelization of fluid-dynamical models for traffic [9] and parallelization of assignment models [17]. Early implementations of parallel micro-simulations can be found in [8, 28, 1].
It is usually easier to make an efficient parallel implementation from scratch than to port existing codes to a parallel computer. Maybe for that reason, early traffic agent-based traffic micro-simulations which used parallel computers were completely new designs and implementations [6, 42, 1, 28]. All of these use domain decomposition as their parallelization strategy, which means that the partition the network graph into domains of approximately equal size, and then each CPU of the parallel computer is responsible for one of these domains. It is maybe no surprise that the first three use, at least in their initial implementation, some cellular structure of their road representation, since this simplifies domain decomposition, as will be seen later. Besides the large body of work in the physics community (e.g. [46]), such ``cellular'' models also have some tradition in the transportation community [16, 10].
Note that domain decomposition is rather different from a functional parallel decomposition, as for example done by DYNAMIT/MITSIM [12]. A functional decomposition means that different modules can run on different computers. For example, the micro-simulation could run on one computer, while an on-line routing module could run on another computer. While the functional decomposition is somewhat easier to implement and also is less demanding on the hardware to be efficient, it also poses a severe limitation on the achievable speed-up. With functional decomposition, the maximally achievable speed-up is the number of functional modules one can compute simultaneously - for example micro-simulation, router, demand generation, ITS logic computation, etc. Under normal circumstances, one probably does not have more than a handful of these functional modules that can truly benefit from parallel execution, restricting the speed-up to five or less. In contrast, as we will see the domain decomposition can, on certain hardware, achieve a more than 100-fold increase in computational speed.
In the meantime, some of the ``pre-existing'' micro-simulations are
ported to parallel computers. For example, this has recently been
done for AIMSUN2 [2] and for DYNEMO [38, 29],
and a parallelization is planned for
VISSIM [44] (M. Fellendorf, personal communication).