Bombyx: Компиляция OpenCilk для аппаратного ускорения FPGA

Основная информация

• ID статьи: 2511.21346
• Название: Bombyx: OpenCilk Compilation for FPGA Hardware Acceleration
• Авторы: Mohamed Shahawy, Julien de Castelnau, Paolo Ienne (École Polytechnique Fédérale de Lausanne)
• Категория: cs.AR (Компьютерная архитектура)
• Дата публикации: 26 ноября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2511.21346

Аннотация

В данной работе предлагается Bombyx — набор инструментов для компиляции программ OpenCilk в аппаратные ускорители FPGA. Bombyx преобразует неявную модель параллелизма задач OpenCilk в явное представление передачи продолжений (continuation-passing) в стиле Cilk-1, которое лучше подходит для потоковых характеристик FPGA. Инструмент поддерживает несколько целей компиляции: среду выполнения, совместимую с OpenCilk, для верификации, а также генератор синтезируемых обрабатывающих модулей для инструментов высокоуровневого синтеза, таких как Vitis HLS. Кроме того, Bombyx вводит оптимизацию развязывания доступа к памяти и выполнения (DAE), которая автоматически генерирует высокопроизводительные обрабатывающие модули, повышая перекрытие памяти-вычисления и общую пропускную способность.

Исследовательский контекст и мотивация

1. Основная проблема

Параллелизм уровня задач (TLP) — широко используемая техника параллелизма в программном обеспечении, позволяющая динамически создавать и планировать независимые задачи во время выполнения. Хотя существуют аппаратные фреймворки (такие как ParallelXL и HardCilk), поддерживающие TLP на FPGA, отсутствуют автоматизированные инструменты для извлечения и компиляции кода обрабатывающих модулей (PE) из фреймворков TLP программного обеспечения. Существующие фреймворки обычно требуют, чтобы пользователи вручную предоставляли код PE, что является утомительным и подверженным ошибкам.

2. Значимость проблемы

• Потребность в автоматизации: Перенос приложений TLP, ориентированных на CPU, на FPGA требует значительных ручных работ, включая переструктурирование кода, адаптацию аппаратных интерфейсов, генерацию файлов конфигурации и т. д.
• Оптимизация производительности: Вручную написанный код сложно применять к продвинутым аппаратным оптимизациям (таким как развязывание доступа к памяти и выполнения)
• Эффективность разработки: Отсутствие автоматизированного набора инструментов препятствует широкому применению TLP в ускорении FPGA

3. Ограничения существующих подходов

• Неявная модель OpenCilk: Модель fork-join с использованием cilk_spawn и cilk_sync требует переключения контекста в точках синхронизации. Реализация переключения контекста в аппаратном обеспечении требует сохранения всего состояния схемы, что не поддерживается напрямую текущими инструментами HLS и требует значительной работы с RTL
• Промежуточное представление TAPIR: OpenCilk использует TAPIR, который использует низкоуровневые конструкции компилятора, что затрудняет генерацию читаемого кода C++, близкого к исходному коду, для HLS
• Ручное написание PE: Требует ручной обработки выравнивания замыканий, интерфейсов буфера записи, генерации файлов конфигурации и других утомительных деталей

4. Исследовательская мотивация

Явная модель передачи продолжений Cilk-1 лучше подходит для реализации на аппаратном обеспечении, поскольку она разделяет функции в точках синхронизации на завершающие функции (выполняемые атомарно, без необходимости переключения контекста). Хотя эта модель не очень интуитивна для программирования на программном обеспечении (и поэтому была исключена в эволюции Cilk), она естественна для реализации на аппаратном обеспечении. Цель Bombyx — автоматизировать преобразование из OpenCilk в явный TLP и генерировать оптимизированные аппаратные PE.

Основные вклады

1. Автоматизированный процесс компиляции: Предложен полный автоматизированный набор инструментов компиляции Bombyx от OpenCilk к аппаратным ускорителям FPGA
2. Явное промежуточное представление: Разработано явное и неявное IR на основе графа управления потоком, реализующее автоматическое преобразование из модели fork-join в модель передачи продолжений
3. Генерация кода для нескольких целей:
   • Бэкэнд HardCilk: автоматическая генерация синтезируемого кода C++ HLS и файлов конфигурации
   • Слой эмуляции Cilk-1: верификация корректности преобразования с использованием среды выполнения OpenCilk
4. Оптимизация развязывания доступа к памяти и выполнения: Поддержка оптимизации DAE через директивы компилятора (pragma), разделение доступа к памяти и вычислений на различные задачи, повышение производительности аппаратного обеспечения
5. Экспериментальная верификация: На эталонных тестах обхода графа оптимизация DAE достигает сокращения времени выполнения на 26,5%

