МЕТОД ОРГАНИЗАЦИИ ДИСКРЕТНО-СОБЫТИЙНЫХ ВЫЧИСЛЕНИЙ ДЛЯ ОБРАБОТКИ БОЛЬШИХ РАЗРЕЖЕННЫХ НЕСТРУКТУРИРОВАННЫХ МАТРИЦ НА РВС

  • А. В. Подопригора Южный федеральный университет
Ключевые слова: Реконфигурируемые вычислительные системы, высокопроизводительные вычислительные системы, разреженная матрица, большая разреженная неструктурированная матрица, сложение разреженных матриц, дискретно-событийное моделирование, системы массового обслуживания, дискретно-событийная организация вычислений

Аннотация

С усложнением моделей исследуемых объектов и процессов в разных областях науки
и техники появляется большое количество задач, для которых необходимо применять вы-
сокопроизводительные вычислительные системы. Так, для обработки матричных массивов
используют кластерные многопроцессорные вычислительные системы с применением спе-
циальных методов, направленных на организации параллельных вычислений, и в большинст-
ве случаев производительность вычислительной системы является достаточно высокой.
Однако такая эффективность вычислений наблюдается не на всех видах матриц. Мат-
ричная структура может содержать большое количество незначимых элементов, боль-
шую размерность, и ее портрет может быть неструктурированным. Решение такого
рода матриц на кластерных МВС не позволяет получить производительность, близкую к
пиковой, поскольку методы обработки никак не учитывают такую сложную структуру
обрабатываемой матрицы, в результате чего производительность системы многократно
снижается. Разработка методов для кластерных МВС не позволяет в полной мере обеспе-
чить высокую производительность на классе задач, посвященной обработке больших раз-
реженных неструктурированных матриц. Жесткая архитектура связей процессоров не
учитывает особенности таких матриц, что приведёт к неоднородности загрузки вычис-
лительного процессора. Для обеспечения производительности, близкой к пиковой на зада-
чах обработки больших разряженных неструктурированных матриц, необходимо приме-
нять реконфигурируемые вычислительные системы, архитектура которых позволяет
адаптироваться под структуру решаемой задачи. Это позволяет организовывать конвей-
ерную обработку так, чтобы вычислительный ресурс РВС был использован только на ин-
формационно значимые операции. Помимо использования общепринятых методов струк-
турной организации высокопроизводительных вычислений для РВС, необходимо разрабо-
тать формат хранения и передачи больших разреженных неструктурированных матриц,
определить принципы построения базовых матричных макроопераций и возможность
организации составных дискретно-событийных матричных функций для решения приклад-
ных задач. В результате проведенных исследований положено начало метода, позволяюще-
го организовать вычисления, операндами которых являются большие разреженные не-
структурированные матрицы. Применение этого метода для организации вычислений
позволяет существенно повысить производительность и обеспечить повышение эффек-
тивности работы такой системы.

Литература

