Parallel processing of unstructured data ºƒ¶Èº®¶Ã¶Â in a graph-like form can be a severe computational challenge because of significant overheads caused by the irregular nature of graph algorithms and the hardware latency of intensive data access. The GPU implementation of the load balancing method that allows one to dramatically improve the parallel breadth-first search algorithm compared to its sequential analog on CPU is considered. This work was partially supported by the Russian Foundation for Basic Research (project 14òÀÓ07òÀÓ00435) and by UB RAS (projects 12òÀÓPòÀÓ1òÀÓ1029 and RCPòÀÓ13òÀÓP18). Numerical experiments were performed using the "Uran" supercomputer installed at IMM UB RAS. This paper was recommended for publication by the Program Committee of the International Scientific Conference "Scientific Services and Internet: all bounds of parallelism" ((http://agora.guru.ru/abrau2013)).

Keywords: breadth-first search, parallel algorithm, graphics processing units

• PDF (in Russian) (315KB)



• PDF. zip (in Russian) (275KB)