Advanced Scheduling Strategies for Distributed Quantum Computing Jobs
تقترح هذه الورقة وتقيّم مجموعة من استراتيجيات الجدولة المتقدمة، بما في ذلك الاستدلالات والتعلم المعزز، لتحسين تخصيص وظائف الحوسبة الكمومية الموزعة عبر الشبكات غير المتجانسة مع معالجة قيود فريدة مثل استغلال وحدات المعالجة الكمومية (QPU) ومعدلات البوابات غير المحلية.
تخيل أنك مدير موقع بناء ضخم وعالي التقنية. ولكن بدلاً من الرافعات والشاحنات، عمالك هم المعالجات الكمومية (QPUs)، والمواد التي يبنون بها هي الحالات الكمومية (مثل الجسيمات المتشابكة).
في الأيام الخوالي، كان لديك رافعة واحدة عملاقة. أما الآن، فلديك أسطول كامل من الرافعات الأصغر المنتشرة في مدينة بأكملها، متصلة ببعضها عبر طرق. هدفك هو بناء ناطحة سحاب ضخمة (حساب كمومي معقد) من خلال جعل كل هذه الرافعات تعمل معاً. هذا هو الحوسبة الكمومية الموزعة (DQC).
المشكلة؟ إنها كابوس لوجستي.
الطرق غريبة الأطوار: الطرق التي تربط بين رافعاتك ليست كلها متشابهة. بعضها عبارة عن طرق سريعة ممهدة (روابط عالية الجودة)، وبعضها مسارات ترابية وعرة (روابط منخفضة الجودة).
المواد هشة للغاية: "الطوب" الذي تستخدمه (الجسيمات المتشابكة) يشبه فقاعات الصابون. إذا لم تستخدمها بسرعة، فستنفجر (فقدان الترابط/Decoherence).
حركة المرور فوضوية: الوظائف (مهام البناء) تصل بشكل عشوائي. بعضها عمليات إصلاح صغيرة؛ والبعض الآخر بناء أجنحة كاملة لناطحة السحاب.
هذه الورقة البحثية تدور حول إيجاد أفضل شرطي مرور لإدارة موقع البناء الفوضوي هذا بحيث يتم بناء ناطحة السحاب بأسرع وقت ممكن دون إهدار الموارد.
التحدي الجوهري: "مدة الإنجاز" (Makespan)
الهدف الرئيسي هو تقليل مدة الإنجاز. فكر في هذا على أنه الوقت من لحظة وصول أول شاحنة إلى الموقع حتى وضع آخر طوبة وانتهاء المبنى تماماً. تريد أن يكون هذا الوقت أقصر ما يمكن.
استراتيجيات شرطي المرور (خوارزميات الجدولة)
اختبر المؤلفون عدة استراتيجيات لـ "شرطي المرور" لمعرفة أي منها يدير الأسطول بشكل أفضل. إليك كيف تعمل باستخدام تشبيه موقع البناء الخاص بنا:
1. شرطي "الأولوية لمن يأتي أولاً" (FIFO)
كيف يعمل: هذا الشرطي صارم جداً. يقوم بصف الشاحنات بنفس الترتيب الذي وصلت به تماماً. إذا كانت الشاحنة الأولى تحتاج إلى 5 رافعات، فإنه ينتظر حتى تتوفر 5 رافعات، حتى لو كانت الشاحنة الثانية تحتاج إلى رافعة واحدة فقط وكان بإمكانها البدء فوراً.
النتيجة: إنه بسيط، ولكنه غالباً ما يكون غير فعال. تظل الرافعات خاملة أثناء انتظار الشاحنة الكبيرة، مما يضيع الوقت.
2. شرطي "تعظيم الموارد" (Resource-Prioritize)
كيف يعمل: ينظر هذا الشرطي إلى الطابور ويسأل: "كيف يمكنني جعل أكبر عدد ممكن من الرافعات تعمل في نفس اللحظة؟" يقوم بتجميع الوظائف معاً لملء الأسطول بالكامل، حتى لو تطلب الأمر الانتظار قليلاً للعثور على التركيبة المثالية.
النتيجة: رائع في الحفاظ على انشغال الرافعات (استغلال عالٍ)، ولكن أحياناً يؤدي وقت الانتظار للعثور على المجموعة المثالية إلى إبطاء وقت الانتهاء الإجمالي.
3. شرطي "المهمة السهلة" (EPR Scheduler)
كيف يعمل: في عالم الكم، تحتاج بعض الوظائف إلى "أزواج متشابكة" (EPRs) — فكر في هذه كأنها كابلات اتصال خاصة وهشة بين الرافعات. بعض الوظائف تحتاج إلى كابل واحد؛ وأخرى تحتاج إلى 100 كابل. هذا الشرطي يعطي الأولوية للوظائف التي تحتاج إلى أقل عدد من الكابلات.
لماذا؟ لأن الوظائف ذات الكابلات الأقل هي عادةً الأسرع في الانتهاء. من خلال إنهاء المهام السهلة أولاً، يقوم الشرطي بتفريغ مساحة للوظائف الكبيرة والصعبة لاحقاً.
النتيجة: غالباً ما يؤدي هذا إلى تجربة أكثر عدلاً لجميع الوظائف وإنهاء سريع جداً للمهام الصغيرة.
4. شرطي "المسار الذكي" (EPR + Node Selection)
كيف يعمل: هذا هو شرطي "المهمة السهلة"، لكنه أيضاً خبير في نظام الـ GPS. هو يعلم أن بعض الطرق (الروابط) وعرة وبطيئة. إذا كانت وظيفة ما تحتاج إلى كابل، فهو لا يكتفي بتعيين أي رافعة؛ بل يعين الرافعة المتصلة بـ "أكثر الطرق سلاسة".
النتيجة: هو البطل في هذه الورقة. من خلال الجمع بين "إنهاء المهام السهلة أولاً" و"استخدام أفضل الطرق"، تمكنوا من إنهاء ناطحة السحاب بشكل أسرع من أي شخص آخر.
5. الشرطي "الديناميكي" (ASAP)
كيف يعمل: هذا الشرطي لا ينتظر تشكل مجموعة. بمجرد أن تصبح رافعة واحدة متاحة، يقوم فوراً بتعيين الوظيفة التالية المتاحة لها. هو في حركة مستمرة، ولا يترك رافعة واحدة خاملة.
النتيجة: سريع جداً، ولكن أحياناً يقوم بتعيين مهمة معقدة لطريق بطيء لأنه كان في عجلة من أمره للبدء.
كيف يعمل: هذا الشرطي هو ذكاء اصطناعي. بدلاً من اتباع كتاب قواعد صارم، هو يلعب لعبة فيديو حيث الهدف هو إنهاء المبنى بسرعة. يحاول استراتيجيات مختلفة، ويحصل على "نقاط" (مكافآت) عند الإنهاء بسرعة، ويتعلم من أخطائه.
النتيجة: هو مرن وذكي للغاية. عندما يتعلم اختيار أفضل الطرق (Node Selection)، فإنه يؤدي بشكل يقارب أداء شرطي "المسار الذكي".
النتائج الرئيسية
أجرى الباحثون آلاف المحاكاة (مثل تشغيل موقع البناء في لعبة فيديو) لمعرفة من سيفوز.
الفائز: كان شرطي "المسار الذكي" (EPR مع اختيار العقدة) و**"المتعلم بالذكاء الاصطناعي" (PPO مع اختيار العقدة)** هما الأسرع. لقد أثبتا أن معرفة أي طريق يجب اتخاذه لا تقل أهمية عن معرفة أي مهمة يجب القيام بها أولاً.
الوصيف: جاء الشرطي "الديناميكي" (ASAP) في المركز الثاني. لقد أظهر أن إبقاء العمال مشغولين في اللحظة التي يصبحون فيها متاحين هو أمر بالغ الأهمية.
الدرس المستفاد: في عالم الكم، لا يمكنك معاملة جميع الاتصالات على أنها متساوية. إذا كان لديك مزيج من الاتصالات السريعة والبطيئة، فيجب أن تأخذ استراتيجية الجدولة الخاصة بك ذلك في الاعتبار.
لماذا هذا مهم؟
بينما نتحرك نحو مستقبل حيث يتم ربط الحواسيب الكمومية معاً (مثل "الإنترنت الكمومي")، لن يكون لدينا مجرد حاسوب خارق واحد؛ بل سيكون لدينا العديد من الحواسيب الأصغر التي تعمل معاً. توفر هذه الورقة البحثية "كتاب القواعد" لكيفية إدارة حركة المرور هذه حتى لا نعلق في ازدحام مروري كمومي، مما يضمن قدرتنا على حل المشكلات المعقدة (مثل علاج الأمراض أو تصميم مواد جديدة) بأسرع وقت ممكن.
إليك ملخص تقني مفصل لورقة البحث بعنوان "استراتيجيات الجدولة المتقدمة لوظائف الحوسبة الكمومية الموزعة".
1. بيان المشكلة
تهدف الحوسبة الكمومية الموزعة (DQC) إلى توسيع قدرة الحوسبة الكمومية من خلال ربط وحدات المعالجة الكمومية (QPUs) المتعددة عبر شبكة كمومية. وبينما يوفر هذا إمكانات توسع أسية مقارنة بالحوسبة الكلاسيكية الموزعة، فإنه يفرض تحديات فريدة في إدارة التنفيذ:
القيود الخاصة بالكم: على عكس الأنظمة الكلاسيكية، تعتمد الحوسبة الكمومية الموزعة على توليد وتوزيع أزواج EPR (حالات متشابكة) للعمليات غير المحلية. وهذا يفرض مقايضة بين معدل توليد التشابك ودقته (fidelity)، بالإضافة إلى قيود زمنية صارمة بسبب فك الترابط (decoherence).
تعقيد الجدولة: إن مشكلة جدولة وظائف الحوسبة الكمومية الموزعة (الدوائر الفرعية التي تتطلب وحدات معالجة كمومية متعددة) هي مشكلة من نوع NP-hard. يجب موازنة أهداف الجدولة التقليدية (تقليل زمن الإنجاز - makespan وتعظيم استغلال الموارد) مقابل مقاييس خاصة بالكم مثل معدلات البوابات غير المحلية والكمون المرتبط بالوظائف في قائمة الانتظار.
عدم التجانس: غالبًا ما تتميز الشبكات الكمومية بروابط غير متجانسة (تختلف في الدقة وسرعة التوليد)، مما يتطلب من المجدولين اتخاذ قرارات ذكية بشأن اختيار العقد، وهو ما لا تأخذه المجدولات الكلاسيكية (مثل FIFO) في الاعتبار.
2. المنهجية
قام المؤلفون بتطوير إطار محاكاة متكامل باستخدام محاكي Qoala لنمذجة سير عمل الحوسبة الكمومية الموزعة، بدءًا من تجميع الدائرة وصولاً إلى إدارة التنفيذ.
أ. سير عمل الحوسبة الكمومية الموزعة ونموذج الشبكة
سير العمل: يتم تفكيك الدائرة الكمومية الموحدة إلى دوائر فرعية (وظائف) بواسطة مترجم (compiler). ثم يقوم مدير التنفيذ بجدولة هذه الوظائف على شبكة متصلة بالكامل من وحدات المعالجة الكمومية (QPUs).
نموذج الشبكة: تستخدم المحاكاة طوبولوجيا متصلة بالكامل مع روابط غير متجانسة. يتم نمذجة جودة الرابط باستخدام معلمات مثل زمن دورة توليد التشابك، واحتمالية النجاح، والدقة.
وصول الوظائف: تصل الوظائف في فترات زمنية تتبع توزيع "بواسون" المقطوع. تتبع المحاكاة أوقات التنفيذ، والكمون، واستخدام الموارد.
ب. مقاييس الأداء
تقيم الدراسة المجدولات باستخدام ستة مقاييس رئيسية:
زمن الإنجاز (Makespan): الوقت الإجمالي لإكمال دفعة من الوظائف.
استغلال وحدة المعالجة الكمومية (QPU Utilization): نسبة موارد وحدة المعالجة الكمومية المشغولة.
معدل البوابة غير المحلية (Non-Local Gate Rate): مقياس للتداخل في أوقات تنفيذ البوابات غير المحلية (استخدام التشابك).
أداء زمن تنفيذ النظام (SELP): المتوسط الهندسي لنسبة وقت التنفيذ إلى إجمالي الكمون (الانتظار + التنفيذ).
5. العدالة (Fairness): تقيس التباين في الكمون بين الوظائف (بهدف تحقيق معاملة متساوية).
ج. استراتيجيات الجدولة المقترحة
تقترح الورقة وتختبر عدة استراتيجيات:
تحديد الأولويات للموارد (Resource-Prioritize): خوارزمية استدلالية تزيد من استغلال وحدات المعالجة الكمومية عند كل خطوة من خلال اختيار مجموعات من الوظائف التي تستخدم أكبر عدد من العقد مع أقصر وقت تنفيذ تقديري.
مجدول EPR: يعطي الأولوية للوظائف التي تتطلب عددًا أقل من أزواج EPR لتقليل اختناقات توليد التشابك.
EPR مع اختيار العقد: يجمع بين أولوية EPR وخوارزمية تخصص الوظائف لأعلى الروابط جودة متاحة، مما يحسن التعامل مع عدم تجانس الروابط.
ASAP (في أقرب وقت ممكن): مجدول ديناميكي يحرر العقد فور اكتمال الوظيفة ويخصص الوظائف المعلقة للعقد الشاغرة، بدلاً من انتظار فترة زمنية متزامنة.
PPO (تحسين السياسة القريبة): نهج يعتمد على التعلم التعزيزي (RL).
الحالة (State): مصفوفة من ميزات الوظيفة (عدد الـ QPUs المطلوبة، أزواج EPR، وقت التنفيذ).
الإجراء (Action): اختيار احتمالي للوظائف للتنفيذ بالتوازي.
المكافأة (Reward): دالة مركبة تعاقب على الكمون وتحفز جدولة الوظائف ذات الـ EPR المنخفض (واستخدام الروابط عالية الجودة في نسخة اختيار العقد).
إطار عمل متكامل: تطوير بيئة محاكاة شاملة لجدولة وظائف الحوسبة الكمومية الموزعة تدمج فيزياء الشبكة الكمومية (توليد EPR، الدقة، فك الترابط).
خوارزميات جدولة مبتكرة: تقديم مجدولي EPR (اختيار العقد) و PPO، اللذين يأخذان في الاعتبار صراحةً عدم تجانس الروابط وقيود الموارد الكمومية.
التعلم التعزيزي للجدولة الكمومية: إثبات إمكانية استخدام تحسين السياسة القريبة (PPO) لتعلم سياسات الجدولة التي توازن بين زمن الإنجاز والكمون وقيود الموارد دون الحاجة إلى قواعد استدلالية ثابتة.
تقييم شامل: مقارنة منهجية لثماني استراتيجيات جدولة مختلفة عبر أحمال شبكة متنوعة، وأنواع وظائف مختلفة (GHZ, QAOA, VQE، إلخ)، وجودة روابط متفاوتة.
4. النتائج
أجريت عمليات المحاكاة على مدار 1,000 فترة زمنية مع أحمال شبكة متغيرة (λ=4 و λ=8) وانحيازات اختيار الوظائف.
زمن الإنجاز (إجمالي وقت الاكتمال):
أفضل الأداء: حقق كل من EPR (اختيار العقد) و PPO (اختيار العقد) أقل زمن إنجاز. فمن خلال إعطاء الأولوية للوظائف التي تتطلب عددًا أقل من EPR وتخصيصها للروابط عالية الجودة، قللا من تأخيرات توليد التشابك.
المركز الثاني: حقق مجدول ASAP أداءً جيدًا نظرًا لتخصيصه الديناميكي للعقد الشاغرة، مما قلل من وقت الخمول.
الأسوأ أداءً: سجلت خوارزميات FIFO و EPR الأساسية (بدون اختيار العقد) أزمنة إنجاز أعلى بسبب عدم كفاءة تجميع الموارد وعدم الوعي بالروابط.
استغلال وحدة المعالجة الكمومية (QPU Utilization):
حقق ASAP و Resource-Prioritize أعلى مستويات الاستغلال. يعمل ASAP على تعظيم الاستخدام بملء الفجوات فورًا، بينما يستهدف Resource-Prioritize صراحةً الوصول إلى أقصى تشبع للعقد.
أظهرت متغيرات EPR استغلالًا أقل لأنها غالبًا ما توقف التوازي مبكرًا لإعطاء الأولوية للوظائف ذات الـ EPR المنخفض، مما يترك العقد في حالة خمول.
أداء زمن تنفيذ النظام (SELP) والعدالة:
حقق EPR و EPR (اختيار العقد) أعلى مستويات SELP والعدالة. فمن خلال إعطاء الأولوية للوظائف قصيرة التنفيذ وتجنب الروابط منخفضة الجودة، ضمنا تنفيذًا أكثر اتساقًا وسرعة للوظائف الفردية.
أظهرت متغيرات PPO أداءً قويًا ولكنها تراجعت قليلاً عن الاستدلالات الخاصة بـ EPR في معيار العدالة، ويرجع ذلك على الأرجية للطبيعة العشوائية لسياسة التعلم التعزيزي.
معدل البوابة غير المحلية:
أظهرت الاستراتيجيات التي تعظم التوازي (Resource-Priority, ASAP) معدلات بوابات أعلى بشكل عام (تداخل أكثر)، وهو أمر مرغوب فيه لزيادة الإنتاجية ولكنه قد يزيد من حدة التنازع على الموارد.
أظهرت استراتيجيات EPR معدلات أقل، مما يشير إلى تنازع أقل على موارد التشابك.
5. الأهمية والخاتمة
تثبت هذه الورقة أن الجدولة الواعية بالكم أمر بالغ الأهمية لجدوى الحوسبة الكمومية الموزعة.
عدم تجانس الروابط أمر جوهري: تجاهل جودة الرابط يؤدي إلى أداء دون المستوى. المجدولات التي تدمج اختيار العقد بناءً على دقة الرابط (EPR + اختيار العقد) تتفوق بشكل كبير على تلك التي لا تفعل ذلك.
توجد مقايضات: هناك مقايضة أساسية بين زمن الإنجاز (الذي يفضله ASAP و PPO مع اختيار العقد) و العدالة/الكمون (الذي تفضله استدلالات EPR). يجب على مصممي الأنظمة اختيار المجدول بناءً على ما إذا كانت أولويتهم هي الإنتاجية أم زمن كمون الوظائف الفردية.
إمكانات التعلم التعزيزي: يوضح نهج PPO أن التعلم التعزيزي يمكنه تعلم سياسات جدولة معقدة في الشبكات الكمومية، مما يوفر مرونة تفتقر إليها القواعد الاستدلالية الثابتة. ورغم أن نهج RL يتراجع حاليًا قليلاً عن أفضل الاستدلالات في مقاييس معينة، إلا أنه يوفر أساسًا للجدولة التكيفية في الشبكات الكمومية الديناميكية والواقعية.
يوفر هذا العمل مخططًا لطبقة "مدير التنفيذ" في أنظمة التشغيل الكمومية المستقبلية، مؤكدًا أن الحوسبة الكمومية الموزعة الفعالة تتطلب تحسينًا مشتركًا لتجميع الدوائر، وطوبولوجيا الشبكة، وجدولة الوظائف.