TRANSFORMATION METHODS OF COMPUTING STRUCTURE WITH FEEDBACKS FOR EFFECTIVE IMPLEMENTATION ON RECONFIGURABLE COMPUTING SYSTEMS

Abstract

At present, various computer-aided (CAD) systems are used for solving tasks on reconfigurable computing systems (RCS). In most cases, they consist of two main parts: a compiler (translator), which translates the source code of a program into a graph-like information and computing structure, and a synthesizer, which maps it on an FPGA architecture. As a rule, existing synthesizers process computing structures without any complex optimization. Therefore, the solution, generated by the synthesizer, may contain inefficient fragments, which decrease a task solution speed. The most common examples of inefficient computing structures are fragments which implement recursive expressions. The paper proposes transformation methods for recursive expressions (fragments with feedbacks), which allow automatically reduce the data supply interval when solving tasks on reconfigurable computing systems. The methods are based on information-equivalent transformations of the computing structure of the original task. For each transformation defined a set of rules that must be satisfied by the vertices of the computing structure. Applying rules allows to perform equivalent transformations not only on simple data structures such as numbers, but also on more complex structures (matrices, vectors, tensors, etc.). On the base of the simulation results, the developed transformation methods of computing structures with feedbacks allow to reduce the task solving time about 2–5 times by reducing the data supply interval. The proposed methods are implemented in a prototype of optimizing synthesizer.