DOI: https://doi.org/10.1371/journal.pone.0342167
PMID: https://pubmed.ncbi.nlm.nih.gov/41632810
تاريخ النشر: 2026-02-03
المؤلف: Mohammed Alaa Ala’anzy وآخرون
الموضوع الرئيسي: الحوسبة المتوازية وتقنيات التحسين
نظرة عامة
يتناول هذا القسم من ورقة البحث الأداء المقارن لمختلف خوارزميات الفرز عند تنفيذها على وحدات معالجة الرسوميات باستخدام تقنية CUDA. يميز بين طرق الفرز المتسلسلة والمتوازية، مع تسليط الضوء على مزايا المعالجة المتوازية من حيث السرعة، خاصةً بالنسبة لمجموعات البيانات الكبيرة. تقيم الدراسة النسخ المعجلة بواسطة GPU من خوارزمية الفرز بالدمج (MS)، الفرز السريع (QS)، الفرز الفقاعي (BS)، فرز الاختيار العلوي (RS)، والفرز البطيء (SS) عبر أربعة سيناريوهات لمجموعات البيانات: عشوائي، مرتب عكسي، مرتب مسبقًا، ومرتبة تقريبًا. تظهر النتائج تسريعًا كبيرًا، حيث تحقق فرز القاعدة تسريعًا ملحوظًا يبلغ حوالي 50×، بينما يظهر الفرز السريع وفرز الدمج تسريعًا قدره 97× و103×، على التوالي. في المقابل، يظل الفرز الفقاعي، على الرغم من تحسينه، غير فعال بشكل عام.
تؤكد الخاتمة على أن الفرز المتوازي المعتمد على GPU يحقق تخفيضات كبيرة في وقت التنفيذ مقارنةً بالفرز المتسلسل على وحدة المعالجة المركزية، خاصةً بالنسبة لـ RS وSS، التي تتماشى جيدًا مع هياكل GPU. تشير تحليل الأداء إلى أن هيكل مجموعة البيانات يؤثر بشكل كبير على كفاءة الفرز، حيث أن MS تؤدي بشكل أفضل على البيانات المرتبة تقريبًا. كما تلاحظ الدراسة وجود تبادل بين وقت التنفيذ واستهلاك الذاكرة، حيث يظهر RS أعلى استخدام للذاكرة وSS أقلها. تشمل اتجاهات البحث المستقبلية توسيع نطاق خوارزميات الفرز التي تم تقييمها، وتنفيذ النسخ المتسلسلة في لغات منخفضة المستوى للحصول على تقييم أفضل، واستكشاف نماذج هجينة من وحدة المعالجة المركزية ووحدة معالجة الرسوميات لتحسين كفاءة الفرز على مجموعات البيانات الكبيرة.
مقدمة
تسلط مقدمة هذه الورقة البحثية الضوء على الطلب المتزايد على خوارزميات الفرز الفعالة في المجالات التي تتطلب بيانات كثيفة مثل الذكاء الاصطناعي والحوسبة العلمية، حيث يمكن أن يشكل الفرز ما يصل إلى 25% من وقت المعالجة. تكافح طرق الفرز المتسلسلة التقليدية مع مجموعات البيانات الكبيرة، مما يدفع لاستكشاف تقنيات الفرز المتوازية، وخاصة تلك التي تستفيد من هياكل متعددة لوحدات معالجة الرسوميات. تشمل التقدمات الملحوظة عمل إيلتش وآخرون، الذي حقق تحسينًا في الإنتاجية بنسبة 14× باستخدام NVLink وPCIe 4.0، وRMG Sort لتولوسكي وآخرون، الذي يستخدم استراتيجية تقسيم القاعدة لتحسين قابلية التوسع. تؤكد الورقة على أهمية تقييم خوارزميات الفرز عبر توزيعات بيانات متنوعة، حيث تشير الدراسات الحديثة إلى أن الفرز بواسطة وحدة المعالجة المركزية يمكن أن يتفوق على الفرز بواسطة وحدة معالجة الرسوميات في ظل ظروف معينة، خاصةً مع مجموعات البيانات المرتبة جزئيًا.
لمعالجة الفجوات الموجودة في الأدبيات، قام المؤلفون بتنفيذ وتقييم أربعة خوارزميات فرز—فرز الدمج (MS)، الفرز السريع (QS)، الفرز الفقاعي (BS)، فرز القاعدة (RS)، وفرز مقطع (SS)—داخل إطار عمل موحد باستخدام CUDA C++. قاموا بتقييم هذه الخوارزميات بشكل منهجي على جهاز NVIDIA GTX 1660 SUPER باستخدام مجموعة بيانات من عشرة ملايين عدد صحيح عبر أربعة توزيعات إدخال: عشوائي، مرتب، مرتب عكسي، ومرتبة تقريبًا. تهدف الدراسة إلى قياس تحسينات الأداء، مع تسريعات تتراوح من 7× إلى 38× مقارنةً بتنفيذات وحدة المعالجة المركزية، مع تقديم رؤى حول متانة الخوارزمية وقابلية التوسع. تشمل مساهمات الورقة تطوير تنفيذات فرز معجلة بواسطة GPU، وتحليل مقارن لمختلف النماذج الخوارزمية، وإنشاء إطار عمل للتقييم الذي يسهل التقييم المتسق لخوارزميات الفرز المعتمدة على GPU.
طرق
في هذا القسم، يوضح المؤلفون الإعداد التجريبي المستخدم لتقييم أداء خوارزميات الفرز المعجلة بواسطة GPU من خلال تحليل مقارن لكل من التنفيذات المتوازية والمتسلسلة لمختلف طرق الفرز، بما في ذلك فرز الدمج (MS)، الفرز السريع (QS)، الفرز الفقاعي (BS)، فرز القاعدة (RS)، وفرز الاختيار (SS). استخدمت التقييم مجموعة بيانات من 10,000,000 عدد صحيح تم إنشاؤها عشوائيًا، مأخوذة من ملفات CSV متاحة للجمهور على Figshare. تم تحديد حجم مجموعة البيانات هذه على أنه الأمثل بناءً على الاختبارات الأولية، حيث فشلت مجموعات البيانات الأصغر في إظهار مزايا التوازي بواسطة GPU، بينما أدت مجموعات البيانات الأكبر إلى استخدام مفرط للذاكرة ووقت تشغيل مطول. أبرز الحجم المختار الفجوات في الأداء بين تقنيات الفرز المتسلسلة والمتوازية بشكل فعال.
تم اختيار بيئة البرمجة للدراسة بعناية لتعزيز كل من التوافق الفني وكفاءة التطوير. تم استخدام CUDA لتنفيذات GPU، مما استلزم استخدام C/C++ نظرًا لدعم CUDA الأصلي لهذه اللغات. تم استخدام Visual Studio كمنصة التطوير الرئيسية لـ CUDA C، حيث توفر ميزات مثل إكمال التعليمات البرمجية التلقائي وأدوات تصحيح الأخطاء المدمجة التي سهلت تطوير والتحقق من صحة الخوارزميات المتوازية بكفاءة. بالنسبة للتنفيذات المتسلسلة، تم اختيار C++ لعدم اعتمادها على منصة معينة وبساطتها، مما ساعد في نمذجة الخوارزمية. ضمنت مجموعة هذه الأدوات والبيئات إطار عمل موثوق لتصميم واختبار ومقارنة خوارزميات الفرز.
نقاش
يستعرض قسم النقاش في الورقة مختلف التقدمات في خوارزميات الفرز المعتمدة على GPU، مع تسليط الضوء على تحسين وتنفيذ تقنيات الفرز المتوازية. تشمل المساهمات الملحوظة مسحًا أجراه جوشي وسينغ، الذي يحدد أكثر خوارزميات الفرز فعالية لـ CUDA، مثل فرز الدمج (MS)، الفرز السريع (QS)، فرز القاعدة (RS)، وفرز العينة. بينما يُلاحظ أن RS يتميز بسرعته مع مجموعات البيانات الكبيرة، يتم التعرف على MS وQS لاستقرارهما عبر توزيعات الإدخال المتنوعة. أظهر تاناسيك وآخرون تحسينات كبيرة في الأداء في بيئات متعددة لوحدات معالجة الرسوميات من خلال تحسين تقسيم البيانات والتواصل بين وحدات معالجة الرسوميات، بينما قدم تشيتين وآخرون إطار عمل فرز متعدد لوحدات معالجة الرسوميات مدرك للذاكرة الذي يحسن توزيع الحمل ويقلل من تكاليف نقل البيانات.
كما يؤكد القسم على الحاجة إلى إطار عمل موحد للتقييم، حيث تركز العديد من الدراسات الحالية على خوارزميات فردية دون مقارنات شاملة تحت ظروف موحدة. يعالج المؤلفون هذه الفجوة من خلال تقييم أربعة خوارزميات تمثيلية—MS، QS، BS، وRS—باستخدام إعدادات الأجهزة المتسقة ومجموعة بيانات كبيرة من 10 ملايين عدد صحيح عبر توزيعات إدخال متنوعة. تهدف هذه الطريقة إلى توفير مقارنة مضبوطة لأداء الخوارزمية وقابلية التوسع في سيناريوهات الحوسبة باستخدام GPU في العالم الحقيقي. تختتم المناقشة بالاعتراف بأهمية كل من التقدمات الخوارزمية والمعمارية في تعزيز كفاءة الفرز على وحدات معالجة الرسوميات، مما يبرز أهمية تعدد الخيوط والاستراتيجيات الهجينة في البحث المعاصر.
DOI: https://doi.org/10.1371/journal.pone.0342167
PMID: https://pubmed.ncbi.nlm.nih.gov/41632810
Publication Date: 2026-02-03
Author(s): Mohammed Alaa Ala’anzy et al.
Primary Topic: Parallel Computing and Optimization Techniques
Overview
This section of the research paper discusses the comparative performance of various sorting algorithms when implemented on GPUs using CUDA technology. It distinguishes between sequential and parallel sorting methods, highlighting the advantages of parallel processing in terms of speed, especially for large datasets. The study evaluates the GPU-accelerated versions of merge sort (MS), quick sort (QS), bubble sort (BS), radix top-k selection sort (RS), and slow sort (SS) across four dataset scenarios: random, reverse-sorted, already-sorted, and nearly-sorted. The results demonstrate significant speedups, with Radix Sort achieving a remarkable acceleration of approximately 50×, while Quick Sort and Merge Sort show speedups of 97× and 103×, respectively. In contrast, Bubble Sort, despite its improvement, remains inefficient overall.
The conclusion emphasizes that GPU-based parallel sorting yields substantial execution time reductions compared to sequential CPU sorting, particularly for RS and SS, which align well with GPU architectures. The performance analysis indicates that the structure of the dataset significantly influences sorting efficiency, with MS performing best on nearly sorted data. The study also notes a trade-off between execution time and memory consumption, with RS exhibiting the highest memory usage and SS the lowest. Future research directions include expanding the range of sorting algorithms evaluated, implementing sequential versions in lower-level languages for better benchmarking, and exploring hybrid CPU-GPU models for enhanced sorting efficiency on large datasets.
Introduction
The introduction of this research paper highlights the increasing demands for efficient sorting algorithms in data-intensive fields such as artificial intelligence and scientific computing, where sorting can constitute up to 25% of processing time. Traditional sequential sorting methods struggle with large datasets, prompting the exploration of parallel sorting techniques, particularly those leveraging multi-GPU architectures. Notable advancements include the work of Ilic et al., which achieved a 14× throughput improvement using NVLink and PCIe 4.0, and Tolovski et al.’s RMG Sort, which employs a radix-partitioning strategy for enhanced scalability. The paper emphasizes the importance of evaluating sorting algorithms across various data distributions, as recent studies indicate that CPU sorting can outperform GPU sorting under certain conditions, particularly with partially sorted datasets.
To address existing gaps in the literature, the authors implement and benchmark four sorting algorithms—Merge Sort (MS), Quick Sort (QS), Bubble Sort (BS), Radix Sort (RS), and Segmented Sort (SS)—within a unified CUDA C++ framework. They systematically assess these algorithms on an NVIDIA GTX 1660 SUPER using a dataset of ten million integers across four input distributions: random, sorted, reverse-sorted, and nearly sorted. The study aims to quantify performance improvements, with speedups ranging from 7× to 38× compared to CPU implementations, while also providing insights into algorithm robustness and scalability. The paper’s contributions include the development of GPU-accelerated sorting implementations, a comparative analysis of different algorithmic paradigms, and the establishment of a benchmarking framework that facilitates consistent evaluation of GPU-based sorting algorithms.
Methods
In this section, the authors detail the experimental setup used to assess the performance of GPU-accelerated sorting algorithms through a comparative analysis of both parallel and sequential implementations of various sorting methods, including Merge Sort (MS), Quick Sort (QS), Bubble Sort (BS), Radix Sort (RS), and Selection Sort (SS). The evaluation utilized a dataset of 10,000,000 randomly generated integers, sourced from publicly available CSV files on Figshare. This dataset size was determined to be optimal based on preliminary tests, as smaller datasets failed to demonstrate the advantages of GPU parallelism, while larger datasets led to excessive memory usage and prolonged runtimes. The selected size effectively highlighted the performance disparities between the sequential and parallel sorting techniques.
The programming environment for the study was carefully chosen to enhance both technical compatibility and development efficiency. CUDA was employed for the GPU implementations, necessitating the use of C/C++ due to CUDA’s native support for these languages. Visual Studio was utilized as the primary development platform for CUDA C, providing features such as code autocompletion and integrated debugging tools that facilitated the efficient development and validation of the parallel algorithms. For the sequential implementations, C++ was selected for its platform independence and simplicity, which aided in algorithm prototyping. The combination of these tools and environments ensured a reliable framework for the design, testing, and comparison of the sorting algorithms.
Discussion
The discussion section of the paper reviews various advancements in GPU-based sorting algorithms, highlighting the optimization and implementation of parallel sorting techniques. Notable contributions include a survey by Joshi and Singh, which identifies the most effective sorting algorithms for CUDA, such as Merge Sort (MS), Quick Sort (QS), Radix Sort (RS), and Sample Sort. While RS is noted for its speed with large datasets, MS and QS are recognized for their stability across diverse input distributions. Tanasic et al. demonstrated significant performance improvements in multi-GPU environments through enhanced data partitioning and inter-GPU communication, while Çetin et al. introduced a memory-aware multi-GPU sorting framework that optimizes workload distribution and minimizes data transfer overhead.
The section also emphasizes the need for a unified benchmarking framework, as many existing studies focus on individual algorithms without comprehensive cross-comparisons under uniform conditions. The authors address this gap by evaluating four representative algorithms—MS, QS, BS, and RS—using a consistent hardware setup and a large dataset of 10 million integers across various input distributions. This approach aims to provide a controlled comparison of algorithmic performance and scalability in real-world GPU computing scenarios. The discussion concludes by acknowledging the importance of both algorithmic and architectural advancements in enhancing sorting efficiency on GPUs, underscoring the relevance of multi-threading and hybrid strategies in contemporary research.