Parallel Cascaded Recursive Filtering on Multi-Core CPUs and GPUs

कल्पना कीजिए कि आप अपने पसंदीदा गाने की एक शोर भरी रिकॉर्डिंग को साफ करने की कोशिश कर रहे हैं, या शायद आप एक ऐसा रोबोट बना रहे हैं जिसे अपने वातावरण पर तुरंत प्रतिक्रिया देने की आवश्यकता है। दोनों ही मामलों में, आपको अच्छे ध्वनियों को बुरी ध्वनियों से अलग करने के लिए एक डिजिटल "फ़िल्टर" की आवश्यकता है। इस काम के लिए सबसे शक्तिशाली उपकरण रिकर्सिव फ़िल्टर्स (recursive filters) कहलाते हैं। इन्हें एक जादुई गूँज कक्ष (echo chamber) की तरह समझें: यह पता लगाने के लिए कि अगला स्वर क्या होना चाहिए, फ़िल्टर वर्तमान ध्वनि और एक क्षण पहले ही द्वारा उत्पन्न ध्वनियों को देखता है। यह "पीछे मुड़कर देखना" उन्हें अविश्वसनीय रूप से कुशल बनाता है, जिससे वे जटिल कार्यों को करने के लिए बहुत कम कंप्यूटर शक्ति का उपयोग करते हैं। हालाँकि, इसमें एक पेंच है: क्योंकि प्रत्येक नई ध्वनि पिछली ध्वनि पर निर्भर करती है, इसलिए फ़िल्टर को चरण-दर-चरण काम करना पड़ता है, जैसे एक लंबे गलियारे में चलता हुआ एक अकेला व्यक्ति। यह एक बाधा (bottleneck) पैदा करता है, जो उच्च-परिभाषा वाले वीडियो या वास्तविक समय के रेडियो जैसे भारी मात्रा में डेटा को प्रोसेस करते समय सब कुछ धीमा कर देता है।

दशकों तक, वैज्ञानिकों ने इसे तेज़ करने के लिए अधिक कंप्यूटरों की मदद लेने की कोशिश की है। चुनौती यह है कि यदि आप काम को कई कंप्यूटरों के बीच विभाजित करते हैं, तो वे भ्रमित हो जाते हैं क्योंकि वे सभी पिछले व्यक्ति को अपना चरण पूरा करने के लिए प्रतीक्षा करते हैं, इससे पहले कि वे अपना हिस्सा शुरू कर सकें। यह एक रिले रेस की तरह है जहाँ धावक बैटन (baton) के मिलने का इंतज़ार करते हुए फंसे हुए हैं, भले ही वे अलग-अलग ट्रैक पर खड़े हों। यह पेपर ठीक इसी समस्या पर काम करता है। यह एक चतुर गणितीय ट्रिक को लेता है जो पहले से ही एक एकल, सुपर-फास्ट कंप्यूटर चिप पर काम करने के लिए सिद्ध हो चुकी थी और इसे आधुनिक, मल्टी-कोर कंप्यूटरों और शक्तिशाली ग्राफिक्स कार्ड (GPUs) पर चलाने के लिए स्केल करता है। लेखकों ने पाया कि वे इन कंप्यूटरों को बिना प्रतीक्षा किए एक साथ काम करने के लिए एक तरीका निकाल सकते हैं, जिससे एक धीमी, एकल-फाइल लाइन एक उच्च-गति वाली बहु-लेन हाईवे में बदल जाती है, जिससे ऐसी गति प्राप्त होती है जो इस प्रकार के गणित के लिए पहले असंभव मानी जाती थी।

रिले रेस की समस्या और जादुगर का जादू

इस सफलता को समझने के लिए, आइए देखें कि ये फ़िल्टर्स आमतौर पर कैसे काम करते हैं। कल्पना कीजिए कि लोगों की एक लंबी कतार है जो एक चेन में संदेश पास कर रहे हैं। प्रत्येक व्यक्ति को संदेश को आगे बढ़ाने से पहले सामने वाले व्यक्ति से संदेश सुनने का इंतज़ार करना पड़ता है। यह "रिकर्सिव" वाला हिस्सा है। यदि आपके पास एक लंबी श्रृंखला है, तो संदेश को अंत तक पहुँचने में लंबा समय लगता है।

इस पेपर के लेखकों ने पहले ही एक लंबे चैन को छोटे टुकड़ों, या "ब्लॉक्स" में तोड़ने का एक तरीका खोज लिया था, जिन्हें तेज़ी से प्रोसेस किया जा सके। लेकिन जब उन्होंने इन ब्लॉक्स को एक साथ कई कंप्यूटरों (जैसे श्रमिकों की एक टीम) को देने की कोशिश की, तो एक नई समस्या सामने आई: एक ब्लॉक का अंत दूसरे ब्लॉक का शुरुआती बिंदु होता है। यदि आप ब्लॉक A को वर्कर 1 को और ब्लॉक B को वर्कर 2 को देते हैं, तो वर्कर 2 वर्कर 1 द्वारा ब्लॉक A को पूरा करने तक प्रतीक्षा करने के लिए मजबूर है। टीम अंततः एक-एक करके ही काम करती है, जिससे टीम होने का उद्देश्य ही समाप्त हो जाता है।

