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.
In the paper we review software tools for translation of sequential C-programs into scalable parallel-pipeline programs written in the COLAMO language, used for programming of reconfigurable computer systems. In contrast to existing tools of high-level synthesis, the translation result is not an IP-core of a task fragment, but a complex task solution for multichip reconfigurable computer systems with automatic synchronization of data and control signals. We analysed the main translation steps of a sequential C-program such as transformation into an information graph, analysis of data dependencies and selection of functional subgraphs, transformation into a scalable resource-independent parallel-pipeline form, and scaling a COLAMO-program for a specified multichip reconfigurable computer system. A program is scaled with the help of performance reduction methods, applied to a completely parallel form of a task (an information graph), adapted to the architecture of a reconfigurable computer system. We developed several rules,significantly reducing the number of transformation steps of task scaling, and providing a continuous flow of data processing in the functional subgraphs of the task. The developed software tools for translation of C-programs into FPGA configuration files significantly decrease the synthesis time of a task computing structure for multichip RCSs and the total task solution time.
