Параллельная реализация алгоритма поиска минимальных остовных деревьев с использованием центрального и графического процессоров

Александр Сергеевич Колганов

Аннотация


Решение задачи поиска минимальных остовных деревьев является распространенной в различных областях исследований: распознавание различных объектов, компьютерное зрение, анализ и построение сетей (например, телефонных, электрических, компьютерных, дорожных и т.д.), химия и биология и многие другие. Обработка больших графов — достаточно трудоемкая задача для центрального процессора (CPU) и является востребованной в данное время. Все более широкое распространение для решения задач общего назначения получают графические ускорители (GPU), имеющие большую вычислительную мощность, чем CPU. В данной статье рассмотрены методы сжатия и преобразования исходных графов для повышения эффективности их обработки. На примере алгоритма поиска минимальных остовных деревьев исследованы предложенные подходы. Исследована возможность гибридной реализация данного алгоритма. Получены самые высокие результаты по производительности на графах R-MAT и SSCA2.


Ключевые слова


поиск остовных деревье, параллельная обработка графов, алгоритм Борувки, CUDA, большие графы

Полный текст:

PDF

Литература


Chazelle, B.A. Minimum spanning tree algorithm with inverse-ackermann type complexity /

B.A. Chazelle — Journal of the ACM. — 2000. — Vol. 47, №. 6. — P. 1028–1047.

Pettie, S. An inverse-Ackermann style lower bound for the online minimum spanning tree

verification problem / S. Pettie — Foundations of Computer Science. — 2002. — P. 155–163.

Wei, W. GPU-Based Fast Minimum Spanning Tree Using Data Parallel Primitives / W.

Wei, G. Shaozhong, Y. Fan, C. Jianxun // Information Engineering and Computer Science

(ICIECS), 2nd International Conference (TBD Wuhan, China). — 2010. — P. 1–4.

Arefin, A.S. kNN-MST-Agglomerative: A fast and scalable graph-based data clustering

approach on GPU / A.S. Arefin, C. Riveros, R. Berretta, P. Moscato // Computer Science &

Education (ICCSE), 7th International Conference (The University of Melbourne, Australia).

— 2012. — P. 585–590.

Vineet, V. Fast Minimum Spanning Tree for Large Graphs on the GPU / V. Vineet, P. Harish,

S. Patidar, P.J. Narayanan // HPG ’09 Proceedings of the Conference on High Performance

Graphics (New Orleans, LA, USA). — 2009. — P. 167–171.

Gibbs, N.E. A comparison of several bandwidth and profile reduction algorithms / N.E. Gibbs,

W.G. Poole, P.K. Stockmeyer — ACM Transactions on Mathematical Software. — 1976. —

Vol. 2, №. 4. — P. 322–330.

Gilbert, J.R. Sparse matrices in MATLAB: Design and Implementation / J.R. Gilbert, C.

Moler, R. Schreiber — SIAM Journal on Matrix Analysis and Applications. — 1992. — Vol.

, №. 1. — P. 333—356.

Chakrabarti, D. R-MAT: A Recursive Model for Graph Mining / D. Chakrabarti, Y. Zhan,

C. Faloutsos // In Proceedings of 4th International Conference on Data Mining (Brighton,

UK). — 2004. — P. 442–446.

Bader D.A., Madduri K. Design and implementation of the HPCS graph analysis benchmark

on symmetric multiprocessors / D.A. Bader , K. Madduri — Technical report. — 2005.

Bor˚uvka. O Jist´em Probl´emu Minim´aln´ım. / Bor˚uvka, Otakar — Pr´ace Moravsk´e

Pˇr´ırodovˇedeck´e Spoleˇcnosti III. — 1926. — №. 3. — P. 37–58.

Описание алгоритмов для структуры Union-Find. URL: https://www.topcoder.com/

community/data-science/data-science-tutorials/disjoint-set-data-structures/

(дата обращения: 30.11.2015)

Описание стандарта OpenMP. URL: http://www.openmp.org/mp-documents/openmp-4.

pdf (дата обращения: 30.11.2015)

Compute Unified Device Architecture. URL: http://www.nvidia.ru/object/

cuda-parallel-computing-ru.html (дата обращения: 30.11.2015)

Unified Memory in CUDA 6. URL: http://devblogs.nvidia.com/parallelforall/

unified-memory-in-cuda-6/ (дата обращения: 30.11.2015)

Nobari, S. Scalable Parallel Minimum Spanning Forest Computation / S. Nobari, T. Cao,

P. Karras, S. Bressan // PPoPP’12 Proceedings of the 17th ACM SIGPLAN symposium

on Principles and Practice of Parallel Programming (New York, NY, USA). — 2012. — P.

–214.

Wei, W. Design and Implementation of GPU-Based Prim’s Algorithm / W. Wei, G.

Shaozhong, Y. Fan, C. Jianxun // Information Engineering and Computer Science (ICIECS)

nd International Conference (TBD Wuhan, China). — 2010. — P. 1–4.




DOI: http://dx.doi.org/10.14529/cmse160301