Алгоритмы разбиения графов на GPU

Герб А.Р.; Омарова Г.А.; Gerb A.; Omarova G.

doi:10.24412/2073-0667-2023-4-78-87

Научные статьи \ Математика. Естественные науки \ Математика \ Комбинаторный анализ. Теория графов

Алгоритмы разбиения графов на GPU

Герб А.Р. Омарова Г.А.

Журнал: Проблемы информатики @problem-info

Рубрика: Прикладные информационные технологии

Статья в выпуске: 4 (61), 2023 года.

Бесплатный доступ

В данной работе рассматриваются два модифицированных и реализованных на GPU алгоритма: алгоритм меток и алгоритм Ja-Bc-Ja. Проведен сравнительный анализ работы на больших графах.

граф \ разреженная матрица \ итерации \ минимальный разрез

Похожие статьи в разделе Комбинаторный анализ. Теория графов

Алгоритмы разбиения графов: обзор литературы

Герб А.Р., Омарова Г.А.

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

Сытник Александр Александрович, Ивженко Сергей Петрович, Гвоздюк Илья Вячеславович

Решение сеточных уравнений неявных разностных схем с циклическими краевыми условиями на двумерных сеточных областях с использованием нескольких графических вычислительных устройств

Головашкин Димитрий Львович, Логанова Лилия Владимировна

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

Воротникова Дарья Геннадьевна, Кочуров Александр Валерьевич, Головашкин Димитрий Львович

Сравнение эффективности CPU и GPU реализаций некоторых комбинаторных алгоритмов на задачах обращения криптографических функций

Булавинцев Вадим Германович

Применение теории графов в алгебраических многосеточных методах для решения разреженных СЛАУ

Герб Артем Родионович, Омарова Гульзира Алимовна

Короткий адрес: https://sciup.org/143182562

IDS: 143182562 | УДК: 519.17-519.61 | DOI: 10.24412/2073-0667-2023-4-78-87

Graph partitioning algorithms on GPU

In this paper we consider two algorithms: the label propagation algorithm and the Ja-Be-Ja algorithm, both modified and implemented on GPU. A comparative analysis of performance on large graphs has been performed

Список литературы Алгоритмы разбиения графов на GPU

CUDA С Programming Guide 7.5. ed: NVIDIA Corporation, 2016.
Timothy A. Davis and Yifan Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software 38, 1, Article 1 (December 2011), 25 pages. https: //, 2011. DOI: 10.1145/2049662.2049663
Meyerhenke H., Monien B., Schamberger S. Graph partitioning and disturbed diffusion Parallel Computing. 2009. V. 35, iss. 10-11. P. 544-569. EDN: IXMPWN
Gottesbiiren L. et al. Deep multilevel graph partitioning. arXiv preprint arXiv:2105.02022. 2021.
Kumar R., Charpiat G., Thonnat M. Multiple object tracking by efficient graph partitioning // Computer Vision-ACCV 2014: 12th Asian Conference on Computer Vision, Singapore (Singapore), Nov. 1-5, 2014. Revised Selected Papers, Part IV 12. Springer International Publishing, 2015.
Subelj L., Bajec M. Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction // Physical Review E. 2011. V. 83, iss. 3.
Raghavan U. N., Albert R., Kumara S. Near linear time algorithm to detect community structures in large-scale networks // Physical review E. 2007. V. 52, No 3.
Rahimian F., et al. Ja-be-ja: A distributed algorithm for balanced graph partitioning // IEEE 7th International Conference on Self-Adaptive and Self-Organizing Systems. IEEE, 2013.

Еще