تسريع مسائل الإشباع المنطقي الهجينة XOR–CNF أصلاً بالحوسبة داخل الذاكرة

لماذا يهم حل المشكلات بسرعة أكبر

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

تحويل القواعد المعقدة إلى بلوكات أبسط

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

إنجاز المزيد بعدد قطع أقل

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

السماح لشرائح الذاكرة بأداء المعالجة

لاستغلال هذا الوصف الأشد اختصارًا، يصمم الفريق مسارعًا مخصصًا لـ«الحوسبة داخل الذاكرة». بدلًا من نقل البيانات ذهابًا وإيابًا بين المعالج والذاكرة، يقوم هذا الجهاز بأداء جزء كبير من الحساب حيث توجد البيانات، داخل شبكات من عناصر إلكترونية دقيقة تُسمى ممرستورات (memristors). يقومون بتكييف استراتيجية بحث محلية معروفة، WalkSAT، إلى متغير جديد اسمه WalkSAT-XNF الذي يتعامل أصلاً مع قواعد XOR–OR المدمجة. تُنفَّذ كل خطوة من الخوارزمية—فحص أي القواعد مكسورة، تقدير أهمية كل متغير، إضافة بعض الضوضاء للخروج من الطرق المسدودة، وقلب أفضل مرشح—مباشرة في دوائر تماثلية على مصفوفات الشبكة المتقاطعة، مع دوائر مساندة بسيطة تختار أي متغير يُقلب بعد ذلك.

إثبات الفاعلية في المختبر والمحاكيات

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

ماذا يعني هذا لأجهزة الحاسوب المستقبلية

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

الاستشهاد: Im, H., Böhm, F., Pedretti, G. et al. Accelerating hybrid XOR–CNF Boolean satisfiability problems natively with in-memory computing. Nat Commun 17, 2922 (2026). https://doi.org/10.1038/s41467-026-69465-2

الكلمات المفتاحية: الإشباع المنطقي, الحوسبة داخل الذاكرة, شبكة ممرستورات, مسارعات الأجهزة, التشفير