85.30 GFLOPS Single-Core FP32 Matrix Multiplication on AMD Zen 3: A Systematic Study of Cache Blocking, Register Blocking, FMA Chaining, and On-the-Fly Packing

कल्पना कीजिए कि आप एक विशाल गोदाम के एक तरफ से दूसरी तरफ रेत का एक बड़ा ढेर (डेटा) ले जाने की कोशिश कर रहे हैं, लेकिन आपको यह काम एक छोटे, सुपर-फास्ट रोबोटिक हाथ (प्रोसेसर) का उपयोग करके करना है। लक्ष्य रेत को एक विशेष फॉर्मूले (मैट्रिक्स मल्टीप्लिकेशन) के साथ यथाशीघ्र मिलाना है। यह शोध पत्र लुकास नामक एक शोधकर्ता का एक विस्तृत लॉगबुक है, जो एक विशिष्ट प्रकार के कंप्यूटर चिप, जिसे AMD Zen 3 कहा जाता है, पर उस रोबोटिक हाथ को मानवीय रूप से जितना संभव हो सके उतना तेज़ चलाने की कोशिश कर रहा है।

मुख्य लक्ष्य: तेज़ होने का क्या मतलब है?

रोबोटिक हाथ की एक सैद्धांतिक शीर्ष गति 134.4 GFLOPS (यानी 134.4 बिलियन गणितीय संचालन प्रति सेकंड) है। इसे एक हाईवे की स्पीड लिमिट की तरह समझें। लुकास चाहता था कि वह केवल इंजन को ट्यून करके, बिना एक नई कार बनाए, उस स्पीड लिमिट के कितने करीब पहुँच सकता है।

28 अलग-अलग ड्राइविंग रणनीतियों का परीक्षण करने के बाद, उसे एक "चैंपियन" सेटअप (जिसे MX24 कहा जाता है) मिला जिसने 85.30 GFLOPS की गति प्राप्त की। यह अधिकतम गति का लगभग 63.5% है। यह 100% पूर्णता नहीं है, लेकिन यह शुरुआती रेखा से एक बहुत बड़ी छलांग है, जहाँ एक धीमा और अनाड़ी तरीका केवल 1.51 GFLOPS पर चल रहा था। वास्तव में, उसकी सबसे अच्छी विधि बुनियादी, अन-ऑप्टिमाइज्ड संस्करण की तुलना में 57 गुना तेज़ थी।

जीतने वाली रणनीति: "4-रो, चेन-4" का नृत्य

इस गति को प्राप्त करने के लिए, लुकास को यह समझना था कि रेत और रोबोट की गतिविधियों को कैसे व्यवस्थित किया जाए। यहाँ वे प्रमुख चालें हैं जो उसने खोजीं:

1. "ऑन-द-फ्लाई" पैकिंग ट्रिक
कल्पना कीजिए कि रेत एक ग्रिड में संग्रहीत है जहाँ आपको अगली रेत का कण उठाने के लिए तिरछा (diagonally) चलना पड़ता है। यह धीमा और थका देने वाला है। लुकास ने पाया कि रोबोट को इसकी आवश्यकता होने से ठीक पहले रेत के एक छोटे टुकड़े को एक सीधी रेखा में कॉपी करना (जिसे on-the-fly packing कहा जाता है) जादुई चाल थी। यह एक सहायक की तरह है जो आगे दौड़कर ईंटों को एक आदर्श पंक्ति में व्यवस्थित करता है ताकि रोबोट बिना लड़खड़ाए उन्हें एक के बाद एक उठा सके। यह पुराने तरीके (जहाँ जैसे थे वैसे ही उठाया जाता था) से बेहतर था, और यह पूरे गोदाम को पहले से पुनर्व्यवस्थित करने से भी बेहतर था।

2. "4-रो" स्टैकिंग
रोबोट के पास रेत को पकड़ने के लिए सीमित संख्या में हाथ (रजिस्टर्स) होते हैं। लुकास ने 2 पंक्तियाँ, फिर 4, फिर 8 पंक्तियाँ पकड़कर परीक्षण किया।

• 2 पंक्तियाँ: बहुत कम। रोबोट को बहुत बार रुककर नई रेत उठानी पड़ती थी।
• 8 पंक्तियाँ: बहुत ज़्यादा! रोबोट के हाथ इतने भरे हुए थे कि उसे रेत गिरानी पड़ती थी और फिर उसे उठाना पड़ता था। यह एक आपदा थी।
• 4 पंक्तियाँ: यह एकदम सही संतुलन (sweet spot) था। भले ही रोबोट को कुछ दाने गिराने पड़ते थे और फिर उन्हें उठाना पड़ता था (एक प्रक्रिया जिसे "स्पिलिंग" कहा जाता है), लेकिन अतिरिक्त काम सार्थक था क्योंकि वह एक बार में अधिक रेत को प्रोसेस कर सकता था। इस एक बदलाव ने रोबोट को 2-रो विधि की तुलना में 59% तेज़ बना दिया।

