CONVERTING SOME TYPES OF SEQUENTIAL INFORMATION GRAPHS INTO PARALLEL-PIPELINE FORM
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
References
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.
2. Levin I.I., Dordopulo A.I., Pisarenko I.V., Mikhaylov D.V. Predstavlenie grafov s
assotsiativnymi operatsiyami na yazyke programmirovaniya SET@L [Description of graphs
with associative operations in SET@L programming language], Izvestiya YuFU. Tekhnicheskie
nauki [Izvestiya SFedU. Engineering Sciences], 2020, No. 3, pp. 98-111.
3. Knut D.E. Iskusstvo programmirovaniya. T.4, A. Kombinatornye algoritmy [The Art of Computer
Programming. Vol. 4, A. Combinatorial Algorithms]. Part 1: transl. from engl. Moscow:
OOO «I. D. Vil'yams», 2013, 960 p.
4. Novikov F. Diskretnaya matematika [Discrete Mathematics]. 3rd ed. Saint Petersburg: Piter,
2019, 496 p.
5. Ivanov A.I. Metody i sredstva sozdaniya effektivnogo parallel'no-konveyernogo programmnogo
obespecheniya vychislitel'nykh sistem, postroennykh na osnove PLIS-tekhnologii: diss. … kand.
tekhn. nauk, po spetsial'nosti: 05.13.11 “Matematicheskoe i programmnoe obespechenie
vychislitel'nykh mashin, kompleksov i komp'yuternykh setey” [Methods and tools for creating effective
parallel pipeline software for computing systems based on FPGA technology: diss. …
cand. of eng. sc., specialty: 05.13.11 “Mathematical and software support for computers, complexes
and computer networks”], scientific director: Corresponding Member of RAS, d.t.s., proff.
Kalyaev I.A., dis. council TSREU D 212.259.05, 2005, 182 p.
6. Zadacha summirovaniya elementov massiva [Problem of Array Elements’ Summation], 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).
7. 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.
8. Tessier R., Pocek K., DeHon A. Reconfigurable Computing Architectures, Proceedings of the
IEEE, 2015, Vol. 103, No. 3, pp. 332-354.
9. Mittal S., Vetter J. A survey of CPU-GPU heterogeneous computing techniques, ACM Computing
Surveys, 2015, Vol. 47, Art. 69.
10. Waidyasooriya H.M., Hariyama M., Uchiyama K. Design of FPGA-Based Computing Systems
with OpenCL. Cham: Springer, 2018, 126 p.
11. Reinhard Diestel. Graph Theory. Springer-Verlag, Heidelberg, Graduate Texts in Mathematics,
2016, Vol. 173, 447 p. ISBN 978-3-662-53621-6.
12. Edward A. Bender. Lists, Decisions and Graphs. With an Introduction to Probability. S. Gill
Williamson, 2010, 251 p.
13. Trudeau, Richard J. Introduction to graph theory. Dover Publications, Inc. New York, 1993, 224 p.
14. Starchenko A.V., Bertsun V.N. Metody parallel'nykh vychisleniy [Methods of Parallel Computing].
Tomsk: Izd-vo Tom. un-ta, 2013, 223 p.
15. 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.
16. Kalyaev A.V., Levin I.I. Modul'no-narashchivaemye mnogoprotsessornye sistemy so strukturnoprotsedurnoy
organizatsiey vychisleniy [Modular-Expandable Multiprocessor Systems with
Structural and Procedural Organization of Calculations]. Moscow: Yanus-K, 2003, 380 p.
17. 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.
18. Dasgupta S., Papadimitriu Kh., Vazirani U. Algoritmy [Algorithms]: transl. from engl., ed. by
A. Shenya. Moscow: MTSNMO, 2014, 320 p.
19. Kharari F. Teoriya grafov [Graph Theory]. Moscow: Mir, 1973, 300 p.
20. Kormen T.M. i dr. Chast' VI. Algoritmy dlya raboty s grafami. Algoritmy: postroenie i analiz =
Introduction to Algorithms [Part IV. Algorithms for working with graphs, Algorithms: construction
and analysis = Introduction to Algorithms]. 2nd ed. Moscow: Vil'yams, 2006, 1296 p.
