शुरुआत से डिज़ाइन किए गए SIMD एल्गोरिदम

SIMD एल्गोरिदम डिज़ाइन

• SIMD optimization का विवरण: SIMD का मतलब Single Instruction, Multiple Data है, और इसके लिए सर्किट डिज़ाइनर की तरह सोचना ज़रूरी है।
• SIMD का ज़िक्र अक्सर performance और HPC (High Performance Computing) में होता है, लेकिन यह शुरुआती लोगों के लिए परिचित विषय नहीं है।
• ज़्यादातर programming languages में SIMD programming API का इस्तेमाल करना कठिन होता है।
• SIMD एल्गोरिदम को procedural programming mindset से समझना मुश्किल है, और functional programming इसमें मददगार हो सकती है।
• यह लेख Rust की std::simd लाइब्रेरी का उपयोग करके base64 codec लागू करने वाले vb64 के बारे में है।

भौतिक सीमाएँ

• कंप्यूटर वास्तविक दुनिया में मौजूद हैं और भौतिक नियमों से बंधे हैं।
• शुरुआती computing दौर में नया कंप्यूटर खरीदकर performance बढ़ाई जा सकती थी।
• Dennard scaling का प्रभाव टूट गया, इसलिए छोटे transistors का मतलब अधिक power consumption हो गया।
• cores की संख्या बढ़ाना नया trend बन गया। Multithreading के ज़रिए CPU performance बढ़ाई जा सकती है, लेकिन synchronization overhead भी आता है।

procedural code की धीमी गति

• आधुनिक computer cores कोड को लाइन-दर-लाइन execute नहीं करते।
• instruction-level parallelism के ज़रिए, अगर data dependency न हो तो कई operations एक साथ किए जाते हैं।
• जब compiler data hazards को हल कर सकता है, तब parallelism बढ़ जाता है।
• branches और memory operations stall पैदा करते हैं, जिससे कोड धीमा हो जाता है।

SIMD और lanes

• SIMD और vector शब्द अक्सर एक ही अर्थ में इस्तेमाल होते हैं।
• SIMD instructions एक fixed-size number array, यानी vector, को मूल इकाई के रूप में इस्तेमाल करते हैं।
• vector के हर element को lane कहा जाता है, और SIMD vectors आम तौर पर छोटे आकार के होते हैं।

वास्तविक vectors पर operations

• SIMD vectors सामान्य registers की तुलना में अधिक जटिल operations प्रदान करते हैं।
• vector registers bit operations, lane-wise arithmetic, lane-wise comparison, shuffle जैसी कई तरह की operations को support करते हैं।
• shuffle, SIMD programming में data को सही स्थान पर ले जाने के लिए बहुत महत्वपूर्ण है।

intrinsics और instruction selection

• SIMD कोड लिखते समय उपलब्ध operations architecture के अनुसार बदलते हैं।
• compiler instruction selection की समस्या हल करता है, यानी उपयोगकर्ता द्वारा मांगे गए operation के लिए कौन-सा instruction चुना जाए।
• portable SIMD कोड लिखना जटिल है, लेकिन runtime feature detection के ज़रिए अलग-अलग processors पर optimal code तैयार किया जा सकता है।

SIMD के साथ parsing

• SIMD का उपयोग करके text parsing की जा सकती है, और यह बहुत तेज़ हो सकती है।
• उदाहरण के तौर पर base64 decoding को SIMD से लागू किया जा सकता है।
• सभी branches को हटाना SIMD version बनाने की प्रक्रिया का मुख्य हिस्सा है।

GN⁺ की राय

इस लेख की सबसे महत्वपूर्ण बात यह है कि SIMD programming पारंपरिक procedural programming से अलग तरीके से data को parallel में process करके performance बढ़ा सकती है। SIMD, high-performance computing के क्षेत्र में बहुत महत्वपूर्ण है, और खासकर Rust जैसी आधुनिक programming languages में SIMD का प्रभावी उपयोग कैसे किया जाए, इसे समझना software engineers के लिए बहुत दिलचस्प विषय हो सकता है। ऐसा इसलिए है क्योंकि SIMD के माध्यम से जटिल एल्गोरिदम को optimize करने और वास्तविक hardware की सीमाओं को पार करने के तरीके सीखे जा सकते हैं।

[GN⁺]

Hacker News राय

• पोर्टेबल SIMD के उपयोग के उदाहरण देखने के लिए यह एक शानदार लेख है। Zen 3 सिस्टम पर बेंचमार्क दोहराने पर वही speedup देखा गया। M1 mbp पर 110 बाइट इनपुट लंबाई में प्रदर्शन सुधार धीरे-धीरे बढ़ते हुए अधिकतम 2x तक पहुँचा। x86_64 की तुलना में लाभ कम है, लेकिन कहा जा सकता है कि लक्ष्य हासिल हो गया। हालांकि, इससे यह भी दिखता है कि Rust, SIMD और pointer से जुड़े कामों तथा समग्र performance engineering में कुछ हद तक असुविधाजनक है।
• कभी-कभी यह हैरान करता है कि C++ में पूरी कोशिश से प्रोग्रामिंग करने पर भी SIMD इस्तेमाल करने वाला संस्करण 10x से अधिक तेज़ प्रदर्शन दिखाता है। कोड की portability घटती है, लेकिन इच्छा है कि compiler automatic vectorization बेहतर तरीके से करे। अच्छा होता अगर annotations के ज़रिए भाषा में यह समर्थन जोड़ा जाता कि कुछ operations के क्रम को पुनर्व्यवस्थित किया जा सके।
• यह इंगित किया गया कि compiler किसी विशेष popcount implementation को एक single instruction में optimize नहीं कर पाया, लेकिन दूसरी implementations के लिए ऐसा संभव हो सकता है।
• _mm256_cvtps_epu32 AVX2 instruction नहीं बल्कि AVX-512 instruction है, और AVX1 में integer signed form में होते हैं, इसलिए संबंधित instruction _mm256_cvtps_epi32 है।
• दाईं ओर का छोटा minimap बहुत पसंद आया।
• ISPC को C++ या Rust में SIMD जोड़ने से बेहतर माना गया। साथ ही, यह dynamic dispatching को support करता है, जो सीधे implement करना कठिन feature है।
• fastbase64 की तुलना में यह कैसा है, इस बारे में सवाल उठाया गया, और साथ ही portable SIMD libraries के प्रति लेखक के आशावादी रवैये से सहमति जताई गई।
• यह एक शानदार लेख है, जिसने ऐसा प्रभाव छोड़ा कि लगता है मैं खुद कभी इतना बुद्धिमान नहीं बन पाऊँगा।
• non-vectorized popcnt implementation के पहले उदाहरण के बारे में कहा गया था कि यह "ईमानदारी से कहें तो हास्यास्पद कोड" पैदा करता है, लेकिन native target CPU पर release mode में compile करने पर फ़ंक्शन काफ़ी अच्छी तरह vectorized होता हुआ दिखता है।
• Rust Simd पर यह काफ़ी अच्छा प्रयास है। generated code की जाँच करने पर सबसे चौंकाने वाली असामान्यता क्या थी, यह सवाल उठाया गया।