لطالما كانت خوارزمية K-Means أداة أساسية في مجال تجميع البيانات لعقود طويلة، تستخدم غالبًا كخطوة معالجة مسبقة للمعلومات قبل الانتقال إلى مهام أخرى. ومع ذلك، مع التطور السريع لخطوط أنابيب الذكاء الاصطناعي الحديثة التي تتطلب استدعاء K-Means داخل حلقات التدريب والاستدلال بشكل متكرر، أصبح زمن الاستجابة لكل استدعاء أكثر أهمية من العمليات الحسابية النظرية (FLOPs). في هذا السياق، يأتي الكشف عن مكتبة Flash-KMeans الجديدة، وهي إنجاز رائد من فريق باحثين في جامعتي كاليفورنيا ببيركلي وتكساس في أوستن.
تعد Flash-KMeans مكتبة مفتوحة المصدر تعيد تصور كيفية عمل خوارزمية K-Means على وحدات معالجة الرسوميات (GPUs). إنها ليست مجرد نسخة محسّنة؛ بل هي تطبيق واعٍ لعمليات الإدخال/الإخراج (IO-aware) لخوارزمية K-Means القياسية من Lloyd. والأهم من ذلك، أنها لا تغير الرياضيات الأساسية للخوارزمية ولا تستخدم أي تقريبات. بدلاً من ذلك، تركز Flash-KMeans على إعادة هيكلة طريقة نقل البيانات داخل وحدة معالجة الرسوميات، مما يؤدي إلى تسريع هائل في الأداء. وقد أظهرت الاختبارات على معالج NVIDIA H200 تسريعًا شاملًا يصل إلى 17.9 مرة مقارنة بأفضل الحلول المرجعية، و33 مرة مقارنة بـ NVIDIA cuML، وأكثر من 200 مرة مقارنة بمكتبة FAISS الرائدة في الصناعة.
ما هو Flash-KMeans؟
Flash-KMeans هي مكتبة K-Means مجمعة (batched) ومكتوبة باستخدام نواة Triton لوحدات معالجة الرسوميات. وهي متوفرة بموجب ترخيص Apache 2.0 ويمكن تثبيتها بسهولة عبر الأمر pip install flash-kmeans. يتميز ناتجها بأنه مطابق رياضيًا لخوارزمية K-Means القياسية من Lloyd. يأتي التسريع المذهل من تدفق البيانات على مستوى النواة (kernel-level dataflow) وليس من تخطي أي عمل حسابي. هذا يميزها عن الطرق الخوارزمية التي تعتمد على التقريب مثل تقليم عدم المساواة المثلثية أو أخذ العينات من المجموعات الأساسية.
تتكون دورة Lloyd القياسية من مرحلتين رئيسيتين: مرحلة التخصيص ومرحلة التحديث. في مرحلة التخصيص، يتم حساب المسافة بين كل نقطة وكل مركز تجميع، ثم يتم اختيار المركز الأقرب. أما في مرحلة التحديث، يتم حساب متوسط النقاط في كل مجموعة لتشكيل مراكز تجميع جديدة. كلتا المرحلتين تتضمنان عمليات حسابية بسيطة. ومع ذلك، على وحدات معالجة الرسوميات، يصبح كلاهما مقيدًا بالذاكرة (memory-bottlenecked) وليس بالقدرة الحاسوبية، وهذا هو التحدي الذي جاء Flash-KMeans لمعالجته.
الاختناقات التي يعالجها Flash-KMeans وحلولها
1. مرحلة التخصيص: تجاوز مصفوفة المسافة
الاختناق الأول الذي تعالجه Flash-KMeans هو مرحلة التخصيص. تقوم التعليمات البرمجية القياسية ببناء مصفوفة مسافة كاملة D بحجم N×K في ذاكرة النطاق الترددي العالي (HBM). تتطلب هذه العملية كتابة المصفوفة ثم قراءتها مرة أخرى لتشغيل عملية argmin (إيجاد الحد الأدنى). على سبيل المثال، بالنسبة لـ N=65536، K=1024، d=128، B=32، تستغرق حسابات المسافة 2.6 مللي ثانية، بينما تستغرق كتابة واستهلاك مصفوفة D حوالي 23 مللي ثانية. هذا يوضح أن المصفوفة نفسها هي التكلفة الحقيقية، وليست العمليات الحسابية.
تستبدل Flash-KMeans هذه العملية بـ FlashAssign. يستعير تصميم FlashAssign من مبادئ FlashAttention، حيث يقوم ببث قطع (tiles) من النقاط والمراكز من ذاكرة HBM إلى ذاكرة SRAM الموجودة على الشريحة. يدمج FlashAssign حساب المسافة مع عملية argmin عبر الإنترنت (online argmin). وبهذه الطريقة، لا يتم إنشاء مصفوفة N×K الكاملة أبدًا. هذا يقلل من تعقيد عمليات الإدخال/الإخراج المهيمن من O(NK) إلى O(Nd + Kd). على مستوى النواة، يحقق FlashAssign تسريعًا يصل إلى 21.2 مرة، وفي إحدى الحالات، خفض وقت التخصيص من 122.5 مللي ثانية إلى 5.8 مللي ثانية فقط.
2. مرحلة تحديث المراكز: القضاء على تضارب الوصول الذري
الاختناق الثاني يكمن في مرحلة تحديث المراكز. تستخدم التعليمات البرمجية القياسية عمليات الجمع الذرية (atomic adds) بنمط التشتيت (scatter-style). يضيف كل خيط (thread) نقطته إلى مخزن مؤقت مجموع مشترك مفتاح بواسطة معرف المجموعة. يتصادف أن العديد من الخيوط تصل إلى نفس المجموعة "الساخنة" في وقت واحد، مما يسبب تضاربًا ذريًا (atomic contention) وتسلسلًا للأجهزة. وقد قاس فريق البحث عرض نطاق ترددي فعالًا يبلغ 50 جيجابايت/ثانية فقط على معالج H200 في هذه المرحلة.
تستبدل Flash-KMeans هذه الطريقة بـ Sort-Inverse Update. يقوم هذا الأسلوب بفرز متجه التخصيص أحادي البعد بواسطة معرف المجموعة باستخدام argsort. ثم تشكل معرفات المجموعات المتطابقة أجزاء متجاورة. يقوم كل بلوك من الخيوط (thread block) بتخفيض جزء على الشريحة، ثم يصدر عملية جمع ذرية واحدة لكل جزء. بهذه الطريقة، لا يتم إعادة ترتيب مصفوفة النقاط الثقيلة فعليًا. تنخفض العمليات الذرية بشكل كبير، ويصل تسريع النواة إلى 6.3 مرة بفضل هذه الاستراتيجية.
مقاييس الأداء والتطبيقات العملية
أجرى فريق البحث اختبارات مكثفة على معالج NVIDIA H200 باستخدام CUDA 12.8 وبيانات FP16 وبُعد d=128، مع تغيير N وK وحجم الدفعة B. كانت النتائج مذهلة، حيث تجاوزت Flash-KMeans أربعة حلول مرجعية محسنة: fast_pytorch_kmeans، fastkmeans، cuML، وFAISS. وبالإضافة إلى ذلك، تبرز Flash-KMeans في سيناريوهات K الكبيرة حيث تفشل تطبيقات PyTorch القياسية في التعامل مع مصفوفة N×K، وتتجاوز FAISS في الأداء حتى على نطاق مليارات النقاط، حيث تنهي تكرارًا في 41.4 ثانية مقارنة بـ 261.8 ثانية للحل المرجعي.
إن القدرة على إجراء K-Means بدقة وبسرعة فائقة لا تغير فقط كيفية معالجة البيانات دون اتصال، بل تفتح أبوابًا لتطبيقات جديدة ومبتكرة في الوقت الفعلي:
- فهرسة البحث المتجهي (Vector search indexing): تستخدم FAISS خوارزمية K-Means لبناء فهارس البحث الخاصة بها. تتيح Flash-KMeans إعادة فهرسة البيانات فور تغيرها، بدلاً من إعادة البناء طوال الليل.
- توجيه الانتباه المتناثر (Sparse attention routing): تستخدم محولات التوجيه (Routing Transformers) وTactic رموز التجميع لتوجيه الانتباه. تسمح K-Means بالمللي ثانية بجعل هذا ممكنًا داخل حلقة الاستدلال.
- ضغط ذاكرة التخزين المؤقت للزوج المفتاح-القيمة (KV-cache compression): تقوم ClusterKV بتجميع الرموز في مساحة دلالية لضغط ذاكرة التخزين المؤقت. يجعل التجميع الأقل تكلفة الضغط لكل طبقة ولكل خطوة عمليًا.
- تكميم KV منخفض البت (Low-bit KV quantization): تقوم الطرق الحديثة بتجميع إدخالات KV في دفاتر رموز بشكل متكرر. يقلل التجميع الأسرع من تكلفة المعالجة المسبقة هذه.
- محولات الانتشار (Diffusion Transformers): تستدعي Sparse VideoGen2 خوارزمية K-Means المجمعة أثناء التمريرات الأمامية. تقوم بترتيب الرموز حسب التشابه الدلالي لاستغلال التشتت (sparsity).
ماذا يعني هذا لك؟
بالنسبة للمطورين والباحثين في مجال الذكاء الاصطناعي، يمثل Flash-KMeans قفزة نوعية. لم تعد K-Means أداة تجميع بيانات تستهلك وقتًا طويلاً ومخصصة للعمليات غير المتصلة بالإنترنت فحسب. الآن، يمكن دمجها بكفاءة في خطوط أنابيب التعلم الآلي والذكاء الاصطناعي التي تعمل في الوقت الفعلي. هذا يعني أوقات تدريب أسرع للنماذج، وقدرة على تحديث أنظمة البحث والتوصية بشكل فوري، وتحسينًا جذريًا في كفاءة الموارد الحاسوبية لوحدات معالجة الرسوميات. يسمح Flash-KMeans للشركات والباحثين بتحقيق أقصى استفادة من بياناتهم، مما يمكنهم من بناء أنظمة ذكاء اصطناعي أكثر استجابة، وديناميكية، وفعالية من حيث التكلفة، خاصة في التطبيقات التي تتطلب معالجة سريعة لكميات هائلة من البيانات.
الخاتمة
يُعد Flash-KMeans إنجازًا تقنيًا مهمًا يعيد تعريف حدود أداء خوارزمية K-Means. من خلال معالجة الاختناقات المتعلقة بالإدخال/الإخراج بذكاء، دون المساس بالدقة الرياضية، يقدم Flash-KMeans تسريعًا غير مسبوق يجعله أداة لا غنى عنها في عصر الذكاء الاصطناعي الحديث. إن قدرته على تحقيق هذه السرعات الهائلة على وحدات معالجة الرسوميات، مع الحفاظ على دقة النتائج، يفتح آفاقًا واسعة للابتكار عبر مجموعة واسعة من تطبيقات الذكاء الاصطناعي، من البحث المتجهي إلى النماذج التحويلية المعقدة، ويدفعنا خطوة أخرى نحو أنظمة ذكاء اصطناعي أكثر كفاءة واستجابة.