पेपर की मुख्य खोज एक गणितीय "जादू की ट्रिक" है जिसे सुपरपोजिशन (superposition) कहा जाता है। पिछले ब्लॉक से उत्तर की प्रतीक्षा करने के बजाय, कार्यकर्ता अनुमान लगाते हैं कि उत्तर क्या होगा यदि वे शून्य से शुरू करते (एक "जीरो-स्टेट" अनुमान)। वे यह गणना तुरंत करते हैं। फिर, वे पिछले कार्यकर्ता से आने वाले वास्तविक शुरुआती नंबर की प्रतीक्षा करते हैं। एक बार जब वह आ जाता है, तो वे अपने अनुमान में बस एक छोटा सा "सुधार" (correction) जोड़ देते हैं। यह एक ऐसे शेफ की तरह है जो एक रेसिपी के आधार पर सूप बनाना शुरू करता है, यह मानते हुए कि उसके पास अभी कोई सामग्री नहीं है। जब डिलीवरी ट्रक वास्तव में सब्जियां गिरा देता है, तो शेफ बस उन्हें जोड़ देता है और मिला देता है। सूप लगभग तुरंत तैयार हो जाता है क्योंकि खाना पकाने की कठिन प्रक्रिया पहले ही समानांतर (parallel) में पूरी हो चुकी होती है।

दौड़ चलाने के दो अलग तरीके

पेपर दिखाता है कि इस जादुई ट्रिक का उपयोग दो बहुत अलग तरीकों से किया जा सकता है, यह इस पर निर्भर करता है कि आप क्या कर रहे हैं।

1. रियल-टाइम स्ट्रीम (एक असेंबली लाइन)
यदि आप लाइव डेटा को प्रोसेस कर रहे हैं, जैसे कि एक रेडियो प्रसारण, तो आप अगला ऑडियो सेकंड बजाने से पहले पूरे बैच के पूरा होने का इंतज़ार नहीं कर सकते। आपको डेटा उसी क्रम में बाहर आना चाहिए जिस क्रम में वह आया था (First-In, First-Out)।

• समाधान: लेखकों ने मल्टी-कोर CPU के लिए एक "वेवफ्रंट पाइपलाइन" बनाई है। एक असेंबली लाइन की कल्पना करें जहाँ विभिन्न कार्यकर्ता एक ही गाने के विभिन्न चरणों को एक साथ संभाल रहे हैं। वर्कर 1 बास (bass) को साफ कर रहा है, वर्कर 2 वोकल्स को ठीक कर रहा है, और वर्कर 3 इको (echo) जोड़ रहा है। जैसे ही वर्कर 1 एक टुकड़े को पूरा करता है, वह इसे वर्कर 2 को सौंप देता है, जो इसे वर्कर 3 को सौंपता है।
• परिणाम: छह शक्तिशाली कोर वाले आधुनिक कंप्यूटर पर, इस पद्धति ने एक जटिल 16वें-ऑर्डर के फ़िल्टर के लिए 2.4 गीगासैंपल्स प्रति सेकंड की गति प्राप्त की। यह एक सिंगल कोर का उपयोग करने की तुलना में लगभग 4 गुना तेज़ है। दिलचस्प बात यह है कि उन्होंने पाया कि इसमें धीमे "एफिशिएंसी" कोर मिलाने से वास्तव में लाइन धीमी हो गई, जो यह साबित करता है कि इस विशिष्ट कार्य के लिए, कई धीमे श्रमिकों के बजाय कुछ तेज़ श्रमिक बेहतर हैं।

2. बैच प्रोसेसिंग (एक फैक्ट्री)
यदि आप रिकॉर्ड किए गए डेटा की एक बड़ी फ़ाइल (जैसे कि मूवी या डेटाबेस) को प्रोसेस कर रहे हैं, तो आपको क्रम की उतनी चिंता नहीं है जितनी कि कच्ची गति (raw speed) की। आप पूरी फ़ाइल को एक साथ प्रोसेस कर सकते हैं।

