Реализация алгоритма построения минимального остовного дерава с использованием библиотеки Spla

Библиотека Spla позволяет реализовывать алгоритмы анализа графов с использованием линейной алгебры на графическом ускорителе. На основе библиотеки уже реализованы некоторые классические алгоритмы анализа графов, но ещё не реализован алгоритм поиска минимального остовного дерева. Алгоритм Борувки, решающий данную задачу, может быть выражен в терминах линейной алгебры (например, как это сделано в LaGraph). Предлагается добавить его в коллекцию алгоритмов, использующих Spla, а также проанализировать производительность полученного решения.

Требования к студенту
  • Отличное знание языков C++, C и соответствующего инструментария (компиляция, системы сборки, профилирование, отладка, тестирование)
  • Отличное знание теории графов, алгоритмов поиска минимальных остовных деревьев.
  • Хорошее знание линейной алгебры: матрицы, вектора, операции над ними, полукольца, моноиды.
  • Понимание основ разработки под графические укорители. Основы OpenCL.
Уровень

2 курс


Руководитель

Григорьев Семен Вячеславович


Консультант

Grigorev Semyon


Источник

Кафедра системного программирования СПбГУ