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

في العالم الرقمي، تُبنى الأنظمة المعقدة على قواعد. وسواء كان ذلك تكويناً لبرمجية يجب أن تعمل مع أجهزة محددة، أو جدول بيانات يحسب ميزانية، أو أداة لتكوين المنتجات تساعد العميل على بناء سيارة مخصصة، فإن هذه الأنظمة تعتمد على مجموعة من القيود. والقيد هو ببساطة قاعدة تحدد ما هو مسموح به وما هو غير مسموح به. وعندما يحاول المستخدم إعداد نظام يكسر هذه القواعد، يجب على الكمبيوتر تحديد أي القواعد تتصارع مع بعضها البعض بالضبط. وهذا ما يسمى بإيجاد "تعارض" (conflict). تخيل لغزاً يحتوي على مائة قطعة، لكن قلة قليلة منها فقط هي التي تمثل المشكلة. مهمة الكمبيوتر هي عزل تلك القطع المحددة حتى يتمكن المستخدم من إصلاحها. هذه العملية هي أساس التشخيص القائم على النماذج (model-based diagnosis)، وهو مجال يساعد المهندسين ومطوري البرمجيات على إصلاح الأنظمة المعطلة تلقائياً.

لعقود من الزمن، طور الباحثون خوارزميات لإيجاد هذه التعارضات بكفاءة. إحدى الطرق الشهيرة، والمعروفة باسم QuickXplain، تعمل مثل المحقق الذي يضيق قائمة المشتبه بهم. فهي تقسم مجموعة كبيرة من القواعد إلى نصفين، وتتحقق مما إذا كان النصف الأول هو المشكلة، وإذا لم يكن كذلك، تتحقق من النصف الثاني. وتكرر هذه العملية، وتقسم القائمة إلى النصف مراراً وتكراراً، حتى تجد أصغر مجموعة من القواعد التي تسبب الخطأ. هذه الطريقة سريعة، لكنها تجد تعارضاً واحداً فقط في كل مرة. وفي كثير من المواقف الواقعية، قد يحتوي النظام على عدة مشكلات مختلفة تحدث في وقت واحد. ولإصلاح النظام بالكامل، يحتاج الكمبيوتر إلى إيجاد كل هذه التعارضات، وليس واحداً فقط. وقد صُممت طريقة لاحقة تسمى MergeXplain للقيام بذلك تحديداً: فهي تجد تعارضات متعددة في عملية تشغيل واحدة. ومع ذلك، مع زيادة سرعة أجهزة الكمبيوتر واكتسابها المزيد من نوى المعالجات، بدأت الطرق القديمة لتشغيل هذه الخوارزميات تصطدم بحائط مسدود. فقد صُممت لتعمل في مسار حركة مرور واحد، بينما تمتلك أجهزة الكمبيوتر الحديثة مسارات عديدة متاحة.

قام فريق من الباحثين من الإكوادور وتشيلي الآن ببناء نسخة جديدة من أداة البحث عن التعارضات المتعددة هذه، والتي أطلقوا عليها اسم ParallelMergeXplain. كان هدفهم هو أخذ الطريقة الحالية وجعلها تعمل على نوى معالجة متعددة في وقت واحد، دون تغيير الإجابات التي تقدمها. أرادوا معرفة ما إذا كان بإمكانهم تسريع عملية العثور على تعارضات متعددة باستخدام القوة الكاملة لشرائح الكمبيوتر الحديثة. واجه الباحثون تحدياً محدداً: فالخوارزمية تتكون من جزأين متميزين. الجزء الأول هو هيكل يشبه الشجرة حيث يقوم الكمبيوتر بتقسيم المشكلة إلى فرعين. والجزء الثاني هو حلقة (loop) حيث يتحقق الكمبيوتر من نتائج تلك الفروع لتنظيف أي أخطاء متبقية. كانت المحاولات السابقة لتسريع هذا الجزء تركز فقط على الجزء الأول، عبر تشغيل الفرعين في نفس الوقت. وأدرك الباحثون أن الجزء الثاني، وهو حلقة التنظيف، كان لا يزال يعمل ببطء، خطوة بخوة، رغم أنه يمكن أيضاً تسريعه.

