China
Africa
Explore chapters and articles related to this topic
Overview
Published in Naoaki Yamanaka, High-Performance Backbone Network Technology, 2020
Sorting networks can be used to implement ATM switches that are contention-free, so long as the arriving cells are all addressed to distinct outputs. The most popular sorting network is Batcher’s bitonic sorter [3], an example of which is illustrated in Fig. 9. In this figure, cells are indicated by the numbers whose values represent the output address for the given cell. The square boxes in the figure represent sorting elements, which propagate arriving cells to the output, based on the relative values of their output addresses; some sorting elements send cells with larger values to the upper output, others to the lower output, as indicated by the arrows in the figure. The sorting network is constructed using a double recursive construction. Some of the components of this construction are highlighted in the figure.
Timing Verification
Published in Perelroyzen Evgeni, Digital Integrated Circuits, 2018
Hardware application of the sorting algorithm is made possible by a dedicated device (sorting network), whose inputs are connected to all disordered array elements, while its outputs develop the ordered array. The hardware application of the sorting algorithm increases its speed, excluding a number of utility operations out of the sorting program, and overlapping a great number of different comparisons in time. This process uses no supplementary memory. The class of sorting algorithms under examination demands that the following condition be met (lack of memory): the sequence of comparisons of the array elements should be independent of its background. Because of that, some branches of the comparison tree need more than the otherwise necessary comparisons for the array ordering.
Big data processing with 1D-Crosspoint Arrays
Published in International Journal of Parallel, Emergent and Distributed Systems, 2023
In another direction, sorting networks [9] were introduced as an alternative to sorting algorithms. A sorting network refers to an architecture that is composed of wires and comparators that can compare their inputs and sort them, where each element in the array to be sorted can be compared with one other element at a time. The sorting network proposed by Ajtai et al. [26], which is commonly known as the AKS network has a hardware complexity of and time complexity of , which is smaller than that of 1D-Crosspoint Array by a factor of under the constant fan-in assumption. It is also faster than Valiant's parallel sorting algorithm by the same factor, when
Speeding Up Monte Carlo Computations by Parallel Processing Using a GPU for Uncertainty Evaluation in accordance with GUM Supplement 2
Published in NCSLI Measure, 2018
C. M. Tsui, Aaron Y. K. Yan, H. W. Lai
Sorting algorithms are either data-dependent, such as QuickSort, or data-independent such as those based on a sorting network. Data-independent sorting algorithms are more suitable for running on a GPU since they require much less interaction between the GPU cores. Both the bitonic sorting algorithm and the odd-even mergesort algorithm are data-independent and may be implemented by a sorting network [9]. The bitonic sorting algorithm is adopted in the new tool.
An extensible circuit-based SAT solver
Published in Journal of Experimental & Theoretical Artificial Intelligence, 2020
To compute minimum-cardinality diagnoses by SAT solving the cardinality constraint is typically enforced using sorting networks or cardinality networks (Asín, Nieuwenhuis, Oliveras, & Rodríguez-Carbonell, 2009; Batcher, 1968; Metodi et al., 2014). A sorting network is a circuit containing comparison elements that implement the merge sort algorithm to sort the given inputs lines such that at the output lines all the s appear on one side and all the s appear on the other side. The cardinality of s on input lines () can then be enforced by setting number of outputs on the s side to be and outputs on the s side to be . For example, Figure 5 shows a 4-input sorter constructed using comparison elements shown in Figure 4. To assert that exactly two inputs must be one simply needs to set the low two outputs to and high two outputs to . The cardinality networks (also called half sorting networks) are more compact versions of sorting networks optimised for cardinality constraints in that their CNF encoding requires much less number of clauses and extra variables than general sorting networks. Let and are the inputs of a 2-input half sorter and and are its outputs. Then, the CNF representation of the half 2-input sorter is given as: .