МЕТОД РАСПАРАЛЛЕЛИВАНИЯ ПО БАЗОВЫМ МАКРООПЕРАЦИЯМ ДЛЯ ОБРАБОТКИ БОЛЬШИХ РАЗРЕЖЕННЫХ НЕСТРУКТУРИРОВАННЫХ МАТРИЦ НА РВС
Ключевые слова:
Большие разреженные неструктурированные матрицы, БРН-матрицы, реконфигу- рируемые вычислительные системы, ПЛИС-технологии, операции над разреженными матрицами, сложение разреженных матриц, умножение разреженных матриц
Аннотация
Анализ методов и средств обработки больших разреженных неструктурированных
матриц кластерными вычислительными системами с традиционной архитектурой пока-
зал, что для большинства задач обработки матриц с числом строк порядка 105 произво-
дительность снижается в 5-7 раз по сравнению с пиковой производительностью, при этом
пиковая производительность вычислительных систем, главным образом, оценивается
тестом LINPAC, который предполагает выполнение матричных операций. Основной целью
работы является повышение эффективности обработки больших разреженных неструк-
турированных матриц, для чего целесообразно использовать реконфигурируемые вычисли-
тельные системы на основе ПЛИС как основной тип вычислительных средств. Для эф-
фективной обработки больших разреженных неструктурированных матриц на реконфигу-
рируемых вычислительных системах используется ряд ранее описанных в работах методов
и подходов, такие как структурная организация вычислений, формат представления боль-
ших разреженных неструктурированных матриц «ряд строк», парадигма дискретно-
событийной организации потоков данных, метод распараллеливание по итерациям.
В статье рассматривается метод распараллеливания по базовым макрооперациям для
решения задачи обработки больших разреженных неструктурированных матриц на РВС,
который предполагает получение постоянной эффективности вычислений независимо от
портрета обрабатываемых больших разреженных неструктурированных матриц. Исполь-
зование для реконфигурируемых вычислительных систем разработанных методов обра-
ботки больших разреженных неструктурированных матриц позволяют обеспечивать эф-
фективность вычислений на уровне 50%, что в несколько раз превосходит эффективность
традиционных вычислительных систем.
Литература
1. Kolodziej S.P., Aznaveh M., Bullock M., David J., Davis T.A., Henderson M., Hu Y., Sandstrom R.
The SuiteSparse Matrix Collection Website Interface, Journal of Open Source Software, March
2019, Vol. 4, No. 35, pp. 1244-1248. DOI: https://doi.org/10.21105/joss.01244 (accessed 02
October 2022).
2. 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.
3. 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.
4. Pelipets A.V. Metody i sredstva resheniya zadach lineynoy algebry na vysokoproizvoditel'nykh
rekonfiguriruemykh vychislitel'nykh sistemakh: disc. … 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.
5. 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
editorship of I.A. Kalyaev. 2nd ed. Rostov-on-Don: Izd-vo YuNTS RAN, 2009, 344 p.
6. Podoprigora A.V. Metod organizatsii diskretno-sobytiynykh vychisleniy dlya obrabotki bol'shikh
razrezhennykh nestrukturirovannykh matrits na RVS [A method for organizing discrete-event
computing for processing large sparse unstructured matrices on RVS], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2021, No. 7, pp. 189-197. DOI:
10.18522/2311-3103-2021-7-189-197.
7. Podoprigora A.V. Metody rasparallelivaniya vychisleniy dlya obrabotki bol'shikh
razrezhennykh nestrukturirovannykh matrits na RVS [Methods of parallelization of calculations
for processing large sparse unstructured matrices on RVS], XVIII Ezhegodnaya
molodezhnaya nauchnaya konferentsiya «Nauka YUga Rossii: dostizheniya i perspektivy»:
Mater. konferentsii (g. Rostov-na-Donu, 18–29 aprelya 2022 g.) [XVIII Annual Youth Scientific
Conference "Science of the South of Russia: achievements and prospects": Materials of
the conference (Rostov-on-Don, Rostov–on-Don, April 18-29, 2022)]. Rostov-on-Don: Izd-vo
YuNTS RAN, 2022, pp. 262. ISBN 978-5-4358-0233-7.
8. Sorokin D.A. Metody resheniya zadach s peremennoy intensivnost'yu potokov dannykh na
rekonfiguriruemykh vychislitel'nykh sistemakh: diss. … 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.
9. Podoprigora A.V. Upravlenie protsessom obrabotki razrezhennykh matrits v diskretno-sobytiynykh
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): Proceedings of
the XIV multi-conference (Divnomorskoe, Gelendzhik, September 27 – October 2, 2021)]: in 4 vol.
Vol. 2, editorial board: I.A. Kalyaev, V.G. Peshekhonov and others. Rostov-on-Don; Taganrog: Izdvo
YuFU, 2021., pp. 276-278. ISBN 978-5-9275-3846-1.
10. Kleynrok L. Teoriya massovogo obsluzhivaniya [Theory of queuing]. Moscow: Mashinostroenie,
1979, 432 p.
11. 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.
12. Tikhonov A.N., Samarskiy A.A. Uravneniya matematicheskoy fiziki [Equations of mathematical
physics]. Moscow: Izd-vo Moskovskogo universiteta, 1999. 6th ed., 798 p. Available at:
https://elar.urfu.ru/bitstream/10995/42951/1/978-5-321-02475-1_2016.pdf (accessed 15 October
2022).
13. Podoprigora A.V. Ob"edinenie bazovykh BRN-matrichnykh makrooperatsiy [Combining basic
BRN-matrix macro operations], Mnogoprotsessornye vychislitel'nye i upravlyayushchie
sistemy: Mater. Vserossiyskoy nauchno-tekhnicheskoy konferentsii (g. Taganrog 27–30 iyunya
2022 g) [.Multiprocessor computing and control systems: Materials of the All-Russian Scientific
and Technical Conference (Taganrog, June 27-30, 2022)]. Rostov-on-Don – Taganrog:
Izd-vo YuFU, 2022, pp. 103. ISBN 978-5-9275-4144-7.
14. 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, pp. 212-218. DOI:
10.23683/2311-3103-2018-8-212-221.
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. Parallel'nye vychisleniya CUDA, NVIDIA Corporation [Parallel computing CUDA, NVIDIA
Corporation], 2018. Available at: http://www.nvidia.ru/object/cuda-parallel-computing-ru.html
(accessed 18 October 2022).
17. Bethune I., Gloss A., Hutter J., Lazzaro A., Pabst H., Reid F. Porting of the DBCSR library for
Sparse Matrix-Matrix Multiplications to Intel Xeon Phi systems, Submitted to the ParCo2017
conference. Distributed, Parallel, and Cluster Computing (cs.DC) - 2017 Italy Bologna 12-15
September 2017. DOI: 10.3233/978-1-61499-843-3-47.
18. 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.
19. 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.
20. 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.
21. Yang C., Buluc A., Owens J. Design Principles for Sparse Matrix Multiplication on the GPU,
International European Conference on Parallel and Distributed Computing. Turin, 2018, pp. 12.
The SuiteSparse Matrix Collection Website Interface, Journal of Open Source Software, March
2019, Vol. 4, No. 35, pp. 1244-1248. DOI: https://doi.org/10.21105/joss.01244 (accessed 02
October 2022).
2. 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.
3. 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.
4. Pelipets A.V. Metody i sredstva resheniya zadach lineynoy algebry na vysokoproizvoditel'nykh
rekonfiguriruemykh vychislitel'nykh sistemakh: disc. … 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.
5. 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
editorship of I.A. Kalyaev. 2nd ed. Rostov-on-Don: Izd-vo YuNTS RAN, 2009, 344 p.
6. Podoprigora A.V. Metod organizatsii diskretno-sobytiynykh vychisleniy dlya obrabotki bol'shikh
razrezhennykh nestrukturirovannykh matrits na RVS [A method for organizing discrete-event
computing for processing large sparse unstructured matrices on RVS], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2021, No. 7, pp. 189-197. DOI:
10.18522/2311-3103-2021-7-189-197.
7. Podoprigora A.V. Metody rasparallelivaniya vychisleniy dlya obrabotki bol'shikh
razrezhennykh nestrukturirovannykh matrits na RVS [Methods of parallelization of calculations
for processing large sparse unstructured matrices on RVS], XVIII Ezhegodnaya
molodezhnaya nauchnaya konferentsiya «Nauka YUga Rossii: dostizheniya i perspektivy»:
Mater. konferentsii (g. Rostov-na-Donu, 18–29 aprelya 2022 g.) [XVIII Annual Youth Scientific
Conference "Science of the South of Russia: achievements and prospects": Materials of
the conference (Rostov-on-Don, Rostov–on-Don, April 18-29, 2022)]. Rostov-on-Don: Izd-vo
YuNTS RAN, 2022, pp. 262. ISBN 978-5-4358-0233-7.
8. Sorokin D.A. Metody resheniya zadach s peremennoy intensivnost'yu potokov dannykh na
rekonfiguriruemykh vychislitel'nykh sistemakh: diss. … 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.
9. Podoprigora A.V. Upravlenie protsessom obrabotki razrezhennykh matrits v diskretno-sobytiynykh
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): Proceedings of
the XIV multi-conference (Divnomorskoe, Gelendzhik, September 27 – October 2, 2021)]: in 4 vol.
Vol. 2, editorial board: I.A. Kalyaev, V.G. Peshekhonov and others. Rostov-on-Don; Taganrog: Izdvo
YuFU, 2021., pp. 276-278. ISBN 978-5-9275-3846-1.
10. Kleynrok L. Teoriya massovogo obsluzhivaniya [Theory of queuing]. Moscow: Mashinostroenie,
1979, 432 p.
11. 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.
12. Tikhonov A.N., Samarskiy A.A. Uravneniya matematicheskoy fiziki [Equations of mathematical
physics]. Moscow: Izd-vo Moskovskogo universiteta, 1999. 6th ed., 798 p. Available at:
https://elar.urfu.ru/bitstream/10995/42951/1/978-5-321-02475-1_2016.pdf (accessed 15 October
2022).
13. Podoprigora A.V. Ob"edinenie bazovykh BRN-matrichnykh makrooperatsiy [Combining basic
BRN-matrix macro operations], Mnogoprotsessornye vychislitel'nye i upravlyayushchie
sistemy: Mater. Vserossiyskoy nauchno-tekhnicheskoy konferentsii (g. Taganrog 27–30 iyunya
2022 g) [.Multiprocessor computing and control systems: Materials of the All-Russian Scientific
and Technical Conference (Taganrog, June 27-30, 2022)]. Rostov-on-Don – Taganrog:
Izd-vo YuFU, 2022, pp. 103. ISBN 978-5-9275-4144-7.
14. 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, pp. 212-218. DOI:
10.23683/2311-3103-2018-8-212-221.
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. Parallel'nye vychisleniya CUDA, NVIDIA Corporation [Parallel computing CUDA, NVIDIA
Corporation], 2018. Available at: http://www.nvidia.ru/object/cuda-parallel-computing-ru.html
(accessed 18 October 2022).
17. Bethune I., Gloss A., Hutter J., Lazzaro A., Pabst H., Reid F. Porting of the DBCSR library for
Sparse Matrix-Matrix Multiplications to Intel Xeon Phi systems, Submitted to the ParCo2017
conference. Distributed, Parallel, and Cluster Computing (cs.DC) - 2017 Italy Bologna 12-15
September 2017. DOI: 10.3233/978-1-61499-843-3-47.
18. 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.
19. 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.
20. 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.
21. Yang C., Buluc A., Owens J. Design Principles for Sparse Matrix Multiplication on the GPU,
International European Conference on Parallel and Distributed Computing. Turin, 2018, pp. 12.
