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.