Подробное описание метода

Определение задачи

Входные данные: Программы параллелизма задач C/C++ с использованием OpenCilk (ориентированные на CPU)
Выходные данные:

• Синтезируемый код C++ HLS (для генерации PE FPGA)
• Файлы конфигурации системы HardCilk (формат JSON)
• Или исполняемый код в стиле Cilk-1 (для верификации)

Ограничения:

• Программа должна соответствовать модели fork-join OpenCilk
• Зависимости между функциями должны быть явно выражены через cilk_spawn и cilk_sync

Проектирование общей архитектуры

Процесс компиляции Bombyx включает три основных этапа (см. рисунок 3):

Исходный код OpenCilk → AST → Неявное IR → Явное IR → Генерация кода
                         ↓              ↓          ↓
                    Фронтэнд Clang   Оптимизация DAE   HardCilk/Cilk-1

1. Преобразование AST в неявное IR

• Использование фронтэнда Clang OpenCilk для генерации абстрактного синтаксического дерева
• Преобразование AST в представление графа управления потоком (CFG) неявного IR
• Каждой функции соответствует CFG, содержащий:
  • Уникальный входной блок (без входящих ребер)
  • Один или несколько выходных блоков (без исходящих ребер)
  • Базовые блоки, состоящие из последовательных операторов C, завершающихся операторами управления потоком

Почему не использовать TAPIR: TAPIR использует низкоуровневые конструкции (такие как φ-узлы, alloca и т. д.), что затрудняет генерацию читаемого кода C++, близкого к исходному коду. IR Bombyx сохраняет структуру исходного кода.

2. Преобразование неявного IR в явное IR

Это ключевой этап преобразования Bombyx, преобразующий неявную модель синхронизации OpenCilk в явную модель передачи продолжений Cilk-1.

Ключевые концепции:

• Замыкание (Closure): Структура данных, представляющая задачу, содержащая:
  • Готовые параметры
  • Заполнители, ожидающие зависимостей
  • Указатель возврата
• spawn_next: Создание задачи продолжения, ожидающей зависимостей
• send_argument: Явная запись параметра в ожидающее замыкание и уведомление планировщика

Алгоритм преобразования:

1. Разделение пути: Обход CFG, начало нового пути при встрече с блоком завершения функции (return) или операцией sync
   • Каждый путь становится самостоятельной завершающей функцией
   • Серые области на рисунке 4(c) представляют два пути
2. Идентификация зависимостей: Анализ отношений зависимостей на границе sync
   • Идентификация переменных, которые необходимо использовать после sync (например, x и y на рисунке 1)
   • Эти переменные должны быть явно сохранены в полях замыкания
3. Замена ключевых слов:
   • Вставка объявления замыкания в точку вызова spawn
   • Замена sync на вызов spawn_next функции-преемника
   • Изменение возвращаемого значения spawn на явную запись в поле замыкания
   • Сохранение оператора return, который позже может быть преобразован в send_argument

Пример преобразования (рисунок 1 в рисунок 2):

// Неявное (OpenCilk)
int x = cilk_spawn fib(n-1);
int y = cilk_spawn fib(n-2);
cilk_sync;
return x + y;

// Явное (Cilk-1)
cont int x, y;
spawn_next sum(k, ?x, ?y);  // Создание задачи продолжения
spawn fib(x, n-1);           // Запись в заполнитель x
spawn fib(y, n-2);           // Запись в заполнитель y
// Завершение функции, sync не требуется

Генерация бэкэнда HardCilk

HardCilk — это генератор архитектуры FPGA TLP с открытым исходным кодом, предоставляющий аппаратный планировщик кража работы. Bombyx автоматически генерирует все компоненты, необходимые для HardCilk:

1. Выравнивание замыканий

• Автоматическое добавление заполнения для выравнивания размера замыкания до 128/256 бит
• Облегчает реализацию на аппаратном обеспечении

2. Интерфейс буфера записи

• HardCilk использует модуль буфера записи для обработки spawn_next и send_argument
• Bombyx автоматически вставляет необходимые метаданные (тип задачи, целевой адрес и т. д.)

3. Генерация конфигурации JSON

Автоматическая генерация файла описания системы посредством статического анализа, содержащего:

• Размер замыкания
• Отношения spawn/spawn_next/send_argument между задачами
• Другие параметры конфигурации системы

Оптимизация развязывания доступа к памяти и выполнения (DAE)

