17 papers · ranked by Valyu relevance
Michael Axtmann, Timo Bingmann, Peter Sanders, Christof Schulz
Previous parallel sorting algorithms do not scale to the largest available machines, since they either have prohibitive communication volume or prohibitive critical path length. We describe algorithms that are a viable compromise and overcome this gap both in theory and practice. The algorithms are multi-level…
Michael Axtmann, Peter Sanders
—We investigate distributed memory parallel sorting algorithms that scale to the largest available machines and are robust with respect to input size and distribution of the input elements. The main outcome is that four sorting algorithms cover the entire range of possible input sizes. For three algorithms we devise…
Alexandros V Gerbessiotis
We propose new sequential sorting operations by adapting techniques and methods used for designing parallel sorting algorithms. Although the norm is to parallelize a sequential algorithm to improve performance, we adapt a contrarian approach: we employ parallel computing techniques to speed up sequential sorting. Our…
Daniel Bascones, Borja Morcillo
—Sorting is one of the fundamental problems in computer science. Playing a role in many processes, it has a lower complexity bound imposed by O(n log n) when executing on a sequential machine. This limit can be brought down to sublinear times thanks to parallelization techniques that increase the number of comparisons…
Tomoyuki Tokuue, Tomoaki Ishiyama
Sorting is one of the most basic algorithms, and developing highly parallel sorting programs is becoming increasingly important in high-performance computing because the number of CPU cores per node in modern supercomputers tends to increase. In this study, we have implemented two multi-threaded sorting algorithms…
Timo Bingmann, Andreas Eberle, Peter Sanders
algorithms and successful parallel sorting algorithms for atomic objects, we first propose string sample sort. The algorithm makes effective use of the memory hierarchy, uses additional word level parallelism, and largely avoids branch mispredictions. Then we focus on NUMA architectures, and develop parallel multiway…
Vipul Harsh, Laxmikant V. Kalé, Edgar Solomonik
To minimize data movement, state-of-the-art parallel sorting algorithms use techniques based on sampling and histogramming to partition keys prior to redistribution. Sampling enables partitioning to be done using a representative subset of the keys, while histogramming enables evaluation and iterative improvement of a…
Marek Kokot, Sebastian Deorowicz, Agnieszka Debudaj-Grabysz
The paper introduces RADULS, a new parallel sorter based on radix sort algorithm, intended to organize ultra-large data sets efficiently. For example 4 G 16-byte records can be sorted with 16 threads in less than 15 seconds on Intel Xeon-based workstation. The implementation of RADULS is not only highly optimized to…
Alexandros V. Gerbessiotis
A secondary objective is to attempt to model the performance of these algorithm implementations under the MBSP (Multi-memory BSP) model. We first provide some general high-level observations on the performance of these implementations. If we can conclude anything is that accurate prediction of performance by taking…
Dmitri I. Arkhipov, Di Wu, Keqin Li, Amelia Regan
—Sorting is a fundamental operation in computer science and is a bottleneck in many important fields. Sorting is critical to database applications, online search and indexing, biomedical computing, and many other applications. The explosive growth in computational power and availability of GPU coprocessors has allowed…
Samuel King Opoku
—Conventional sorting algorithms make use of such data structures as array, file and list which define access methods of the items to be sorted. These traditional methods – exchange sort, divide and conquer sort, selection sort and insertion sort – require supervisory control program. The supervisory control program…
Michael Axtmann, Sascha Witt, Daniel Ferizovic, Peter Sanders
We present new sequential and parallel sorting algorithms that now represent the fastest known techniques for a wide range of input sizes, input distributions, data types, and machines. Somewhat surprisingly, part of the speed advantage is due to the additional feature of the algorithms to work in-place, i.e., they do…
Esam Nsour, Mohammad Fasha
| List of Tables 3 | | --- | | List of Figures 4 | | Abstract 5 | | 1. Introduction 5 | | 1.1 Sorting 6 | | 1.2 Quick Sort Algorithm, 6 | | 1.3 Interconnection networks 6 | | 1.4 The Hyper-Hexa Cell (HHC) 7 | | 1.5 Optical transpose interconnection system (OTIS) 7 | | 1.6 Parallel computing 9 | | 2. Related Work 10 | |…
Tianyi Yu, Wei Li
Sorting is one of the most fundamental problems in the field of computer science.Withtherapid development of manycore processors, it shows great importance to designefficientparallelsortalgorithm on manycore architecture. This paper studies the parallel memory sortingmethodonmodernhardware, and summarizes its research…
Oded Green, Saher Odeh, Yitzhak Birk
We present a novel, visually intuitive approach to partitioning two input sorted arrays into pairs of contiguous sequences of elements, one from each array, such that 1) each pair comprises any desired total number of elements, and 2) the elements of each pair form a contiguous sequence in the output merged sorted…
Alexandros V. Gerbessiotis, Constantinos J. Siniolakis
The Bulk-Synchronous Parallel model of computation has been used for the architecture independent design and analysis of parallel algorithms whose performance is expressed not only in terms of problem size n but also in terms of parallel machine properties. In this paper the performance of implementations of…
Mohammad Fasha
This work presents a comparison for the performance of sequential sorting algorithms under four different modes of execution, the sequential processing mode, a conventional multi-threading implementation, multi-threading with OpenMP Library and finally parallel processing on a super computer. Quick Sort algorithm was…