METHOD OF PARALLELIZATION ON BASIC MACRO OPERATIONS FOR PROCESSING LARGE SPARSE UNSTRUCTURED MATRIXES ON RCS
Keywords:
Large sparse unstructured matrices, LRN matrices, reconfigurable computing systems, FPGA technologies, sparse matrix operations, sparse matrix addition, sparse matrix multiplication
Abstract
Analysis calculating large sparse unstructured matrices (LSU-matrices) methods and tools
for cluster computing systems with a traditional architecture showed that for most tasks of processing
matrices with about 105 rows, performance compose reduced 5-7 times compared to the
peak performance. Meanwhile peak performance of computing systems is mainly estimated by the
LINPAC test, which involves the execution of matrix operations. The main goal of the work is to
increase the efficiency processing LSU-matrices, for this purpose advisable to use reconfigurable
computing systems (RSC) based on FPGAs as the main type of computing tools. For efficient processing
LSU-matrices on RCS, a set method and approaches previously described in the papers
are used, such as the structural organization of calculations, the format for representing
LSU-matrices "row of lines", the paradigm of discrete-event organization of data flows, the method of parallelization by iterations. The article considers the method of parallelization by basic
macro-operations for solving the problem of processing LSU-matrices on RCS, which implies
obtaining a constant computational efficiency, regardless of the portrait of processed LSUmatrices.
Using developed methods for processing LSU-matrices for reconfigurable computing
systems makes it possible to provide computational efficiency at the level of 50%, which is several
times superior to traditional parallelization methods
References
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.
Published
2023-02-27
Issue
Section
SECTION II. INFORMATION PROCESSING ALGORITHMS