Мотивация

В наивной реализации PE один модуль отвечает как за инициирование запросов в память, так и за выполнение вычислений, что приводит к:

• Простою PE при остановке памяти
• Снижению общей пропускной способности

Традиционный конвейер в инструментах HLS (таких как Vitis) имеет ограничения:

• Невозможность обработки циклических границ с зависимостями данных
• Статический планировщик не может определить, когда планировать доступ к памяти

Решение DAE

В условиях TLP разделение доступа к памяти и выполнения на различные задачи:

• Задача доступа к памяти: Специально отвечает за запросы в память
• Задача выполнения: Обрабатывает логику вычисления
• Планировщик задач: Координирует выполнение, реализует гибкий конвейер

Способ реализации

Направление компилятора через pragma:

#PRAGMA BOMBYX DAE
struct node_t nd = *n;  // Операция доступа к памяти
// Последующий код становится задачей выполнения

Компилятор автоматически:

1. Извлекает аннотированную строку в независимую функцию (задача доступа к памяти)
2. Заменяет на вызов spawn
3. Вставляет sync
4. После преобразования в явную форму задача доступа к памяти порождает продолжение задачи выполнения

Экспериментальная установка

Эталонные тесты

Программа обхода графа (рисунок 5):

• Параллельный обход графа в ширину
• Доступ к списку смежности узла (интенсивное использование памяти)
• Рекурсивный параллельный доступ к соседним узлам

Наборы данных

Синтетически сгенерированные графы в виде деревьев:

• График 1: Глубина D=7, коэффициент ветвления B=4, всего 5 461 узел
• График 2: Глубина D=9, коэффициент ветвления B=4, всего 87 381 узел
• Расчет количества узлов: $\frac{B^D - 1}{B - 1}$

Конфигурация эксперимента

• Платформа FPGA: Xilinx Alveo U55C (xcu55c-fsvh2892-2L-e)
• Инструмент синтеза: Vivado 2024.1
• Целевая частота: 300 МГц
• Количество PE:
  • Non-DAE: 1 PE
  • DAE: 3 PE (по одному для spawner, executor и access)

Показатели оценки

1. Время выполнения: Время, необходимое для обхода всего графа
2. Использование ресурсов:
   • LUT (таблицы поиска)
   • FF (триггеры)
   • BRAM (блочная оперативная память)

Результаты экспериментов

Основные результаты производительности

• Сокращение времени выполнения: Оптимизация DAE достигает повышения производительности на 26,5%
• Благодаря развязыванию доступа к памяти и выполнения повышается перекрытие памяти-вычисления

Анализ использования ресурсов

Затраты на ресурсы:

• Увеличение LUT на 47% (2 657 → 3 896)
• Увеличение FF на 50% (2 305 → 3 464)
• Удвоение BRAM (2 → 4)

Экспериментальные выводы

1. Компромисс производительность-ресурсы: Повышение производительности на 26,5% за счет примерно 50% увеличения ресурсов является разумным компромиссом для приложений, интенсивно использующих память
2. Анализ размера PE:
   • Spawner + Executor ≈ размер одного PE Non-DAE
   • Задача Access занимает дополнительные ресурсы
   • Рекомендация: использование PE с параллелизмом данных, реализованного на RTL, может распределить стоимость задачи доступа к памяти
3. Потенциал оптимизации: В статье указывается, что в будущем задача доступа к памяти может быть интегрирована как примитив черного ящика, а не генерироваться с использованием HLS

Связанные работы

Фреймворки TLP программного обеспечения

1. Intel Thread Building Blocks (TBB): Широко используемая в промышленности библиотека параллелизма задач
2. Cilk Plus: Расширение Cilk от Intel
3. OpenCilk: Последний фреймворк Cilk, превосходящий по производительности предыдущие фреймворки

Фреймворки TLP аппаратного обеспечения

1. ParallelXL: Ранняя архитектура TLP на FPGA
2. HardCilk: Целевая платформа Bombyx, открытая система FPGA TLP, предоставляющая аппаратный планировщик кража работы

Эволюция Cilk

1. Cilk-1: Ранняя версия, принявшая явную передачу продолжений
2. Последующие версии: Переход к неявной модели fork-join (более подходящей для программирования на программном обеспечении)
3. Теоретическая база: Доказано, что любая неявная программа может быть преобразована в явную форму

Преимущества данной работы

