TRANSFORMATION OF SORTING NETWORKS FOR DIFFERENT DEGREES OF PARALLELISM

Abstract

Some well-known sorting algorithms may be more efficient than others according to any of the main criteria: the number of performed operations, the execution time of elementary operations, the used memory capacity, the parallelism degree, the functional regularity of connections in the information graph of algorithm, etc. At the same time, it is possible to choose such sorting algorithm, which will take up a minimum hardware resource after performance reducing operation of computational structure. The choice of a particular algorithm directly depends on it parallelization degree, the specified by the data processing time, the coefficient of reduction and latency of the computational structure and the number and bit depth of the sorted elements. Sorting algorithms are information-equivalent, since they perform the same mathematical function. However, each of algorithms is considered as an autonomous and independent approach to solving the data ordering problem. It is known that the same sorting network correspond to the "bubble", "inserts" and "selection" sorting algorithms. However, the transition from one algorithm to another has not yet been described in the form of mathematical transformations. It can be argued that the mathematical tools for describing various sorting algorithms and sorting networks is not fully formalized for today. Because of this, there is no methodological basis for the transition from one algorithm to another. Another method to describe the algorithm for solving the problem is its representation in the form of an information graph. In it, the performed operations are vertices that are combined by arcs reflecting the information dependence between operations. Transformation of the information graph can lead to obtaining other information and equivalent algorithms. The advantage of similar approach for the algorithm description of is the comparative simplicity of the used conceptual tools. In this paper, the transformation rules of sorting networks are considered, on the basis of which the transition from one network to another is performed. Each of the resulting sorting networks can be effective at different parallelization coefficients and data processing rates, on which the performance reduction coefficient of the implemented computational structure directly depends. Automation of the proposed transformation methods can allow the use the different sorting algorithms, derived from a single problem description in the form of an information graph, and depending on the specified data processing rate.