📊 statistics

Dynamic Core Allocation for Malleable Jobs with Unknown Speed-up Parameters

यह शोध पत्र एक पुनरावृत्ति शिक्षण-और-नियंत्रण ढांचे का प्रस्ताव करता है जो एक मल्टीकोर सिस्टम में मैलेबल (malleable) जॉब्स के बीच कोर को गतिशील रूप से आवंटित करने और दीर्घकालिक औसत रिस्पॉन्स टाइम को न्यूनतम करने के लिए अज्ञात स्पीड-अप मापदंडों के मैक्सिमम लाइकलीहुड एस्टीमेशन को मार्कोव डिसीजन प्रोसेस-आधारित पॉलिसी अपडेट्स के साथ जोड़ता है।

मूल लेखक: S. ~A. Bodas, J. ~L. Dorsman, M. Mandjes, L. Ravner

प्रकाशित 2026-06-19

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: S. ~A. Bodas, J. ~L. Dorsman, M. Mandjes, L. Ravner

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक व्यस्त रसोई के प्रबंधक (मैनेजर) हैं जहाँ शेफ की एक निश्चित संख्या (कोर्स/cores) उपलब्ध है। हर दिन, ऑर्डर (जॉब्स) आते हैं। कुछ ऑर्डर सरल होते हैं, जैसे सलाद बनाना, जबकि अन्य जटिल होते हैं, जैसे बहु-परत वाला केक बेक करना।

आपकी सबसे बड़ी चुनौती समानांतरता (parallelism) है: क्या आप एक ही ऑर्डर पर अधिक शेफ लगाकर उसे तेज़ी से पूरा कर सकते हैं?

चुनौती: यह हमेशा 1-से-1 का सटीक गति लाभ नहीं होता है। यदि आपके पास 10 शेफ हैं, तो शायद आप एक केक को 1-शेफ की तुलना में 10 गुना तेज़ी से पूरा नहीं कर पाएंगे। हो सकता है कि 5 शेफ सब्जियां काट रहे हों, लेकिन 2 ओवन का इंतज़ार कर रहे हों, और 3 बस एक-दूसरे के काम में बाधा डाल रहे हों। इसे घटता हुआ प्रतिफल (diminishing returns) कहा जाता है।

अतीत में, प्रबंधक यह मान लेते थे कि उन्हें पता है कि उनके शेफ हर प्रकार के ऑर्डर के लिए कितने कुशल हैं। लेकिन वास्तविक दुनिया में (जैसे आधुनिक क्लाउड कंप्यूटिंग या AI ट्रेनिंग में), चीजें बदलती रहती हैं। हार्डवेयर अपग्रेड किया जाता है, सॉफ्टवेयर अलग तरह से व्यवहार करता है, और आपको वास्तव में यह नहीं पता होता कि अधिक मदद मिलने पर आपके ऑर्डर कितनी तेज़ी से पूरे होंगे—यानी आपको वह "गुप्त रेसिपी" नहीं पता होती।

यह शोध पत्र एक स्मार्ट सिस्टम प्रस्तुत करता है जो रसोई चलते समय इस गुप्त रेसिपी को सीखता है।

ऑर्डर्स के दो प्रकार

रसोई दो प्रकार के ऑर्डर (क्लास 1 और क्लास 2) संभालती है।

क्लास 1 एक ऐसे ऑर्डर का प्रकार हो सकता है जिसे अधिक शेफ देने पर बहुत बड़ा गति लाभ मिलता है।
क्लास 2 एक ऐसे ऑर्डर का प्रकार हो सकता है जहाँ अधिक शेफ देने से मदद तो मिलती है, लेकिन बहुत कम।
समस्या: आप देख सकते हैं कि किस प्रकार का ऑर्डर अभी आया है, लेकिन आप उस विशिष्ट "स्पीड-अप पैरामीटर" (वह गुप्त संख्या जो बताती है कि मदद मिलने पर काम कितना तेज़ होगा) को नहीं जानते।

"सीखें और समायोजित करें" (Learn and Adjust) रणनीति

लेखक एक सीखने (Learning) और कार्य करने (Acting) के चक्र का प्रस्ताव देते हैं, जैसे कोई शेफ सूप चखकर उसमें नमक या मिर्च को समायोजित करता है:

