Research Article
Heuristic Acceleration of Routing in Transportation Simulations using GPUs
@INPROCEEDINGS{10.4108/icst.simutools.2011.245589, author={Sunil Thulasidasan}, title={Heuristic Acceleration of Routing in Transportation Simulations using GPUs}, proceedings={4th International ICST Conference on Simulation Tools and Techniques}, publisher={ICST}, proceedings_a={SIMUTOOLS}, year={2012}, month={4}, keywords={Traffic Simulation GPU Path Computation}, doi={10.4108/icst.simutools.2011.245589} }
- Sunil Thulasidasan
Year: 2012
Heuristic Acceleration of Routing in Transportation Simulations using GPUs
SIMUTOOLS
ICST
DOI: 10.4108/icst.simutools.2011.245589
Abstract
We present a brief overview of how path computations for real-world road network graphs can be speeded up using GPUs, in the context of a large scale transportation simulator. This is motivated by the following observations: (i) Routing is the most computationally intensive part of a large scale transportation simulator, and thus, optimizations to routing that exploit any inherent structure and parallelism in the problem significantly improve application performance; (ii) near-optimal paths are often acceptable in lieu of the most optimal path, which motivates the use of heuristics in speeding up path computations; and finally, (iii) paths from source to destination in real-world road network graphs are spatially constrained, implying that to solve the path problem, one needs to consider only a small subset of the routing graph. This has important practical implications for a GPU, which, while offering a great degree of parallelism, is also significantly constrained by memory limitations. GPUs have already been shown to significantly outperform CPUs in path computation problems for small graphs. The previous observations allow us to deploy GPUs for much larger graphs that arise in transportation simulations.