CONVERTING SOME TYPES OF SEQUENTIAL INFORMATION GRAPHS INTO PARALLEL-PIPELINE FORM

Abstract

Many digital signal processing tasks can be represented in the form of information
graphs. Reconfigurable computing systems based on FPGAs can have a structure that directly
corresponds to the information graph of the problem being solved. The construction of the task
graph and the subsequent creation of the computational structure can take a significant amount
of time when performed manually. In this regard, it becomes necessary to create algorithms for
transforming information graphs that can be performed automatically. The article proposes
algorithms for transforming homogeneous graphs containing associative operations and mixed
graphs containing two types of operations, one of which is distributive with respect to the other.
Transformations of graphs of the first type (consisting of operations of the same type) are reduced
to the transition from a sequential form of a graph to a pyramidal form to speed up the
execution of all graph operations. If the available amount of equipment is not enough to impl ement
all operations of the graph, a transformation is applied that splits the original graph into
isomorphic subgraphs. The size of the subgraph depends on the available computing resources.
In this case, the computational structure will correspond to such a subgraph. Transformations
of graphs of the second type (consisting of operations of two types, some of which are distributive
with respect to others) are reduced to dividing the graph into subgraphs containing operations
of the same type, connected in a special way. After that, these subgraphs can be converted
into a pyramid shape to speed up the execution of all graph operations. In this case, the number
of vertices with distributive operations can increase significantly, and therefore it may be necessary
to reduce their number. It follows that when transforming graphs of the second type, it is
necessary to choose a specific form to which the graph will be reduced, based on the ratio of its
size and the available computing resource. Thus, the proposed algorithms for transforming
information graphs of various types can be effectively used in the development of computational
structures based on FPGAs