Peter Sanders · KITopen · 2011
The talk describes algorithm engineering (AE) as a methodology for algorithmic research where design, analysis, implementation and experimental evaluation of algorithms form a feedback cycle driving the development of efficient algorithms. Additional important components of the methodology include realistic models, algorithm libraries, and collections of realistic benchmark instances. We use one main example throughout this talk: sorting huge data sets using many multi-core processors and disks. The described system broke records for the GraySort and MinuteSort sorting benchmarks and helped with the record for the Joule Sort benchmark.
Cited by 0Open access
Philippos Papaphilippou · Chips · 2026
Sorting networks are of prime importance as circuits, with applications in sorting small data chunks, big data analytics, permuting packets, and system interconnects. Finding optimal sorting networks is a highly complex problem, and knowledge on optimal sorting networks is limited. When optimising the network depth or the number of comparators, one of the most expensive tasks is considered to be verification, that is, to verify that the candidate compare-and-swap network actually sorts the data. This grows exponentially with the size of the sorting network. However, FPGAs allow vast amounts of internal parallelism, and our presented work exploits this flexibility using dataflow techniques to achieve unparalleled amounts of speedup for sorting network verification. This work can be used in a modular way to accelerate the search for optimal sorting networks with a high number of inputs, as well for similar verification problems.
Cited by 0Open access
Richard P. Brent, Andrew Tridgell · 1993
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 sorting algorithm, then uses a two-phase parallel merge. The algorithm is comparisonbased and requires additional storage of order 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. Key words and phrases. Batcher's merge-exchange sort, distributed memory, Fujitsu AP1000, parallel sorting, sorting, Sparc, Thinking Machines CM5. 1: Introduction and Aims There is a large literature on parallel sorting -- see, for example, [1, 2, 9] and the references given there. Many of these papers have dealt with the problem from a theoretical point of view, neglecting issues which are ...
Cited by 0
William Gasarch Evan, Lance Fortnow, William Gasarch et al. · 2007
this paper only work if n is \\large." The algorithm in Theorem 4.15 needs much larger n than usual. 11 5 A Randomized Algorithm
Cited by 0
Xiaojun Guan, Michael A. Langston · IEEE Transactions on Computers · 1991
The authors present a parallel merging algorithm that, on an exclusive-read exclusive-write (EREW) parallel random-access machine (PRAM) with k processors merges two sorted lists of total length n in O(n/k+log n) time and constant extra space per processor, and hence is time-space optimal for any value of k<or=n/(log n). The authors also describe how this gives rise to a stable version of the parallel merging algorithm that is similarly time-space optimal on an EREW PRAM. The authors observe that this technique for achieving stability incurs two penalties: a slightly more complicated algorithm and somewhat larger constants of proportionality. These two parallel merges naturally lead to time-space optimal parallel sorting algorithms. Extensions to sorting and open topics for future research are discussed.<<ETX>>
Cited by 2
James G. H. Whiting, Richard Mayne, Andrew Adamatzky · Biomimetics · 2018
The aquatic unicellular organism <i>Paramecium caudatum</i> uses cilia to swim around its environment and to graze on food particles and bacteria. <i>Paramecia</i> use waves of ciliary beating for locomotion, intake of food particles and sensing. There is some evidence that <i>Paramecia</i> pre-sort food particles by discarding larger particles, but intake the particles matching their mouth cavity. Most prior attempts to mimic cilia-based manipulation merely mimicked the overall action rather than the beating of cilia. The majority of massive-parallel actuators are controlled by a central computer; however, a distributed control would be far more true-to-life. We propose and test a distributed parallel cilia platform where each actuating unit is autonomous, yet exchanging information with its closest neighboring units. The units are arranged in a hexagonal array. Each unit is a tileable circuit board, with a microprocessor, color-based object sensor and servo-actuated biomimetic cilia actuator. Localized synchronous communication between cilia allowed for the emergence of coordinated action, moving different colored objects together. The coordinated beating action was capable of moving objects up to 4 cm/s at its highest beating frequency; however, objects were moved at a speed proportional to the beat frequency. Using the local communication, we were able to detect the shape of objects and rotating an object using edge detection was performed; however, lateral manipulation using shape information was unsuccessful.
Cited by 7Open access
Torben Hagerup, Rajeev Raman · 1993
Padded sorting requires n input keys to be output in sorted order in an array with slightly more than n locations, unused locations being filled with a special null value. We show that a deterministic CRCW PRAM with h processors can padded-sort n keys in ~(log log k)s . 2(*0g" '-lOg* '+1) time, for any k with 4 s k s n, which is close to a known lower bound of Q(log n/log k). As a consequence, we are able to improve the best previous result on deterministic sublogarithmic standard sorting. Other results include deterministic algorithms with optimal speedup for approximate prefix summation and for padded-sorting independent uniformly distributed random variables. In the first case the running time is O((log log n)4/log log log n), and in the second case the average running time is O((log log log n)4 /log(4) n).
Cited by 17Open access
Si Zheng · 2002
A simple computing model for sorting an arbitrary number of elements using a fixed-size sorting device is proposed, and a framework for designing a class of parallel sorting algorithms under this model is presented.
Cited by 2
Maria Cristina Pinotti · Institutional Research Information System (Università degli Studi di Trento) · 1998
Cited by 0
Stephan Olariu, M. Cristina Pinotti, Ieee Computer Society et al. · 2000
Cited by 2
S. Olariu, S. Zheng, Pinotti, Maria Cristina · Institutional Research Information System (Università degli Studi di Trento) · 1998
Cited by 0
David R. Helman, David A. Bader, Joseph F. JáJá · Digital Repository at the University of Maryland (University of Maryland College Park) · 1998
Previous schemes for sorting on general-purpose parallel machines have had to choose between poor load balancing and irregular communication or multiple rounds of all-to-all personalized communication. In this paper, we introduce a novel variation on sample sort which uses only two rounds of regular all-to-all personalized communication in a scheme that yields very good load balancing with virtually no overhead. This algorithm was implemented in Split-C and run on a variety of platforms, including the Thinking Machines CM-5, the IBM SP-2, and the Cray Research T3D. We ran our code using widely different benchmarks to examine the dependence of our algorithm on the input distribution. Our experimental results are consistent with the theoretical analysis and illustrate the efficiency and scalability of our algorithm across different platforms. In fact, it seems to outperform all similar algorithms known to the authors on these platforms, and its performance is invariant over the set of in...
Cited by 3Open access
Vineet Kumar Singh, Vipan Kumar, Gul Agha et al. · International Journal of Parallel Programming · 1991
Cited by 9
Ya.E. Romm, D. A. Chabanyuk · Advanced Engineering Research (Rostov-on-Don) · 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
Keqiang Qiu, Henk Meijer, Selim G. Akl · Lecture notes in computer science · 1991
Cited by 28
Т. Б. Мартынюк, B. I. Krukivskyi · Cybernetics and Systems Analysis · 2024
Cited by 0
Tom Leighton · IEEE Transactions on Computers · 1985
In this paper, we prove tight upper and lower bounds on the number of processors, information transfer, wire area, and time needed to sort N numbers in a bounded-degree fixed-connection network. Our most important new results are: 1) the construction of an N-node degree-3 network capable of sorting N numbers in O(log N) word steps; 2) a proof that any network capable of sorting N (7 log N)-bit numbers in T bit steps requires area A where AT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> = Ω(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> N); and 3) the construction of a ``small-constant-factor'' bounded-degree network that sorts N Θ(log N)-bit numbers in T = Θ(log N) bit steps with A = Θ(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) area.
Cited by 372
Michael Süß, Claudia Leopold · 2008
Some algorithmic patterns are difficult to express in OpenMP. In this paper, we use a simple sorting algorithm to illustrate problems with recursion and the avoidance of busy waiting. We compare several solution approaches with respect to programming expense and performance: stacks, nesting and a workqueue (for recursion), as well as condition variables and the sched yield–function (for busy waiting). Enhancements of the OpenMP–specification are suggested where we saw the need. Performance measurements are included to backup our claims. 1.
Cited by 0
Linh Ha, Jens Krüger, Cláudio T. Silva · 2009
Efficient sorting is a key requirement for many computer science algorithms. Acceleration of existing techniques as well as developing new sorting approaches is crucial for many realtime graphics scenarios, database systems, and numerical simulations to name just a few. It is one of the most fundamental operations to organize and filter the ever growing massive amounts of data gathered on a daily basis. While optimal sorting models for serial execution on a single processor exist, efficient parallel sorting remains a challenge. In this paper we present a hardware-optimized parallel implementation of the radix sort algorithm that results in a significant speed up over existing sorting implementations. We outperform all known GPU based sorting systems by about a factor of two and eliminate restrictions on the sorting key space. This makes our algorithm not only the fastest, but also the first general GPU sorting solution.
Cited by 0
Jun Xie, Hui Deng, Qi Yang et al. · Applied Mechanics and Materials · 2014
The kinematics model of the robot was established, and its structural parameters were studied. Based on coordinate transformation, the inverse solution of the robot was obtained. Its workspace was solved by MATLAB program. Three-dimensional diagram and projection drawing on XY plane of workspace were obtained. In addition, the sorting range various with the different value of Z was studied and obtained. Finally, on the premise of meeting working range of the robot, using the minimum mass of the moving parts as optimization objective, the structural parameters of the sorting robot were optimized using the search method. Simulation results show that the optimized robot can achieve the minimum weight of moving parts and meet the preset sorting range. It is also ensured the sorting flexibility.
Cited by 0