Bombyx: Compilación OpenCilk para Aceleración de Hardware FPGA

Información Básica

• ID del Artículo: 2511.21346
• Título: Bombyx: OpenCilk Compilation for FPGA Hardware Acceleration
• Autores: Mohamed Shahawy, Julien de Castelnau, Paolo Ienne (École Polytechnique Fédérale de Lausanne)
• Clasificación: cs.AR (Arquitectura de Computadores)
• Fecha de Publicación: 26 de noviembre de 2025 (preimpresión en arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2511.21346

Resumen

Este artículo propone Bombyx, una cadena de herramientas que compila programas OpenCilk en aceleradores de hardware FPGA. Bombyx convierte el modelo de paralelismo de tareas implícito de OpenCilk en una representación intermedia de paso de continuaciones explícita al estilo de Cilk-1, más adecuada para las características de flujo de datos de FPGA. La herramienta admite múltiples objetivos de compilación: tiempo de ejecución compatible con OpenCilk para verificación, así como generadores de unidades de procesamiento sintetizables para herramientas de síntesis de alto nivel como Vitis HLS. Además, Bombyx introduce la optimización de Acceso a Memoria-Ejecución Desacoplada (DAE), que genera automáticamente unidades de procesamiento de alto rendimiento, mejorando la superposición memoria-cómputo y el rendimiento general.

Antecedentes de Investigación y Motivación

1. Problema Central a Resolver

El paralelismo a nivel de tareas (TLP) es una técnica de paralelismo ampliamente utilizada en software que permite crear y programar dinámicamente tareas independientes en tiempo de ejecución. Aunque existen marcos de hardware (como ParallelXL y HardCilk) que admiten TLP en FPGA, carece de herramientas automatizadas para extraer y compilar automáticamente código de unidades de procesamiento (PE) a partir de marcos de software TLP. Los marcos existentes generalmente requieren que los usuarios proporcionen manualmente el código PE, lo cual es tedioso y propenso a errores.

2. Importancia del Problema

• Necesidad de Automatización: Portar aplicaciones TLP orientadas a CPU a FPGA requiere un trabajo manual considerable, incluyendo reestructuración de código, adaptación de interfaces de hardware y generación de archivos de configuración
• Optimización de Rendimiento: El código escrito manualmente es difícil de aplicar optimizaciones de hardware avanzadas (como Acceso a Memoria-Ejecución Desacoplada)
• Eficiencia de Desarrollo: La falta de cadenas de herramientas automatizadas obstaculiza la adopción generalizada de TLP en aceleración FPGA

3. Limitaciones de Métodos Existentes

• Modelo Implícito de OpenCilk: El modelo fork-join que utiliza cilk_spawn y cilk_sync requiere cambio de contexto en puntos de sincronización. Implementar cambio de contexto en hardware requiere guardar el estado completo del circuito, lo cual no es directamente soportado por herramientas HLS actuales y requiere ingeniería RTL extensiva
• Representación Intermedia TAPIR: TAPIR, utilizada por OpenCilk, emplea construcciones de compilador de bajo nivel que dificultan generar código C++ legible cercano al código original para HLS
• Escritura Manual de PE: Requiere manejar manualmente alineación de clausuras, interfaces de búfer de escritura, generación de archivos de configuración y otros detalles tediosos

4. Motivación de la Investigación

El modelo explícito de paso de continuaciones de Cilk-1 es más adecuado para implementación en hardware, ya que divide funciones en puntos de sincronización en funciones terminales (que se ejecutan atómicamente sin necesidad de cambio de contexto). Aunque este modelo no es suficientemente intuitivo para programación de software (razón por la cual fue abandonado en la evolución de Cilk), es natural para implementación en hardware. El objetivo de Bombyx es automatizar la conversión de OpenCilk a TLP explícito y generar PE de hardware optimizados.

Contribuciones Principales

1. Proceso de Compilación Automatizado: Propone una cadena de herramientas de compilación completa y automatizada de OpenCilk a aceleradores de hardware FPGA llamada Bombyx
2. Representación Intermedia Explícita: Diseña IR implícita y explícita basada en grafos de flujo de control, implementando conversión automática del modelo fork-join al modelo de paso de continuaciones
3. Generación de Código Multi-Objetivo:
   • Backend HardCilk: Genera automáticamente código C++ HLS sintetizable y archivos de configuración
   • Capa de Simulación Cilk-1: Utiliza tiempo de ejecución OpenCilk para verificar la corrección de la conversión
4. Optimización de Acceso a Memoria-Ejecución Desacoplada: Soporta optimización DAE mediante directivas de compilación (pragma), separando acceso a memoria y cómputo en tareas diferentes, mejorando rendimiento de hardware
5. Verificación Experimental: En pruebas de referencia de recorrido de grafos, la optimización DAE logra una reducción de tiempo de ejecución del 26.5%

Explicación Detallada del Método

Definición de Tareas

Entrada: Programa C/C++ de paralelismo de tareas escrito con OpenCilk (orientado a CPU)
Salida:

• Código C++ HLS sintetizable (para generación de PE FPGA)
• Archivo de configuración del sistema HardCilk (formato JSON)
• O código ejecutable al estilo Cilk-1 (para verificación)

Restricciones:

• El programa debe seguir el modelo fork-join de OpenCilk
• Las dependencias entre funciones deben expresarse explícitamente mediante cilk_spawn y cilk_sync

Diseño de Arquitectura General

El proceso de compilación de Bombyx incluye tres fases principales (ver Figura 3):

Código Fuente OpenCilk → AST → IR Implícita → IR Explícita → Generación de Código
                          ↓              ↓          ↓
                    Frontend Clang   Optimización DAE   HardCilk/Cilk-1

1. Conversión de AST a IR Implícita

• Utiliza el frontend Clang de OpenCilk para generar árbol de sintaxis abstracta
• Convierte AST a representación de grafo de flujo de control (CFG) de IR implícita
• Cada función corresponde a un CFG que contiene:
  • Bloque de entrada único (sin aristas de entrada)
  • Uno o más bloques de salida (sin aristas de salida)
  • Bloques básicos compuestos de sentencias C secuenciales, terminados por sentencias de flujo de control

Por qué no usar TAPIR: TAPIR utiliza construcciones de bajo nivel (como nodos φ, alloca, etc.), lo que dificulta generar código C++ legible cercano al código original. La IR de Bombyx preserva la estructura del código original.

2. Conversión de IR Implícita a IR Explícita

Este es el paso de conversión central de Bombyx, que transforma el modelo de sincronización implícita de OpenCilk al modelo explícito de paso de continuaciones de Cilk-1.

Conceptos Clave:

• Clausura (Closure): Estructura de datos que representa una tarea, conteniendo:
  • Parámetros ya disponibles
  • Marcadores de posición esperando dependencias
  • Puntero de retorno
• spawn_next: Crea una tarea de continuación esperando dependencias
• send_argument: Escribe explícitamente un parámetro en una clausura esperante y notifica al programador

Algoritmo de Conversión:

1. Partición de Rutas: Recorre el CFG, iniciando una nueva ruta al encontrar bloques terminales de función (return) u operaciones de sincronización
   • Cada ruta se convierte en una función terminal autónoma
   • Las regiones grises en la Figura 4(c) representan dos rutas
2. Identificación de Dependencias: Analiza relaciones de dependencia en límites de sincronización
   • Identifica variables necesarias después de sincronización (como x e y en la Figura 1)
   • Estas variables deben almacenarse explícitamente en campos de clausura
3. Reemplazo de Palabras Clave:
   • Inserta declaración de clausura en llamadas spawn
   • Reemplaza sincronización con llamadas spawn_next a funciones sucesoras
   • Cambia valores de retorno de spawn a escritura explícita en campos de clausura
   • Preserva sentencias return, que se pueden convertir posteriormente a send_argument

Ejemplo de Conversión (Figura 1 a Figura 2):

// Implícita (OpenCilk)
int x = cilk_spawn fib(n-1);
int y = cilk_spawn fib(n-2);
cilk_sync;
return x + y;

// Explícita (Cilk-1)
cont int x, y;
spawn_next sum(k, ?x, ?y);  // Crea tarea de continuación
spawn fib(x, n-1);           // Escribe en marcador x
spawn fib(y, n-2);           // Escribe en marcador y
// Función termina, sin necesidad de sincronización

Generación del Backend HardCilk

HardCilk es un generador de arquitectura TLP FPGA de código abierto que proporciona un programador de robo de trabajo de hardware. Bombyx automatiza la generación de todos los componentes requeridos por HardCilk:

1. Alineación de Clausuras

• Añade automáticamente relleno para alinear tamaños de clausura a 128/256 bits
• Facilita la implementación de hardware

2. Interfaz de Búfer de Escritura

• HardCilk utiliza módulo de búfer de escritura para manejar spawn_next y send_argument
• Bombyx inserta automáticamente metadatos requeridos (tipo de tarea, dirección de destino, etc.)

3. Generación de Configuración JSON

Genera automáticamente archivos de descripción del sistema mediante análisis estático, conteniendo:

• Tamaños de clausura
• Relaciones spawn/spawn_next/send_argument entre tareas
• Otros parámetros de configuración del sistema

Optimización de Acceso a Memoria-Ejecución Desacoplada (DAE)

Motivación

En implementación PE ingenua, la misma unidad es responsable de iniciar solicitudes de memoria y ejecutar cómputo, resultando en:

• Estancamiento de memoria que deja PE inactivo
• Reducción de rendimiento general

Las tuberías tradicionales en herramientas HLS (como Vitis) están limitadas:

• No pueden manejar límites de bucle con dependencias de datos
• El programador estático no puede determinar cuándo programar accesos a memoria

Solución DAE

Bajo TLP, expresar acceso a memoria y ejecución como tareas diferentes:

• Tarea de Acceso a Memoria: Responsable específicamente de solicitudes de memoria
• Tarea de Ejecución: Maneja lógica de cómputo
• Programador de Tareas: Coordina ejecución, implementando tubería elástica

Método de Implementación

Mediante directivas pragma que guían al compilador:

#PRAGMA BOMBYX DAE
struct node_t nd = *n;  // Operación de acceso a memoria
// Código posterior se convierte en tarea de ejecución

El compilador automáticamente:

1. Extrae línea anotada a función independiente (tarea de acceso a memoria)
2. Reemplaza con llamada spawn
3. Inserta sincronización
4. Después de conversión a forma explícita, la tarea de acceso a memoria spawn la continuación de tarea de ejecución

Configuración Experimental

Pruebas de Referencia

Programa de Recorrido de Grafos (Figura 5):

• Recorrido paralelo en amplitud de grafos
• Acceso a lista de adyacencia de nodos (intensivo en memoria)
• Acceso recursivo paralelo a nodos adyacentes

Conjuntos de Datos

Árboles generados sintéticamente:

• Grafo 1: Profundidad D=7, Factor de Ramificación B=4, 5,461 nodos totales
• Grafo 2: Profundidad D=9, Factor de Ramificación B=4, 87,381 nodos totales
• Cálculo de número de nodos: $\frac{B^D - 1}{B - 1}$

Configuración Experimental

• Plataforma FPGA: Xilinx Alveo U55C (xcu55c-fsvh2892-2L-e)
• Herramienta de Síntesis: Vivado 2024.1
• Frecuencia Objetivo: 300 MHz
• Cantidad de PE:
  • Sin DAE: 1 PE
  • Con DAE: 3 PE (spawner, executor, access cada uno)

Métricas de Evaluación

1. Tiempo de Ejecución: Tiempo requerido para recorrer el grafo completo
2. Utilización de Recursos:
   • LUT (Look-Up Tables / Tablas de Búsqueda)
   • FF (Flip-Flops)
   • BRAM (Block RAM / RAM de Bloque)

Resultados Experimentales

Resultados Principales de Rendimiento

• Reducción de Tiempo de Ejecución: La optimización DAE logra mejora de rendimiento del 26.5%
• Mediante desacoplamiento de acceso a memoria y ejecución, se mejora la superposición memoria-cómputo

Análisis de Utilización de Recursos

Sobrecarga de Recursos:

• Aumento de LUT del 47% (2,657 → 3,896)
• Aumento de FF del 50% (2,305 → 3,464)
• BRAM se duplica (2 → 4)

Hallazgos Experimentales

1. Compensación Rendimiento-Recursos: La mejora de rendimiento del 26.5% a costa de aproximadamente 50% de sobrecarga de recursos es una compensación razonable para aplicaciones intensivas en memoria
2. Análisis de Tamaño de PE:
   • Spawner + Executor ≈ tamaño de PE único sin DAE
   • Tarea de acceso consume recursos adicionales
   • Recomendación: Usar PE de paralelismo de datos implementado en RTL puede amortizar costo de tarea de acceso
3. Potencial de Optimización: El artículo señala que en el futuro se puede integrar tarea de acceso como primitiva de caja negra, en lugar de generarla con HLS

Trabajo Relacionado

Marcos de Software TLP

1. Intel Thread Building Blocks (TBB): Biblioteca de paralelismo de tareas ampliamente utilizada en la industria
2. Cilk Plus: Extensión Cilk de Intel
3. OpenCilk: Marco Cilk más reciente, con mejor rendimiento que marcos anteriores

Marcos de Hardware TLP

1. ParallelXL: Marco de arquitectura TLP temprana en FPGA
2. HardCilk: Plataforma objetivo de Bombyx, sistema FPGA TLP de código abierto que proporciona programador de robo de trabajo de hardware

Evolución de Cilk

1. Cilk-1: Versión más temprana que adopta paso de continuaciones explícito
2. Versiones Posteriores: Transición a modelo fork-join implícito (más adecuado para programación de software)
3. Fundamento Teórico: Se ha demostrado que cualquier programa implícito puede convertirse a forma explícita

Ventajas de Este Artículo

• Primera Herramienta Automatizada: Proceso completo y automatizado de OpenCilk a PE FPGA
• Conversión Explícita: Utiliza estilo Cilk-1 para evitar cambio de contexto costoso en hardware
• Soporte de Optimización: Integra optimizaciones específicas de hardware como DAE

Conclusiones y Discusión

Conclusiones Principales

1. Bombyx implementa exitosamente un proceso de compilación automatizado de OpenCilk a hardware FPGA
2. El modelo explícito de paso de continuaciones es adecuado para características de flujo de datos de FPGA, evitando cambio de contexto costoso
3. La optimización DAE logra mejora de rendimiento del 26.5% en pruebas de referencia de recorrido de grafos
4. La herramienta es extensible a otros marcos de hardware TLP

Limitaciones

1. Optimización DAE Requiere Guía Manual: Actualmente requiere que programadores inserten pragma, sin automatización completa
2. Evaluación Limitada:
   • Evaluación solo en una prueba de referencia única (recorrido de grafos)
   • Falta de comparación con otros métodos (como código escrito manualmente, otros compiladores)
   • Sin pruebas en escenarios de aplicación más diversos
3. Sobrecarga de Recursos: La optimización DAE introduce aproximadamente 50% de aumento de recursos, que puede limitar sistemas a gran escala
4. Implementación de Tarea de Acceso: Generar PE de acceso con HLS es ineficiente, se recomienda RTL pero no está implementado
5. Madurez de Herramienta: Como prototipo de investigación, carece de manejo completo de errores y soporte de casos límite

Direcciones Futuras

1. Identificación Automática de DAE: Desarrollar análisis de compilador para identificar automáticamente patrones de código adecuados para optimización DAE
2. Unidades de Acceso RTL: Integrar implementaciones RTL eficientes de unidades de acceso de paralelismo de datos
3. Más Optimizaciones: Explorar otras optimizaciones específicas de hardware (como reutilización de datos, optimización de localidad)
4. Extensión de Objetivos: Soportar más marcos de hardware TLP y herramientas HLS
5. Evaluación Completa: Evaluar en más pruebas de referencia, incluyendo diferentes tipos de aplicaciones TLP

Evaluación Profunda

Fortalezas

1. Innovación de Método

• Estrategia de Conversión Única: Utiliza ingeniosamente el modelo explícito de paso de continuaciones de Cilk-1 para resolver el difícil problema de cambio de contexto en hardware
• Valor de Automatización: Primera herramienta que implementa cadena de herramientas automatizada completa de OpenCilk a FPGA, llenando un vacío importante
• Diseño de IR Razonable: El diseño de IR que preserva estructura de código original hace que código HLS generado sea más legible

2. Contribución de Ingeniería

• Fuerte Practicidad: Automatiza manejo de detalles tediosos como alineación de clausuras, interfaces de búfer de escritura, generación de archivos de configuración
• Verificabilidad: Proporciona capa de simulación Cilk-1 para verificar corrección de conversión, aumentando confiabilidad de herramienta
• Amigable con Código Abierto: HardCilk objetivo es sistema de código abierto, favorable para promoción de herramienta

3. Perspectiva Técnica

• Sinergia Hardware-Software: Comprensión profunda de problemas de adaptación entre modelos TLP de software e implementación de hardware
• Optimización DAE: Combina optimización de hardware clásica con TLP, demostrando potencial de optimización guiada por compilador

4. Claridad de Escritura

• Presenta claramente conversión implícita a explícita mediante ejemplo Fibonacci
• Comparación de IR en Figura 4 es intuitiva y fácil de entender
• Diagrama de proceso de compilación es claro

Insuficiencias

1. Evaluación Insuficiente

• Prueba de Referencia Única: Solo evalúa recorrido de grafos, incapaz de verificar completamente generalidad de herramienta
• Falta de Comparación: Sin comparación con código escrito manualmente, otros métodos de compilación
• Escala Limitada: Grafos de prueba relativamente pequeños (máximo 87K nodos)
• Análisis de Rendimiento No Profundo: Sin análisis de fuentes específicas de mejora de rendimiento (utilización de ancho de banda, eficiencia de programación de tareas, etc.)

2. Limitaciones de Método

• DAE Semi-automatizado: Requiere pragma manual, limitando facilidad de uso
• Espacio de Optimización Limitado: Solo demuestra una optimización (DAE), sin exploración de otras optimizaciones de hardware
• Sobrecarga de Recursos Grande: 50% de aumento de recursos puede limitar aplicaciones prácticas

3. Detalles Técnicos Faltantes

• Algoritmo de Conversión Incompleto: Sin explicación detallada de análisis de dependencias, selección de campos de clausura y otros algoritmos clave
• Garantía de Corrección: Sin prueba formal o método de verificación sistemática
• Casos Límite: Sin discusión de manejo de recursión, punteros, estructuras de datos complejas

4. Profundidad de Evaluación

• Escalabilidad Desconocida: Sin pruebas en aplicaciones a gran escala o flujo de control complejo
• Generalidad Cuestionable: ¿Es recorrido de grafos representativo de aplicaciones TLP típicas?
• Brecha con Teoría: ¿Es mejora del 26.5% cercana al límite teórico?

Impacto

1. Contribución al Campo

• Llena Vacío de Cadena de Herramientas: Proporciona infraestructura importante para aplicación de TLP en aceleración FPGA
• Inspira Investigación Posterior: Enfoque de conversión explícita puede aplicarse a otros modelos de paralelismo
• Promueve TLP en Hardware: Reduce barrera de entrada, ayuda a promoción de TLP en aceleración FPGA

2. Valor Práctico

• Practicidad Moderada: Tiene valor directo para usuarios de HardCilk, pero requiere maduración adicional
• Costo de Aprendizaje: Aún requiere comprensión de conceptos TLP y restricciones de hardware
• Preparación para Producción: Como prototipo de investigación, hay distancia antes de uso en producción

3. Reproducibilidad

• Moderada: Depende de cadena de herramientas OpenCilk, HardCilk, Vitis HLS, etc.
• Código No Abierto: Artículo no menciona planes de código abierto
• Detalles Experimentales Suficientes: Proporciona detalles de implementación y experimento suficientes

Escenarios Aplicables

Escenarios Adecuados

1. Aplicaciones de Paralelismo de Tareas Dinámicas: Algoritmos de grafos, recorrido de árboles, programación dinámica, etc.
2. Cómputo Intensivo en Memoria: Optimización DAE es particularmente adecuada para aplicaciones con cuello de botella de acceso a memoria
3. Usuarios de HardCilk: Desarrolladores que ya usan o planean usar HardCilk
4. Prototipado Rápido: Necesidad de portar rápidamente código TLP orientado a CPU a FPGA

Escenarios No Adecuados

1. Paralelismo Regular: Paralelismo de datos, tuberías y otros escenarios sin necesidad de programación dinámica
2. Recursos Limitados: 50% de sobrecarga de recursos puede ser inaceptable
3. Rendimiento Extremo: RTL optimizado manualmente puede ser aún superior
4. Patrones de Memoria Complejos: Soporte de herramienta para punteros complejos, memoria dinámica desconocido

Sugerencias de Mejora

1. Expandir Evaluación: Añadir más pruebas de referencia (ordenamiento, búsqueda, cómputo científico, etc.)
2. Comparación de Rendimiento: Comparar con código HLS escrito manualmente, implementaciones CPU, implementaciones GPU
3. Automatizar DAE: Desarrollar análisis de compilador para identificar automáticamente oportunidades de DAE
4. Diversidad de Optimización: Explorar más optimizaciones de hardware (reutilización de datos, caché local, etc.)
5. Verificación Formal: Proporcionar garantías formales de corrección de conversión
6. Lanzamiento de Código Abierto: Abrir código para promover contribución comunitaria y verificación

Referencias

Artículos clave citados en este trabajo:

1. 2 OpenCilk (PPoPP'23): Marco Cilk más reciente, lenguaje de entrada de Bombyx
2. 4 HardCilk (FCCM'24): Plataforma objetivo de Bombyx, trabajo anterior de autores
3. 5 Cilk-1 (SIGPLAN'95): Sistema TLP clásico de paso de continuaciones explícito, fundamento teórico de Bombyx
4. 6 Tesis Doctoral de Joerg (1996): Demuestra viabilidad teórica de conversión implícita a explícita

Evaluación General: Bombyx es un trabajo de investigación valioso que llena el vacío de cadena de herramientas automatizada de OpenCilk a aceleración de hardware FPGA. Su innovación central radica en utilizar el modelo explícito de paso de continuaciones de Cilk-1 para evitar cambio de contexto costoso en hardware, proporcionando un proceso de compilación completo. Sin embargo, como trabajo inicial, el artículo presenta deficiencias evidentes en amplitud y profundidad de evaluación experimental, y la semi-automatización de optimización DAE también limita la facilidad de uso. La herramienta tiene valor directo para usuarios de HardCilk e investigadores de TLP, pero requiere maduración adicional para aplicación generalizada. Se recomienda que trabajo posterior se enfoque en identificación automática de optimización, expansión de evaluación de pruebas de referencia y lanzamiento de código abierto para promover verificación y mejora comunitaria.