TRANSFORMATION OF THE SIMPLEST SORTING NETWORKS TO AN ODD-EVEN BUTCHER NETWORK

Abstract

All sorting algorithms are information-equivalent. Therefore, the choice of the most effective algorithm
usually depends on its operation velocity and the capacity of used memory. At parallel, hardware
implementation, the efficiency of sorting algorithms is also affected by the degree of utilization of
hardware resources; the latency of the resulting computing structure; the number and digit capacity of
the sorted elements. The problem of sorting or ordering data is not formalized in the form of mathema tical
transformations. Therefore, each of the known algorithms for solving it is considered an atomic,
independent unit. The transition from one algorithm for solving the problem to another is possible at
describing the problem in the form of an information graph, the vertices of which represent the elementary
performed operations, and the arcs – the information dependencies between them. Having a set of
elementary transformations, it is possible to influence the functional regularity of the information
graph connections, the latency of the computing structure, the coefficient of parallelism, etc. The information
graph of the “bubble” sorting problem is a simple sorting network, developed on the “head -
tail” principle of combining steps. In this paper, the functional redundancy of such sorting networks is
shown and justified; the methods to optimize the number of operations and change the order of their
sequence are given. The main result of the paper is the method for converting sorting networks into an
odd-even Butcher mergesort. A program has been developed that automatically performs the transformation
of sorting networks and allows to adjust the information graph topology to the most effective
form, depending on the resulting degree of parallelism of the computing structure. Summarizing the obtained results, note that the automated reduction of known algorithms to “fast” ones can ensure the
optimal parallel pipeline program under specified constraints, which will significantly accelerate the
process of their development.