Omnisolver: An extensible interface to Ising spin-glass and QUBO solvers: adding a distributed GPU brute-force plugin

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

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

جوهر هذا العمل هو إضافة برمجية تسمى Omnisolver-bruteforce، والتي تعمل كمترجم عالمي لأنواع مختلفة من الحلول الحاسوبية. فكر فيها كمفتاح رئيسي يسمح للباحثين بتوصيل أدوات متنوعة لمعالجة نفس المشكلة. قام الباحثون بأخذ أداة موجودة يمكنها فحص كل الاحتمالات على بطاقة رسوميات واحدة وترقيتها لتعمل عبر شبكة من ثماني بطاقات قوية في آن واحد. لقد حققوا ذلك من خلال تقسيم مساحة البحث الهائلة إلى قطع أصغر ومستقلة. تخيل مكتبة حيث تحتاج إلى العثور على كتاب معين؛ بدلاً من شخص واحد يفحص كل رف، يتم تقسيم المهمة بحيث يفحص ثمانية أشخاص أقسامًا مختلفة في نفس الوقت، ويبلغون فقط عند العثور على الهدف. في هذه الحالة، "المكتبة" هي مجموعة كافة الترتيبات الممكنة للمشكلة، و"الباحثون" هم بطاقات الرسوميات التي تعمل بالتوازي.

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

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

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

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