Введение 4
1. Постановка задачи 6
2. Обзор 7
2.1. Обзор аналогичных инструментов 7
2.2. Платформа OpenCL и модель исполнения 9
2.3. Язык программирования F# 11
2.4. Библиотека Brahma.FSharp 12
3. Реализация 14
3.1. Поддержка обобщенных атомарных операций 14
3.2. Поддержка трансфера пользовательских типов данных . 17
3.3. Улучшение модели управления памятью 19
3.4. Общая архитектура решения 20
4. Эксперимент 24
4.1. Условия эксперимента 24
4.2. Оценка затрат на трансфер данных 24
4.3. Оценка затрат на использование атомарных операций . . 28
Заключение 30
Список литературы 31
Данные, представимые в виде графов, встречаются повсеместно: при анализе компьютерных и социальных сетей, в биоинформатике и статическом анализе кода [5]. Графы, возникающие в этих областях, могут содержать миллионы узлов и ребер, поэтому существует необходимость в высокопроизводительных инструментах анализа больших графов. В связи с этим многообещающей становится идея использования графических ускорителей общего назначения — GPGPU. Существующие решения уже сейчас доказывают, что использование GPGPU может повысить производительность алгоритмов анализа графов [1] [6], однако ценой служит более сложная модель программирования [10]. Иным является подход к организации вычислений над графами, основанный на стандарте GraphBLAS [5], который определяет базовые примитивы для построения графовых алгоритмов в терминах линейной алгебры. Свойством такого подхода является способность оперировать богатым набором графов различных типов с помощью небольшого набора матричных операций над полукольцами. Например, умножение матрицы на вектор, как показано на рисунке 1, является шагом в алгоритме поиска в ширину. Решения, основанные на стандарте GraphBLAS, производительны, масштабируемы и имеют более дружественное API [3]. Тем не менее на данный момент нет полноценных инструментов, реализующих стандарт GraphBLAS на графических процессорах общего назначения. Текущие реализации GraphBLAS на GPGPU (например, GraphBLAST [10]) показывают, что использование GPGPU действительно может улучшить производительность инструментов такого рода, однако разработчики сталкиваются не только с проблемами, связанными с реализацией обобщенных операций на графических процессорах с помощью стандартных инструментов языка Cd—+, но и с переносимостью решений, основанных на программно-аппаратной платформе CUDA.
Одним из возможных подходов к реализации GraphBLAS на GPU является использование языка высокого уровня, а также библиотек,динамически транслирующих конструкции и объекты данного языка в низкоуровневый код, способный исполнятся на графическом процессоре видеокарты. Данный подход был опробован на прототипе GraphBLAS- sharp1 2, разработанном на кафедре системного программирования СПбГУ, который показал жизнеспособность этой идеи. В качестве библиотеки для взаимодействия с OpenCL прототип использует библиотеку Brahma.FSharp, которая также разрабатывается на кафедре системного программирования СПбГУ. Библиотека позволяет использовать подмножество языка F# для написания OpenCL ядер и предоставляет интерфейс для работы с ними. В ходе работы над прототипом GraphBLAS-sharp был выявлен ряд недостатков библиотеки Brahma.FSharp, перечисленных ниже.
1. Отсутствие атомарных операций для произвольных типов данных, что не позволяет реализовывать некоторые алгоритмы, которые могут оказаться лучше аналогов.
2. Отсутствие поддержки трансфера пользовательских типов данных из управляемой памяти в видеопамять.
3. Отсутствие возможности вручную управлять выделением памяти на OpenCL устройстве.
4. Отсутствие возможности исполнения нескольких OpenCL ядер параллельно.
В рамках данной работы1 были получены перечисленные ниже результаты.
• Реализована поддержка обобщенных атомарных операций.
• Реализована поддержка трансфера обобщенных типов данных, таких как структуры, кортежи и размеченные объединения.
• Улучшена модель управления памятью.
• Реализована возможность параллельного исполнения OpenCL ядер.
• Проведено экспериментальное сравнение предложенной реализации с аналогами.
