باحثون يحلون مشكلة نقل تتضمن 268 مليون نقطة في 2.5 ساعة

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

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

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

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

اختبر الباحثون هذه الطريقة على وحدة معالجة رسومية واحدة من طراز A100. شغلوها على بيانات من محاكاة كونية تتضمن 134 مليون جسيم في كل جانب. كان العدد الإجمالي للنقاط 268 مليوناً.

وصل الحل إلى مستوى دقة عالٍ في أقل من 2.5 ساعة. تم إبقاء الخطأ في المطابقة النهائية أقل من 0.01. تشير الورقة إلى أن هذه أكبر مشكلة منفصلة من هذا النوع تم حلها بهذه الدقة خلال ساعات قليلة.

تعتمد الطريقة على ميزات محددة في العتاد. فهي تستخدم تقنية تسمى التنفيذ المدمج لنوى الموترات للتعامل مع الرياضيات بسرعة. يتم ترتيب الكتل بطريقة تسمح للحاسوب بتخطي الحسابات غير الضرورية.

لهذا آثار على المجالات التي تعمل مع مجموعات بيانات كبيرة. على سبيل المثال، غالباً ما تتعامل علم الكونيات مع محاكاة لمليارات الجسيمات. قد يؤدي القدرة على معالجة هذه البيانات بشكل أسرع إلى تسريع الأبحاث حول بنية الكون.

أطلق المطورون نسخة مفتوحة المصدر من الكود. هذا يسمح للباحثين الآخرين باختبار الطريقة على بياناتهم الخاصة. توفر الورقة تفاصيل حول كيفية تعامل الخوارزمية مع التكاليف المحددة لنقل النقاط في فضاءات منخفضة الأبعاد.

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

لا يوفر المصدر معايير أداء لأنواع أخرى من دوال التكلفة أو البيانات عالية الأبعاد. النتائج محددة بالعتاد وحجم المشكلة التي تم اختبارها في الورقة.