البحث عن التشابه بين مليارات المتّجهات باستخدام GPU

الفكرة الأساسية في التعلُّم العميق هي تحويل الصور والجمل ومقاطع الفيديو إلى متّجهات — أي قوائم من الأرقام تلتقط جوهر المحتوى. كلما تشابهت صورتان، اقترب متّجهاهما في هذا الفضاء عالي الأبعاد. وعندما نريد إيجاد أقرب $k$ جار لمتّجه استعلام $x$ ضمن قاعدة بيانات من المتّجهات $[y_i]$، فإنّنا نحلّ المسألة التالية:

$L = k\text{-}\arg\min_{i} \|x - y_i\|^2$

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

لنحسبها: متّجه من 128 بُعداً يشغل 512 بايت عند تخزينه كأرقام عشرية بدقة 32 بت. مليار متّجه من هذا النوع يحتاج 512 غيغابايت — وهذا أكبر بكثير من ذاكرة أي GPU متوفرة. هنا يأتي دور التكميم الجداءي: نقسّم كل متّجه إلى $b$ شريحة، ثم نستبدل كل شريحة بفهرس أقرب مركز عنقودي إليها من دفتر رموز صغير تعلّمناه مسبقاً، يضمّ 256 مُدخلاً فقط. بهذه الطريقة، يتقلّص كل متّجه إلى $b$ بايت فقط (عادةً 8 إلى 64 بايت) — أي ضغط بعامل يتراوح بين 8 و64 مرة.

الفكرة قريبة من ضغط الألوان في صور GIF: بدلاً من تخزين قيم RGB الدقيقة لكل بكسل، نبني لوحة من 256 لوناً ونخزّن فهرس اللون فقط. التكميم الجداءي يفعل الأمر نفسه، لكنه يطبّقه بشكل مستقل على كل شريحة من شرائح المتّجه.

حتى بعد ضغط المتّجهات، يبقى فحصها جميعاً عملاً مُهدِراً. هنا يتدخّل الفهرس المقلوب بإضافة مرحلة توجيه ذكية: نبدأ بتجميع قاعدة البيانات كلها في $|C_1|$ عنقود باستخدام خوارزمية التعنقد k-means. عند وصول استعلام، نحدّد أقرب $\tau$ عنقود إليه (وهو ما يُسمّى مُعامل الفحص المتعدد)، ثم نفحص المتّجهات الموجودة في تلك العناقيد فقط. إذا اخترنا $|C_1| = \sqrt{n}$ وأبقينا $\tau$ صغيراً، فسنتخطّى الغالبية العظمى من القاعدة.

تصوَّر نظام بريد يغطي مدينة كاملة. بدلاً من تفقّد كل صندوق بريد في كل حيّ، تحدّد أولاً أيّ $\tau$ منطقة بريدية هي الأقرب لوجهة رسالتك، ثم تبحث فقط في صناديق تلك المناطق. كلما زاد عدد المناطق التي تفحصها ($\tau$) تحسّنت نسبة الاسترجاع، لكنك تدفع ثمن ذلك بمزيد من وقت البحث.

قوة GPU تكمن في آلاف الخيوط التي تعمل بالتوازي، لكن مسألة انتقاء أصغر $k$ مسافة هي بطبيعتها عملية تسلسلية. الأكوام التقليدية لا تعمل جيداً على GPU لأنّ كل عملية إدراج فيها تتّبع مساراً مختلفاً حسب البيانات، فيرتفع ما يُعرف بانحراف الحزمة (warp divergence) ويتباطأ الأداء.

WarpSelect يتعامل مع هذه المشكلة بأسلوب مختلف تماماً: يحتفظ بكامل الحالة الوسيطة داخل ملف السجلّات في GPU — وهي أسرع طبقة ذاكرة على الإطلاق، بعرض نطاق يفوق الذاكرة المشتركة بـ10 إلى 100 مرة. كل حزمة (32 خيطاً) تحافظ على طابور مُرتَّب لأصغر $k$ قيمة رأتها حتى الآن، ولكل خيط طابور صغير يعمل كمصفاة مبدئية: أي قيمة أكبر من رأس طابور الخيط تُرفض فوراً دون معالجة. فقط حين تمتلئ طوابير الخيوط تُدمج النتائج في طابور الحزمة عبر شبكة ترتيب ثنائية النغم (bitonic sort).

