התייחסות לדלילות כמאפיין במקום כפרט (מייגע) של הטמעה מאפשרת לכלי להפיכת קוד לדליל של הקומפיילר 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. תמיכה בקומפיילר לחישובים של מטריצות דלילות. עבודת דוקטורט, אוניברסיטת ליידן, מאי 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. Format Abstraction for Sparse Tensor Algebra Compilers. Proceedings of the ACM on Programming Languages, אוקטובר 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. טכניקות בסיסיות לפתרון מערכות דלילות של משוואות ליניאריות. ב-Sparse Matrices and Their Applications, דפים 41–52. Plenum Press, New York, 1972.
[Kjolstad17] Fredrik Berg Kjolstad, Shoaib Ashraf Kamil, Stephen Chou, David Lugato, and Saman Amarasinghe. המהדר של אלגברת טנסורים. 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. PhD thesis, MIT, February, 2020.
רוצה לתרום? ריכזנו כאן כמה בעיות טובות למתחילים.
-
חשוב לציין שאנחנו מעדיפים עכשיו את המונח 'sparsifier' (מפחית דלילות) על פני המונח 'sparse compiler' (קומפיילר דליל) שגם הוא בשימוש נפוץ, כדי להבהיר שהשלב של הפחתת הדלילות הוא לא קומפיילר נפרד, אלא צריך להיות חלק בלתי נפרד מכל צינור קומפיילר שנבנה באמצעות תשתית הקומפיילר MLIR. ↩