Тема: Brahma.FSharp как основа для обобщённой разреженной линейной алгебры на GPGPU

Данные, представимые в виде графов, встречаются повсеместно: при анализе компьютерных и социальных сетей, в биоинформатике и статическом анализе кода [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 ядер.
• Проведено экспериментальное сравнение предложенной реализа­ции с аналогами.
Купить