3. "चेन-4" लय
रोबोट के हाथ को एक गणितीय चाल पूरी करने में 4 सेकंड (साइकिल) लगते हैं, इससे पहले कि वह उसी रेत के टुकड़े पर अगली चाल शुरू कर सके। यदि रोबमा केवल एक चाल करता और प्रतीक्षा करता, तो वह 3 सेकंड तक खाली बैठा रहता।
लुकास ने पाया कि यदि रोबोट अपने हाथों में रेत के 4 अलग-अलग ढेर रखता और उन पर एक लूप में काम करता (Chain-4), तो वह रोबोटिक हाथ को लगातार चलते रख सकता था। जब एक ढेर "पक रहा" होता, तब वह दूसरे ढेरों पर काम करता। यह रोबोट के 4-सेकंड के कुकिंग टाइम से पूरी तरह मेल खाता था, जिससे इंजन पूरी गति से चलता रहता।

क्या काम नहीं आया ( "यह न करें" की सूची)

कभी-कभी, जो आप सोचते हैं कि काम करेगा, वह वास्तव में चीज़ों को बिगाड़ सकता है। लुका la ने कुछ लोकप्रिय विचारों का परीक्षण किया और पाया कि वे इस विशिष्ट रोबोट के लिए बहुत खराब थे:

• "प्री-फेच" की गलती: लोग अक्सर रोबोट को निर्देश देते हैं कि वह अगली रेत की ज़रूरत पड़ने से पहले उसे "देख ले" और उठा ले। लुकास ने इसे आज़माया, लेकिन रोबोट की अपनी आँखें पहले से ही पैटर्न देखने में इतनी अच्छी थीं कि अतिरिक्त "लुक अहेड" कमांड्स बाधा बन गईं। इसने रोबोट की गति को लगभग 8% कम कर दिया।
• "नॉन-टेम्पोरल" डंप: एक तकनीक है जहाँ आप रोबोट को निर्देश देते हैं कि वह रेत को सीधे फर्श पर डाल दे, बिना किसी बिन में रखे। यह तब बहुत अच्छा काम करता है जब आप केवल कचरा फेंक रहे हों। लेकिन यहाँ, रोबोट को रेत को मिलाना है, जिसका अर्थ है कि उसे इसे फिर से उठाना होगा। सीधे डंप करने से रोबोट अपने ही पैरों में उलझ गया, जिससे उसकी गति गिरकर एक दयनीय 1.24 GFLOPS रह गई।
• "8-रो" ओवरलोड: जैसा कि उल्लेख किया गया है, 8 पंक्तियों की रेत पकड़ने की कोशिश करने से रोबोट इतना अधिक रेत गिरा देता था कि वह उसे उठाने में ही ज़्यादा समय बिता देता था।

हम कितने आश्वस्त हैं?

यह शोध पत्र इन आंकड़ों के बारे में बहुत आश्वस्त है क्योंकि ये केवल अनुमान नहीं थे, बल्कि मापे गए थे। लुकास ने प्रत्येक रणनीति के लिए कोड को 15 बार चलाया, सबसे तेज़ और सबसे धीमी रन को हटा दिया (अजीब कंप्यूटर ग्लिच से बचने के लिए), और बाकी का औसत निकाला। उसने यह सुनिश्चित करने के लिए कि तेज़ संस्करण ने धोखाधड़ी न की हो, गणित की जांच एक सरल, धीमी विधि के विरुद्ध भी की।

उसने एक गणितीय "प्री-फ़िल्टर" मॉडल भी बनाया—एक तरह का क्रिस्टल बॉल—जो वास्तव में चलाने से पहले ही किसी रणनीति की गति की भविष्यवाणी कर सके। यह क्रिस्टल बॉल काफी अच्छा था, जो अधिकांश रणनीतियों के लिए वास्तविक गति के 11.3% के भीतर रहता था। यह थोड़ा रूढ़िवादी था, इसने भविष्यवाणी की थी कि सबसे अच्छी रणनीति 78.1 GFLOPS होगी, लेकिन जब उन्होंने वास्तव में इसे चलाया, तो इसने 85.30 GFLOPS प्राप्त किया।

निष्कर्ष

यह शोध पत्र यह सिद्ध करता है कि आपको "असेंबली लैंग्वेज" (रोबोट की मूल भाषा) में कोड लिखने के लिए जादूगर होने की आवश्यकता नहीं है। C++ इंट्रिंसिक्स (intrinsics) जैसे मानक उपकरणों का उपयोग करके और सावधानीपूर्वक "डांस स्टेप्स" (ब्लॉकिंग, चेनिंग और पैकिंग) को ट्यून करके, आप अपने कंप्यूटर को उसके सैद्धांतिक अधिकतम गति के 63.5% तक चला सकते हैं।

मुख्य सबक? अनुमान न लगाएं। जो एक प्रकार के रोबोट (या कंप्यूटर चिप) के लिए काम करता है, वह दूसरे को तोड़ सकता है। लुकास ने यह खोजने के लिए 28 अलग-अलग संयोजनों का परीक्षण किया कि कौन सा काम करता है, जो यह दर्शाता है कि कभी-कभी "स्पष्ट" दिखने वाले तरीके (जैसे लुक अहेड करना या सीधे डंप करना) वास्तव में गलत चाल होते हैं।