• समाधान: उन्होंने शक्तिशाली ग्राफिक्स प्रोसेसिंग यूनिट्स (GPUs) का उपयोग किया, जिनमें हजारों छोटे कार्यकर्ता होते हैं। उन्होंने डिकपल्ड लुकबैक (decoupled lookback) नामक तकनीक का उपयोग किया। एक ऐसी फैक्ट्री की कल्पना करें जहाँ प्रत्येक कार्यकर्ता तुरंत अपने उत्पाद का अपना हिस्सा कैलकुलेट करता है। यदि किसी कार्यकर्ता को पिछले स्टेशन से किसी भाग की आवश्यकता है, तो वह रुकता नहीं है; वह बस एक "स्टेटस बोर्ड" चेक करता है कि क्या पिछला स्टेशन पूरा हो गया है। यदि हो गया है, तो वह भाग ले लेता है। यदि नहीं, तो वह तब तक अन्य चीजों पर काम करना जारी रखता है जब तक कि वह तैयार न हो जाए।
• परिणाम: यह दृष्टिकोण अविश्वसनीय रूप से तेज़ था। NVIDIA RTX 3060 ग्राफिक्स कार्ड पर, सिस्टम ने एक सिंगल फ़िल्टर सेक्शन के लिए 38.2 गीगासैंपल्स प्रति सेकंड की गति प्राप्त की। यह हार्डवेयर की सैद्धांतिक रूप से सक्षम अधिकतम गति (मेमोरी बैंडविड्थ रूफ) का 85% है।

यह क्यों मायने रखता है और यह किसे मात देता है

लेखकों ने केवल चीज़ों को तेज़ ही नहीं बनाया; उन्होंने यह भी साबित किया कि उनकी विधि पुरानी विधियों की तुलना में अधिक विश्वसनीय है।

• "डायरेक्ट फॉर्म" की विफलता: "डायरेक्ट फॉर्म" नामक एक पुरानी विधि है जो एक विशाल कदम में गणित करने की कोशिश करती है। पेपर दिखाता है कि जटिल फ़िल्टर्स (जैसे 16वें-ऑर्डर वाला) के लिए, यह पुरानी विधि विफल हो जाती है। संख्याएँ इतनी उलझ जाती हैं कि कंप्यूटर कचरा परिणाम देने लगता है या क्रैश हो जाता है। इस पेपर में उपयोग किया गया नया "कैस्केडेड" (cascaded) तरीका इन उच्च स्तरों पर भी सटीक रहता है।
• प्रतिस्पर्धा को मात देना: उन्होंने अपने नए GPU कोड की तुलना उपलब्ध सबसे मजबूत मौजूदा पैरेलल फ़िल्टरिंग इंजनों से की। उनकी विधि द्वारा टेस्ट किए गए हर फ़िल्टर ऑर्डर पर यह अधिक तेज़ थी।
• गति की लागत: पेपर ने उनकी गति की "लागत" को भी सावधानीपूर्वक मापा। उन्होंने पाया कि नए, तेज़ चिप्स (जैसे RTX 3060) पर, "बैरियर्स" (चेक जो कार्यकर्ता करते हैं कि क्या वे आगे बढ़ सकते हैं) सस्ते हैं, इसलिए वे अधिक जटिल, तेज़ तरीकों का उपयोग कर सकते हैं। पुराने चिप्स पर, वे चेक महंगे हैं, इसलिए उन्हें सरल तरीकों का उपयोग करना पड़ता है। यह इंजीनियरों को यह जानने में मदद करता है कि उन्हें अपने सॉफ़्टवेयर को विभिन्न हार्डवेयर के लिए ठीक से कैसे ट्यून करना चाहिए।

निचोड़ (The Bottom Line)

यह पेपर एक कठिन, अनुक्रमिक (sequential) गणितीय समस्या को एक पैरेलल पार्टी में बदल देता है। "अनुमान लगाओ और सुधारो" (guess-and-correct) रणनीति का उपयोग करके, उन्होंने कंप्यूटरों को एक-दूसरे का इंतज़ार किए बिना एक साथ काम करने की अनुमति दी।

• लाइव स्ट्रीमिंग के लिए, उन्होंने एक पाइपलाइन बनाई जो एक मानक कंप्यूटर पर 3.95 गुना तेज़ चलती है।
• बैच प्रोसेसिंग के लिए, उन्होंने एक GPU इंजन बनाया जो 38.2 गीगासैंपल्स प्रति सेकंड पर चलता है, जो एक बहुत बड़ी छलांग है।
• महत्वपूर्ण रूप से, उन्होंने साबित किया कि यह तरीका न केवल तेज़ काम करता है, बल्कि यह बेहतर भी है, जहाँ पुराने तरीके विफल हो जाते हैं वहाँ यह सटीक रहता है।

लेखकों ने अपने कोड को एक ओपन-सोर्स लाइब्रेरी के रूप में जारी किया है, जिसका अर्थ है कि अब कोई भी इन सुपर-फास्ट फ़िल्टर्स का उपयोग बेहतर ऑडियो टूल्स, स्पष्ट वीडियो और स्मार्ट रोबोट बनाने के लिए कर सकता है। उन्होंने प्रभावी रूप से एक "सीक्वेंशियल" बाधा को एक "पैरेलल" सुपरहाइवे में बदल दिया है, यह दिखाते हुए कि यहाँ तक कि सबसे जिद्दी गणितीय समस्याओं को भी कंप्यूटरों की एक टीम को तालमेल में काम करने देकर हल किया जा सकता है।