अनुमान लगाना (एलोकेशन): आप एक अनुमान के साथ शुरू करते हैं कि ऑर्डर कितनी तेज़ी से चलेंगे। आप अपने अनुमान के आधार पर ऑर्डर्स को शेफ आवंटित करते हैं।
अवलोकन (डेटा संग्रह): आप रसोई पर नज़र रखते हैं। आप नोट करते हैं कि ऑर्डर्स को पूरा होने में वास्तव में कितना समय लगा और उस दौरान कितने शेफ उन पर काम कर रहे थे।
सबक सीखना (एस्टिमेशन): आप मैक्सिमम लाइकलीहुड एस्टिमेशन (Maximum Likelihood Estimation) नामक एक गणितीय उपकरण का उपयोग करते हैं (इसे एक बहुत ही स्मार्ट जासूस की तरह समझें) जो प्रस्थान के समय (departure times) का विश्लेषण करता है। यह पूछता है: "इन ऑर्डर्स के वास्तव में इतनी तेज़ी से समाप्त होने के आधार पर, प्रत्येक प्रकार के लिए सबसे संभावित 'गुप्त स्पीड-अप नंबर' क्या था?"
अपडेट करना (ऑप्टिमाइज़ेशन): आप इन नए, अधिक सटीक नंबरों का उपयोग करते हैं और एक जटिल पहेली (मार्कोव डिसीजन प्रोसेस - Markov Decision Process) को हल करते हैं ताकि यह पता लगाया जा सके कि रसोई को सबसे तेज़ चलाने के लिए अपने शेफ को दो प्रकार के ऑर्डर्स के बीच विभाजित करने का परफेक्ट तरीका क्या है।
दोहराना: आप इस नए प्लान के साथ रसोई चलाते हैं, अधिक डेटा एकत्र करते हैं, फिर से सीखते हैं, और और भी बेहतर होते जाते हैं।

"समान साझाकरण" का नियम

प्रत्येक प्रकार के ऑर्डर के भीतर, सिस्टम एक सरल नियम का पालन करता है: शेफ को समान रूप से साझा करें।
यदि आपके पास टाइप 1 के 3 ऑर्डर हैं और आपने तय किया है कि आप उन्हें कुल 6 शेफ देंगे, तो प्रत्येक ऑर्डर को 2 शेफ मिलेंगे। आप एक को 5 और दूसरे को 1 शेफ नहीं देंगे। शोध पत्र यह सिद्ध करता है कि इस विशिष्ट प्रकार की रसोई के लिए, एक बार जब आप जान जाते हैं कि ऑर्डर कितनी तेज़ी से चलते हैं, तो काम संभालने का सबसे अच्छा तरीका यही समान साझाकरण है। कठिन काम यह पता लगाना है कि वे कितनी तेज़ी से चलते हैं।

प्रयोगों ने क्या दिखाया

लेखकों ने कंप्यूटर सिमुलेशन के साथ इस सिस्टम का परीक्षण किया:

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

मुख्य निष्कर्ष (The Bottom Line)

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

तकनीकी सारांश: अज्ञात त्वरण मापदंडों (Speed-up Parameters) वाले लचीले कार्यों (Malleable Jobs) के लिए गतिशील कोर आवंटन

समस्या विवरण
यह शोध पत्र मल्टीकोर कंप्यूटिंग सिस्टम में डायनेमिक रिसोर्स एलोकेशन की समस्या को संबोधित करता है, जो "लचीले" (malleable) कार्यों की एक स्ट्रीम को संभाल रहे हैं। "मोल्डेबल" (moldable) कार्यों के विपरीत, जहाँ आवंटित कोर की संख्या आगमन पर स्थिर रहती है, लचीले कार्य निष्पादन के दौरान प्रसंस्करण क्षमता के गतिशील पुनर्वितरण की अनुमति देते हैं। सिस्टम में निश्चित संख्या में समान कोर ( $c$ ) और दो अवलोकन योग्य जॉब क्लास मौजूद हैं। प्रत्येक जॉब क्लास को एक विशिष्ट, अज्ञात त्वरण फलन (speed-up function) $s(z; p)$ द्वारा परिभाषित किया जाता है, जहाँ $z$ आवंटित क्षमता है और $p$ समानांतरकरण की डिग्री को नियंत्रित करने वाला एक अज्ञात पैरामीटर है।

