NDLI: Improving vertex-frontier based GPU breadth-first search

Content Provider	Springer Nature Link
Author	Yang, Bo Lu, Kai Gao, Ying hui Xu, Kai Wang, Xiao ping Cheng, Zhi quan
Copyright Year	2014
Abstract	Breadth-first search (BFS) is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effective solution, GPU-acceleration achieves the state-of-the-art result of 3.3×10$^{9}$ traversed edges per second on a NVIDIA Tesla C2050 GPU. A novel vertex frontier based GPU BFS algorithm is proposed, and its main features are three-fold. Firstly, to obtain a better workload balance for irregular graphs, a virtual-queue task decomposition and mapping strategy is introduced for vertex frontier expanding. Secondly, a global deduplicate detection scheme is proposed to remove reduplicative vertices from vertex frontier effectively. Finally, a GPU-based bottom-up BFS approach is employed to process large frontier. The experimental results demonstrate that the algorithm can achieve 10% improvement over the state-of-the-art method on diverse graphs. Especially, it exhibits 2–3 times speedup on low-diameter and scale-free graphs over the state-of-the-art on a NVIDIA Tesla K20c GPU, reaching a peak traversal rate of 11.2×10$^{9}$ edges/s.
Starting Page	3828
Ending Page	3836
Page Count	9
File Format	PDF
ISSN	20952899
Journal	Journal of Central South University of Technology
Volume Number	21
Issue Number	10
e-ISSN	22275223
Language	English
Publisher	Central South University
Publisher Date	2014-10-17
Publisher Place	Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	breadth-first search GPU graph traversal vertex frontier Engineering Metallic Materials
Content Type	Text
Resource Type	Article
Subject	Metals and Alloys Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Scalable GPU graph traversal

GPU acceleration of subgraph isomorphism search in large scale graph

High-Performance and Scalable GPU Graph Traversal

Scalable GPU graph traversal

Accelerating Breadth First Search on GPU-BOX

Breadth First Search on Cost-efficient Multi-GPU Systems

FlexBFS:a parallelism-aware implementation of breadth-first search on GPU

Task-based parallel breadth-first search in heterogeneous environments.

A method for improving graph queries processing using positional inverted index (P.I.I) idea in search engines and parallelization techniques

Improving vertex-frontier based GPU breadth-first search

Similar Documents

Scalable GPU graph traversal

GPU acceleration of subgraph isomorphism search in large scale graph

High-Performance and Scalable GPU Graph Traversal

Scalable GPU graph traversal

Accelerating Breadth First Search on GPU-BOX

Breadth First Search on Cost-efficient Multi-GPU Systems

FlexBFS:a parallelism-aware implementation of breadth-first search on GPU

Task-based parallel breadth-first search in heterogeneous environments.

A method for improving graph queries processing using positional inverted index (P.I.I) idea in search engines and parallelization techniques

Improving vertex-frontier based GPU breadth-first search