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.