• Первый автоматизированный инструмент: Полный автоматизированный процесс от OpenCilk к PE FPGA
• Явное преобразование: Использование стиля Cilk-1 для избежания дорогостоящего переключения контекста на аппаратном обеспечении
• Поддержка оптимизации: Интеграция оптимизаций, специфичных для аппаратного обеспечения, таких как DAE

Заключение и обсуждение

Основные выводы

1. Bombyx успешно реализует автоматизированный процесс компиляции от OpenCilk к аппаратному обеспечению FPGA
2. Явная модель передачи продолжений подходит для потоковых характеристик FPGA, избегая дорогостоящего переключения контекста
3. Оптимизация DAE достигает повышения производительности на 26,5% на эталонном тесте обхода графа
4. Инструмент может быть расширен на другие фреймворки аппаратного TLP

Ограничения

1. DAE оптимизация требует ручного направления: В настоящее время требуется вставка pragma программистом, полная автоматизация не реализована
2. Ограниченная оценка:
   • Оценка проведена только на одном эталонном тесте (обход графа)
   • Отсутствует сравнение с другими методами (например, вручную написанный код, другие компиляторы)
   • Не протестированы более разнообразные сценарии приложений
3. Затраты на ресурсы: Оптимизация DAE приводит к примерно 50% увеличению ресурсов, что может ограничить крупномасштабные системы
4. Реализация задачи доступа к памяти: Использование HLS для генерации PE доступа к памяти неэффективно, рекомендуется использование RTL, но не реализовано
5. Зрелость инструмента: Как исследовательский прототип, отсутствует полная обработка ошибок и поддержка граничных случаев

Направления будущих исследований

1. Автоматическое определение DAE: Разработка анализа компилятора для автоматического определения кодовых паттернов, подходящих для оптимизации DAE
2. RTL модули доступа к памяти: Интеграция эффективных реализаций на RTL модулей доступа к памяти с параллелизмом данных
3. Дополнительные оптимизации: Исследование других оптимизаций, специфичных для аппаратного обеспечения (например, переиспользование данных, оптимизация локальности)
4. Расширение целей: Поддержка большего количества фреймворков аппаратного TLP и инструментов HLS
5. Полная оценка: Оценка на большем количестве эталонных тестов, включая различные типы приложений TLP

Глубокая оценка

Преимущества

1. Инновационность метода

• Уникальная стратегия преобразования: Умелое использование явной модели передачи продолжений Cilk-1 для решения проблемы переключения контекста на аппаратном обеспечении
• Ценность автоматизации: Первая реализация полного автоматизированного набора инструментов от OpenCilk к FPGA, заполняющая важный пробел
• Разумное проектирование IR: Дизайн IR, сохраняющий структуру исходного кода, делает сгенерированный код HLS более читаемым

2. Инженерный вклад

• Высокая практичность: Автоматизация обработки выравнивания замыканий, интерфейсов буфера записи, генерации файлов конфигурации и других утомительных деталей
• Верифицируемость: Предоставление слоя эмуляции Cilk-1 для верификации корректности преобразования, повышение надежности инструмента
• Дружественность к открытому исходному коду: Целевой HardCilk — это система с открытым исходным кодом, что способствует распространению инструмента

3. Технические идеи

• Сотрудничество аппаратного и программного обеспечения: Глубокое понимание проблемы адаптации модели TLP программного обеспечения к реализации на аппаратном обеспечении
• Оптимизация DAE: Сочетание классической аппаратной оптимизации с TLP, демонстрирующее потенциал оптимизации, направляемой компилятором

4. Ясность изложения

• Четкое представление неявного-явного преобразования через пример Fibonacci
• Интуитивное и легко понимаемое сравнение IR на рисунке 4
• Четкая диаграмма процесса компиляции

Недостатки

1. Недостаточные эксперименты

• Единственный эталонный тест: Оценка только обхода графа, невозможно полностью проверить универсальность инструмента
• Отсутствие сравнения: Нет сравнения с вручную написанным кодом, другими методами компиляции
• Ограниченный масштаб: Протестированные графы относительно небольшие (максимум 87K узлов)
• Неглубокий анализ производительности: Не проанализированы конкретные источники повышения производительности (использование полосы пропускания, эффективность планирования задач и т. д.)

2. Ограничения метода

• Полуавтоматическая оптимизация DAE: Требуется ручное pragma, ограничивает удобство использования
• Ограниченное пространство оптимизации: Демонстрируется только одна оптимизация (DAE), не исследуются другие аппаратные оптимизации
• Большие затраты на ресурсы: 50% увеличение ресурсов может ограничить практическое применение

3. Отсутствие технических деталей

