Research on Parallel Yen Algorithms on GPUs Using CUDA

Jian Fu Li

doi:10.4028/www.scientific.net/AMM.519-520.90

Paper Titles

Research on PPHIIS Based on Ontology Model
p.66

Online Data Compression Technique for Real Time Data of Energy Management System in the Industrial Production
p.70

Time Synchronization Method for Parallel Traffic Simulation Framework
p.77

Comparison of Parallel Computing Methods for Fast Cone-Beam Reconstruction with Similar Optimization Strategies
p.85

Research on Parallel Yen Algorithms on GPUs Using CUDA
p.90

Parallelization Analysis of Dissolved Gases in Transformer Oil Based on Random Forest Algorithm
p.98

GPU Accelerated Reconstruction in Compton Scattering Tomography Using Matrix Compression
p.102

Parallel Scheduling Algorithms Investigation of Support Strict Resource Reservation from Grid
p.108

A Dynamic Back-Off Algorithm in Ad Hoc Networks
p.117

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 519-520Research on Parallel Yen Algorithms on GPUs Using...

Research on Parallel Yen Algorithms on GPUs Using CUDA

Abstract:

With the arrival of the intermodality era, to design fast and efficient K shortest paths (KSP) algorithms becomes gradually one of the core technologies in traveler information systems. Yen is a classical algorithm for KSP. However, Yen is time-consuming. In view of powerful general-purpose computing capabilities, GPU(Graphics Processing Units) has received increasing attention in various fields. Based on CUDA software development environment, combined with the structure of the Yen algorithm itself, this paper proposed two parallel algorithms for Yen. The first parallel algorithm computes candidate shortest paths for very possible deviation nodes in parallel. The second one computes candidate shortest paths in serial, but computes very candidate path in parallel. Finally, the efficiency of the two parallel algorithms was tested through experiments.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 519-520)

Pages:

90-97

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.519-520.90

Citation:

Cite this paper

Online since:

February 2014

Authors:

Jian Fu Li

Keywords:

Graphic Processing Unit (GPU), K-Shortest Path, Parallel Algorithms, Yen

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] Yang HH, Chen YL. Finding K shortest looping paths in a traffic-light network. Computers & Operations Research 2005; 32: 571–81.

DOI: 10.1016/j.cor.2003.08.004

Google Scholar

[2] David Canca, Alejandro Zarzo, Pedro L. González-R, Eva Barrena4 and Encarnación Algaba. A methodology for schedule-based paths recommendation in multimodal public transportation networks. JOURNAL OF ADVANCED TRANSPORTATION, 2013; 47: 319–335.

DOI: 10.1002/atr.1207

Google Scholar

[3] Wangtu Xu, ShiweiHe, RuiSong, SohailS. Chaudhry. Finding the K shortest paths in a schedule-based transit network. Computers & Operations Research 39 (2012) 1812–1826.

DOI: 10.1016/j.cor.2010.02.005

Google Scholar

[4] JanRiezebosJ, vanWenzelW. k-Shortest routing of trains on shunting yards. OR Spectrum 2009, 31(4): 745–58.

Google Scholar

[5] J.Y. Yen, Finding the K shortest loopless paths in a graph, Management Science, 17 (1971) 712-716.

DOI: 10.1287/mnsc.17.11.712

Google Scholar

[6] E.Q.V. Martins, An algorithm for ranking paths that may contain cycles. European Journal of Operational Research, 18 (1984) 123-130.

DOI: 10.1016/0377-2217(84)90269-8

Google Scholar

[7] E.Q.V. Martins, M.M.B. Pascoal, J.L.E. Santos, A new algorithm for ranking loopless paths, Research report, CISUC, (1997).

Google Scholar

[8] J. Hershberger, M. Maxel, S. Sur, Finding the K shortest simple paths: a new algorithm and its implementation. ACM Transactions on Algorithms, 3 (2007) 45-es.

DOI: 10.1145/1290672.1290682

Google Scholar

[9] J.F. Li, An Improved Yen Algorithm based on A*, Journal of Computational Information Systems, 8 (2012) 9017-9024.

Google Scholar

[10] K.J. MARK. All-Pairs Shortest Path Algorithms Using CUDA. Thesis (Masters), Durham University, (2012).

Google Scholar

[11] O.A. Hector, T. Yuri, R.L. Diego and G.E. Arturo, A Tuned, concurrent-kernel approach to speed up the APSP problem, Proceedings of the 13th International Conference on Computational and Mathematical Methods in Science and Engineering, (2013).

Google Scholar

[12] M. Kazuya, N. Naohito, G.S. Stanislav, Blocked United Algorithm for the All-Pairs Shortest Paths Problem on Hybrid CPU-GPU Systems, IEICE Transactions on Information and Systems, E95- D(2012) 2759-2768.

DOI: 10.1587/transinf.e95.d.2759

Google Scholar