Richard P. Brent, Andrew Tridgell · 2002
A parallel sorting algorithm is presented for storage-efficient internal sorting on MIMD machines. The algorithm first sorts the elements within each node using a serial based algorithm, then a two-phase parallel merge. It requires additional storage of order of the square root of the number of elements in each node. Performance of the algorithm on two general-purpose MIMD machines, the Fujitsu AP1000 and the Thinking Machines CM5, is examined. The algorithm is suitable for implementation on special-purpose parallel machines, e.g., parallel database machines.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 2
Mark H. Nodine, Jeffrey Scott Vitter · 2001
We present a load balancing technique that leads to an optimal deterministic algorithm called Balance Sort for external sorting on multiple disks. Our measure of performance is the number of input/output (I/O) operations. In each I/O, each of the D disks can simultaneously transfer a block of data. Our algorithm improves upon the randomized optimal algorithm of Vitter and Shriver as well as the (non-optimal) commonly-used technique of disk striping. It also improves upon our earlier mergebased sorting algorithm in that it has smaller constants hidden in the big-oh notation, and it is possible to implement using only striped writes (but independent reads). In a companion paper, we show how to modify the algorithm to achieve optimal CPU time, even on parallel processors and parallel memory hierarchies.
Cited by 0
Han, Y, Chong, KW, Lam, TW et al. · The HKU Scholars Hub (University of Hong Kong) · 2010
Cited by 0
Susanne Albers, Torben Hagerup · Information and Computation · 1997
Cited by 69
Kazem U. Ahmed, D. Yun Yeh · Lecture notes in computer science · 1991
Cited by 0
Shi Yao · 2003
Sorting is an important operation of transaction processing. It is a relatively mature field, as many algorithms for memory sorting, disk sorting and parallel sorting have come forth in the past decades. In this paper, the sorting algorithm is studied from a thoroughly different standpoint, and the THSORT (Tsinghua SORT), a parallel sorting algorithm on a single computer, is brought forward. THSORT uses several processes to control different components of a computer, which enables the data input, sorting and output to be run concurrently, and thus greatly enhances the parallelism and efficiency of the hardware. Experimental results based on a computer with two RAIDs (redundant array of inexpensive disks) indicate that THSORT has almost doubled the performance of NTSORT (new technology SORT), a famous sorting program. Moreover, THSORT has won the 2002 PennySort competition and is still holding the world record in the Daytona category.
Cited by 2
Lingxiao Zeng · 2021
As a basic operation, sorting has a wide range of applications. Early research provides a variety of serial sorting algorithms to speed up sorting. However, these serial algorithms waste the parallel computing capacity of current computers. On the other hand, it is of vital importance to promote the speed of sorting large-scale data because of the boom in data science, while traditional sorting algorithms are no longer suitable due to its relatively long complexity. Consequently, we propose two parallel sorting algorithms, Parallel Quick Sort Algorithm (PQSA) and Merging Subarrays from Quick Sort Algorithm (MSQSA) to solve this problem. In the meantime, we carry out simulation experiments to evaluate their performance. The experiment results show that two sorting algorithms run faster than traditional serial sorting algorithms. Furthermore, with the number of total threads increasing, PQSA and MSQSA have shorter running time and higher parallel speedup. Most importantly, when data size grows, MSQSA becomes slightly faster than PQSA, which shows its stronger practicability in sorting massive data.
Cited by 2
Michael McKinsey, Stephanie Brink, Stephanie Lam et al. · 2025
Understanding parallel algorithms is crucial for accelerating scientific simulations on complex, distributed memory, high-performance computers. Modern algorithm classification approaches learn semantics directly from source code to differentiate between algorithms, however, accessing source code is not always possible. We can learn about parallel algorithms from observing their performance, as programs running the same algorithms and using the same hardware should exhibit similar performance characteristics. We develop an approach to learn parallel sorting algorithm classes from performance data directly in order to classify parallel sorting algorithms without using the source code. In this paper, we focus on the workflow and interfaces we developed for collecting, processing, and modeling performance data using Caliper, Thicket, PyTorch, and Scikit-learn. Our workflow results in classification accuracy of our machine learning models up to 95.3% across five different algorithm classes.
Cited by 0
Kung-Shiuh Huang, Lishing Liu, Jih-Kwon Peir · Optical Society of America Annual Meeting · 1990
Sorting a sequence of N items requires at least O (NlogN) time steps on a conventional uniprocessor computer and O(log2 N) for most electronic parallel sorting networks, such as old-even merging network, bitonic merging network and perfect shuffle network. In this paper we provide an optical facility for sorting a sequence of N items in only O(1) time steps.
Cited by 0
Garimella Sai Sankeerth, Arunava Mukherjee, N. Gopalakrishna Kini et al. · Lecture notes in networks and systems · 2026
Cited by 0
Zhihui Du, Sen Zhang, David A. Bader · Lecture notes in computer science · 2023
Cited by 1
David K. Hsiao, M. Jaishankar Menon · Defense Technical Information Center (DTIC) · 1980
In this report, we demonstrate methods for implementing a fast hardware sorter in DBC. Given the trend towards cheaper processors and block-oriented access memories, we are especially interested in methods that utilize multiple processors with large-capacity block-oriented access memories in a parallel fashion. Many parallel sorting methods are already available. Most of these methods use P processors to sort P records. Even though these methods are fast, they suffer from the fact that groups of records larger than P in number will have to be sorted in separate batches and then merged. Batching and merging defeats the intent of parallelism for high performance. Our methods, therefore, attempt to use P processors to sort more than P records without the need for batching and merging. Furthermore, our methods employ block-oriented access memories (such as magnetic bubbles and charge-coupled devices). Three sorting methods are described in this report. The first one, called the odd-even sort, uses P processors, each of which utilizes its own block-access memory to accommodate M records and has two processor-to-processor interconnections. This method sorts MP records in 0(M log M + MP) time. There is no restriction on either P or M. More importantly, since each processor needs to be connected to only two others, we can increase the number of processors in the sorter without having to increase the number of connections per processor. (Author)
Cited by 5
William Gasarch, et al. · 2008
Cited by 0
Steven Molnar, Michael Cox, David Ellsworth et al. · 1994
communication traffic between sortfirst processors rendering NCGA ÒheadÓ Picture-Level benchmark [1]. Arrow color indicates the number of primitives transferred between processors between these two successive frames. Range is 0 (black) to 800 (white) using a heated-object spectrum. We describe three broad classes of parallel rendering methods, based on where the sort from object-space to screen space occurs. These classes encompass most feedforward parallel software and hardware rendering architectures that have been described to date. After introducing the classes, we perform a coarse analysis of the aggregate processing and communication costs of each and identify constraints they impose on the rendering application. The aim is to provide a conceptual model of the tradeoffs between the approaches as an aid to designers and implementers of high-performance, parallel rendering systems.
Cited by 0
Bhattacharya Chrostowski · 1996
In this paper we present an efficient randomized sorting algorithm for a multiprocessor computer which uses all-to-all broadcast freespace optical interconnects. This algorithm has a better time complexity compared to other sorting algorithms utilizing optical processing that have been proposed in the existing literature. The present algorithm has better performance compared to similar randomized sorting algorithms on electrically interconnected mutiprocessors, due to the higher bandwidths and parallelism of optical interconnections. 1 Introduction High bandwidth and low latency are the requirements for interconnection networks for high performance computers. As individual processor data rates and complexities grow, electrical interconnects impose a communications bottleneck since the bandwidth of each link and the physical distance these links can cover are limited by power dissipation and electrical crosstalk[11, 12, 5, 8, 9]. The result is a limitation in practical increases in t...
Cited by 0
William Gasarch, Evan Golub, Clyde P. Kruskal · Journal of Computer and System Sciences · 2003
Cited by 7
K. Harikrishna, S. K. Tripathy · Communications in computer and information science · 2024
Cited by 0
Tao Tang · 2005
This paper describes a generalized version of a previously published sort algorithm, parallel shell merge.[3] This version was implemented on the JPLKaltech Mark I11 hypercube concurrent processor. Each node starts out with a sublist of items to be sorted first internally, and then among the other nodes. Parallel shell merge is an algorithm used to produce a whole sorted list across the hypercube once each sublist is sorted internally. This version is general in the sense that it allows sublists of very different sizes to be sorted as well as being able to handle balanced sublists. This general version performs quite well when it is used to sort balanced loads of data; however, there are some efficiency losses due to the generalization, but they are acceptable. I. Background A prototype of SEQGEN, the software that verifies and expands high-level activities into low-level command sequences for PL flight projects, is in the process of development on the JPL/Caltech Mark I11 hypercube concurrent processor.[l1[21 The purpose of this prototype is to show that the process of generating commands and sending them to the spacecraft, generally called uplink, can be greatly sped up utilizing computers. Since SEQGEN spends a significant portion of its time sorting commands in time order, a sort algorithm is necessary for the best possible speed UP. 11. Parallel Sort The sort works as follows. Each node of the hypercube starts out containing a sublist of commands in which there are time fields to be sorted. Each sublist can be of any arbw size. The algorithm to be described is a generalization of shell merge. [3] The algorithm's prerequisite is that the sublist on each node is sorted; therefore, the sequential version of quick sort is applied to each sublist independently using the median-of-three method to select a pivot point where partition starts. Once each sublist is sorted independently by quick sort as node 0 node 1 node 3 node 2
Cited by 7
M. T. Noga · BIT Numerical Mathematics · 1987
Cited by 4
Tianzhen Wang, Li Zhou, Qin Xiozhen · 2002
We present the standardized parallel sorting algorithm. Instead of the most basic CCI (compare and conditional interchange) operation in traditional sorting algorithms, this algorithm compares sorting data with a standard value sequence simultaneously and synchronously on an SIMD array processor. The algorithm possesses three significant advantages. First, the running time T is independent of the problem size, T=0(1). The second attractive feature of the algorithm is that it is not necessary to build a communication network between PEs. Finally, no bottleneck occurs in output. We have implemented the algorithm in an SIMD array processor that is designed by our research group. The experiment verifies all the theoretical predictions. For these merits the algorithm is of significance in both theory and practice.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 0