स्पार्सिटी को लागू करने की मुश्किल प्रक्रिया के बजाय, इसे एक प्रॉपर्टी के तौर पर इस्तेमाल करने से, कंपाइलर का स्पार्सिफ़ायर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. स्पार्स टेंसर ऐल्जेब्रा कंपाइलर के लिए फ़ॉर्मैट ऐब्स्ट्रैक्शन. Proceedings of the ACM on Programming Languages, अक्टूबर 2018.
[Chou20] Stephen Chou, Fredrik Berg Kjolstad, and Saman Amarasinghe. Automatic Generation of Efficient Sparse Tensor Format Conversion Routines. प्रोग्रामिंग लैंग्वेज डिज़ाइन ऐंड इंप्लीमेंटेशन पर 41वीं एसीएम एसआईजीप्लान कॉन्फ़्रेंस की कार्रवाइयां, जून, 2020.
[Gustavson72] Fred G. गुस्तावसन. रैखिक समीकरणों के विरल सिस्टम को हल करने की कुछ बुनियादी तकनीकें. In Sparse Matrices and Their Applications, pages 41–52. Plenum Press, New York, 1972.
[Kjolstad17] फ़्रेडरिक बर्ग क्योलस्टैड, शोएब अशरफ़ कामिल, स्टीफ़न चाउ, डेविड लुगाटो, और समन अमरासिंघे. Tensor Algebra Compiler. प्रोसीडिंग्स ऑफ़ द एसीएम ऑन प्रोग्रामिंग लैंग्वेज, अक्टूबर 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. स्पार्स टेंसर अलजेब्रा कंपाइलेशन. पीएचडी थीसिस, एमआईटी, फ़रवरी, 2020.
क्या आपको योगदान देना है? यहां कुछ अच्छे शुरुआती मुद्दे दिए गए हैं.
-
कृपया ध्यान दें कि अब हम इस तरह के पास के लिए, 'स्पार्स कंपाइलर' के बजाय 'स्पार्सिफ़ायर' शब्द का इस्तेमाल करते हैं. इससे यह साफ़ तौर पर पता चलता है कि स्पार्सिफ़ायर पास, कोई अलग कंपाइलर नहीं है. हालांकि, यह MLIR कंपाइलर इन्फ़्रास्ट्रक्चर के साथ बनाई गई किसी भी कंपाइलर पाइपलाइन का अहम हिस्सा होना चाहिए. ↩