Search

Search Results

• DESCRIPTION OF GRAPHS WITH ASSOCIATIVE OPERATIONS IN SET@L PROGRAMMING LANGUAGE

  I. I. Levin , I. V. Pisarenko, D. V. Mikhailov , A. I. Dordopulo

  2020-10-11

  Abstract ▼

  Usually, an information graph with associative operations has a sequential (“head/tail”) or
  parallel (“half-splitting”) topology with invariable quantity of operational vertices. If computational
  resource is insufficient for the implementation of all vertices, the reduction transformations
  of graphs with basic topologies do not allow for the creation of an efficient resource-independent
  program. In fact, the “half-splitting” variant is characterized by irregular connections between
  iterations, and the “head/tail” structure has an increased data duty cycle in the reduced form.
  In this paper, we propose to transform the topology of a graph with associative operations into a
  combined variant with sequential and parallel fragments of calculations. The resultant combined
  topology depends on computational resource of a parallel computer system, and such transformation
  provides the improvement of specific performance for the reduced computing structure.
  The considered topology contains isomorphic subgraphs with the “half-splitting” topology, which
  include the maximal number of hardwarily implemented operational vertices, but the processing of
  intermediate data is performed using the “head/tail” principle. The computing structure for the
  combined topology has minimal latency and includes one basic subgraph and one vertex with
  feedback. This vertex is obtained as a result of the “head/tail” block reduction. We develop an
  algorithm for the conversion of the initial sequential graph to various combined topologies or to
  the limiting case of the “half-splitting” topology with regard to available hardware resource.
  Within traditional methods of parallel programming, it is possible to describe the variety of topologies
  only as a set of separated subprograms. To create an efficient resource-independent program,
  we propose the application of the Set@l programming language. We describe the
  “head/tail” and “half-splitting” principles as the attributes of set processing methods in Set@l.
  Resource-independent program uses these types and parallelism attributes for the modification of
  topology and further reduction of performance in the corresponding aspects.

• CONVERSION OF THE SEQUENTIAL INFORMATION GRAPH OF THE THOMAS ALGORITHM INTO A PARALLEL FORM

  D. V. Mikhailov

  177-188

  2021-10-05

  Abstract ▼

  Many computational tasks can be represented in the form of a sequential information graph. In the general case, such an information graph cannot be reduced to a parallel form in order to speed up the execution of its operations. But if the vertices of this graph have the properties of associativity, distributivity, etc., such a graph can be transformed into a parallel-pipeline form. These transformations can be performed not only on graphs containing elementary operations - addition, multiplication, logical AND, etc. - but also over graphs containing macro operations. One example of such graphs is the information graph for solving SLAEs by the sweep method (Thomas's method). The article considers a solution for tridiagonal linear systems. The infor-mation graph of the sweep method consists of two parts: the forward move, in which the transition from the three-diagonal form to the two-diagonal form is performed, and the reverse move, in which the values of the variables are directly calculated. Despite the fact that the operations that make up the basic macro-operation of the sweep method have the property of associativity, a sim-ple transformation of the graph to a pyramidal form will not give the desired result. It is necessary to transform the basic macro operations in a special way and change what data is received on them. After that, it will be possible to bring the graph to a pyramidal form. For the reverse move, a similar transformation of the graph and its constituent base subgraphs is applied. Since in order to start computations in the reverse run, we need to complete the computations of the forward run, we should switch from two specialized types of computational blocks to one universal one, and build a universal computational structure on its basis.

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

  D.V. Mikhailov

  2021-02-25

  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