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.