Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 3,727 papers for “parallel sorting”

A Novel Parallel Sorting Algorithm for Contemporary Architectures

David R. Cheng, Viral B. Shah, John R. Gilbert et al. · 2007

Traditionally, the field of scientific computing has been dominated by numerical methods. However, modern scientific codes often combine numerical methods with combinatorial methods. Sorting, a widely studied problem in computer science, is an important primitive for combinatorial scientific computing. As high

Cited by 0

Performance evaluation of GPU-based parallel sorting algorithms

Mohammed Alaa Ala’anzy, Nurdaulet Tolendi, Baizhan Baubek et al. · PLoS ONE · 2026

Sorting can be approached in two main ways: sequentially and in parallel. In sequential sorting, data is processed in a single-threaded manner, which can be slow for large datasets. However, parallel sorting divides the task across multiple processing units, enabling faster results by processing data simultaneously. Furthermore, Compute Unified Device Architecture (CUDA) technology enables developers to leverage GPU power for general-purpose parallel computing, significantly accelerating tasks like sorting. This paper investigates the GPU-based parallelization of merge sort (MS), quick sort (QS), bubble sort (BS), radix top-k selection sort (RS), and slow sort (SS) presenting optimized algorithms designed for efficient sorting of large datasets using modern GPUs. The primary objective is to evaluate the performance of these algorithms on GPUs utilizing CUDA, with a focus on analyzing both parallel time complexity and space complexity across various data types. Experiments are conducted on four dataset scenarios: randomly generated data, reverse-sorted data, already-sorted data, and nearly-sorted data. Also, the performance of GPU-accelerated implementations is compared with their sequential counterparts to assess improvements in computational efficiency and scalability. Earlier GPU-based generations of this type typically achieved acceleration rates between 2× and 9× over scalar CPU code. With newer GPU enhancements, including parallel-aware primitives and radix- or merge-optimized operations, acceleration rates have seen significant improvement. Our experiments indicate that Radix Sort based on GPUs achieves a significant speedup of approximately 50× (sequential: 240.8 ms, parallel: 4.83 ms) on 10 million random sort elements. Quick Sort and Merge Sort have 97× and 103× speedups, respectively (Quick: 1461.97 ms vs. 15.1 ms; Merge: 2212.33 ms vs. 21.4 ms). Bubble Sort, while significantly improving in parallel (123,321.9 ms to 7377.8 ms for an ≈17× improvement), is considerably worse overall. Slow Sort demonstrates a moderate but consistent acceleration, reducing execution time from 74.07 ms in the sequential version to 3.99 ms on the GPU, yielding an ≈18.6× speedup. These experimental findings confirm that the new single-GPU implementations can get speedups ranging from 17× to over 100×, surpassing the typical gains reported in previous generations and comparable to or over rates of acceleration reported for cutting-edge parallel sorting algorithms in recent studies.

Cited by 0Open access

Parallel sorting on Intel Single-Chip Cloud Computer

Kenan Avdic, Nicolas Melot, Jörg Keller et al. · 2011

Abstract. After multicore processors, many core architectures are becoming increasingly popular in research activities. The development of multicore and many core processors yields the opportunity to revisit classic sorting algorithms, which are important subroutines of many other algorithms. The Single-Chip Cloud Computer (SCC) is an experimental processor created by Intel Labs. It introduces 48 IA32 cores linked by an on-chip high performance network. This work introduces the evaluation of the performances this chip provides, regarding access to main memory and mesh network throughput. It also gives implementations of several variants of parallel mergesort algorithms, and analyzes the performance of the merging phase. The results presented in this paper motivate to use on-chip pipelined mergesort on SCC, which is an issue of ongoing work. 1

Cited by 0

merging, and sorting in parallel models of computation

A. Borodin, J. E. Hopcroft · 1982

