Параллельная реализация алгоритма поиска минимальных остовных деревьев с использованием центрального и графического процессоров
Автор
А.С. Колганов
Аннотация
Решение задачи поиска минимальных остовных деревьев является распространенной в различных областях исследований: распознавание различных объектов, компьютерное зрение, анализ и построение сетей (например, телефонных, электрических, компьютерных, дорожных и т.д.), химия и биология и многие другие. Существует, по крайней мере, три известных алгоритма, решающих данную задачу: Борувки, Крускала и Прима. Обработка больших графов – достаточно трудоемкая задача для центрального процессора (CPU) и является востребованной в данное время. Все более широкое распространение для решения задач общего назначения получают графические ускорители (GPU), имеющие большую вычислительную мощность, чем CPU. Но данная задача, как и многие задачи по обработке графов, плохо ложится на архитектуру GPU. В данной статье будет рассмотрена гибридная реализация данного алгоритма.
Ключевые слова
MST, CUDA, NVidia, Graphs, Boruvka.
Язык
Русский
Представлена на
Библиографическая ссылка
А.С. Колганов. Параллельная реализация алгоритма поиска минимальных остовных деревьев с использованием центрального и графического процессоров // Сборник трудов Международной научной конференции "Параллельные вычислительные технологии 2016", Челябинск: Издательский центр ЮУрГУ, 2016, C. 530-543