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

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.