A variety of models have been proposed for the study of synchronous parallel computation. These models are reviewed and some prototype problems are studied further. Two classes of models are recognized, fixed connection networks and models based on a shared memory. Routing and sorting are prototype problems for the networks; in particular, they provide the basis for simulating the more powerful shared memory models. It is shown that a simple but important class of deterministic strategies (oblivious routing) is necessarily inefficient with respect to worst case analysis. Routing can be viewed as a special case of sorting, and the existence of an O(log n) sorting algorithm for some n processor fixed connection network has only recently been established by Ajtai, Komlos, and Szemeredi (“15th ACM Sympos. on Theory of Cornput., ” Boston, Mass., 1983, pp. l-9). If the more powerful class of shared memory models is considered then it is possible to simply achieve an O(log n loglog n) sort via Valiant’s parallel merging algorithm, which it is shown can be implemented on certain models. Within a spectrum of shared memory models, it is shown that loglogn is asymptotically optimal for n processors to merge two sorted lists containing n elements. 0 1985 Academic Press, Inc.

Cited by 0

Parallel construction of binary tree based on sorting

Bulletin of Miscellaneous Information (Royal Gardens Kew) · 2018

Introduction . Algorithms for the parallel binary tree construction are developed. The algorithms are based on sorting and described in a constructive form. For the Nelement set, the time complexity has T(R) = O(1) and T(R) = O(log 2 N) estimates, where R = (N 2 -N)/2 is the number of processors. The tree is built with the uniqueness property. The algorithms are invariant with respect to the input sequence type. The work objective is to develop and study ways of accelerating the process of organizing and transforming the tree-like data structures on the basis of the stable maximum parallel sorting algorithms for their application to the basic operations of information retrieval on databases. Materials and Methods. A one-to-one relation between the input element set and the binary tree built for it is established using a stable address sorting. The sorting provides maximum concurrency, and, in an operator form, establishes a one-to-one mapping of input and output indices. On this basis, methods for the mutual transformation of the binary data structures are being developed. Research Results. An efficient parallel algorithm for constructing a binary tree based on the address sorting with time complexity of T(N 2 ) = O(log 2 N) is obtained. From the well-known analogues, the algorithm differs in structure and logarithmic estimation of time complexity, which makes it possible to achieve the acceleration of O(N α ), α≥1 order analogues. As an advanced version, an algorithm modification, which provides the maximum parallel construction of the binary tree based on a stable address sorting and a priori calculation of the stored subtree root indices is suggested. The algorithm differs in structure and estimation of T(1) = O(1) time complexity. A similar estimate is achieved in a sequential version of the modified algorithm, which allows obtaining the acceleration of known analogs O(N α ), α>1 order. Discussion and Conclusions. The results obtained are focused on the creation of effective methods for the dynamic database processing. The proposed methods and algorithms can form an algorithmic basis for an advanced deterministic search on the relational databases and information systems.

Cited by 0Open access

Deep Recyclable Trash Sorting Using Integrated Parallel Attention

Hualing Lin, Xue Zhang, Junchen Yu et al. · Sensors · 2024

Sorting recyclable trash is critical to reducing energy consumption and mitigating environmental pollution. Currently, trash sorting heavily relies on manpower. Computer vision technology enables automated trash sorting. However, existing trash image classification datasets contain a large number of images without backgrounds. Moreover, the models are vulnerable to background interference when categorizing images with complex backgrounds. In this work, we provide a recyclable trash dataset that supports model training and design a model specifically for trash sorting. Firstly, we introduce the TrashIVL dataset, an image dataset for recyclable trash sorting encompassing five classes (TrashIVL-5). All images are collected from public trash datasets, and the original images were captured by RGB imaging sensors, containing trash items with real-life backgrounds. To achieve refined recycling and improve sorting efficiency, the TrashIVL dataset can be further categorized into 12 classes (TrashIVL-12). Secondly, we propose the integrated parallel attention module (IPAM). Considering the susceptibility of sensor-based systems to background interference in real-world trash sorting scenarios, our IPAM is specifically designed to focus on the essential features of trash images from both channel and spatial perspectives. It can be inserted into convolutional neural networks (CNNs) as a plug-and-play module. We have constructed a recyclable trash sorting network building upon the IPAM, which produces an acuracy of 97.42% on TrashIVL-5 and 94.08% on TrashIVL-12. Our work is an effective attempt of computer vision in recyclable trash sorting. It makes a positive contribution to environmental protection and sustainable development.

Cited by 1Open access