उद्देश्य सिस्टम में लंबे समय तक रहने वाले औसत जॉब्स की संख्या (जो स्थिर अवस्था में औसत प्रतिक्रिया समय के बराबर है) को कम करना है। यहाँ एक मौलिक ट्रेड-ऑफ मौजूद है: अधिक कोर आवंटित करने से कार्य तेजी से पूरा होता है, लेकिन घटते प्रतिफल (जैसे, एमडाहल का नियम/Amdahl's Law) के कारण, अधिक कोर आवंटित करने से होने वाला लाभ कम होता जाता है। जब त्वरण पैरामीटर ज्ञात और स्थिर होते हैं, तो ऐसे सिस्टम के लिए इष्टतम नीतियां (विशेष रूप से क्लासेज के भीतर समान साझाकरण के लिए EQUI नीति और मार्कोव निर्णय प्रक्रियाओं के माध्यम से क्लासेज के बीच इष्टतम अंश) ज्ञात हैं, लेकिन यह शोध पत्र उस परिदृश्य को संबोधित करता है जहाँ पैरामीटर्स $p_1$ और $p_2$ अज्ञात हैं और उन्हें परिचालन डेटा से सीखना आवश्यक है। यह अंतराल आधुनिक अनुप्रयोगों जैसे कि क्लाउड GPU पर बड़े पैमाने पर मशीन लर्निंग ट्रेनिंग से प्रेरित है, जहाँ वर्कलोड या हार्डवेयर अपग्रेड के कारण स्पीड-अप की विशेषताएं बदल सकती हैं, जिससे स्थिर धारणाएं अवास्तविक हो जाती हैं।

कार्यप्रणाली
लेखक एक पुनरावृत्ति शिक्षण-और-नियंत्रण (iterative learning-and-control) ढांचे का प्रस्ताव करते हैं जो पैरामीटर अनुमान और नीति अनुकूलन के बीच बारी-बारी से कार्य करता है।

सिस्टम मॉडल:
- जॉब्स $\lambda$ दर के पॉइसन प्रक्रिया (Poisson process) के माध्यम से आते हैं। सेवा आवश्यकताएं $\mu$ दर के साथ एक्सपोनेंशियल रूप से वितरित होती हैं।
- जॉब्स क्लास 1 (प्रायिकता $\alpha$ ) या क्लास 2 (प्रायिकता $1-\alpha$ ) के होते हैं।
- त्वरण फलन $s(z; p)$ $z \le 1$ के लिए रैखिक है और $z > 1$ के लिए अवतल (concave)/गैर-घटता हुआ है। दो विशिष्ट मॉडलों पर विचार किया गया है: एमडाहल का नियम और एक पावर-लॉ मॉडल ( $s(z; p) = \max\{z, 1\}^p$ )।
- आवंटन नीति $\pi$ वर्तमान सिस्टम स्टेट $(n^{(1)}, n^{(2)})$ के आधार पर क्लास 1 के जॉब्स को आवंटित कोर के अंश को निर्धारित करती है। प्रत्येक क्लास के भीतर, कोर समान रूप से साझा किए जाते हैं (EQUI नीति)।
पैरामीटर अनुमान (मैक्सिमम लाइक्लीहुड - Maximum Likelihood):
- सीखने की प्रक्रिया का मुख्य भाग स्टेट-डिपेंडेंट इंटर-डिपार्चर टाइम (state-dependent inter-departure times) पर आधारित एक मैक्सिमम लाइक्लीहुड एस्टीमेटर (MLE) है।
- प्रत्येक क्लास के लिए डिपार्चर प्रोसेस को एक स्टेट-डिपेंडेंट पॉइसन प्रक्रिया के रूप में मॉडल किया गया है। तात्कालिक डिपार्चर दर $\delta^{(i)}$ जॉब्स की संख्या $n^{(i)}$ , आवंटित कोर $c^{(i)}$ , और अज्ञात पैरामीटर $p_i$ पर निर्भर करती है।
- लाइक्लीहुड फंक्शन को उन उप-अंतरालों (sub-intervals) में विभाजित करके बनाया जाता है जहाँ सिस्टम स्टेट (और इस प्रकार डिपार्चर दर) स्थिर रहती है। लॉग-लाइक्लीहुड को देखे गए डिपार्चर समय और सिस्टम स्टेट के अनुक्रम के आधार पर स्पष्ट रूप से व्युत्पन्न किया गया है।
- लेखक सिद्ध करते हैं कि एक निश्चित आवंटन नीति के तहत, ये MLEs स्ट्रॉन्गली कंसिस्टेंट (लगभग निश्चित रूप से वास्तविक पैरामीटर्स की ओर अभिसरित होते हैं) हैं, जैसे-जैसे देखे गए डिपारचर्स की संख्या बढ़ती है। यह प्रमाण क्यूइंग सिस्टम की पुनर्योजी संरचना (regenerative structure) और $p$ के सापेक्ष स्पीड-अप फंक्शन की लिप्सचिट्ज़ निरंतरता (Lipschitz continuity) पर आधारित है।
नीति अनुकूलन (MDP):
- एक बार पैरामीटर अनुमानित हो जाने के बाद, एक मार्कोव निर्णय प्रक्रिया (MDP) के बेलमैन ऑप्टिमैलिटी इक्वेशन को हल करके इष्टतम आवंटन नीति की गणना की जाती है।
- स्टेट स्पेस को प्रत्येक क्लास में जॉब्स की संख्या द्वारा परिभाषित किया जाता है। एक्शन स्पेस क्लास 1 को आवंटित कोर का अंश है।
- कॉस्ट फंक्शन सिस्टम में मौजूद जॉब्स की कुल संख्या है। MDP को निरंतर-समय प्रक्रिया को डिस्क्रीट-टाइम समकक्ष में यूनिफॉर्माइज करने के बाद वैल्यू इटरेशन का उपयोग करके हल किया जाता है।
लर्निंग एल्गोरिदम:
लेखक इस लूप को लागू करने वाले दो विशिष्ट एल्गोरिदम प्रस्तावित करते हैं:
- एल्गोरिदम 1a: केवल हालिया ऑब्जर्वेशन विंडो (एक निश्चित संख्या में डिपारचर्स $N_k$ द्वारा परिभाषित) के दौरान एकत्र किए गए डेटा का उपयोग अनुमान अपडेट करने के लिए करता है। यह गैर-स्थिर (non-stationary) वातावरण में अनुकूलन क्षमता प्रदान करता है जहाँ पैरामीटर्स समय के साथ बदल सकते हैं।
- एल्गोरिदम 1b: अनुमान अपडेट करने के लिए समय $t=0$ से संचित सभी डेटा का उपयोग करता है। हालांकि यह स्थिर सेटिंग्स में तेज़ अभिसरण और उच्च सटीकता प्रदान करता है, यह बदलते पैरामीटर्स के प्रति कम अनुकूलनीय है।

मुख्य योगदान

मैलिएबल जॉब मॉडल्स का विस्तार: यह शोध पत्र अज्ञात त्वरण मापदंडों के लिए लर्निंग मैकेनिज्म पेश करके शास्त्रीय मैलिएबल-जॉब कोर एलोकेशन मॉडल्स का विस्तार करता है, जो पूर्व-निर्धारित ज्ञान की धारणा से आगे बढ़ता है।
क्यूइंग सिस्टम में सांख्यिकीय अनुमान: यह स्टेट-डिपेंडेंट इंटर-डिपार्चर टाइम का उपयोग करके समानांतरकरण विशेषताओं का अनुमान लगाने के लिए एक विशिष्ट MLE प्रक्रिया विकसित करता है, और निश्चित नीतियों के तहत स्ट्रॉन्ग कंसिस्टेंसी को सिद्ध करता है।
एकीकृत लर्निंग फ्रेमवर्क: यह दो पुनरावृत्ति एल्गोरिदम (1a और 1b) का प्रस्ताव और विश्लेषण करता है जो सांख्यिकीय अनुमान को डायनेमिक प्रोग्रामिंग-आधारित नीति अपडेट के साथ जोड़ते हैं।
संख्यात्मक सत्यापन: अपने विस्तृत संख्यात्मक प्रयोगों के माध्यम से, शोध पत्र प्रदर्शित करता है कि प्रस्तावित विधियाँ सटीक पैरामीटर अनुमान प्राप्त करती हैं और अपेक्षाकृत कम अवलोकन अवधि के बाद इष्टतम सिस्टम प्रदर्शन प्रदान करती हैं। यह एक "क्वासी-आइडेंटिफिएबिलिटी" (quasi-identifiability) मुद्दे को भी उजागर करता है जहाँ कम समानांतरकरण (लो $p$ ) वाले जॉब्स के लिए पैरामीटर का अनुमान लगाना अधिक कठिन होता है।

परिणाम

अभिसरण (Convergence): संख्यात्मक प्रयोग पुष्टि करते हैं कि एस्टीमेटर्स वास्तविक पैरामीटर्स की ओर अभिसरित होते हैं। स्थिर सेटिंग्स में एल्गोरिदम 1b, पूर्ण डेटा इतिहास के उपयोग के कारण 1a की तुलना में तेज़ी से अभिसरण करता है।
अनुकूलन क्षमता (Adaptability): एक गैर-स्थिर प्रयोग में जहाँ स्पीड-अप पैरामीटर्स विशिष्ट समय बिंदुओं पर बदलते हैं, एल्गोरिदम 1a सफलतापूर्वक विकसित होते हुए पैरामीटर्स को ट्रैक करता है और अपनी आवंटन नीति को समायोजित करता है, जो गतिशील वातावरण में इसकी उपयोगिता को दर्शाता है।
प्रदर्शन: सीखे गए नीतियां (learned policies) उस सैद्धांतिक इष्टतम के करीब औसत प्रतिक्रिया समय प्राप्त करती हैं जो तब प्राप्त होता यदि वास्तविक पैरामीटर्स शुरुआत से ही ज्ञात होते।
अनुमान में विषमता (Asymmetry in Estimation): परिणाम संकेत देते कि कम समानांतरकरण (छोटा $p$ ) वाली क्लास के पैरामीटर का अनुमान लगाना स्वाभाविक रूप से अधिक चुनौतीपूर्ण और धीमा है, क्योंकि इस शासन (regime) में कोर आवंटन परिवर्तनों के प्रति स्पीड-अप फंक्शन की संवेदनशीलता कमजोर होती है।

महत्व
यह शोध पत्र एक महत्वपूर्ण अंतर को संबोधित करके अपना महत्व दावा करता है: स्पीड-अप फंक्शन्स के ज्ञात और स्थिर होने की धारणा। इन पैरामीटर्स को ऑनलाइन सीखने का ढांचा प्रदान करके, यह कार्य आधुनिक, गतिशील कंप्यूटिंग वातावरण (जैसे क्लाउड-आधारित AI ट्रेनिंग) के लिए एक व्यावहारिक समाधान पेश करता है जहाँ संसाधन दक्षता सर्वोपरि है लेकिन सिस्टम की विशेषताएं अनिश्चित हैं। लेखक नोट करते हैं कि जबकि यह ढांचा दो से अधिक जॉब क्लासेज के लिए स्वाभाविक रूप से विस्तारित होता है, संबंधित बेलमैन समीकरणों को हल करने की कम्प्यूटेशनल जटिलता काफी बढ़ जाती है, जो मॉडल की अभिव्यक्ति (expressiveness) और ट्रैक्टेबिलिटी (tractability) के बीच एक ट्रेड-ऑफ को रेखांकित करती है। यह कार्य गैर-स्थिर सेटिंग्स, सामान्य सर्विस-टाइम डिस्ट्रीब्यूशन और उच्च-आयामी प्रणालियों के लिए स्केलेबल एप्रोक्सिमेशन विधियों में भविष्य के अनुसंधान के लिए आधार तैयार करता है।

ऑर्डर्स के दो प्रकार

"सीखें और समायोजित करें" (Learn and Adjust) रणनीति

"समान साझाकरण" का नियम

प्रयोगों ने क्या दिखाया

मुख्य निष्कर्ष (The Bottom Line)

इसी तरह के और पेपर