В данной статье будет рассказано о попытке ускорить операции над разреженными булевыми матрицами, реализованные на OpenCL, с помощью замены целевой платформы GPGPU на FPGA.
Эта задача возникла при работе над библиотекой примитивов линейной алгебры, необходимых для решения некоторых задач анализа графов. Данные, структурированные в виде графов, играют огромную роль в современной жизни и встречаются в таких областях, как социальные сети, транспортные и коммуникационные сети, являются основой для набирающих популярность графовых баз данных.
Объем таких данных неуклонно растет и потому для получения хорошей производительности в задачах анализа графов все острее встает вопрос о разработке параллельных алгоритмов, что оказывается нетривиальной задачей из-за нерегулярности данных.
Одним из подходов к решению такой проблемы является использование линейной алгебры: граф естественным образом представим в виде матрицы (например, матрицы смежности), а задача выражается через операции над матрицами и векторами. Например, построение транзитивного замыкания и поиск кратчайших путей могут быть выражены через произведение и поэлементную сумму матриц смежности в различных полукольцах (булевом и min-plus соответственно).
Данную идею развивает стандарт GraphBLAS, описывающий набор примитивов и операций линейной алгебры, необходимый для реализации различных алгоритмов анализа графов. Этот стандарт определяет операции над произвольными моноидами и полукольцами и его реализация на массово-параллельных платформах является нетривиальной инженерной задачей. Поэтому в данной работе мы сконцентрировались на важном частном случае, на булевой линейной алгебре.
Важным аспектом прикладных задач является то, что реальные графы сильно разрежены: в случае представления их в виде матрицы смежности большинство ячеек окажутся пустыми. Это выдвигает дополнительные требования к реализации операций, так как матрицы должны храниться в специализированных форматах для экономии памяти.
Одной из естественных платформ для реализации операций разреженной линейной алгебры является GPGPU, что подтверждается, например, такими библиотеками, как cuSparse, clSparse и др. Однако, данные библиотеки реализуют операции над такими типами данных, как float или double, что является избыточным при работе с булевыми матрицами. Более того, ряд операций, необходимых при анализе графов (например, произведение Кронекера) в них не представлен. Потому нами была реализована библиотека разреженной булевой линейной алгебры. Языком разработки был выбран OpenCL C для того, чтобы обеспечить максимальную переносимость решения.
Выбор стандарта OpenCL позволил нам рассматривать в качестве целевой платформы не только CPU и GPGPU, но и FPGA, благодаря наличию таких решений, как «Intel FPGA SDK for OpenCL» или SDAccel Environment от Xilinx. Создание программы для FPGA – это прежде всего разработка архитектуры, на которой программа работает наиболее эффективно, а подобные инструменты позволяют использовать FPGA как еще одно устройство для исполнения OpenCL-кода, снимая с разработчика задачу создания архитектуры.
И хотя производители инструментов часто описывают процесс разработки как «написал код, отладил на GPU, запустил на FPGA», вопрос об эффективности результирующего решения без адаптации кода под специфику FPGA в ряде случаев остается открытым.
Наш случай один из таких. Таким образом, нам было необходимо выяснить, можно ли с помощью использования FPGA в качестве целевой платформы повысить производительность библиотеки операций разреженной линейной алгебры. При этом необходимо максимально переиспользовать уже существующий OpenCL-код, эффективно работающий на GPGPU.
Что такое FPGA
Ядром FPGA как устройства является перепрограммируемая логическая матрица (ПЛИС, программируемая логическая интегральная схема), что позволяет изменять логику работы устройства (чипа) и предоставляет разработчику (и пользователю) «мягкий» (изменяемый) чип. Этим ПЛИС принципиально отличаются от «жестких» систем, таких как, например, центральный процессор или графический сопроцессор, низкоуровневая логика работы которых (архитектура) задана единожды при производстве и не может быть изменена в процессе использования.
Схема матрицы представлена на рисунке ниже. Матрица состоит из набора программируемых логических ячеек, поведение которых, как правило, задается таблицами истинности, и программируемых коммутаторов, соединяющих эти ячейки, что позволяет управляемо собирать более сложные функции из простых.
Стоит отметить, что современные ПЛИС содержат не только программируемые логические блоки, но и набор предопределенных блоков с более сложными функциями, которые зависят от специфики устройства. Например, большинство ПЛИС содержат мультиплексоры для целых чисел и даже для чисел с плавающей запятой. Такие операции часто используются в различных устройствах и алгоритмах и нет смысла каждый раз программировать их заново и тратить на это логические блоки.
В современном мире можно выделить две больших, частично пересекающихся, группы устройств, именуемых FPGA. Первая категория — это так называемые отладочные платы и дизайн-платы, предназначенные прежде всего для разработки архитектуры новых устройств и ее отладки перед выпуском в серийное производство. Вторая — так называемые FPGA-ускорители, предназначенные для ускорения определенных задач и в чем-то схожие по своим задачам с GPGPU.
Такие ускорители, как и GPGPU, как правило являются специализированными сопроцессорами основного, центрального, процессора и предназначены для того, чтобы быстро решать конкретную, часто достаточно узкую задачу, а взаимодействие с ними на высоком уровне схоже с работой с GPGPU и представлено на рисунке ниже. В нашей задаче нас будет интересовать именно вторая категория, так как мы хотим использовать FPGA как ускоритель для операций линейной алгебры.
Custom Core — ядра сконфигурированные для решения конкретной задачи
Изначально для программирования логической матрицы использовались низкоуровневые языки типа VHDL и Verilog, которые предназначались прежде всего для описания архитектуры устройства и логики его работы, для чего и используются по сей день. Однако, когда речь идет об использовании FPGA как ускорителя, возникает потребность в том, чтобы описывать прикладную задачу, для чего указанные языки оказываются слишком низкоуровневыми.
Дабы устранить данную проблему, в настоящее время активно развиваются инструменты, позволяющие использовать OpenCL C для программирования FPGA. Несмотря на то, что предлагаемый язык С-подобен и в известном смысле является низкоуровневым, это существенно упрощает разработку, так как позволяет программировать в более привычных для прикладного разработчика терминах.
Конечно, за повышение уровня абстракции приходится платить, в частности, уменьшением уровня контроля и, возможно, уменьшением производительности решения. Однако, история развития языков программирования показывает, что качественная инструментальная поддержка процесса разработки, хорошие компиляторы, и плюсы высокого уровня абстракции в некоторых сферах позволяют нивелировать незначительные потери в производительности.
В нашем случае для эксперимента использовался набор инструментов Intel FPGA SDK for OpenCL, и плата от Euler Project с установленным чипом Arria 10. А цель как раз и заключалась в том, чтобы выяснить, даст ли использование данного стека технологий возможность получить высокопроизводительное и переносимое решение для разреженной линейной алгебры.
Разреженная линейная алгебра
Как было сказано, одной из особенностей разрабатываемой библиотеки является работа с разреженными структурами данных. В частности, для матриц был выбран формат DCSR — модификация классического CSR (Compressed Sparse Row), предназначенная для сильно разреженных матриц.
В качестве основных операций были выбраны поэлементное сложение двух матриц и классическое умножение, как операции, наиболее часто используемые в прикладных алгоритмах, и наиболее нетривиальные с точки зрения получения высокопроизводительных реализаций (особенно это касается умножения).
Для умножения разреженных матриц на GPGPU разработано множествоалгоритмов и лидирующими по производительности на сегодняшний день являются алгоритмы В. Лю (основанный на слиянии) и Ю. Нагасака (использующий хэш-таблицы). Оба этих алгоритма были реализованы на OpenCL и в результате экспериментов было выяснено, что алгоритм Ю. Нагасака на GPGPU работает быстрее, чем алгоритм В. Лю на интересных для нас данных. В дальнейшем необходимо было оценить их производительность при использовании FPGA в качестве целевой платформы.
Для сложения матриц используется перевод в координатный формат, в котором сложение сводится к объединению двух упорядоченных массивов. Возможности по ускорению этой операции с использованием FPGA также было решено оценить в рамках эксперимента.
Особенности реализации
Хотя мы говорим о том, чтобы использовать для разработки под FPGA уже привычный и знакомый стандарт OpenCL и соответствующий язык программирования, есть ряд особенностей, которые необходимо учитывать при запуске уже имеющегося кода, отлаженного на GPU, на FPGA.
Первая особенность связана с необходимостью статической компиляции для FPGA. Стандарт OpenCL подразумевает распространение программ в виде исходных кодов и компиляцию драйвером конкретного устройства при обращении, что реализовано для большинства GPGPU и чем активно пользуются разработчики, формируя код ядер и компилируя их по ходу выполнения основной программы (хоста). Однако, чтобы запустить код на FPGA, необходима предварительная компиляция, что может потребовать изменений как в кода хоста, так и в кода ядер.
Для компиляции ядер используется компилятор aoc, который в связке с «Intel® Quartus® Prime» создает бинарный файл с описанием архитектуры логической матрицы. Необходимо иметь ввиду, что данный этап очень ресурсозатратный: процесс компиляции небольшого ядра для поэлементного сложения двух векторов может занимать около 40 минут, более сложные ядра, вроде тех, которые возникли в нашей задачи, компилировались порядка 4–6 часов.
Следующий важный момент заключается в том, что результат компиляции не просто «выполняется» FPGA, а фактически перепрограммирует ее. При этом один файл описывает одну конфигурацию. А это означает, во-первых, что загрузка бинарного файла на FPGA занимает существенное время (около секунды в нашем случае), что, например, делает нерациональным использование нескольких файлов для одной матричной операции. Во-вторых, единовременно на FPGA может быть загружен один такой файл. Что приводит к желанию компилировать как можно больше ядер в один бинарный файл.
Однако, чем больше ядер обрабатываются за один вызов компилятора, тем сложнее ему распределить ресурсы FPGA для их выполнения этих ядер. Более того, ресурсы FPGA ограничены, что также ограничивает количество ядер, которые могут компилироваться, а значит и выполняться, одновременно.
Так, например, умножение с хэш-таблицами (алгоритм Нагасака) содержит 16 различных ядер, но и такое количество не удалось скомпилировать на устройстве из-за недостатка ресурсов. Типичное предупреждение в таком случае — предупреждения о превышении допустимых ресурсов памяти:
>aoc: Warning RAM Utilization is at 345%!Большое количество ядер в умножении связано с группировкой рядов матрицы по ожидаемым вычислительным затратам. Мы сокращали количество групп, пока процесс компиляции не завершился успешно. Сложение требует значительно меньшего числа ядер, и его удалось запустить без существенных изменений.
Эксперименты
Для экспериментов были выбраны квадратные матрицы из SuiteSparse Matrix Collection различного размера и различной степени заполненности. Характеристики матриц приведены в таблице 2 (Nnz — Number of Non Zeroes, количество ненулевых элементов). Умножение тестировалось на возведении матрицы в квадрат, а сложение на вычислении суммы матрицы со своим квадратом, где квадрат заранее предпросчитан.
Для возможности оценить эффект от использования FPGA, эксперименты были проведены как на FPGA (Intel® Arria® 10), так и на GPGPU (AMD Radeon Vega Frontier Edition). Детальные характеристики оборудования, на котором производились измерения, представлены в таблице 1.
| Вендор | AMD | Intel |
|---|---|---|
| Имя | Radeon Vega Frontier Edition | Arria® 10 |
| Глобальная память, Gb | 15,98 | 8 |
| Локальная память, Kb | 64 | 16 |
| Макс. размер блока | 256 | 2147483647 |
| Частота, MHz | 1600 | 1000 |
| Число АЛУ | 4096 | 427200 |
Необходимо отметить, что указанная для FPGA частота — это максимальная частота тактового генератора. Реальная частота зависит от выполняемого кода и в нашем случае, по информации, полученной от компилятора (статистика Kernel clock), для сложения и умножения составляет порядка 240 MHz.
Отметим, что при экспериментах измерялось время работы «клиентской» функции, то есть время необходимое на передачу данных на FPGA и обратно включается в замеры. Аналогично и для GPU. Результаты экспериментов показаны в таблице 2. Время измерялось в миллисекундах. Прочерк означает, что не удалось дождаться завершения вычислений за разумное время.
| Сложение (мс) | Умножение (мс) | ||||||
|---|---|---|---|---|---|---|---|
| № | Число строк, млн | Nnz(M), млн | Nnz(M + M2), млн | GPGPU | FPGA | GPGPU | FPGA |
| 1 | 0,06 | 0,24 | 0,92 | 1,71 ± 0,30 | 86,51 | 2,78 ± 1,46 | 5590,79 |
| 2 | 0,11 | 0,24 | 0,39 | 1,32 ± 0,12 | 58,54 | 2,43 ± 0,25 | 9824,65 |
| 3 | 0,40 | 3,20 | 14,97 | 11,43 ± 3,18 | 1572,83 | 38,60 ± 3,92 | 40527,5 |
| 4 | 0,74 | 5,16 | 26,40 | 17,19 ± 4,59 | 2714,14 | 55,65 ± 6,07 | 67595,9 |
| 5 | 0,92 | 5,11 | 30,81 | 19,34 ± 4,68 | 3077,81 | 85,97 ± 8,78 | 77601,9 |
| 6 | 1,09 | 3,08 | 9,93 | 7,92 ± 2,58 | 944677 | 19,75 ± 1,27 | 96978,8 |
| 7 | 1,39 | 3,84 | 12,26 | 9,01 ± 2,68 | 1167,12 | 23,29 ± 1,68 | 122992 |
| 8 | 1,44 | 3,10 | 8,41 | 6,78 ± 2,59 | 771219 | 23,08 ± 1,84 | 126465 |
| 9 | 1,97 | 5,53 | 17,74 | 11,89 ± 3,23 | 1686,66 | 29,35 ± 1,65 | 175612 |
| 10 | 2,22 | 4,88 | 13,63 | 9,27 ± 2,81 | 1248,45 | 29,66 ± 0,85 | - |
Как видно из результатов экспериментов, код, ориентированный на особенности GPU, оказался неэффективен на устройстве с совершенно другой архитектурой. Здесь, правда, нужно учесть, что при работе с разреженными матрицами и на видеокартах не происходит полной утилизации мощности устройства.
Результаты, которых удалось добиться сообществу к настоящему моменту — это итог многих лет развития алгоритмов для работы с разреженными матрицами и экспериментов с распределением нагрузки, способами обработки строк.
Чтобы выявить причину столь существенного замедления, были отдельно проанализированы все этапы алгоритмов. Одним из самых слабых мест оказалась префиксная сумма, которая используется как в сложении, так и в умножении. Например, на массиве размером 10^7 элементов данная операция занимает в среднем 253 мс, тогда как даже центральный процессор может выполнить данную операцию за 79 мс (при неоптимизированной реализации).
К сожалению, нам не удалось найти реализацию префиксной суммы для FPGA, которая была бы сравнима с GPU по производительности, и, судя по возникающим в сообществе вопросам, эта проблема все еще остается открытой.
Выводы
Проведенный эксперимент показал, что создание переносимой библиотеки для разреженной линейной алгебры на OpenCL C хотя и возможно, но в текущих реалиях использование FPGA как целевой платформы не дает выигрыша в производительности. При этом, необходимо обратить внимание на следующие важные моменты.
Во-первых, эффективная реализация операций разреженной линейной алгебры — область, в которой до сих пор ведутся работы даже для таких более привычных платформ, как многоядерные CPU и GPGPU. Создание подобных решений для FPGA — область, в которой ведуться активные исследования («The algorithms for FPGA implementation of sparse matrices multiplication», «SpArch: Efficient Architecture for Sparse Matrix Multiplication»), и на текущий момент с использованием более низкоуровневых средств.
Во-вторых, проведенный эксперимент показал зрелость стека технологий, применяемого для разработки под FPGA с использованием OpenCL C: реализованные в ходе эксперимента современные алгоритмы сложения и умножение разреженных матриц весьма сложны и достаточно объемны на фоне, например, реализации сверточных фильтров.
Отдельно необходимо отметить, что, хотя мы и говорим об использовании стандарта OpenCL, в действительности, для повышения эффективности разрабатываемых решений, для FPGA, как Intel, так и Xilinx предоставляют специфичные расширения языка. Вместе с этим, существуют и специфичные техники оптимизации кода, уместные для FPGA, но вряд ли применимые, например, для GPGPU.
Таким образом, технология уже достаточно зрелая, чтобы использовать ее для решения реальных задач. Необходимо только аккуратно проанализировать особенности предметной области и конкретной решаемой задачи. Так, существует ряд вычислительных задач, которые одинаково хороши как для видеокарт, так и для FPGA. Например, обработка изображений и видео. И вот для таких задач переносимые решения, утилизирующие как FPGA, так и GPGPU, уже могут быть разработаны в единой среде с использованием OpenCL C.
Автор текста — Семен Григорьев (Доцент кафедры информатики СПбГУ)
