ПРЕОБРАЗОВАНИЕ НЕКОТОРЫХ ВИДОВ ПОСЛЕДОВАТЕЛЬНЫХ ИНФОРМАЦИОННЫХ ГРАФОВ В ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНУЮ ФОРМУ
Аннотация
Многие задачи цифровой обработки сигналов могут быть представлены в виде информа-
ционных графов. Реконфигурируемые вычислительные системы, построенные на основе ПЛИС,
могут иметь структуру, непосредственно соответствующую информационному графу ре-
шаемой задачи. Построение графа задачи и последующее создание вычислительной структуры
может занимать значительное время при выполнении их вручную. В связи с этим возникает
необходимость создания алгоритмов преобразования информационных графов, которые могут
выполняться автоматически. В статье предложены алгоритмы преобразования однородных
графов, содержащих ассоциативные операции, и смешанных графов, содержащих два типа
операций, один из которых является дистрибутивным по отношению к другому. Преобразова-
ния графов первого типа (состоящих из операций одного типа) сводятся к переходу от после-
довательной формы графа к пирамидальной для ускорения выполнения всех операций графа.
В случае если имеющегося количества оборудования недостаточно для реализации всех опера-
ций графа, применяется преобразование, разбивающее исходный граф на изоморфные подгра-
фы. Размер подграфа зависит от имеющегося вычислительного ресурса. В этом случае вычис-
лительная структура будет соответствовать такому подграфу. Преобразования графов вто-
рого типа (состоящих из операций двух типов, одни из которых являются дистрибутивными
по отношению к другим) сводятся к разделению графа на подграфы, содержащие операции
одного типа, соединённые особым образом. После этого эти подграфы могут быть преобра-
зованы в пирамидальную форму для ускорения выполнения всех операций графа. При этом
количество вершин с дистрибутивными операциями может значительно возрасти, в связи с
чем может потребоваться сокращение их числа. Отсюда следует, что при преобразовании
графов второго типа не обходимо выбирать конкретную форму, к которой будет приведён
граф, исходя из соотношения его размера и имеющегося вычислительного ресурса. Таким
образом, предложенные алгоритмы преобразования информационных графов различных типов
могут быть эффективно использованы при разработке вычислительных структур, основанных
на ПЛИС.
Литература
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.
