Portable SIMD Acceleration of Sparse Linear Algebra Libraries on RISC-V
تقدم هذه الورقة تسريعًا لنقل الأداء لعمليات المتجهات أحادية التعليمات والبيانات (SIMD) لمكتبات الجبر الخطي المتناثر (Ginkgo، وPETSc، وSLEPc) باستخدام Google Highway على أجهزة RISC-V، مع تقييم المقايضات بين قابلية النقل، وقابلية البرمجة، والأداء لتوجيه الاعتماد المستقبلي على منصات بنية التعليمات المفتوحة الناشئة.
المؤلفون الأصليون:Patricia Siwinska, Adrián Castelló, Héctor Martínez, Andrés E. Tomás, Enrique S. Quintana-Ortí
تُبنى الحواسيب الحديثة للتعامل مع كميات هائلة من البيانات، لكنها غالباً ما تعاني عندما تكون تلك البيانات مبعثرة وغير مكتملة. في عالم الحوسبة العلمية، تتضمن العديد من المشكلات معلومات "متفرقة" (sparse)، حيث تكون معظم الأرقام في شبكة كبيرة هي أصفار. تخيل خريطة لمدينة حيث تم تحديد الطرق فقط وتُركت الحقول الفارغة بيضاء؛ فإن الحاسوب الذي يحاول حساب تدفق حركة المرور عبر هذه الخريطة لا يحتاج إلى معالجة الحقول الفارغة، ومع ذلك تهدر الطرق التقليدية الوقت في فحصها على أي حال. ولحل هذه المشكلات بكفاءة، يعتمد المهندسون على مكتبات برمجية متخصصة تعمل كمحرك للمحاكاة في الفيزياء والهندسة وعلوم المناخ. وعلى مدى عقود، أصبحت هذه المكتبات أسرع باستخدام تقنية تسمى SIMD، والتي تسمح للمعالج بإجراء نفس العملية الحسابية على أرقام متعددة في وقت واحد، تماماً مثل خط تجميع في مصنع يختم قطعاً متطابقة في حركة واحدة بدلاً من القيام بذلك واحدة تلو الأخرى. ومع ذلك، مع ظهور أنواع جديدة من شرائح الحاسوب، وخاصة تلك القائمة على بنية RISC-V المفتوحة، أصبح الحفاظ على ميزة السرعة هذه أمراً صعباً لأن التعليمات التي تخبر الشريحة بكيفية العمل تختلف اختلافاً كبيراً من مصنع إلى آخر.
استكشف فريق من الباحثين من إسبانيا طريقة لجعل هذه الحسابات عالية السرعة تعمل بسلاسة عبر أنواع مختلفة من الأجهزة دون إعادة كتابة البرامج لكل شريحة جديدة. لقد ركزوا على ثلاث مكتبات رئيسية يستخدمها العلماء في جميع أنحاء العالم، وهي: Ginkgo وPETSc وSLEPc، المصممة لحل الألغاز الرياضية المعقدة التي تتضمن شبكات كبيرة ومتفرقة من الأرقام. واختبر الباحثون أداة تسمى Google Highway، وهي قطعة من الكود البرمجي تعمل كمترجم عالمي لهذه الحسابات. فبدلاً من كتابة تعليمات محددة لشريحة معينة، يمكن للمطورين كتابة مجموعة واحدة من التعليمات باستخدام هذه الأداة، وهي تتكيف تلقائياً للعمل على أي معالج متاح، سواء كانت شريحة من شركة تقنية كبرى أو تصميماً جديداً مفتوح المصدر مثل RISC-V. قام الفريق بأخذ العمليات الرياضية الجوهرية من هذه المكتبات الثلاث وأعاد بناءها باستخدام هذه الأداة العالمية، ثم شغلوها على شريحة RISC-V تجارية تسمى SpacemiT K1 ليروا ما إذا كانت السرعة ستصمد.
أظهرت النتائج أن هذا النهج فعال، ولكن مع وجود تحفظات مهمة فيما يتعلق بكيفية تنظيم البيانات. فعندما اختبر الباحثون البرنامج على شريحة RISC-V، وجدوا أن الأداة العالمية نجحت في تسريع الحسابات، مما أثبت أنه من الممكن كتابة الكود مرة واحدة وتشغيله بسرعة على آلات مختلفة. ومع ذلك، لم تكن مكاسب السرعة موحدة عبر جميع المهام. فبعض العمليات، وخاصة تلك التي أبقت النتائج الوسيطة داخل الذاكرة السريعة للمعالج، شهدت تحسينات هائلة، حيث كانت بعض الخطوات تعمل بسرعة تزيد عن عشر مرات عن النسخة القياسية. أما المهام الأخرى، التي تطلبت نقل البيانات باستمرار من وإلى الذاكرة، فقد شهدت مكاسب أقل بكثير. وكان الاكتشاف الحاسم هو أن التنسيق الذي تُخزن فيه البيانات كان أكثر أهمية من الكود نفسه. فعندما أعاد الباحثون ترتيب البيانات المتفرقة في هيكل محدد ومُحشو (padded structure)، كانت التحسينات في السرعة كبيرة. وعندما تركوها في تنسيقها الأصلي غير المنتظم، كان التسريع ضئيلاً. وهذا يشير إلى أنه بينما تعد أداة الترجمة العالمية فعالة، فإن الهيكل الفيزيائي للبيانات يظل العامل الأهم في تحقيق الأداء العالي.
كما سلطت الدراسة الضوء على المقايضات المرتبطة باستخدام هذا النهج العالمي. وجد الباحثون أنه بينما جعلت الأداة الكود أسهل في الكتابة وأكثر قابلية للنقل، إلا أنها تطلبت منهم تجريد المكتبات الأصلية من بعض الميزات المعقدة والمرنة لجعل الحسابات تعمل بكفاءة. اضطروا إلى تبسيط المنطق الداخلي للبرنامج، وإزالة بعض الفحوصات الشرطية التي تبطئ المعالج. وهذا يعني أنه للحصول على أفضل أداء، لم يكن بإمكانهم ببساطة توصيل الأداة بالمكتبات الموجودة، بل توجب عليهم إعادة بناء أجزاء محددة من البرنامج من الصفر. ورغم هذه التحديات الهندسية، أثبتت التجربة أن الأداة العالمية نجحت في سد الفجوة بين أنواع المعالجات المختلفة. وخلص الباحثون إلى أنه بينما توفر الأداة أساساً قوياً للبرمجيات المستقبلية، فإن تحقيق أعلى سرعة ممكنة لا يزال يعتمد على التخطيط الدقيق لكيفية تخزين البيانات وهيكلة الحسابات. ويقدم هذا العمل مساراً عملياً للمطورين الذين يرغبون في بناء برمجيات علمية سريعة يمكنها العمل على النطاق المتنوع من شرائح الحاسوب المتوقعة في المستقبل.
تعتمد مكتبات الجبر الخطي المتناثر المعاصرة (مثل Ginkgo وPETSc وSLEPc) بشكل كبير على التوجيه المتجه (Vectorization) باستخدام تعليمات البيانات الواحدة لعدة عمليات (SIMD) لتحقيق أداء عالٍ على معماريات المعالجات الحديثة. ومع ذلك، يظل تحقيق نقل الأداء (Performance Portability) تحديًا كبيرًا. إذ تختلف توسعات SIMD بشكل واسع عبر عائلات المعالجات ومجموعات التعليمات البرمجية (ISAs). تقليديًا، يتعين على المطورين كتابة وصيانة تنفيذات منفصلة باستخدام تعليمات داخلية (Intrinsics) خاصة بكل معمارية (مثل AVX2 لمعالجات x86، وNEON لمعالجات Arm، وRVV لمعالجات RISC-V). هذا النهج يؤدي إلى تضخم تعقيد الكود ويعيق تطوير أطر عمل للجبر الخطي المتناثر تكون عالية الأداء وقابلة للنقل في آن واحد.
يستهدف المؤلفون تحديدًا منظومة RISC-V، وهي مجموعة تعليمات مفتوحة وخالية من حقوق الملكية، لكنهم يهدفون إلى عدم قصر جهودهم على RISC-V وحدها. تكمن المشكلة الجوهرية في كيفية تطوير برمجيات جبر خطي متناثر مسرعة بـ SIMD تكون عالية الأداء على RISC-V وقابلة للنقل إلى مجموعات تعليمات متجهية أخرى دون عبء صيانة مسارات كود منخفضة المستوى متعددة.
المنهجية
يبحث البحث في استخدام Google Highway (GHW)، وهو طبقة تجريد لغة C++ مفتوحة المصدر، لتطوير تنفيذات مسرعة بـ SIMD وقابلة للنقل. تتيح GHW للمطورين كتابة كود متجه بأسلوب مشابه للتعليمات الداخلية الأصلية، ولكنها تقوم بربطه بمختلف مجموعات التعليمات (مثل RVV وAVX وNEON وغيرها) عند وقت التجميع (Compile time).
تتضمن المنهجية ثلاث مراحل رئيسية:
اختيار وتحليل المكتبات: اختار المؤلفون ثلاث مكتبات ممثلة ذات فلسفات تصميم متباينة:
Ginkgo: مكتبة C++ حديثة تركز على المعماريات غير المتجانسة، وتستخدم تصميمًا قائمًا على المنفذ (Executor-based design)، والقوالب (Templates)، ودوال لامدا (Lambda functions).
PETSc: مجموعة أدوات تعتمد على لغة C للحوسبة العلمية، تستخدم أنماط التصميم كائنية التوجه (عبر الهياكل ومؤشرات الدوال) والقابلية للتشكيل في وقت التشغيل.
SLEPc: امتداد لـ PETSc لمسائل القيم الذاتية (Eigenvalue problems)، وترث تصميمها ونماذج التوازي الخاصة بها.
استراتيجية التوجيه (Vectorization Strategy):
تحديد النواة (Kernel Identification): حدد المؤلفون ثلاثة عوامل تشغيل (Operators) رئيسية للمحللات (Solvers) ونواها الأساسية:
Ginkgo: محلل BiCGStab (النواوات: التحضير المسبق Preconditioning، الضرب النقطي Dot products، عمليات شبيهة بـ AXPY، وSpMV).
بالنسبة لـ Ginkgo، وجد المؤلفون أن البنية الكثيفة القائمة على القوالب ودوال لامدا، بالإضافة إلى الثوابت الشرطية في الحلقات الداخلية، تعيق التوجيه المباشر. لذا اختاروا تطوير نواوات جديدة صديقة للتوجيه (Vectorization-friendly) تعمل على إزالة القوالب ودوال لامدا، وإلغاء المنطق الشرطي في الحلقات الأكثر داخلية لتسهيل دمج GHW.
بالنسبة لـ PETSc/SLEPc، قام المؤلفون يدويًا بتطوير تنفيذات موجهة للروتينات المستقلة في لغة C. وأشاروا إلى أنه بينما يعتمد PETSc على مكتبات BLAS/LAPACK الأساسية للعمليات الكثيفة، فإن روتينات معينة خاصة به للمصفوفات المتناثرة تتطلب دمجًا يدويًا لـ GHW لاستخراج الأداء الأمثل.
المقارنة: تمت مقارنة نهج GHW مقابل تعليمات RVV 1.0 الأصلية. يسلط البحث الضوء على أنه بينما توفر RVV تحكمًا منخفض المستوى (إدارة طول المتجه الصريحة، والتسميات المطولة)، توفر GHW تجريدًا عالي المستوى (معالجة تلقائية للذيل/Tail handling، تسميات عامة، وتقليل الكود الإضافي/Boilerplate).
الإعداد التجريبي:
الأجهزة: معالج SpacemiT K1 (بثماني نوى، بتردد 1.6 جيجاهرتز) على لوحة Banana Pi BPI-F3. اقتصرت التجارب على نواة واحدة لعزل تأثيرات التوجيه عن مشكلات توازن عبء العمل. تدعم وحدة المتجهات معمارية RVV 1.0 بطول متجه قدره 256 بت.
البيانات: 159 مصفوفة متناثرة من مجموعة مصفوفات SuiteSparse (أبعاد > 100,000)، باستثناء المسائل المتعلقة بالرسوم البيانية (Graph-related problems).
التنسيقات: تم اختبار ضرب المصفوفة المتناثرة والمتجه (SpMV) باستخدام كل من تنسيقات CSR (الصف المتناثر المضغوط) وsELL-C (ELLPACK المقسم).
المساهمات الرئيسية
تجريد SIMD القابل للنقل: إثبات جدوى استخدام Google Highway لإنشاء تنفيذات SIMD قابلة للنقل للأداء في الجبر الخطي المتناثر على RISC-V، مما يسد الفجوة بين التعليمات الأصلية وقابلية النقل عبر مجموعات التعليمات المختلفة.
التكيف الخاص بالمكتبات: تفصيل التحديات الهندسية والحلول لدمج GHW في ثلاث مكتبات متميزة:
التغلب على تعقيد القوالب ودوال لامدا في Ginkgo عبر إعادة هيكلة النواوات.
تكييف روتينات PETSc/SLEPc القائمة على لغة C وكائنية التوجه من أجل التوجيه.
توجيه المحللات (Solver Vectorization): توجيه ثلاثة محللات حاسمة بنجاح: BiCGStab (Ginkgo)، وGMRES (PETSc)، وKrylov–Schur (SLEPc)، بالإضافة إلى نواوات BLAS من المستوى الأول والمستوى الثاني الخاصة بها.
التوصيف التجريبي: تقديم تقييم شامل للأداء على شريحة RISC-V تجارية، مع تحليل المقايضات بين القابلية للنقل، وقابلية البرمجة، والأداء.
النتائج
أسفرت التجارب عن الملاحظات التالية:
تسريع النواة (Kernel-Level Speed-ups): حققت معظم النواوات الموجهة تسارعات جيدة مقارنة بالنسخ القياسية (Scalar)، وإن تفاوتت القيم بشكل كبير بناءً على نوع النواة وبنية المصفوفة.
المكاسب العالية: أظهرت الخطوتان Step_1 وStep_2 في محلل BiCGStab الخاص بـ Ginkgo أعلى معدلات التسريع (وصلت إلى 13 ضعفًا في الحالات القصوى)، ويُعزى ذلك إلى إزالة عدم الكفاءة في روتينات المنفذ (OMP executor) الأصلية.
قيود النطاق الترددي للذاكرة: أظهرت عمليات الضرب النقطي تسارعات متواضعة ومتجمعة بإحكام، وهو ما يتفق مع كونها مقيدة بنطاق عرض نطاق الذاكرة (Memory-bandwidth-bound).
الاعتماد على التنسيق: كان اختيار تخطيط البيانات أمرًا جوهريًا. تفوق تنسيق sELL-C باستمرار على CSR في عملية SpMV. حيث حدت أطوال الصفوف غير المنتظمة في CSR من كفاءة التوجيه، بينما يتوافق تنسيق sELL-C من حيث الحشو والتقسيم بشكل أفضل مع عروض SIMD.
أداء المحلل (Solver-Level Performance):
Ginkgo (BiCGStab): حقق المحلل القائم على sELL-C تسريعات أعلى بكثير من النسخة القائمة على CSR، مما يعكس نتائج SpMV بدقة. وهذا يؤكد أن SpMV هو المحدد الحاسم للأداء الإجمالي للمحلل.
PETSc (GMRES) & SLEPc (Krylov–Schur): حتى مع استخدام تخزين CSR، استفادت المحللات الكاملة من التوجيه. ومع ذلك، فإن العمليات التي تحتفظ بالنتائج الوسيطة في السجلات (Registers) (مثل VecNorm وVecMDot) استفادت أكثر من العمليات التي تتطلب الكتابة في الذاكرة (مثل VecAXPY وVecPointwiseMult).
GHW مقابل تعليمات RVV الأصلية: نجحت GHW في تجريد تعقيد RVV (مثل التعامل التلقائي مع طول المتجه عبر LoadN وReduceSum مقابل vsetvl وخطوات الاختزال اليدوية) دون تكبد خسائر كبيرة في الأداء، مما يؤكد فائدتها لكود عالي الجودة.
الأهمية والادعاءات
يزعم البحث أن Google Highway يوفر أساسًا واعدًا لتسريع SIMD القابل للنقل للجبر الخطي المتناثر على RISC-V والمعماريات المتجهية الأخرى.
الإرشاد العملي: يقدم العمل إرشادات عملية لاعتماد GHW في البرمجيات الإنتاجية، مؤكدًا أنه بينما تحل GHW مشكلة القابلية للنقل، فإن تحقيق الأداء العالي لا يزال يتطلب تخطيطات بيانات مناسبة (مثل تفضيل sELL-C على CSR لعمليات SpMV)، وتنظيم النواوات (إزالة الثوابت الشرطية)، وتنفيذات مدركة للذاكرة.
تحليل المقايضة: توضح الدراسة المقايضات بين القابلية للنقل والأداء. وبينما تضيف GHW طبقة تجريد، فإن مكاسب الأداء على RISC-V كبيرة بما يكفي لتبرير استخدامها، بشرط أن تكون النواوات الأساسية محسنة لمعمارية المتجهات.
الجدوى المستقبلية: تشير الدراسة إلى أن GHW يمكن أن يعمل كأساس لتمكين مكتبات الجبر الخطي المتناثر المسرعة بـ SIMD والقابلة للنقل والتي تمتد إلى ما وراء RISC-V لتشمل مجموعات تعليمات أخرى، مما يعالج عقبة حرجة في منظومة الحوسبة عالية الأداء (HPC).
يظل المؤلفون متواضعين في طرحهم، مشيرين إلى أن دمج GHW في المكتبات ذات الجودة الإنتاجية يتطلب مراعاة دقيقة لبنية الكود، وأن الأداء يعتمد بشدة على نوع النواة وخصائص المصفوفة.