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