Meerkat: фреймворк для динамических алгоритмов обработки графов на графических процессорах | Кеви...

Описание: Семинар «Инновации в технологиях компиляторов 2025», Бангалор, Индия
https://compilertech.org/
------------------------------------------------------------------------------------------------------------------

Реализация алгоритмов для работы с графами представляет собой сложную задачу из-за их изменяющейся топологии и нерегулярных шаблонов доступа. Графы реального мира динамичны по своей природе и регулярно подвергаются добавлению и удалению ребер и вершин. Типичными примерами динамических графов являются социальные сети, сети сотрудничества и дорожные сети. Многократное применение статических алгоритмов к динамическим графам неэффективно. Кроме того, из-за быстрого роста неструктурированных и полуструктурированных данных алгоритмы для работы с графами требуют эффективной параллельной обработки. К сожалению, мы мало знаем о том, как эффективно обрабатывать динамические графы на архитектурах с массовым параллелизмом, таких как графические процессоры (GPU). Существующие подходы к представлению и обработке динамических графов либо не являются универсальными, либо неэффективны. В данной работе мы предлагаем библиотеку для динамических алгоритмов обработки графов, использующую адаптированное для графовых процессоров представление графа и модель выполнения с кооперативным распределением работы (WCWS), которая использует внутригрупповые внутренние механизмы, предотвращает расходимость потоков и обеспечивает согласованный доступ соседей вершины. Основанная на стратегии кооперативного распределения работы, наша библиотека, названная Meerkat, базируется на недавно предложенном динамическом представлении графа на графических процессорах и обеспечивает быструю итерацию по группе вершин — шаблон, имеющий решающее значение для повышения производительности в графовых приложениях. Мы реализовали динамические версии популярных алгоритмов обработки графов, таких как поиск в ширину, поиск кратчайших путей от одного источника, подсчет треугольников, PageRank и алгоритм слабосвязанных компонент, и оценили их по сравнению с другими общедоступными динамическими структурами данных и фреймворками для обработки графов: GPMA, Hornet и faimGraph. Используя различные графы из реального мира, мы видим, что Meerkat значительно повышает эффективность базового алгоритма динамического графа, превосходя по производительности эти фреймворки.

Полная статья: https://link.springer.com/article/10....