Approaches to parallel implementation Yen´s algorithm using CUDA

Author

Tribrat, M.I. ; Pogorilyy, S.D. ; Afanas´ev, D.V.

Author_Institution

Radiophys. Fac., Taras Shevchenko Nat. Univ. of Kyiv, Kiev, Ukraine

Volume

1

fYear

2011

fDate

15-17 Sept. 2011

Firstpage

243

Lastpage

246

Abstract

Analysis of opportunities and approaches to parallel implementation of the Yen´s algorithm is done and the expediency of such implementation using video adapters is argue. A parallel implementation of the Yen´s algorithm with realization of developed method of templates and parallelization of basic Dijkstra´s algorithm using hardware-software platform CUDA is created. Acceleration of work of parallel algorithm in comparison with serial algorithm is received.

Keywords

computational complexity; graph theory; parallel algorithms; CUDA hardware-software platform; Dijkstra algorithm; Yen algorithm; compute unified device architecture; parallel algorithm; parallel implementation; parallelization; serial algorithm; video adapter; Algorithm design and analysis; Central Processing Unit; Educational institutions; Graphics processing unit; Instruction sets; Parallel processing; Software algorithms; CUDA; Dijkstra´s algorithm; Yen´s algorithm; method of templates;

fLanguage

English

Publisher

ieee

Conference_Titel

Intelligent Data Acquisition and Advanced Computing Systems (IDAACS), 2011 IEEE 6th International Conference on

Conference_Location

Prague

Print_ISBN

978-1-4577-1426-9

Type

conf

DOI

10.1109/IDAACS.2011.6072749

Filename

6072749