أنظمة الفرز المتوازي الجديدة

في هذه الورقة، نصف عائلة من الخوارزميات الفرز المتوازية لنظام معالجات متعددة. هذه الخوارزميات هي خوارزميات فرز تعداد وتتضمن المراحل التالية: 1) اكتساب العداد: يتم تقسيم المفاتيح إلى مجموعات فرعية ونعين لكل مفتاح عدد المفاتيح الأصغر (العداد) في كل مجموعة فرعية؛ 2) تحديد الرتبة: رتبة المفتاح هي مجموع العدادات التي تم الحصول عليها سابقًا؛ 3) إعادة ترتيب البيانات: يتم وضع كل مفتاح في الموضع المحدد بواسطة رتبته. التجديد الأساسي للخوارزميات هو استخدام الدمج المتوازي لتنفيذ اكتساب العدادات. من خلال استخدام مخطط الدمج لڤاليانت، نظهر أن n مفتاح يمكن فرزها بالتوازي باستخدام n log2n معالجات في زمن C log 2 n + o(log 2 n)؛ بالإضافة إلى ذلك، إذا لم يُسمح بتعارض fetch في الذاكرة، باستخدام نسخة معدلة من خوارزمية دمج باتشر لتنفيذ المرحلة 1)، نظهر أن n مفتاح يمكن فرزها باستخدام n 1 +α معالجات في زمن (C'/α a) log 2 n + o(log 2 n)، مما يتطابق مع أداء خوارزمية هيرشبرغ، والتي ليست خالية من تعارضات fetch.