• Неполный алгоритм преобразования: Недостаточно подробное описание анализа зависимостей, выбора полей замыкания и других ключевых алгоритмов
• Гарантии корректности: Отсутствует формальное доказательство или систематический метод верификации
• Граничные случаи: Не обсуждается обработка рекурсии, указателей, сложных структур данных

4. Глубина оценки

• Масштабируемость неизвестна: Не протестированы крупномасштабные приложения или сложные потоки управления
• Универсальность под вопросом: Является ли обход графа репрезентативным для типичных приложений TLP?
• Расстояние от теории: Является ли повышение производительности на 26,5% близким к теоретическому пределу?

Влияние

1. Вклад в область

• Заполнение пробела в инструментах: Предоставление важной инфраструктуры для применения TLP на FPGA
• Вдохновение для последующих исследований: Идея явного преобразования может быть применена к другим моделям параллелизма
• Продвижение аппаратного TLP: Снижение барьера входа, способствование распространению TLP в ускорении FPGA

2. Практическая ценность

• Средняя практичность: Прямая ценность для пользователей HardCilk, но требуется дальнейшее совершенствование
• Стоимость обучения: Все еще требуется понимание концепций TLP и ограничений аппаратного обеспечения
• Готовность к производству: Как исследовательский прототип, требуется дальнейшее развитие для производственного использования

3. Воспроизводимость

• Средняя: Зависит от набора инструментов OpenCilk, HardCilk, Vitis HLS и т. д.
• Код не открыт: В статье не упоминается план открытия исходного кода
• Достаточные детали реализации: Предоставлены достаточные детали реализации и экспериментов

Применимые сценарии

Подходящие сценарии

1. Приложения с динамическим параллелизмом задач: Алгоритмы графов, обход деревьев, динамическое программирование и т. д.
2. Вычисления, интенсивно использующие память: Оптимизация DAE особенно подходит для приложений с узким местом доступа к памяти
3. Пользователи HardCilk: Разработчики, уже использующие или планирующие использовать HardCilk
4. Быстрое прототипирование: Требуется быстрый перенос кода TLP CPU на FPGA

Неподходящие сценарии

1. Регулярный параллелизм: Параллелизм данных, конвейеризация и другие сценарии, не требующие динамического планирования
2. Ресурсоограниченные системы: 50% увеличение ресурсов может быть неприемлемым
3. Экстремальная производительность: Вручную оптимизированный RTL может быть более эффективным
4. Сложные паттерны доступа к памяти: Поддержка инструментом сложных указателей, динамической памяти неизвестна

Рекомендации по улучшению

1. Расширение оценки: Добавление большего количества эталонных тестов (сортировка, поиск, научные вычисления и т. д.)
2. Сравнение производительности: Сравнение с вручную написанным кодом HLS, реализацией на CPU, реализацией на GPU
3. Автоматизация DAE: Разработка анализа компилятора для автоматического определения возможностей оптимизации DAE
4. Разнообразие оптимизаций: Исследование дополнительных аппаратных оптимизаций (переиспользование данных, локальное кэширование и т. д.)
5. Формальная верификация: Предоставление формальных гарантий корректности преобразования
6. Открытие исходного кода: Открытие инструмента для содействия вкладам сообщества и верификации

Ключевые ссылки

Основные цитируемые работы:

1. 2 OpenCilk (PPoPP'23): Последний фреймворк Cilk, входной язык Bombyx
2. 4 HardCilk (FCCM'24): Целевая платформа Bombyx, предыдущая работа авторов
3. 5 Cilk-1 (SIGPLAN'95): Классическая система явной передачи продолжений TLP, теоретическая основа Bombyx
4. 6 Диссертация Joerg (1996): Доказательство теоретической возможности преобразования неявного в явное

Общая оценка: Bombyx — это ценная исследовательская работа, заполняющая важный пробел в автоматизированном наборе инструментов от OpenCilk к аппаратному ускорению FPGA. Его основная инновация заключается в использовании явной модели передачи продолжений Cilk-1 для избежания дорогостоящего переключения контекста на аппаратном обеспечении и предоставлении полного процесса компиляции. Однако, как предварительная работа, статья имеет явные недостатки в широте и глубине экспериментальной оценки, а полуавтоматическая оптимизация DAE ограничивает удобство использования. Инструмент имеет прямую ценность для пользователей HardCilk и исследователей TLP, но требует дальнейшего совершенствования для широкого применения. Рекомендуется, чтобы последующие работы сосредоточились на автоматизированном определении оптимизации, расширении оценки эталонных тестов и открытии исходного кода для содействия верификации и улучшению сообществом.