# An Efficient Parallelization of Microscopic Traffic Simulation
## 1 Introduction
### State of the Art  
Conventional, flow-based traffic assignment methods have been invented to determine traffic flows in larger urban road networks; see [1] for a comprehensive overview. These assignment problems could be solved with the limited computing power available during the 1960s and 1970s. The representation of individual vehicles or even pedestrians in large-scale scenarios (e.g., with thousands of vehicles and people) only became feasible with increasing computing power and memory size at the turn of the century. Different open-source projects such as TRANSIMS [2] and SUMO (Simulation of Urban MObility) [3,4] or commercial software such as VISSIM [5], AIMUSUN [6], or DRACULA [7] have been developed. Microsimulation models are typically very detailed, including lanes (with individual access-rights, speed-limits, and widths), different intersection types (priority, stop, etc. ), and traffic-light systems (TLSs) with different traffic-light logic (TLL) and different TLS control strategies. Vehicles are essentially represented by the vehicle-following model, which includes driver behavior and a lane change model [3]. The computation time for large-scale microsimulation scenarios is typically slower than real time [8]. In many applications, traffic assignments run in a loop, for example, during an activity plan generation [9] or user-equilibrium assignment [10]. If thousands of simulation runs are required, such as in AI-reinforced learning [11], then the simulation of a single run should complete in a fraction of the real time. One possibility for simulating individual vehicles at higher speeds is the use of _mesoscopic_ simulators, which use dynamic First Input, First Output (FIFO) queues as a basic edge model. FIFO queues are widely used in transportation, as these queues preserve the order in which vehicles enter and leave the queue. In contrast with microscopic simulations, mesoscopic simulations do not reproduce speed profiles because the vehicles in the queue are not coupled through vehicle following models. The mesoscopic simulation platforms MATSIM [12] or JDEQSIM are used to generate or calibrate agent-based and activity-based demand models [13]. JDEQSIM is the simulation engine of the Behavior, Energy, and Autonomy Modeling (BEAM CORE) platform [14], where agents can also change plans and routes during the simulation. JDEQSIM has parallelized some algorithms, for example, queuing-events or routing can be processed in parallel by different cores on the CPU [14]. Also, SUMO and other microsimulators have the ability to multithread for dedicated tasks; for example, the core simulation and routing [15]. However, none of the established microsimulators exploit the possibility to distribute the computational burden across thousands of GPU cores. One reason may be that it takes considerable effort to migrate from the serialized algorithms implemented for CPUs to parallel algorithms suitable for GPUs. There have been several attempts to create microsimulators for GPUs from scratch instead of migrating from an existing code base: the simulator \"Microsimulation Analysisfor Network Traffic Assignment\" (MANTA) [16; 17] was later integrated into a larger framework called Large-scale multi-GPU Parallel Computing based Regional Scale Traffic Simulation (LPSim) [18]. LPSim is a discrete time-discrete space simulator, which means that the speeds and positions of all active vehicles are updated during each simulation step, where one simulation step advances the simulation time by a regular time interval. The vehicle positions are discrete, as the lanes of the road network are subdivided into lane-cells of 1 m length, where a lane-cell corresponds to one byte on the GPU's memory. If a cell is occupied by a vehicle, then the cell-value corresponds to the speed of the respective vehicle; otherwise, it defaults to 255. This means that the space is discretized in 1 m sections and the speed is discretized in 1 m/s steps.