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.
References
A. Kombinatornye algoritmy [Combinatorial Algorithms]. Part 1: transl. from engl. Moacow:
OOO «I. D. Vil'yams», 2013, 960 p.
2. Novikov F. Diskretnaya matematika [Discrete Mathematics]. 3rd ed. Saint Petersburg: Piter,
2019, 496 p.
3. Karepova E.D. Osnovy mnogopotochnogo i parallel'nogo programmirovaniya [Fundamentals
of Multithreaded and Parallel Programming]. Krasnoyarsk: Sib. feder. un-t, 2016, 356 p.
4. Zadacha summirovaniya elementov massiva [Problem of Array Elements’ Summation],
Laboratorii Parallel'nykh informatsionnykh tekhnologiy NIVTS MGU [The Laboratory of Parallel
Information Technologies of the Research Computing Center of the Moscow State University].
Available at: https://parallel.ru/fpga/Summ2 (accessed 27 April 2020).
5. Starchenko A.V., Bertsun V.N. Metody parallel'nykh vychisleniy [Methods of Parallel Computing].
Tomsk: Izd-vo Tom. un-ta, 2013, 223 p.
6. Efimov S.S. Obzor metodov rasparallelivaniya algoritmov resheniya nekotorykh zadach
vychislitel'noy diskretnoy matematiki [Review of Parallelizing Methods for Algorithms Aimed
at Solution of Certain Problems of Computational Discrete Mathematics], Matematicheskie
struktury i modelirovanie [Mathematical Structures and Modeling], 2007, Issue 17, pp. 72-93.
7. Kalyaev I.A., Levin I.I., Semernikov E.A., Shmoylov V.I. Razvitie otechestvennykh
mnogokristall'nykh rekonfiguriruemykh vychislitel'nykh sistem: ot vozdushnogo k
zhidkostnomu okhlazhdeniyu [Evolution Domestic of Multichip Reconfigurable Computer
Systems: from Air to Liquid Cooling: From Air to Liquid Cooling], Tr. SPIIRAN [SPIIRAS
Proceedings], 2017, Issue 1, pp. 5-31.
8. Mittal S., Vetter J. A survey of CPU-GPU heterogeneous computing techniques, ACM Computing
Surveys, 2015, Vol. 47, Art. 69.
9. Waidyasooriya H.M., Hariyama M., Uchiyama K. Design of FPGA-Based Computing Systems
with OpenCL. Cham: Springer, 2018, 126 p.
10. Tessier R., Pocek K., DeHon A. Reconfigurable Computing Architectures, Proceedings of the
IEEE, 2015, Vol. 103, No. 3, pp. 332-354.
11. Levin I.I., Dordopulo A.I. K voprosu ob avtomaticheskom sozdanii parallel'nykh prikladnykh
programm dlya rekonfiguriruemykh vychislitel'nykh sistem [On the problem of automatic development
of parallel applications for reconfigurable computer systems], Vychislitel'nye
tekhnologii [Computational Technologies], 2020, Vol. 25, No. 1, pp. 66-81.
12. Kalyaev A.V., Levin I.I. Modul'no-narashchivaemye mnogoprotsessornye sistemy so
strukturno-protsedurnoy organizatsiey vychisleniy [Modular-Expandable Multiprocessor
Systems with Structural and Procedural Organization of Calculations]. Moscow: YAnus-K,
2003, 380 p.
13. Levin I.I., Dordopulo A.I., Gudkov V.A. i dr. Sredstva programmirovaniya rekonfiguriruemykh
i gibridnykh vychislitel'nykh sistem na osnove PLIS [Tools for Programming of Reconfigurable
and Hybrid Computer Systems Based on FPGAs], XIII Mezhdunar. konf. «Parallel'nye
vychislitel'nye tekhnologii» (PaVT-2019), korotkie stat'i i opisaniya plakatov [XIII International
Conference «Parallel computational technologies» (PCT’2019), short papers and poster
descriptions]. Chelyabinsk: Izd. tsentr YuUrGU, 2019, pp. 299-312.
14. Pisarenko I.V., Alekseev K.N., Mel'nikov A.K. Resursonezavisimoe predstavlenie
sortiruyushchikh setey na yazyke programmirovaniya Set@l [Resource-Independent Representation
of Sorting Networks in Set@l Programming Language], Vestnik komp'yuternykh i
informatsionnykh tekhnologiy [Herald of Computer and Information Technologies], 2019,
No. 11, pp. 53-60.
15. Levin I.I., Dordopulo A.I., Pisarenko I.V., Melnikov A.K. Aspect-Oriented Set@l Language for
Architecture-Independent Programming of High-Performance Computer Systems, Communications
in Computer and Information Science, 2019, Vol. 1129, pp. 517-528.
16. Levin I.I., Dordopulo A.I., Pisarenko I.V., Mel'nikov A.K. Yazyk arkhitekturno-nezavisimogo
programmirovaniya vychislitel'nykh sistem Set@l [Architecture-Independent Set@l Programming
Language for Computer Systems], Vestnik komp'yuternykh i informatsionnykh
tekhnologiy [Herald of Computer and Information Technologies], 2019, No. 3, pp. 48-56.
17. Knut D.E. Iskusstvo programmirovaniya. T. 1. Osnovnye algoritmy [The Art of Computer
Programming. Vol. 1. Fundamental Algorithms]. 3rd ed. Moscow: OOO «I.D. Vil'yams»,
2017, 720 p.
18. Dasgupta S., Papadimitriu Kh., Vazirani U. Algoritmy [Algorithms]: transl. from engl., ed. by
A. Shenya. Moscow: MTSNMO, 2014, 320 p.
19. Kovalenko A.G., Levin I.I., Mel'nikov A.K. Avtomatizatsiya postroeniya parallel'nokonveyernykh
programm dlya rekonfiguriruemykh vychislitel'nykh sistem [Automatization of
parallel-pipeline program development for reconfigurable computer systems], Vestnik
komp'yuternykh i informatsionnykh tekhnologiy [Herald of Computer and Information Technologies],
2013, No. 5, pp. 50-56.
20. Levin I.I., Dordopulo A.I., Pisarenko I.V., Melnikov A.K. Objects of Alternative Set Theory in Set@l
Programming Language, Lecture Notes in Computer Science, 2019, Vol. 11657, pp. 18-31.
