قرص ممتلئ مستعار يجعل الحواسيب أسرع
بعض المسائل رخيصة من حيث الوقت لكنها شرهة للذاكرة، وبعضها على العكس. وبالنسبة إلى بضع مهام أساسية، أثبت المنظّرون حدودًا صارمة لهذه المقايضة: مع ذاكرة عمل صغيرة، لا يمكنك أن تكون سريعًا. وتُظهر ورقة بحثية جديدة أن موردًا غريبًا، هو ذاكرة ممتلئة أصلًا ويجب إعادتها سليمة، يكسر هذه الحدود.
القرص الصلب المستعار
يُسمّى هذا النموذج الحوسبة الحفّازة، وقدّمه عام 2014 كلٌّ من Buhrman وCleve وKoucký وLoff وSpeelman. تحصل الخوارزمية على ذاكرة نظيفة صغيرة جدًا، بحجم يقارب log n بتّ لمُدخل حجمه n، إضافةً إلى ذاكرة متّسخة ضخمة ممتلئة أصلًا ببيانات عشوائية لم تخترها. ويحقّ لها استخدام الاثنتين كما تشاء، لكن عندما تتوقف، يجب أن يكون كل بتّ في الذاكرة المتّسخة كما كان تمامًا.
يستخدم المؤلفون الصورة المعتادة: تستعير القرص الصلب الضخم لصديق، المليء بذكريات رقمية ثمينة، لتجري حسابًا. ولأنك لا تريد أن تخسر صديقًا، تعيد كل بتّ إلى حاله عند الانتهاء.
كان الهدف الأول من النموذج إثبات أن ذاكرة كهذه عديمة الفائدة. فبالحدس، لكي تستعيد كل شيء يجب أن تحتفظ بكل المعلومات، فلا تحرّر أي مساحة أبدًا. والمفاجأة أن العكس هو ما تبيّن: فالذاكرة الممتلئة تتيح حلّ مسائل لا يعرف أحد كيف يحلّها بالذاكرة النظيفة وحدها. لكن تلك النتائج كانت تخصّ المساحة، وكانت الخوارزميات بطيئة للغاية.
أسرع مما هو ممكن بحسب البرهان
يتناول Adelmo Morrison Orozco وNathan Sheffield وRyan Williams (معهد ماساتشوستس للتكنولوجيا) الآن مسألة السرعة. فبذاكرة نظيفة لوغاريتمية وكمية حدودية من الذاكرة المستعارة، يقدّمون خوارزميات:
- تفرز قائمة وتحسب تحويل فورييه المتقطع في زمن n^(1+o(1))، أي شبه خطي؛
- تضرب المصفوفات في زمن n^(ω+o(1))، بسرعة أفضل طريقة معروفة مع ذاكرة غير محدودة.
ومن دون القرص المستعار، ثبت أن حاصل ضرب الزمن في الذاكرة يجب ألا يقل عن رتبة n² للفرز وتحويل فورييه، وn³ لضرب المصفوفات. وبذلك تبلغ هذه الخوارزميات الحفّازة سرعات لا تستطيع أي خوارزمية عادية ذات ذاكرة صغيرة بلوغها. ويصف المؤلفون ذلك بأنه أول إثبات غير مشروط على أن الخوارزميات الحفّازة تتفوق على نظيراتها غير الحفّازة.
بدِّل، اقرأ، تراجَع
المكوّن الأساسي حيلة توافقية قصيرة. لنفترض أن خوارزمية تستطيع أن تبدّل جزءًا من الذاكرة المستعارة بين قيمة مجهولة τ والقيمة τ + x، حيث x هي النتيجة التي تهمّها. في جدول «مساعد» كبير، مستعار هو الآخر، أضِف 1 إلى مجموعة مختارة بعناية من الخانات. عندئذ تزداد الخانة في الموضع τ بمقدار واحد إذا وفقط إذا كانت x تنتمي إلى مجموعة معيّنة. ثم نفّذ كل خطوة بالعكس، فيعود القرص كما كان، باستثناء بتّ الإجابة الذي أردته.
وبتكديس هذه الحيلة طبقةً فوق طبقة، تُقيَّم الدوائر الضحلة بسرعة. ثم يعيد المؤلفون صياغة شبكات الفرز وتحويلات فورييه السريعة وضرب المصفوفات السريع على هيئة دوائر من هذا النوع. وفي الحساب، لا تكلّف إضافيًا إلا الطبقات التي تضرب مجهولين أحدهما في الآخر؛ أما الطبقات الخطية البحتة فتكاد تكون مجانية.
مقارنة عادلة
ثمة اعتراض: فالحدود الكلاسيكية تفترض أن الإجابة تُكتب مرة واحدة، من اليسار إلى اليمين، على شريط إخراج منفصل، بينما تكتب الخوارزميات الحفّازة إجابتها في القرص المستعار. وتتصدى الورقة لذلك. إذ يبيّن المؤلفون أن خوارزمياتهم تستطيع كتابة الإجابة في مرورين على شريط إخراج، وأن المرورين لا يفيدان الخوارزميات العادية أكثر من مرور واحد. وبالتالي تظل الحدود سارية، ويظل الفصل قائمًا. كما يثبتون أن مرورًا واحدًا لا يكفي حتى مع القرص المستعار: إذ يصطدم الفرز حينها بالحاجز n² نفسه.
قائمة طويلة من المستفيدين
تقدّم الأدوات نفسها خوارزميات حفّازة سريعة لضرب الأعداد الصحيحة الكبيرة وكثيرات الحدود، وعدّ المثلثات وإيجاد الزُّمَر (cliques) في الشبكات، واكتشاف المسارات والدورات، ومطابقة أنماط النصوص مع رموز البدل. وتضاهي أزمنة تشغيلها، باستثناء عوامل صغيرة، أفضل الخوارزميات المعروفة التي تملك كل الذاكرة التي تريدها. وفي كل حالة، يجب أن تعود الذاكرة المستعارة تمامًا كما أُعيرت.