Efficient Graph Component Labeling on Hybrid CPU and GPU Platforms

Xiao Hui Pan

doi:10.4028/www.scientific.net/AMM.596.276

Paper Titles

Research on Multi-Agent Formation’s Obstacle Avoidance Problem Based on Three-Dimensional Vectorial Artificial Potential Field Method
p.251

A Evaluation Model for Valid Prediction of Cabs’ Number Change from Urban Cabs Trajectories
p.259

A Method of Building Chinese Sentiment Lexicon Based on Semantics
p.263

A Model of Predicting Corrosion Rate for Substation Grounding Grid Based on the Similarity and Support Vector Regression
p.271

Efficient Graph Component Labeling on Hybrid CPU and GPU Platforms
p.276

Evaluation Research on Agricultural Informatization Level in Tropical Areas of China Based on Entropy Method
p.280

The Generalized Fuzzy Time Series Model for Forecasting Base on the Optimization of the Length of Intervals
p.286

Web Page Ranking Algorithm Based on the Meta-Information
p.292

E-Bayes Estimation of Burr Distribution Parameter under Square Loss Function
p.297

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vol. 596Efficient Graph Component Labeling on Hybrid CPU...

Efficient Graph Component Labeling on Hybrid CPU and GPU Platforms

Abstract:

Graph component labeling, which is a subset of the general graph coloring problem, is a computationally expensive operation in many important applications and simulations. A number of data-parallel algorithmic variations to the component labeling problem are possible and we explore their use with general purpose graphical processing units (GPGPUs) and with the CUDA GPU programming language. We discuss implementation issues and performance results on CPUs and GPUs using CUDA. We evaluated our system with real-world graphs. We show how to consider different architectural features of the GPU and the host CPUs and achieve high performance.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volume 596)

Pages:

276-279

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.596.276

Citation:

Cite this paper

Online since:

July 2014

Authors:

Xiao Hui Pan*

Keywords:

Connected Components, GPU, Graph Processing

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] P. Harish, V. Vineet, and P. J. Narayanan. Large graph algorithms for massively multithreaded architectures. Technical Report IIIT/TR/2009/74, International Institute of Information Technology Hy-derabad, INDIA, (2009).

Google Scholar

[2] V. Vineet, P. Harish, S. Patidar, and P. J. Narayanan. Fast minimum spanning tree for large graphs on the GPU. In Proceedings of the Conference on High Performance Graphics, (2009), pp.167-171.

DOI: 10.1145/1572769.1572796

Google Scholar

[3] D. Merrill, M. Garland, and A. Grimshaw. Scalable GPU graph traversal. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, (2012), pp.117-128.

DOI: 10.1145/2145816.2145832

Google Scholar

[4] A. Gharaibeh, L. B. Costa, E. Santos-Neto, and M. Ripeanu. On graphs, GPUs, and blind dating: A workload to processor matchmaking quest. In Proceedings of IEEE IPDPS (2013).

DOI: 10.1109/ipdps.2013.37

Google Scholar

[5] L. Valiant. A bridging model for parallel computation. Communications of the ACM, Vol. 33, No. 8 (1990), pp.103-111.

Google Scholar

[6] A. Kyrola, G. Blelloch, and C. Guestrin. Graphchi: large-scale graph computation on just a pc. In Proceedings of OSDI, (2012), pp.31-46.

Google Scholar

[7] J. Yang and J. Leskovec. Defining and Evaluating Network Communities based on Ground-truth. In Proceedings of ICDM, (2012).

Google Scholar