Введение 5
1. Постановка задачи 8
2. Обзор 9
2.1. Вычисления на графическом процессоре 9
2.2. Библиотеки для работы с графическими процессорами . 10
2.3. Форматы представления матриц и векторов 11
2.4. Операции линейной алгебры 12
2.5. Алгоритмы анализа графов 14
2.6. Аналогичные библиотеки 17
3. Архитектура библиотеки 20
3.1. Основные компоненты 20
3.2. Сценарий использования 21
4. Реализация и оптимизации 25
4.1. Поэлементное сложение CSR-матриц 25
4.2. Умножение CSR-матрицы на плотный вектор 26
4.3. Умножение CSR-матрицы на разреженный вектор .... 27
4.4. Оптимизация префиксной суммы и сортировки 27
4.5. Оптимизация Brahma.FSharp 28
5. Реализация алгоритмов анализа графов 29
6. Исследование производительности 31
6.1. Постановка экспериментов 31
6.2. Исследование оптимизаций Brahma.FSharp и базовых операций 32
6.3. Сравнение производительности с аналогичными библиотеками 35
6.4. Выводы из исследования производительности 41
Заключение
Список литературы
Одной из самых известных структур данных информатики является граф. Графы активно применяются в рекомендательных системах и
СУБД, а также в разных науках: биологии [17], физике [9] и химии [3],
как и в математике — теории групп [2], топологии [20], теории вероятностей [4]. Следует отметить, что алгоритмы анализа графов получили
широкое распространение в анализе социальных сетей [15].
Классическое представление графа в виде множеств вершин и дуг
не всегда удобно для программирования алгоритмов анализа графов,
поэтому граф часто представляется иным образом. Одним из способов
представить граф в памяти машины является матрица смежности —
квадратная матрица размера N ×N, где N — количество вершин графа.
Ячейка (i, j) матрицы отвечает за наличие дуги между вершинами i и j
и имеет значение 0 (дуги нет) или 1 (дуга есть). Алгоритмы обработки
графов, представленных в виде матриц смежности, создаются на языке
линейной алгебры и широко освещены в литературе [10].
Граф, имеющий небольшое количество дуг относительно количества вершин, разумно представлять в виде разреженной, а не плотной
матрицы. Разреженная матрица — это матрица с преимущественно нулевыми элементами. Одним из наиболее активно используемых форматов разреженных матриц является CSR-формат1, сжимающий хранимые строковые индексы. Помимо CSR-формата используется симметричный ему CSC-формат, а также координатный формат, хранящий
индексы и значения элементов в виде троек.
Развитие идей о связи графов и разреженной линейной алгебры послужило толчком к созданию стандарта GraphBLAS [16], определяющего алгоритмы обработки графов на языке линейной алгебры с использованием разреженных матриц и векторов, заданных над полукольцами.
В рамках данной работы были достигнуты следующие результаты.
1. Выполнена реализация библиотеки, включая перечисленные ниже
возможности.
• Доработаны и оптимизированы базовые операции библиотеки: сортировка и префиксная сумма массива.
• Выявлены и устранены ухудшающие производительность
недочеты в Brahma.FSharp: асинхронная коммуникация с
очередью OpenCL через MailboxProcessor и лишние синхронизации этой очереди при обработке сообщений.
• Реализованы алгебраические операции: поэлементное сложение разреженных матриц и умножение разреженной матрицы
на плотный и разреженный вектор.
2. С помощью имеющихся операций реализованы следующие алгоритмы анализа графов: классический обход графа в ширину (с
плотным фронтом), поиск кратчайшего пути, а также ранжирование веб-страниц с помощью PageRank. Реализованы две дополнительные вариации обхода в ширину: обход с чередованием плотного и разреженного фронта, и обход с только разреженным фронтом.
3. Исследована производительность созданной библиотеки. Установлено, что реализованные оптимизации для Brahma.FSharp и базовых операций привели к увеличению производительности не менее чем в 3 раза. Произведено сравнение быстродействия библиотечных операций и графовых алгоритмов с реализациями из аналогичных библиотек на устройствах AMD и NVIDIA. Обнаружено, что производительность рассмотренных базовых операций не
уступает аналогичным реализациям, однако наблюдается отставание в производительности алгоритмов анализа графов от аналогов
на CUDA и OpenCL.
43В планы по дальнейшей разработке проекта входит устранение
выявленных в ходе данной работе проблем с производительностью, а также разработка более дружественного пользовательского интерфейса, пополнение набора операций библиотеки и доработка транслятора Brahma.FSharp.
Код проекта GraphBLAS-sharp доступен в репозитории на сервисе github16. Имя пользователя: kirillgarbar
