ParallelMergeXplain: A Speculative Parallel Variant of MergeXplain for Multi-Conflict Detection in Constraint-Based Systems

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

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

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

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

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

परिणामों ने दिखाया कि नया तरीका सटीकता के मामले में पुराने वाले के समान ही काम करता है। हर एक परीक्षण में, नए एल्गोरिदम ने संघर्षों का बिल्कुल वही सेट पाया जो मूल ने पाया था, जिससे यह सिद्ध हुआ कि गति बढ़ाने वाली तकनीकों ने कोई त्रुटि पेश नहीं की। जब बात गति की आई, तो नया तरीका तेज़ था, लेकिन गति में कितनी वृद्धि हुई यह समस्या की जटिलता पर निर्भर था। वास्तविक-दुनिया के बेंचमार्क पर, नया सिस्टम पुराने वाले की तुलना में लगभग 1.5 गुना तेज़ था। सिंथेटिक परीक्षणों पर, गति में वृद्धि अधिक मामूली थी, जो औसतन लगभग 1.2 गुना तेज़ थी। शोधकर्ताओं ने पाया कि सबसे बड़ी बढ़त तब आई जब उन्होंने दोनों रणनीतियों को मिलाया: शाखाओं को समानांतर में चलाना और क्लीनअप लूप में स्पेक्युलेटिव गेसिंग का उपयोग करना। हालाँकि, उन्होंने एक सीमा भी खोजी। यदि वे दो उपलब्ध कोर पर बहुत अधिक कार्यों को डालने की कोशिश करते, तो कंप्यूटर समस्या को हल करने के बजाय कार्यों को प्रबंधित करने में अधिक समय बिताता, और गति का लाभ समाप्त हो जाता। इसने पुष्टि की कि केवल अधिक कार्यकर्ता जोड़ने से काम हमेशा तेज़ नहीं होता; कार्यकर्ताओं को कार्य के आकार के अनुरूप होना चाहिए।

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