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

All sorting algorithms are information-equivalent. Therefore, the choice of the most effective algorithmusually depends on its operation velocity and the capacity of used memory. At parallel, hardwareimplementation, the efficiency of sorting algorithms is also affected by the degree of utilization ofhardware resources; the latency of the resulting computing structure; the number and digit capacity ofthe sorted elements. The problem of sorting or ordering data is not formalized in the form of mathema ticaltransformations. 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 atdescribing the problem in the form of an information graph, the vertices of which represent the elementaryperformed operations, and the arcs – the information dependencies between them. Having a set ofelementary transformations, it is possible to influence the functional regularity of the informationgraph connections, the latency of the computing structure, the coefficient of parallelism, etc. The informationgraph 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 isshown and justified; the methods to optimize the number of operations and change the order of theirsequence are given. The main result of the paper is the method for converting sorting networks into anodd-even Butcher mergesort. A program has been developed that automatically performs the transformationof sorting networks and allows to adjust the information graph topology to the most effectiveform, 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 theoptimal parallel pipeline program under specified constraints, which will significantly accelerate theprocess of their development.