المحصّلة: خوارزمية بتمريرة واحدة تصل إلى 55% من الحدّ الأقصى النظري لعرض نطاق ذاكرة GPU — يعني أنّها تقترب من سرعة مجرد قراءة البيانات دون فعل أي شيء بها.

من أجمل خصائص التكميم الجداءي أنّك لست بحاجة لفكّ ضغط المتّجهات لحساب المسافات بينها. الآلية كالتالي: لاستعلام $x$ ومركز عنقودي خشن معلوم $q_1(y)$، نحسب مسبقاً جدول بحث $T_j$ بحجم 256 مُدخلاً لكل مُكمِّم فرعي من المُكمِّمات الـ$b$. كل مُدخل فيه يخزّن مربّع المسافة بين شريحة الاستعلام المقابلة وأحد المراكز العنقودية. بعد ذلك، لحساب المسافة التقريبية لأي متّجه مضغوط، لا نحتاج سوى $b$ قراءة من الجدول وعمليات جمع — بلا عمليات ضرب وبلا فكّ ضغط.

هذا يحوّل المسألة من $n \times d$ عملية فاصلة عائمة (وهي مكلفة) إلى $n \times b$ قراءة بايت (رخيصة وتستفيد من الذاكرة المؤقتة بكفاءة). على GPU، هذه الجداول تتسع تماماً في الذاكرة المشتركة — وهي ذاكرة سريعة مدمجة في الشريحة يتشاركها كل خيوط الكتلة الواحدة.

عند معالجة دفعة من الاستعلامات، يمرّ البحث الكامل بثلاث مراحل:

• التكميم الخشن: لكل استعلام، نحدّد أقرب $\tau$ مركز عنقودي عبر بحث شامل دقيق (ضرب مصفوفات باستخدام cuBLAS).

• فحص القوائم: لكل استعلام، نفحص فقط القوائم المقلوبة الـ$\tau$ التي اخترناها. لكل متّجه مضغوط في القائمة، نحسب مسافته التقريبية من جداول البحث المخزّنة في الذاكرة المشتركة، ثم نمرّر النتيجة إلى WarpSelect الذي يعمل في السجلّات.

• إنهاء الاختيار: ندمج النتائج الجزئية من جميع القوائم والمقاطع للوصول إلى أفضل $k$ نتيجة نهائية لكل استعلام.

تقسيم الاستعلامات إلى شرائح ($t_q$ في كل مرة) مع تشغيل عدة تيارات (streams) بالتوازي يُبقي استغلال GPU مرتفعاً مع ضبط استهلاك الذاكرة. الأهم من ذلك أنّ خط الأنابيب بأكمله يتجنّب الرحلات غير الضرورية إلى الذاكرة العامة — وهذه هي النقطة الجوهرية التي تجعل FAISS بهذه السرعة.

حين يكون الفهرس أكبر من أن تستوعبه ذاكرة GPU واحدة، يوفّر FAISS استراتيجيتين متكاملتين:

• النَّسخ: ننسخ الفهرس كاملاً على $R$ وحدة GPU. كل وحدة تتولّى $n_q/R$ استعلاماً مقابل قاعدة البيانات الكاملة، فنحصل على تسارع شبه خطّي مع دفعات الاستعلامات الكبيرة.

• التجزئة: نقسّم قاعدة البيانات على $S$ وحدة GPU، كل منها تحتفظ بـ$\ell/S$ متّجهاً. كل استعلام يُرسل إلى جميع الأجزاء، ثم تُدمج النتائج الجزئية بجولة إضافية من اختيار أصغر k عنصر. هذا يتيح فهرسة مجموعات بيانات أكبر من ذاكرة أي وحدة منفردة.

الاستراتيجيتان قابلتان للتركيب: $S$ جزء مع $R$ نسخة لكل منها تستخدم $S \times R$ وحدة إجمالاً. عملياً، 4 وحدات GPU تكفي لمعالجة مليار متّجه بأبعاد 128 بسهولة.

يمكن القول إنّ FAISS بالنسبة للبحث المتّجهي كـcuBLAS بالنسبة لضرب المصفوفات: اللبنة المُحسَّنة التي يُبنى فوقها كل نظام أعلى مستوى. الاسترجاع الكثيف للنصوص ما كان ليظهر بدونه، ولا أنظمة الاسترجاع التي تشغّل مساعدات النماذج اللغوية اليوم.