THE ALGORITHMS OF PARALLEL RADIX SORTING ON GPGPU

Г.В. Воронцов, А. П. Преображенский, О. Н. Чопоров · Modelirovanie, optimizaciâ i informacionnye tehnologii. · 2018

В данной статье проводится анализ возможностей разработки алгоритма построения BVH-дерева. Этот алгоритм должен позволять быструю перестройку дерева при изменении параметров задачи. Предлагается анализировать линейное BVH-дерево, вначале выбирается порядок, в котором листовые узлы обозначаются в дереве, затем генерируются внутренние узлы по этому порядку. Рассматривается кривая Z-порядка, вычисляются Мортон-коды для каждого листового узла. На следующем шаге осуществляется сортировка получившихся Мортон-кодов. В алгоритме сортировки двоичной последовательности используется параллельный алгоритм Radix Sort. Для анализа последовательности листовых узлов, необходимо разбить ее на подинтервалы, размеры которых определяются в рамках бинарного поиска. Чтобы повысить значение занятости видеокарты, предлагается указать внутренние узлы определенным образом, и тогда, появляется возможность узнать, к какому диапазону листовых узлов относится любой выбранный внутренний узел. Для тестирования алгоритма быстрого построения BVH-дерева на GPGPU была использована технология DirectCompute и язык программирования шейдеров - HLSL. Приведена зависимость времени выполнения каждой от количества примитивов при вычислении ограничивающих объемов листовых узлов и их кодов Мортона, формировании иерархии дерева, а также вычислении ограничивающих объемов внутренних узлов. This paper analyzes the possibilities of developing the BVH tree construction algorithm. This algorithm should allow to quickly rebuild the tree when you change the parameters of the problem. It is proposed to analyze the linear BVH tree, first select the order in which the leaf nodes are indicated in the tree, then the internal nodes are generated in this order. The z-order curve is selected and the Morton codes for each leaf node are calculated. The next step is to sort the resulting Morton codes. The binary sequence sorting algorithm uses a parallel Radix Sort algorithm. To analyze the sequence of leaf nodes, it is necessary to divide it into subintervals, the sizes of which are determined by binary search. In order to increase the occupancy of the graphics card, you are prompted to specify the internal nodes in a certain way, and then you have the opportunity to find out what range of leaf nodes any selected internal node belongs to. DirectCompute technology and Shader programming language-HLSL were used to test the algorithm of fast BVH tree construction on GPGPU. Given the dependence of running time of each of the number of primitives in the computation of the bounding volumes of the leaf nodes and their codes of Morton, forming a tree hierarchy, the computation of the bounding volumes of internal nodes.

Cited by 2Open access

Parallel Sorting based OS-CFAR Implementation in FPGA

Shine Parekkadan Sunny, Prakash Narayanan M · OCEANS 2022 - Chennai · 2022

Target detection in Sonar systems involves the comparison of the received signal amplitude against a threshold. To obtain a Constant False-Alarm Rate (CFAR), an adaptive threshold representing the local clutter situation must be applied. Order Statistics CFAR (OS-CFAR) is a popular CFAR method, using a single value extracted from the ordered statistic. This method can tolerate background singularities and can have superior results in certain conditions. This includes the presence of multi-targets in the reference window or the case when the reference window is crossing clutter edges.Numerical sorting involved in OS-CFAR is a computationally expensive operation. The best asymptotic run-time complexity of sorting is O(n log n) in a sequential processing system. In this context, a novel approach is proposed, developed, and tested for running OS-CFAR on FPGA. The proposed approach has a run-time complexity of O(n) , that is linear computation complexity by rigorous parallelization. Moreover, optimum re-source utilization is maintained by time-division multiplexing of sorting hardware and tri-state buffering of output. The developed approach is tested for simultaneous 60-beam, 32.5 kHz sensor data by considering 200 range cells.

Cited by 4

Improving Collaborative Convergence through Distributed and Parallel Sorting

Christopher B.R. Diller, Joel H. Helquist, John Kruse · International Journal of e-Collaboration · 2016

