Анализ графов

Проект для исследования графовых алгоритмов с ускорением на CPU и GPU.

О проекте

Проект предназначен для изучения и сравнительного анализа графовых алгоритмов в различных реализациях. В нём используются высокопроизводительные библиотеки обработки графов SPLA, Gunrock и LAGraph, что позволяет сравнивать производительность алгоритмов на CPU и GPU.

Алгоритмы и реализации

Слайды к проекту находятся в каталоге slides.

В рамках эксперимента сравниваются различные реализации следующих алгоритмов:

1. Алгоритм Прима:

   • PrimSpla — реализация на базе SPLA (автор: Демченко);
   • PrimGunrock — реализация на базе Gunrock (автор: Лановая).

2. Алгоритм Борувки:

   • BoruvkaSpla — реализация на базе SPLA с бэкендом OpenCL (автор: Ржанков);
   • BoruvkaLagraph — реализация на базе LAGraph, надстройки над GraphBLAS (автор: Ржанков);
   • BoruvkaGunrock — реализация на базе Gunrock (автор: Лановая).

3. Поиск в ширину (BFS) с построением дерева родителей:

   • BFSSpla — реализация на базе SPLA (автор: Демченко);
   • BFSLaGraph — реализация на базе LAGraph, надстройки над GraphBLAS (автор: Демченко).

Системные требования

• CMake версии 3.20 или новее;
• компилятор с поддержкой C++20;
• CUDA Toolkit 12.0 или новее — для ускорения вычислений на GPU;
• Python 3.7 или новее — для визуализации результатов экспериментов.

Зависимости

В проекте используются следующие библиотеки:

• GraphBLAS — библиотека разреженной линейной алгебры для реализации графовых алгоритмов;
• LAGraph — библиотека графовых алгоритмов на базе GraphBLAS;
• Gunrock — библиотека обработки графов с ускорением на GPU;
• SPLA — фреймворк разреженной линейной алгебры с поддержкой ускорения на GPU.

Все зависимости подключены как Git-подмодули.

Начало работы

Клонирование репозитория

git clone --recurse-submodules https://github.com/aartdem/graph-analysis.git
cd graph-analysis

Сборка проекта

mkdir -p build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
make -j

Чтобы отключить поддержку CUDA, используйте следующую команду:

cmake .. -DUSE_CUDA=OFF

Запуск тестов

cd build
ctest

Структура проекта

graph-analysis/
├── data/            # Наборы данных с графами
├── deps/            # Зависимости (Git-подмодули)
│   ├── GraphBLAS/   # Библиотека GraphBLAS
│   ├── LAGraph/     # Библиотека LAGraph
│   ├── gunrock/     # Библиотека Gunrock
│   └── spla/        # Библиотека SPLA
├── src/             # Исходный код
│   ├── lib/         # Основной код библиотеки
│   ├── tests/       # Модульные тесты
│   └── experiment/  # Код для измерения производительности
└── test_data/       # Тестовые данные

Эксперимент

В эксперименте сравнивается производительность алгоритмов построения минимального остовного дерева (MST) — алгоритмов Прима и Борувки. Для каждого алгоритма рассматриваются реализации на базе разных библиотек и проводится тестирование на нескольких наборах графов.

Конфигурация тестового стенда

• Аппаратная и программная конфигурация:
  • ОС: Ubuntu 24.04 LTS;
  • GPU: NVIDIA GeForce RTX 3050 Ti Laptop GPU (4 ГБ видеопамяти);
  • драйвер GPU: версия 32.0.15.5597;
  • CUDA Toolkit: 12.3;
  • ядра CUDA: 2560;
  • CPU: Intel Core i7-11800H 11-го поколения, 2,30 ГГц;
  • кеш-память: L1 — 640 КБ, L2 — 10 МБ, L3 — 24 МБ;
  • оперативная память: 16 ГБ.

Запуск эксперимента

cd build
./mst_benchmark

Анализ результатов

По итогам эксперимента создаются CSV-файлы с подробными измерениями производительности. Для визуализации результатов используйте входящий в проект Python-скрипт:

mv build/benchmark_results.csv .
python make_graphics.py

Лицензия

Проект распространяется по лицензии MIT. Подробности приведены в файле LICENSE.