1. Tikhonov A.N., Samarskiy A.A. Uravneniya matematicheskoy fiziki [Equations of mathematical
physics]. Moscow: Izd-vo Moskovskogo universiteta, 1999. 6 ed., 798 p. Nauchnaya
biblioteka dissertatsiy i avtoreferatov disserCat [Dissercat Scientific Library of Dissertations
and Abstracts]. Available at: http://www.dissercat.com/content/razrabotka-i-issledovanieekonomichnykh-
algoritmov-resheniya-setochnykh-zadach-naklastere-r#ixzz5WvO2qG2e (accessed
23 November 2018).
2. Kolodziej Scott P., Mohsen Aznaveh, Matthew Bullock, Jarrett David, Davis Timothy A., Matthew
Henderson, Yifan Hu, and Read Sandstrom. The SuiteSparse Matrix Collection Website
Interface, Journal of Open Source Software 4, 35 (March 2019), pp. 1244-1248. DOI:
https://doi.org/10.21105/joss.01244 (accessed 02 December 2021).
3. Параллельные вычисления CUDA, NVIDIA Corporation, 2018. Available at:
http://www.nvidia.ru/object/cuda-parallel-computing-ru.html (accessed 14 December 2021).
4. Chungz E.S., Davisz J.D., Kestury S. An FPGA Drop-In Replacement for Universal Matrix-
Vector Multiplication. Portland: Workshop on the Intersections of Computer Architecture and
Reconfigurable Logic, 2012, pp. 1-6.
5. Yang C., Buluc A., Owens J. Design Principles for Sparse Matrix Multiplication on the GPU,
Turin: International European Conference on Parallel and Distributed Computing, 2018, pp. 12.
6. Georgopoulos L., Sobczyk A., Christofidellis D., Dolfi M., Auer C., Staar P., Bekas C. Enhancing
multi-threaded sparse matrix multiplication for knowledge graph oriented algorithms and analytics
IBM Research. Zurich Säumerstrasse 4 CH-8803 Rüschlikon Switzerland, 2019, 11 p.
7. Podoprigora A.V. Metody i sredstva obrabotki bol'shikh razrezhennykh matrits na
rekonfiguriruemoy vychislitel'noy sisteme [Methods and means of processing large sparse matrices
on a reconfigurable computing system], XVI Ezhegodnaya molodezhnaya nauchnaya
konferentsiya «YUg Rossii: vyzovy vremeni, otkrytiya, perspektivy»: Mater. konferentsii (g.
Rostov-na-Donu, 13–28 aprelya 2020 g.) [XVI Annual Youth Scientific Conference "South of
Russia: challenges of the time, discoveries, prospects": materials of the conference (Rostovon-
Don, April 13-28, 2020)]. Rostov-on-Don: Izd-vo YuNTS RAN, 2020, 168 p. ISBN 978-5-
4358-0196-5.
8. Kunchum R. On Improving Sparse Matrix-Matrix Multiplication on GPUs (Thesis). The Ohio
State University, 2017, pp. 36-42 Available at: https://etd.ohiolink.edu/!etd.send_file? accession=
osu1492694387445938&disposition=inline.
9. Sorokin D.A. Metody resheniya zadach s peremennoy intensivnost'yu potokov dannykh na
rekonfiguriruemykh vychislitel'nykh sistemakh: disc. … kand. tekhn. nauk [Methods for solving
problems with variable intensity of data flows on reconfigurable computing systems: cand.
of eng. sc. diss.]: 05.13.11 protected: 15.06.12: approved: 11.03.13. Taganrog, 2013, 168 p.
005043774.
10. Kalyaev I.A., Levin I.I., Semernikov E.A., Shmoylov V.I. Rekonfiguriruemye mul'tikonveyernye
vychislitel'nye struktury [Reconfigurable multiconveyor computing structures], under the general
ed. by I.A. Kalyaeva. 2nd ed. revised and expanded. Rostov-on-Don: Izd-vo YuNTS
RAN, 2009б 344 p.
11. Podoprigora A.V., Chekina M.D. Reshenie razrezhennykh SLAU bol'shoy i sverkhbol'shoy
razmernosti mnogosetochnym metodom na RVS [The solution of sparse SLOWS of large and
extra-large dimensions by the multigrid method on RVS], Izvestiya YuFU. Tekhnicheskie
nauki [Izvestiya SFedU. Engineering Sciences], 2018, No. 8 (202), pp. 212-221.
12. Dordopulo A.I. Kalyaev I.A., Levin I.I., Semernikov E.A. Semeystvo mnogoprotsessornykh
vychislitel'nykh sistem s dinamicheski perestraivaemoy arkhitekturoy [A family of multiprocessor
computing systems with dynamically tunable architecture], Mnogoprotsessornye
vychislitel'nye i upravlyayushchie sistemy: Mater. nauchno-tekhnicheskoy konferentsii [Multiprocessor
computing and control systems: Proceedings of the scientific and technical conference].
Taganrog, 2007, pp. 11-17.
13. Kalyaev I.A., Levin I.I., Semernikov E.A., Dordopulo A.I. Rekonfiguriruemye vychislitel'nye
sistemy na osnove PLIS semeystva VIRTEX-6 [Reconfigurable computing systems based on
FPGAs of the VIRTEX-6 family], Parallel'nye vychislitel'nye tekhnologii (PAVT’2011):
Tr. mezhdunarodnoy nauchnoy konferentsii [Parallel computing technologies (PAVT'2011):
Proceedings of the International Scientific Conference], 2011, pp. 203-211.
14. Guzik V.F., Kalyaev I.A., Levin I.I. Rekonfiguriruemye vychislitel'nye sistemy [Reconfigurable
computing systems], ed. by I.A. Kalyaeva. Taganrog: Izd-vo YuFU, 2016, 472 p.
15. Kalyaev A.V., Levin I.I. Modul'no-narashchivaemye mnogoprotsessornye sistemy so
strukturno-protsedurnoy organizatsiey vychisleniy [Modular-stackable multiprocessor systems
with structural and procedural organization of computing]. Moscow: Yanus-K, 2003, 380 p.
16. Pelipets A.V. Metody i sredstva resheniya zadach lineynoy algebry na vysokoproizvoditel'nykh
rekonfiguriruemykh vychislitel'nykh sistemakh: diss. … kand. tekhn. nauk [Methods and
means of solving linear algebra problems on high-performance reconfigurable computing systems:
cand. of eng. sc. diss.]. Taganrog, 2016, 199 p.
17. Podoprigora A.V. Upravlenie protsessom obrabotki razrezhennykh matrits v diskretnosobytiynykh
matrichnykh operatsiyakh [Managing the process of processing sparse matrices in
discrete-event matrix operations], XIV Vserossiyskaya mul'tikonferentsiya po problemam
upravleniya (MKPU-2021): Mater. XIV mul'tikonferentsii (Divnomorskoe, Gelendzhik, 27
sentyabrya – 2 oktyabrya 2021 g.) [XIV All-Russian Multi-conference on Management Problems
(MCPU-2021): Materials of the XIV multi-conference (Divnomorskoye, Gelendzhik,
September 27 - October 2, 2021)]: In 4 vol. Vol. 2, Editorial board: I.A. Kalyaev, V.G.
Peshekhonov i dr. Rostov-on-Don; Taganrog: Izd-vo YuFU, 2021, pp. 276-278. ISBN 978-5-
9275-3846-1.
18. Kleynrok L. Teoriya massovogo obsluzhivaniya [Theory of queuing]. Moscow: Mashinostroenie,
1979, 432 p.
19. Podoprigora A.V., Sorokin D.A. Upravlenie potokami dannykh pri reshenii bol'shoy
razrezhennoy slau mnogosetochnym metodom na rekonfiguriruemykh vychislitel'nykh
sistemakh [Managing data flows when solving a large sparse SLA by a multigrid method on
reconfigurable computing systems], XII mul'tikonferentsiya po problemam upravleniya
(MKPU-2019): Mater. XII mul'tikonferentsii (Divnomorskoe, Gelendzhik, 23–28 sentyabrya
2019 g.) [XII Multi-conference on Management Problems (MCPU-2019): Materials of the XII
multi-conference (Divnomorskoye, Gelendzhik, September 23-28, 2019)]: In 4 vol. Vol. 3, Editorial
board: I.A. Kalyaev, V.G. Peshekhonov i dr. Rostov-on-Don, Taganrog: Izd-vo YuFU,
2019, pp. 120-122. ISBN 978-5-9275-3188-2.
20. Konnov A.L., Ushakov Yu.A. Metody rascheta pokazateley proizvoditel'nosti setey EVM s
neodnorodnym trafikom [Methods for calculating performance indicators of computer networks
with heterogeneous traffic]. Orenburg: OGU, 2013, pp. 10-16.
Опубликован
2022-03-02
Выпуск
Раздел
РАЗДЕЛ III. ОБРАБОТКА ИНФОРМАЦИИ В РАСПРЕДЕЛЕННЫХ, РЕКОНФИГУРИРУЕМЫХ И НЕЙРОСЕТЕ