ولحل هذه المشكلة، ابتكر الفريق خوارزمية تهاجم كلا الجزأين من المشكلة في آن واحد. فقد سمحوا للفرعين الرئيسيين للبحث بالعمل على نوى معالجة مختلفة، تماماً كما في السابق. لكنهم أضافوا أيضاً طبقة جديدة من السرعة إلى حلقة التنظيف. لقد استخدموا تقنية تسمى "التوازي التخميني" (speculative parallelization). وهي طريقة يخمن فيها الكمبيوتر ما سيحتاجه لاحقاً ويبدأ في العمل على تلك المهام قبل أن يتأكد تماماً من حاجته إليها. الأمر يشبه طباخاً يبدأ في تحضير مكونات الطبق التالي بينما يقوم بتقطيع الخضروات للطبق الحالي، لأنه يعلم أن الطبق التالي قادم. إذا كان التخمين صحيحاً، يتم توفير الوقت. وإذا كان التخمين خاطئاً، يتم ببساطة التخلص من العمل والمضي قدماً. في هذا النظام الجديد، يستخدم الكمبيوتر نوى المعالجة الخاملة لحساب نتائج عمليات التحقق المستقبلية مسبقاً بينما لا تزال الخوارزمية الرئيسية تعمل.

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

أظهرت النتائج أن الطريقة الجديدة تعمل بدقة تماثل الطريقة القديمة تماماً من حيث الدقة. ففي كل اختبار، وجدت الخوارزمية الجديدة نفس مجموعة التعارضات التي وجدتها الأصلية، مما أثبت أن تقنيات التسريع لم تؤدِ إلى أي أخطاء. وعندما تعلق الأمر بالسرعة، كانت الطريقة الجديدة أسرع، لكن مقدار السرعة المكتسبة اعتمد على تعقيد المشكلة. ففي الاختبار الواقعي، كان النظام الجديد أسرع بنحو 1.5 مرة من النظام القديم. أما في الاختبارات الاصطناعية، فكانت زيادة السرعة أكثر تواضعاً، بمتوسط 1.2 مرة أسرع. ووجد الباحثون أن أكبر المكاسب جاءت عند الجمع بين الاستراتيجيتين: تشغيل الفروع بالتوازي واستخدام التخمين الاستباقي في حلقة التنظيف. ومع ذلك، اكتشفوا أيضاً حداً معيلاً؛ فإذا حاولوا فرض مهام كثيرة جداً على نواتي المعالجة المتاوتين، يقضي الكمبيوتر وقتاً في إدارة المهام أكثر مما يقضيه في حل المشكلة فعلياً، فتختفي ميزة السرعة. وقد أكد هذا أن مجرد إضافة المزيد من العمال لا يجعل المهمة أسرع دائماً؛ إذ يجب مطابقة العمال مع حجم المهمة.

يُظهر هذا العمل أنه من الممكن أخذ خوارزمية متسلسلة معقدة وتكييفها لتعمل على أجهزة الكمبيوتر متعددة النوى الحديثة دون فقدان موثوقيتها. لقد أثبت الباحثون أنه من خلال الجمع بعناية بين أنواع مختلفة من التوازي، يمكنهم جعل عملية العثور على تعارضات النظام المتعددة أسرع بشكل ملحوظ. وتشير نتائجهم إلى أنه بالنسبة للأنظمة التي تحتوي على قيود عديدة، فإن استخدام التوازي على مستوى الفروع والتطلع الاستباقي (speculative lookahead) هو النهج الأكثر فعالية. كما سلطت الدراسة الضوء على أن فوائد هذه التقنيات تختلف اعتماداً على الطبيعة المحددة للمشكلة التي يتم حلها. ورغم أن زيادة السرعة لم تكن هائلة على جهاز صغير بنواتين، إلا أن المبادئ التي أرساها الباحثون توفر مساراً واضحاً لتسريع أنظمة التشخيص هذه على أجهزة أقوى وأكبر في المستقبل. الكود والبيانات الخاصة بدراستهم متاحة للجمهور، مما يسمح للباحثين الآخرين بالبناء على هذا الأساس واختبار هذه الأساليب على أنظمة واقعية أكبر وأكثر تعقيداً.