This paper examines a convergence process of organizing ideas that are generated during collaborative idea generation activities. The method presented reduces the impact of organizing brainstorming ideas on individual participants by dividing the convergence activity into smaller, discrete tasks that can be completed individually, and in parallel, by the participants. The entire pool of brainstorming ideas is subdivided into smaller pools and each participant is then tasked with organizing one of the subsets of ideas. The results show that by dividing up the overall activity into subtasks, the subjects experienced a more favorable environment. Furthermore, the subjects were able to work through their subset of ideas and produce results that were similar to those performing the full sort of the entire pool.

Cited by 3

A NOTE ON COARSE GRAINED PARALLEL INTEGER SORTING

Albert P.C. Chan, F. Dehne · Parallel Processing Letters · 1999

We observe that for n/p ≥ p, which is usually the case in practice, there exists a very simple, deterministic, optimal coarse grained parallel integer sorting algorithm with 24 communication rounds (6 [Formula: see text]-relations and 18 p-relations), O (n/p) memory per processor and O (n/p) local computation. Experimental data indicates that the algorithm has very good performance in practice.

Cited by 26

Parallel suffix sorting based on bucket pointer refinement

Habiba Mohamed, Mohamed Abouelhoda · 2010

Suffix array is one of the most important data structures in bioinformatics. Much effort has been devoted to find efficient sequential algorithms for its construction, but little is done to introduce parallel construction algorithms. The bucket pointer refinement algorithm is one of the efficient suffix sorting algorithms that is tuned for genomic datasets. In this paper, we introduce a parallel version of this algorithm running on (shared memory) multicore computers. We present experimental results comparing our algorithms to other parallel algorithms running on similar architecture. Our program is open source and available at http://www.nubios.nileu. edu.eg/tools/pbpr.

Cited by 9

Sorting by transposition and translocation using parallel approach

Pranav Kumar, G. Sahoo · 2016

Study of genomic rearrangement helps in species recognition and is an important procedure to understand evolution process and comparative genomics in a better way. If we have two genome A and B, our aim is to convert one genomic sequence A into another one using two sorting process called transposition and translocation. Sorting by transposition and translocation (SBT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) problem is based on minimum length sequence conversion. During evolution genomes undergo large scale mutations to change gene order, mainly (reversal, translocation and transposition) but here we focus on transposition and translocation only. This paper reexamines the problem of genome sorting by transposition and translocation together and proposed a layout with a parallel concept. We give an elementary proof for computing arrangement distance formula and a proficient algorithm is derived to solve the problem of sorting by transposition and translocation which looks simpler, faster and natural.

Cited by 0

A Balanced Parallel Distributed Sorting Implemented with PGX.D.

Zahra Khatami, Sungpack Hong, Jinsu Lee et al. · 2016

Sorting has been one of the most challenging studied problems in different scientific researches. Although many techniques and algorithms have been proposed on the theory of having efficient parallel sorting implementation, however achieving desired performance on different types of the architectures with large number of processors is still a challenging issue. Maximizing parallelism level in applications can be achieved by minimizing overheads due to load imbalance and waiting time due to memory latencies. In this paper, we present a distributed sorting algorithm implemented in PGX.D, a fast distributed graph processing system, which outperforms the Spark's distributed sorting implementation by around 2x-3x by hiding communication latencies and minimizing unnecessary overheads. Furthermore, it shows that the proposed PGX.D sorting method handles dataset containing many duplicated data entries efficiently and always results in keeping balanced workloads for different input data distribution types.

Cited by 0

An Efficient Parallel Sorting Algorithm for Multicore Machines

D. Abhyankar, M. Ingle · 2011

Sorting an array of integers is one of the most basic problems in Computer Science. Also it is an issue in high performance database applications. Though literature is imbued with a variety of sorting algorithms, different architectures need different optimizations to reduce sorting time. This paper presents a Multicore ready parallel sorting algorithm which has been designed with Multicore/Manycore architecture in mind. Our study shows that the proposed algorithm is excellent for large input size and multiple free cores. In essence algorithm has potential to be a success in situations when one has large input and machine is a Multicore machine. The paper does not neglect overhead involved with parallel programming and suggests two system calls to check the availability of free cores and to reserve a core for a fixed time quantum.

Cited by 0