فرز سريع في glsl؟

Question

أنا أفكر في تنقل قطعة كبيرة من المعالجة إلى GPU باستخدام شادر GLSL. واحدة من المشكلات المباشرة التي تعثرت عبرها هي أنه في إحدى الخطوات، تحتاج الخوارزمية إلى الحفاظ على قائمة العناصر، فرزها وأخذها أكبر عدد قليل منها (الرقم الذي يعتمد على البيانات). على وحدة المعالجة المركزية، يتم ذلك ببساطة باستخدام ناقلات STL و Qsort () ولكن في GLSL ليس لدي هذه المرافق. هل هناك طريقة للتعامل مع هذا النقص؟

Answer 1

الإفصاح: أنا حقا لا أعرف GLSL - لقد كنت تقوم ببرمجة GPGPU مع SDK AMD Stream، والتي تحتوي على لغة برمجة مختلفة.

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

لا أستطيع إلا أن أقول بشكل عام:

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

GPUS هي أجهزة SIMD، لذلك يحبون الحصول على كل نواة تنفيذ نفس العمليات في خطوة قفل. الحسابات رخيصة ولكن الفروع هي فروع باهظة الثمن وتعتمد على البيانات حيث كل فروع النواة طريقة مختلفة للغاية للغاية للغاية ومكلفة للغاية.

لذلك إذا كان كل Kernel يحتوي على مجموعة بيانات صغيرة خاصة بالفرز، ويعتمد رقم البيانات المراد فرز البيانات ويمكن أن يكون رقما مختلفا لكل نواة، فمن المحتمل أنك أفضل حالا في اختيار أقصى حجم (إذا كنت تستطيع)، الحشو أدت المصفوفات التي تحتوي على ما لا نهاية أو عدد كبير، ولها كل نواة نفس النوع بالضبط نفس النوع، والذي سيكون فرز فقاعة غير صحيحة بدون إطار، شيء من هذا القبيل:

Pseudocode (بما أنني لا أعرف GLSL)، نوعا من 9 نقاط

#define TwoSort(a,b) { tmp = min (a, b); b = a + b - tmp; a = tmp; }
for (size_t n = 8; n ; --n) {
  for (size_t i = 0; i < n; ++i) {
    TwoSort (A[i], A[i+1]);
  }
}

Answer 2

هل رأيت هذا المقال؟https:/developer.nvidia.com/gpugems/gpugems2/gpugems2_chapter46.html.

لم أكن متأكدا من أنك تبحث عن خوارزمية QuickSort أو خوارزمية فرز سريعة. خوارزمية في المقالة تستخدم دمج فرز ...

Answer 3

ليس لدي أي معرفة حول برمجة GPU.

كنت أستخدم HeApsort بدلا من QuickSort، لأنك قلت عليك فقط أن تنظر إلى القيم القليلة الأولى. يمكن بناء الكومة في O(n) الوقت، ولكن الحصول على القيمة العليا هي log(n). وبعد لذلك إذا كنت عدد القيم التي تحتاجها أصغر بكثير من إجمالي عدد العناصر التي يمكنك الحصول على بعض الأداء.