Введение 4
1. Цель и задачи 6
2. Обзор предметной области 7
2.1. Терминология 7
2.2. Поиск путей с ограничениями 8
2.3. Существующие решения 9
2.4. Поиск путей с КС ограничениями через тензорное произведение 10
2.5. Вычисления на GPU 11
2.6. Примитивы разреженной линейной алгебры для GPGPU 12
3. Архитектура библиотеки 14
3.1. Компоненты библиотеки 15
3.2. Последовательность обработки операций 18
4. Детали реализации 20
4.1. Примитивы и операции 20
4.2. Cuda-модуль 21
4.3. Python-пакет 21
4.4. Пример использования 22
5. Алгоритм поиска путей с КС ограничениями 24
6. Экспериментальное исследование 26
6.1. Постановка экспериментов 26
6.2. Результаты 30
7. Заключение 34
Список литературы 36
Все чаще современные системы аналитики и рекомендаций строятся на основе анализа данных, структурированных с использованием графовой модели. В данной модели основные сущности представляются вершинами графа, а отношения между сущностями — ориентированными ребрами с различными метками. Подобная модель позволяет относительно легко и практически в явном виде моделировать сложные иерархические структуры, которые не так просто представить, например, в классической реляционной модели. В качестве основных областей применения графовой модели можно выделить следующие: графовые базы данных [4], анализ RDF данных [6], биоинформатика [26] и статический анализ кода [14].
Поскольку графовая модель используется для моделирования отношений между объектами, при решении прикладных задач возникает необходимость в выявлении неявных взаимоотношений между объектами. Для этого формируются запросы в специализированных программных средствах для управления графовыми базами данных. В качестве запроса можно использовать некоторый шаблон на путь в графе, который будет связывать объекты, т.е. выражать взаимосвязь между ними. В качестве такого шаблона можно использовать формальные грамматики, например, регулярные или контекстно-свободные (КС). Используя выразительные грамматики, можно формировать сложные запросы и выявлять нестандартные и скрытые ранее взаимоотношения между объектами. Например, same-generation queries[1] могут быть выражены КС грамматиками, в отличие от регулярных.
Результатом запроса может быть множество пар объектов, между которыми существует путь в графе, удовлетворяющий заданным ограничениям. Также может возвращаться один экземпляр такого пути для каждой пары объектов или итератор всех путей, что зависит от семантики запроса. Поскольку один и тот же запрос может иметь разную семантику, требуются различные программные и алгоритмические средства для его выполнения.
Запросы с регулярными ограничениями изучены достаточно хорошо, языковая и программная поддержка выполнения подобных запросов присутствует в некоторых современных графовых базах данных. Однако, полноценная поддержка запросов с КС ограничениями до сих пор не представлена. Существуют алгоритмы [3,6,7,17,21] для вычисления запросов с КС ограничениями, но потребуется еще время, прежде чем появиться полноценная высокопроизводительная реализация одного из алгоритмов, способная обрабатывать реальные графовые данные.
Работы Никиты Мишина и др. [12] и Арсения Терехова и др. [8] показывают, что реализация алгоритма Рустама Азимова [3], основанного на операциях линейной алгебры, с использованием GPGPU для выполнения наиболее вычислительно сложных частей алгоритма, дает существенный прирост в производительности. Это позволило заключить, что подобный подход к реализации может быть в теории применим для анализа данных близких к реальным.
Недавно представленный алгоритм [7] для вычисления запросов с КС ограничениями также полагается на операции линейной алгебры: тензорное произведение, матричное умножение и сложение в булевом полукольце. Данный алгоритм в сравнении с алгоритмом Рустама Азимова [8] позволяет выполнять запросы для всех ранее упомянутых се-мантик и потенциально поддерживает КС запросы с большим количеством нетерминалов и правил вывода (в некоторой нормальной форме).
Для его реализации на GPGPU требуются высокопроизводительные библиотеки примитивов линейной алгебры. Подобные инструменты для работы со стандартными типами данных, такими как float, double, int и long,уже представлены. Однако библиотека, которая бы работала с разреженными данными и имела специализацию указанных ранее операций для булевых значений, еще не разработана.
Поэтому важной задачей является не только реализация перспективного алгоритма [7] на GPGPU, но и разработка библиотеки примитивов линейной булевой алгебры, которая позволит реализовать этот и подобные алгоритмы на данной вычислительной платформе.
В рамках выполнения данной работы были получены следующие результаты.
• Спроектирована библиотека примитивов разреженной линейной булевой алгебры cuBool для вычислений на GPGPU. Данная библиотека экспортирует С-совместимый интерфейс, имеет поддержку различных вычислительных модулей, а также предоставляет Python-пакет для работы конечного пользователя с примитивами библиотеки в высокоуровневой среде вычислений с управляемыми ресурсами.
• Реализована библиотека cuBool в соответствии с разработанной архитектурой. Ядро библиотеки написано на языке С—+, а математические операции, выполняющиеся на GPU, реализованы на языке Cuda C/C+—+. Библиотека предоставляет модуль CPU вычислений для компьютеров без Cuda-устройства. Также создан Python-пакет pycubool, который доступен для скачивания через пакетный менеджер PyPI.
• С использованием pycubool реализован алгоритм поиска путей с КС ограничениями через тензорное произведение. Данный алгоритм использует операции матричного умножения, сложения и произведение Кронекера в булевом полукольце, а также различные операции для манипуляций над значениями матриц.
• Выполнено экспериментальное исследование реализованной библиотеки и алгоритма. Матричное умножение показывает ускорение до 5 раз по сравнению с существующими аналогами, матричное сложение сравнимо по времени с существующими аналогами, однако операции потребляют до 3 раз меньше видеопамяти. Реализация алгоритма поиска путей с КС ограничениями на основе cuBool показывает ускорение до 6 раз по сравнению с CPU версией, что делает ее более применимой для анализа реальных данных.
Результаты, полученные в данном исследовании, были представлены на конференции GrAPL 2021 . Соответствующая статья опубликована в сборнике материалов конференции.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
