إنّ التعامل مع التناثر كخاصية بدلاً من تفصيل (ممل) للتنفيذ يسمح لبرنامج التناثر في المترجم1 بإنشاء رمز متناثر تلقائيًا. تمت ريادة هذا المفهوم في الجبر الخطي من خلال [Bik96] في MT1، وتمت صياغته في جبر الموتر من خلال [Kjolstad17,Kjolstad20] في مشروع Sparse Tensor Algebra Compiler(TACO).
تتيح حزمة SparseTensor جميع السمات والأنواع والعمليات وعمليات النقل المطلوبة لجعل أنواع الموتر المتفرّق من الدرجة الأولى ضمن البنية الأساسية لمترجم MLIR. تشكّل لغة الآلة جسرًا بين العمليات العالية المستوى على أنواع الموتر المتناثر والعمليات المنخفضة المستوى على مخططات التخزين المتناثر الفعلية التي تتألف من المواضع والإحداثيات والقيم. قد يتألف الدعم على مستوى أدنى من تعليمات برمجية تم إنشاؤها بالكامل أو قد يتم توفيره من خلال مكتبة صغيرة لدعم وقت التشغيل.
يتّبع تنفيذ MLIR [Biketal22] بشكل وثيق نظرية التكرار المتناثر التي تشكّل أساس TACO. يحتوي المحوّل البرمجي على قاعدة إعادة كتابة لكل تعبير موتر في لغة Linalg (ترميز فهرس الموتر في MLIR): تتم الإشارة إلى تباعد كل مستوى من الموتر من خلال أنواع المستويات (مثل، كثيف، مضغوط، أحادي) وتحديد ترتيب المستويات (راجِع [Chou18] للحصول على مناقشات متعمقة وتوسيعات محتملة لأنواع المستويات هذه). بالنسبة إلى كل تعبير موتر في الإدخال، ينشئ المترجم البرمجي أولاً رسمًا بيانيًا مكررًا مرتبًا طوبولوجيًا يعكس ترتيب الإحداثيات بالنسبة إلى مستويات كل موتر، ما يضمن الوصول إلى جميع الموترات بترتيب الإحداثيات الطبيعي على مستوى كل موتر. بعد ذلك، يتم إنشاء شبكات التكرار لكل فهرس بترتيب طوبولوجي. تتألف كل نقطة في شبكة التكرار من اقتران لإحداثيات الموتر وتعبير (فرعي) للموتر يجب تقييمه لهذا الاقتران. ضمن الشبكة، يتم ترتيب نقاط التكرار وفقًا لطريقة استنفاد الإحداثيات. وبالتالي، تؤدي شبكات التكرار هذه إلى إنشاء رمز مبعثر فعلي، وهو عبارة عن عملية ربط بسيطة نسبيًا بين شبكات التكرار ومجموعات من حلقات for وحلقات while وجمل if. يتم التعامل مع مخرجات الموتر المتفرّق التي يتم إنشاؤها بدون تهيئة باستخدام عمليات إدراج مباشرة، إذا كانت جميع الحلقات المتوازية هي الأبعد، أو عمليات إدراج تمر بشكل غير مباشر عبر توسيع نمط الوصول الأحادي الأبعاد (المعروف أيضًا باسم مساحة العمل)، حيثما أمكن ذلك [Gustavson72,Bik96,Kjolstad19].
[Bik96] Aart J.C. Bik. Compiler Support for Sparse Matrix Computations. رسالة دكتوراه، جامعة لايدن، مايو 1996
[Biketal22] Aart J.C. Bik, Penporn Koanantakool, Tatiana Shpeisman, Nicolas Vasilache, Bixia Zheng, and Fredrik Kjolstad. إتاحة عمليات حسابية على موترات متفرقة في MLIR ACM Transactions on Architecture and Code Optimization، يونيو 2022 يمكنك الاطّلاع على: https://dl.acm.org/doi/10.1145/3544559
[Chou18] Stephen Chou, Fredrik Berg Kjolstad, and Saman Amarasinghe. تجريد التنسيق لمترجمات جبر المتجهات المتفرقة Proceedings of the ACM on Programming Languages, October 2018.
[Chou20] Stephen Chou, Fredrik Berg Kjolstad, and Saman Amarasinghe. الإنشاء التلقائي لروتينات تحويل تنسيق موترات متفرقة فعّالة Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, June, 2020.
[Gustavson72] Fred G. Gustavson. بعض التقنيات الأساسية لحل أنظمة المعادلات الخطية المتفرقة In Sparse Matrices and Their Applications, pages 41–52. Plenum Press, New York, 1972.
[Kjolstad17] Fredrik Berg Kjolstad, Shoaib Ashraf Kamil, Stephen Chou, David Lugato, and Saman Amarasinghe. هي أداة تجميع مادة كتاب Tensor Algebra. Proceedings of the ACM on Programming Languages, October 2017.
[Kjolstad19] Fredrik Berg Kjolstad, Peter Ahrens, Shoaib Ashraf Kamil, and Saman Amarasinghe. Tensor Algebra Compilation with Workspaces, Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization, 2019.
[Kjolstad20] Fredrik Berg Kjolstad. Sparse Tensor Algebra Compilation. رسالة دكتوراه، معهد ماساتشوستس للتكنولوجيا، شباط (فبراير) 2020
هل تريد المساهمة؟ إليك بعض المشاكل الجيدة للمبتدئين.
-
يُرجى العِلم أنّنا نفضّل الآن استخدام مصطلح "مُخفِّف الكثافة" بدلاً من مصطلح "المترجم البرمجي المخفِّف الكثافة" الشائع الاستخدام أيضًا للإشارة إلى عملية التمرير هذه، وذلك لتوضيح أنّ عملية التمرير هذه ليست مترجمًا برمجيًا منفصلاً، ولكن يجب أن تكون جزءًا لا يتجزأ من أي مسار مترجم برمجي تم إنشاؤه باستخدام البنية الأساسية للمترجم البرمجي MLIR. ↩