Highlights A data-parallel multiple source shortest path algorithm is proposed. Achieves high performance for sparse graphs when executed on many-core processors. The algorithm is implemented in SATURN for macroscopic road network assignment. The assignment application run-time is reduced by a factor of 7.8 for a 5194 zone network.

    Abstract The performance and scalability of macroscopic assignment and simulation software limits the quantity, scale and complexity of simulations of transport networks that are used to aid the planning, design and operation of transport systems. Through the application of many-core processing architectures (such as Graphics Processing Units (GPUs)) and data-parallel algorithms, the performance of such software can be dramatically increased. In this paper, a work-efficient, Multiple Source Shortest Path (MSSP) implementation of the Bellman-Ford algorithm is proposed to dramatically increase the performance of shortest path calculations for low-density high-diameter graphs, which are characteristic of transportation networks. This is achieved through the use of an Origin-Vertex Frontier to increase the level of parallelism within the shortest path algorithm for multiple source vertices in low-density graphs, when executed on GPUs. The algorithm is implemented within the SATURN transport simulation software and benchmarked on a range of real-world transportation networks. Our algorithm improves hardware utilisation of massively-parallel GPUs; demonstrating performance improvements of up to 7.8 x over a multi-core CPU (Central Processing Unit) implementation.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A data-parallel many-source shortest-path algorithm to accelerate macroscopic transport network assignment


    Beteiligte:
    Heywood, Peter (Autor:in) / Maddock, Steve (Autor:in) / Bradley, Richard (Autor:in) / Swain, David (Autor:in) / Wright, Ian (Autor:in) / Mawson, Mark (Autor:in) / Fletcher, Graham (Autor:in) / Guichard, Roland (Autor:in) / Himlin, Roger (Autor:in) / Richmond, Paul (Autor:in)


    Erscheinungsdatum :

    2019-05-16


    Format / Umfang :

    16 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Parallel All-Pairs Shortest Path Algorithm: Network Decomposition Approach

    Abdelghany, Khaled / Hashemi, Hossein / Alnawaiseh, Ala | Transportation Research Record | 2016


    Based on Transcad of the Shortest Path Assignment Method

    Li, Qing Yin ;Tang, Rui ;Tan, Zhang Lu | Trans Tech Publications | 2011


    Traffic assignment by shortest path method using TD factor

    Benesh, A.H. | Engineering Index Backfile | 1967


    Real World Applications Using Parallel Computing Techniques in Dynamic Traffic Assignment and Shortest Path Search

    Attanasi, Alessandro / Silvestri, Edmondo / Meschini, Pietro et al. | IEEE | 2015


    Network Model of the Shortest Path Selection in Transport

    Dramski, M. / Maka, M. / Uchacz, W. | British Library Conference Proceedings | 2014