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.