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.