هل توجد خوارزمية لفرز مجموعة سلاسل من GPU؟

Question

صفيف للفرز لديه ما يقرب من مليون سلاسل، حيث يمكن أن تحتوي كل سلسلة طول ما يصل إلى مليون حرف.

أبحث عن أي تنفيذ خوارزمية فرز GPU.

لدي كتلة من البيانات بحجم 1 ميغابايت تقريبا وأحتاج إلى بناء صفيف لاحقة .الآن يمكنك أن ترى كيف يمكن الحصول على مليون سلاسل داخل كمية صغيرة حقا من الذاكرة.

Answer 1

حالة الفن في فرز GPU ليس مشجعا بشكل خاص.

لفرز الأعداد الصحيحة 32 بت من الورق التالي من عام 2009 (مع اثنين من المؤلفين الذين هم الباحثون في NVIDIA) يدعي فقط زيادة بنسبة 23٪ من أجل أفضل فرز CUDA على GTX280 مقارنة بأفضل وحدة المعالجة المركزية فرز على 4 كور يوركفيلد.

http://www.mgarland.org/files/papers/gpusort -Ibdps09.pdf

يستخدم هذا راديكس فرز على GPU، ودمج الترتيب على وحدة المعالجة المركزية. كنت بحاجة إلى فرز قائم على المقارنة من أجل إنشاء صفيف لاحقة، لذلك بدلا من GPU Radix فرز أفضل ما في الورق سيكون فرز دمج GPU، الذي حقق حوالي نصف سرعة راديكس GPU (مع 1 مليون مفاتيح) - أي حوالي 40٪ أبطأ من دمج وحدة المعالجة المركزية.

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

بشكل عام إذا كان هدفك هو بناء نظام فعال، فسوف أوصي باستخدام تنفيذ وحدة المعالجة المركزية لهذه المشكلة لأنه سيكون أسرع وأسهل في الكتابة.

ولكن، إذا كان هدفك هو تجربة GPU أو فقط، يمكنك العثور على تطبيق CUDA للدمج من الورق في CUDA SDK:

p> http://developer.download.nloadia .com / حساب / CUDA / SDK / موقع الويب / البيانات - parallel_algorithms.html