خوارزميات الرسم البياني على GPU

Question

مؤشرات الترابط GPU الحالية محدودة بطريقة أو بأخرى (حد الذاكرة، والحد من هياكل البيانات، ولا توجد إصداقية ...).

هل تعتقد أنه سيكون من الممكن تنفيذ مشكلة نظرية رسم بيانية على GPU. على سبيل المثال غطاء رأس القمة؟ السيطرة على مجموعة؟ مجموعة مستقلة؟ ماكس زمرة؟

هل من الممكن أيضا الحصول على خوارزميات فرع ومضمون على GPU؟ التراجع العريضة؟

Answer 1

سوف تكون مهتما

1. استكشاف حدود GPUs مع خوارزميات الرسم البياني الموازي
   

2. تسريع خوارزميات الرسم البياني الكبيرة على GPU باستخدام CUDA.

Answer 2

هذا يرتبط بشكل واضح على سؤالك، لكنني قمت بتنفيذ خوارزمية تراجع "متكررة" لتعداد "المشي الذاتي" على شعرية (NB: تم محاكاة المكدس داخل Kuda Kernel، لتجنب النفقات العامة لإنشاء المتغيرات المحلية للحصول على مجموعة كاملة من مكالمات الوظيفة). من الممكن القيام بذلك بكفاءة، لذلك أنا متأكد من أن هذا يمكن تكييفه مع سياق رسمي رسمي. إليك رابطا لندقة دراسية حول الموضوع حيث أعطيت بعض النقاش العام حول التراجع ضمن نموذج التعليمات الواحدة متعددة (SIMD)؛ انها pdf من حوالي 1MB في الحجم http://bit.ly/9forgs. .

لا أدعي أنه يعرف عن الأدبيات الأوسع نطاقا على الخوارزميات النظرية الرسمية على GPUS، ولكن الأمل ما سبق يساعد قليلا.

(themachinecharmer، شكرا على الروابط.)