4th International ICST Conference on Simulation Tools and Techniques

Research Article

Heuristic Acceleration of Routing in Transportation Simulations using GPUs

Download474 downloads
  • @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
Sunil Thulasidasan1,*
  • 1: Los Alamos National Laboratory
*Contact email: sunil@lanl.gov

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.