Bombyx: OpenCilk Compilation for FPGA Hardware Acceleration
Shahawy, de Castelnau, Ienne
Task-level parallelism (TLP) is a widely used approach in software where independent tasks are dynamically created and scheduled at runtime. Recent systems have explored architectural support for TLP on field-programmable gate arrays (FPGAs), often leveraging high-level synthesis (HLS) to create processing elements (PEs). In this paper, we present Bombyx, a compiler toolchain that lowers OpenCilk programs into a Cilk-1-inspired intermediate representation, enabling efficient mapping of CPU-oriented TLP applications to spatial architectures on FPGAs. Unlike OpenCilk's implicit task model, which requires costly context switching in hardware, Cilk-1 adopts explicit continuation-passing - a model that better aligns with the streaming nature of FPGAs. Bombyx supports multiple compilation targets: one is an OpenCilk-compatible runtime for executing Cilk-1-style code using the OpenCilk backend, and another is a synthesizable PE generator designed for HLS tools like Vitis HLS. Additionally, we introduce a decoupled access-execute optimization that enables automatic generation of high-performance PEs, improving memory-compute overlap and overall throughput.
تقدم هذه الورقة Bombyx، وهي سلسلة أدوات لتجميع برامج OpenCilk إلى معجلات أجهزة FPGA. يحول Bombyx نموذج التوازي الضمني للمهام في OpenCilk إلى تمثيل وسيط صريح بأسلوب Cilk-1 لنقل الاستمرارية (continuation-passing)، وهو أكثر ملاءمة للخصائص الانسيابية لـ FPGA. تدعم الأداة أهدافاً تجميعية متعددة: وقت تشغيل متوافق مع OpenCilk للتحقق، ومولدات وحدات معالجة قابلة للتوليف لأدوات التوليف عالية المستوى مثل Vitis HLS. بالإضافة إلى ذلك، يقدم Bombyx تحسين الفصل بين الوصول للذاكرة والتنفيذ (DAE)، الذي يولد تلقائياً وحدات معالجة عالية الأداء، مما يحسّن التداخل بين التخزين والحساب والإنتاجية الإجمالية.
التوازي على مستوى المهام (TLP) هو تقنية توازي مستخدمة على نطاق واسع في البرامج، وتتيح إنشاء وجدولة المهام المستقلة ديناميكياً في وقت التشغيل. بينما توجد أطر عمل أجهزة (مثل ParallelXL و HardCilk) تدعم TLP على FPGA، يوجد نقص في أدوات الأتمتة لاستخراج وتجميع رمز وحدات المعالجة (PE) تلقائياً من أطر عمل TLP البرمجية. عادة ما تتطلب الأطر الموجودة من المستخدمين توفير رمز PE يدويّاً، وهو أمر مرهق وعرضة للأخطاء.
الحاجة للأتمتة: نقل تطبيقات TLP الموجهة للمعالج إلى FPGA يتطلب عملاً يدويّاً كبيراً، بما في ذلك إعادة هيكلة الرمز، وتكييف واجهات الأجهزة، وإنشاء ملفات التكوين
تحسين الأداء: يصعب تطبيق تحسينات أجهزة متقدمة (مثل فصل الوصول للذاكرة والتنفيذ) على الرمز المكتوب يدويّاً
كفاءة التطوير: يعيق غياب سلسلة أدوات أتمتة الاستخدام الواسع لـ TLP في تسريع FPGA
النموذج الضمني لـ OpenCilk: يستخدم نموذج fork-join مع cilk_spawn و cilk_sync الذي يتطلب تبديل السياق عند نقاط المزامنة. تنفيذ تبديل السياق في الأجهزة يتطلب حفظ حالة الدائرة بأكملها، وهو ما لا تدعمه أدوات HLS الحالية بشكل مباشر وتتطلب هندسة RTL كبيرة
تمثيل TAPIR الوسيط: يستخدم OpenCilk TAPIR الذي يعتمد على بنى مترجم منخفضة المستوى، مما يصعب توليد رمز C++ قابل للقراءة قريب من الرمز الأصلي لـ HLS
كتابة PE يدويّة: تتطلب التعامل اليدوي مع محاذاة الإغلاق، وواجهات المخزن المؤقت للكتابة، وإنشاء ملفات التكوين وغيرها من التفاصيل المرهقة
نموذج نقل الاستمرارية الصريح في Cilk-1 أكثر ملاءمة لتنفيذ الأجهزة، لأنه يقسم الدالة عند نقاط المزامنة إلى دوال نهائية (تُنفذ بشكل ذري، بدون الحاجة لتبديل السياق). بينما لا يكون هذا النموذج بديهياً كافياً لبرمجة البرامج (وبالتالي تم التخلي عنه في تطور Cilk)، إلا أنه طبيعي لتنفيذ الأجهزة. الهدف من Bombyx هو أتمتة التحويل من OpenCilk إلى TLP الصريح، وتوليد وحدات معالجة أجهزة محسّنة.
استخدام واجهة Clang في OpenCilk لتوليد شجرة بناء الجملة المجردة
تحويل AST إلى تمثيل الرسم البياني للتحكم (CFG) للـ IR الضمني
تتوافق كل دالة مع CFG واحد، تتضمن:
كتلة إدخال فريدة (بدون حواف إدخال)
كتلة إخراج واحدة أو أكثر (بدون حواف إخراج)
تتكون الكتل الأساسية من عبارات C متسلسلة، وتنتهي بعبارات تحكم التدفق
لماذا لا نستخدم TAPIR: يستخدم TAPIR بنى منخفضة المستوى (مثل عقد φ وalloca)، مما يصعب توليد رمز C++ قابل للقراءة قريب من الرمز الأصلي. يحافظ IR في Bombyx على بنية الرمز الأصلي.
هذه هي خطوة التحويل الأساسية في Bombyx، وتحول نموذج المزامنة الضمني في OpenCilk إلى نموذج نقل الاستمرارية الصريح في Cilk-1.
المفاهيم الرئيسية:
الإغلاق (Closure): بنية بيانات تمثل المهمة، تتضمن:
معاملات جاهزة
عناصر نائبة تنتظر التبعيات
مؤشر الإرجاع
spawn_next: إنشاء مهمة استمرارية تنتظر التبعيات
send_argument: كتابة صريحة للمعامل إلى إغلاق الانتظار وإخطار جدولة المهام
خوارزمية التحويل:
تقسيم المسارات: اجتياز CFG، بدء مسار جديد عند مواجهة كتلة نهاية دالة (return) أو عملية مزامنة
يصبح كل مسار دالة نهائية مستقلة بذاتها
تمثل المناطق الرمادية في الشكل 4(c) مسارين
تحديد التبعيات: تحليل العلاقات التبعية على حدود المزامنة
تحديد المتغيرات التي تحتاج إلى الاستخدام بعد المزامنة (مثل x و y في الشكل 1)
يجب تخزين هذه المتغيرات بشكل صريح في الإغلاق
استبدال الكلمات الرئيسية:
إدراج إعلان إغلاق عند استدعاء spawn
استبدال المزامنة باستدعاء 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
// نهاية الدالة، لا حاجة للمزامنة
2 OpenCilk (PPoPP'23): أحدث إطار عمل Cilk، لغة الإدخال لـ Bombyx
4 HardCilk (FCCM'24): منصة Bombyx المستهدفة، عمل سابق للمؤلفين
5 Cilk-1 (SIGPLAN'95): نظام TLP كلاسيكي لنقل الاستمرارية الصريح، الأساس النظري لـ Bombyx
6 أطروحة Joerg (1996): إثبات الجدوى النظرية للتحويل من الضمني إلى الصريح
التقييم الشامل: Bombyx هو عمل بحثي ذو قيمة، يملأ فراغاً مهماً في سلسلة أدوات الأتمتة من OpenCilk إلى تسريع أجهزة FPGA. يكمن الابتكار الأساسي في استخدام ذكي لنموذج نقل الاستمرارية الصريح في Cilk-1 لتجنب تبديل السياق في الأجهزة، وتوفير سلسلة تجميع كاملة. ومع ذلك، كعمل أولي، تظهر الورقة نقصاً واضحاً في عمق وعمومية التقييم التجريبي، كما أن الطبيعة شبه الأتمتة لتحسين DAE تحد من سهولة الاستخدام. تتمتع الأداة بقيمة مباشرة لمستخدمي HardCilk والباحثين في TLP، لكنها تحتاج إلى مزيد من النضج قبل التطبيق الواسع. يُنصح بأن يركز العمل اللاحق على تحديد التحسينات الأتمتة تلقائياً وتوسيع تقييم اختبارات المقارنة والنشر مفتوح المصدر لتعزيز التحقق والتحسين من قبل المجتمع.