असिम्प्टोटिकली ऑप्टिमल मल्टीपल पैरललाइजेबल नौकरी कक्षाओं का शेड्यूलिंग

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