MCTS يخسر أمام إعادات التشغيل العشوائية بنسبة 2,88% في جدولة DAG عند تساوي الميزانية

وضع باحثون على arXiv خوارزمية Monte Carlo Tree Search ومجدوِل قوائم (list scheduler) عادياً بإعادات تشغيل عشوائية في ظروف متطابقة: 2048 جدولاً يُبنى ويُقيَّم لكل مهمة. وخسرت شجرة البحث. ففي 72 من أصل 96 حالة مُستبقاة (held-out) كان لدى الحل الأساسي فيها هامش للتحسين، جاء MCTS أسوأ بنسبة 2,88% في makespan (فاصل الثقة 95%: من −3,62% إلى −2,15%). لا يثبت هذا العمل أن MCTS عديم الفائدة، لكنه يبيّن أن أي مقارنة تخلو من منافس بسيط بالميزانية نفسها تكشف القليل.

بروتوكول كان بإمكانه دحض MCTS

ينطلق المؤلفون من ملاحظة مفادها أن الأوراق التي تتناول MCTS في جدولة سير عمل DAG نادراً ما تمنح الطريقة البسيطة القدر نفسه من الحوسبة. هنا يحصل جميع المشاركين على العدد نفسه من الجداول المرشحة. المشارك الأساسي هو طريقة MCTS التي أُعلن مسبقاً أنها الطريقة الرئيسة. أما المجموعة الضابطة فهي مجدوِل قوائم بإعادات تشغيل عشوائية ودون شجرة. وأُضيف لاحقاً مشارك ثالث على المجال نفسه: MCTS مع UCT الكلاسيكي.

ثُبِّتت خطة التحليل قبل جمع البيانات. وتحقق مدقِّق مستقل من جميع الجداول البالغ عددها 768 في مرحلة التأكيد: كلها صالحة، وأزمنة الإنجاز محسوبة بشكل صحيح.

• الميزانية الأساسية: 2048 جدولاً مُقيَّماً.
• الفجوة بين MCTS وإعادات التشغيل: −2,88%، فاصل الثقة [−3,62%; −2,15%].
• التحسّن الذاتي على مجموعة الدراسة المنفصلة: إعادات التشغيل +1,85%، وMCTS +0,24%.
• النتائج الأولى لـ MCTS: 700 من أصل 720 تطابقت مع warm start الذي سُلِّم إليه.
• MCTS مع UCT الكلاسيكي: −0,26%، فاصل الثقة [−0,71%; +0,23%].
• النطاق: 8 و16 و32 مهمة، من 2 إلى 8 معالجات، وميزانيات حتى 2048.

لماذا لم تفد الشجرة

الفرضية الأولى أن ميزانية MCTS ببساطة لم تكفِ. لكن البيانات لا تدعمها: ففي مجموعة الدراسة حسّنت إعادات التشغيل نفسها بنسبة 1,85%، بينما حسّن MCTS نفسه بنسبة 0,24% فقط. يضاف إلى ذلك أن النتيجة الأولى لـ MCTS في 700 من أصل 720 حالة لم تكن سوى الحل الابتدائي الذي سُلِّم إليه. أي أن الشجرة بالكاد ابتعدت عن نقطة البداية.

وبحسب المؤلفين، يكمن السبب في قاعدة الاختيار. فهي تعلق بصورة حتمية عند أول فرع جديد يُفتَح، ولذلك ترتبط التجارب داخل الفرع الواحد ارتباطاً قوياً. أما إعادات التشغيل فتختار في كل مرة مساراً جديداً وتستفيد من أطراف التوزيع. ويصف المؤلفون صلة ذلك بـ makespan بأنها استنتاج، لا آلية سببية مثبتة. ويدعم هذه الفرضية تجربة استبدال القاعدة بـ UCT الكلاسيكي: يتقلص التأخر إلى 0,26%، ويشمل فاصل الثقة الصفر. لكن الإشارة تبقى سالبة، فلا يتفوق MCTS على إعادات التشغيل حتى في النسخة المصحَّحة.

وبنى المؤلفون كذلك خريطة بنيوية منفصلة. ففي سير العمل المتفرق وغير المنتظم تتفوق إعادات التشغيل. وفي سير العمل المنتظم ذي الطبقات لا تظهر فروق. أما في الرسوم الكثيفة فلا يكاد يوجد ما يمكن تحسينه، لأن الحل الأساسي قريب أصلاً من الحد الأقصى.

ما الذي يجب فحصه قبل بناء الشجرة

بالنسبة إلى المهندسين الذين يجدولون المهام في خطوط أنابيب البيانات أو تدريب النماذج أو سلاسل الوكلاء، الخلاصة عملية. قبل اعتماد MCTS، يستحق الأمر تشغيل مجدوِل قوائم عشوائي بالعدد نفسه من التقييمات. ينجَز ذلك في أمسية واحدة ويوفر نقطة مرجعية نزيهة. وإذا لم تتفوق الشجرة عليه، فلا مبرر للتعقيد.

الفحص الثاني هو نسبة الحلول التي ابتعد فيها البحث عن warm start. فإذا تطابقت جميع النتائج تقريباً مع نقطة البداية، فالخوارزمية لا تستكشف تقريباً. والفحص الثالث هو قاعدة اختيار الفرع نفسها، إذ يتوقف عليها تنوع الشجرة.

ويذكر المؤلفون بأنفسهم حدود العمل. فالتجربة اصطناعية، والرسوم صغيرة (حتى 32 مهمة)، والميزانية لا تتجاوز 2048. ولا توجد استنتاجات عن الميزانيات الأكبر ولا عن سير العمل الحقيقي. لكن العمل مفيد كنموذج للانضباط المنهجي: تسجيل مسبق للخطة، وميزانية متساوية، وتحقق مستقل من صلاحية الجداول. وفي الأنظمة الوكيلة، حيث كثيراً ما يُعتمد المجدوِل لمجرد أن اسم الخوارزمية رائج، فإن هذا النوع من الضبط لا يقل ضرورة عن الطرق الجديدة.