Title :
Method of workload balancing in GPU implementation of breadth-first search
Author :
Chernoskutov, Mikhail
Author_Institution :
Comput. Sci. Dept., IMM UB, Yekaterinburg, Russia
Abstract :
Optimized version of the parallel breadth-first search algorithm is considered in the paper. An optimization method described in the paper allows reducing the overhead of the suggested algorithm on each its iteration. It is shown that the optimized parallel algorithm for GPU is more than five times faster than its sequential analog on CPU.
Keywords :
graphics processing units; optimisation; parallel algorithms; tree searching; GPU; optimization method; parallel breadth-first search algorithm; workload balancing; Arrays; Complexity theory; Filling; Graphics processing units; Instruction sets; Parallel algorithms; Runtime; GPGPU; data intensive; parallel algorithms;
Conference_Titel :
High Performance Computing & Simulation (HPCS), 2014 International Conference on
Conference_Location :
Bologna
Print_ISBN :
978-1-4799-5312-7
DOI :
10.1109/HPCSim.2014.6903664
