Параллельная реализация алгоритма поиска минимальных остовных деревьев с использованием центрального и графического процессоров
Бесплатный доступ
Решение задачи поиска минимальных остовных деревьев является распространенной в различных областях исследований: распознавание различных объектов, компьютерное зрение, анализ и построение сетей (например, телефонных, электрических, компьютерных, дорожных и т.д.), химия и биология и многие другие. Обработка больших графов - достаточно трудоемкая задача для центрального процессора (CPU) и является востребованной в данное время. Все более широкое распространение для решения задач общего назначения получают графические ускорители (GPU), имеющие большую вычислительную мощность, чем CPU. В данной статье рассмотрены методы сжатия и преобразования исходных графов для повышения эффективности их обработки. На примере алгоритма поиска минимальных остовных деревьев исследованы предложенные подходы. Исследована возможность гибридной реализация данного алгоритма. Получены самые высокие результаты по производительности на графах R-MAT и SSCA2.
Поиск остовных деревье, параллельная обработка графов, алгоритм борувки, большие графы
Короткий адрес: https://sciup.org/147160599
IDR: 147160599 | DOI: 10.14529/cmse160301
Список литературы Параллельная реализация алгоритма поиска минимальных остовных деревьев с использованием центрального и графического процессоров
- Chazelle B.A. Minimum spanning tree algorithm with inverse-ackermann type complexity//Journal of the ACM. 2000. Vol. 47, No. 6. P. 1028-1047.
- Pettie S. An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem//Foundations of Computer Science. 2002. P. 155-163.
- Wei W., Shaozhong G., Fan Y., Jianxun C. GPU-Based Fast Minimum Spanning Tree Using Data Parallel Primitives//Information Engineering and Computer Science (ICIECS), 2nd International Conference (TBD Wuhan, China). 2010. P. 1-4.
- Arefin A.S., Riveros C., Berretta R., Moscato P. kNN-MST-Agglomerative: A fast and scalable graph-based data clustering approach on GPU//Computer Science & Education (ICCSE), 7th International Conference (The University of Melbourne, Australia). 2012. P. 585-590.
- Vineet V., Harish P., Patidar S., Narayanan P.J. Fast Minimum Spanning Tree for Large Graphs on the GPU//HPG ’09 Proceedings of the Conference on High Performance Graphics (New Orleans, LA, USA). 2009. P. 167-171.
- Gibbs N.E., Poole W.G., Stockmeyer P.K. A comparison of several bandwidth and profile reduction algorithms//ACM Transactions on Mathematical Software. 1976. Vol. 2, No. 4. P. 322-330.
- Gilbert J.R., Moler C., Schreiber R. Sparse matrices in MATLAB: Design and Implementation//SIAM Journal on Matrix Analysis and Applications. 1992. Vol. 13, No. 1. P. 333-356.
- Chakrabarti D., Zhan Y., Faloutsos C. R-MAT: A Recursive Model for Graph Mining//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. Technical report. 2005.
- Bor˚uvka O. O Jist´em Probl´emu Minim´aln´ım. Pr´ace Moravsk´e Pˇr´ırodovˇedeck´e SpoleˇcnostiIII. 1926. No. 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.5.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., Cao T., Karras P., Bressan S. Scalable Parallel Minimum Spanning Forest Computation//PPoPP’12 Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming (New York, NY, USA). 2012. P. 205-214.
- Wei W., Shaozhong G., Fan Y., Jianxun C. Design and Implementation of GPU-Based Prim’s Algorithm//Information Engineering and Computer Science (ICIECS) 2nd International Conference (TBD Wuhan, China). 2010. P. 1-4.
