Speakers
Description
Обработка графов широко применяется в различных приложениях, например в алгоритмах маршрутизации в компьютерных сетях, анализе социальных сетей и анализе геномных данных. Разработка и оптимизация программ обработки графов - нетривиальная задача. Для повышения эффективности в настоящее время используется представление графа в виде разреженной матрицы смежности с ориентацией на применение методов линейной алгебры на базе стандартного интерфейса GraphBLAS. Разработано несколько библиотек операций над графами, обеспечивающих сверхэффективную реализацию на графических процессорах (GPU), однако библиотеки крайне сложны для пользователя.
Другой подход к обработке графов применяется в предикатном (функциональном) программировании. Вершины и ребра графа представлены множествами. Отметим, что традиционно графы представляются в объектно-ориентированном стиле. Язык предикатного программирования P расширен дополнительными конструкциями для работы с множествами. Введены также матричные операции на полукольцах с ориентацией на интерфейс GraphBLAS для эффективной реализации на GPU. Достоинство нашего подхода в возможности применения формальной верификации предикатных программ на графах, что продемонстрировано на нескольких алгоритмах.
Эффективность предикатных программ достигается применением последовательности оптимизирующих трансформаций, преобразующих исходную программу в императивную программу в стиле языка Си. Здесь добавлено множество трансформаций для операций над графами, в частности, для битовых шкал. Методы трансформации демонстрируются на следующих программах: построение списка максимальных клик, нахождение изоморфного подграфа, поиск компонент сильной связности в графе (алгоритм Косараджу) и других.
| Секция конференции | Теоретическое, экспериментальное и системное программирование |
|---|
