ПРЕДСТАВЛЕНИЕ ГРАФОВ С АССОЦИАТИВНЫМИ ОПЕРАЦИЯМИ НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ SET@L

  • И.И. Левин Южный Федеральный Университет
  • И. В. Писаренко Южный Федеральный Университет
  • Д.В. Михайлов Южный Федеральный Университет
  • А. И. Дордопуло Общество с ограниченной ответственностью «НИЦ су- пер-ЭВМ и нейрокомпьютеров»
Ключевые слова: Информационные графы с ассоциативными операциями, ресурсонезависимое программирование, редукция производительности, язык программирования Set@l, признаки «голова/хвост» и «разбиение пополам»

Аннотация

Как правило, информационный граф с ассоциативными операциями реализуется в
виде последовательной («голова/хвост») или параллельной («разбиение пополам») топ о-
логии, причем обе структуры содержат одинаковое число операционных вершин. Реду к-
ционные преобразования графов с представленными топологиями при недостатке в ы-
числительного ресурса не обеспечивают создание эффективной ресурсонезависимой пр о-
граммы: вариант «разбиение пополам» характеризуется нерегулярной межитерацион-
ной коммутацией, а структура «голова/хвост» – увеличенной скважностью данных при
редукции. В данной статье предлагается преобразовать топологию графа с ассоци а-
тивными операциями в один из комбинированных вариантов с последовательными и па-
раллельными фрагментами вычислений, синтезированный в соответствии с заданным
вычислительным ресурсом. Это позволяет повысить удельную производительность в ы-
числений при редукции. Модифицированная топология включает изоморфные подграфы с
топологией «разбиение пополам», содержащие максимальное число аппаратно реализу е-
мых операционных вершин, а обработка промежуточных данных осуществляется по
принципу «голова/хвост». Вычислительная структура для рассмотренной топологии
имеет минимальную латентность и состоит из одного базового подграфа и одной вер-
шины, в которую редуцируется блок обработки промежуточных данных с топологией
«голова/хвост». Разработан алгоритм, позволяющий в зависимости от доступного а п-
паратного ресурса перейти от базового последовательного варианта реализации к раз-
личным комбинированным топологиям вплоть до предельного случая топологии «разби е-
ние пополам». Поскольку традиционные методы параллельного программирования могут
описать множество топологий только в виде набора отдельных подпрограмм, для соз-
дания ресурсонезависимого описания графов с ассоциативными операциями предлагае т-
ся использовать язык архитектурно-независимого программирования Set@l. Принципы
построения топологий «голова/хвост» и «разбиение пополам» описаны в виде признаковметода обработки множеств на языке Set@l, а ресурсонезависимая программа оперирует
этими типами и типами параллелизма для модификации топологии графа и последующей
редукции производительности в соответствующих аспектах программы.

Литература

1. Knut D.E. Iskusstvo programmirovaniya [The Art of Computer Programming]. Vol. 4,
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.
Опубликован
2020-10-11
Выпуск
Раздел
РАЗДЕЛ II. АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