2020, issue 2, p. 53-66

Received 19.03.2020; Revised 03.04.2020; Accepted 30.06.2020

Published 24.07.2020; First Online 27.07.2020


Previous  |  Full text (in Ukrainian)  |  Next


MSC 28A12, 90C25

Parallel Algorithms for Solving Linear Systems on Hybrid Computers

Alexander Khimich 1 ORCID ID favicon Big,   Victor Polyanko 1,   Tamara Chistyakova 1 *

1 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv

* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.


Introduction. At present, in science and technology, new computational problems constantly arise with large volumes of data, the solution of which requires the use of powerful supercomputers. Most of these problems come down to solving systems of linear algebraic equations (SLAE). The main problem of solving problems on a computer is to obtain reliable solutions with minimal computing resources. However, the problem that is solved on a computer always contains approximate data regarding the original task (due to errors in the initial data, errors when entering numerical data into the computer, etc.). Thus, the mathematical properties of a computer problem can differ significantly from the properties of the original problem. It is necessary to solve problems taking into account approximate data and analyze computer results. Despite the significant results of research in the field of linear algebra, work in the direction of overcoming the existing problems of computer solving problems with approximate data is further aggravated by the use of contemporary supercomputers, do not lose their significance and require further development. Today, the most high-performance supercomputers are parallel ones with graphic processors. The architectural and technological features of these computers make it possible to significantly increase the efficiency of solving problems of large volumes at relatively low energy costs.

The purpose of the article is to develop new parallel algorithms for solving systems of linear algebraic equations with approximate data on supercomputers with graphic processors that implement the automatic adjustment of the algorithms to the effective computer architecture and the mathematical properties of the problem, identified in the computer, as well with estimates of the reliability of the results.

Results. A methodology for creating parallel algorithms for supercomputers with graphic processors that implement the study of the mathematical properties of linear systems with approximate data and the algorithms with the analysis of the reliability of the results are described. The results of computational experiments on the SKIT-4 supercomputer are presented.

Conclusions. Parallel algorithms have been created for investigating and solving linear systems with approximate data on supercomputers with graphic processors. Numerical experiments with the new algorithms showed a significant acceleration of calculations with a guarantee of the reliability of the results.


Keywords: systems of linear algebraic equations, hybrid algorithm, approximate data, reliability of the results, GPU computers.


Cite as: Khimich A., Polyanko V., Chistyakova T. Parallel Algorithms for Solving Linear Systems on Hybrid Computers. Cybernetics and Computer Technologies. 2020. 2. P. 53–66. (in Ukrainian) https://doi.org/10.34229/2707-451X.20.2.6



           1.     TOP 500 supercomputers 2019. http://www.top500.org/lists/2019/11/.

           2.     NetLib. https://www.netlib.org/.

           3.     AMD math LibM. http://developer.amd.com/amd-aocl/amd-math-library-libm/.

           4.     Math Kernel Library. https://software.intel.com./en-us/mkl/.

           5.     Boreskov A.V., Kharlamov A.A. Basics of working with CUDA technology. M.: Press, 2010. 232 p. (in Russian)

           6.     cuBLAS. https://developer.nvidia.com/cublas/.

           7.     cuSparse Library. https://developer.nvidia.com/cusparse/.

           8.     CULA Tools. https://developer.nvidia.com/em-photonics-cula-tools.

           9.     MAGMA Software. https://icl.cs.utk.edu/magma/.

       10.     CUSP. https://developer.nvidia.com/cusp/.

       11.     MathCAD. https://www.ptc.com/ru/products/mathcad/.

       12.     Maple. https://www.maplesoft.com/products/Maple/.

       13.     Mathematica. https://www.wolfram.com/mathematica/.

       14.     Matlab. https://www.mathworks.com/help/matlab/.

       15.     Voevodin V.V., Voevodin Vl.V. Parallel computing. St. Petersburg: BHV-Petersburg, 2002. 608 p. (in Russian).

       16.     Khimich A.N., Molchanov I.N., Mova V.I. et al. Inparcom numerical MIMD computer software. Kiev: Naukova Dumka, 2007. 222 p. (in Ukrainian).

       17.     Khimich A.N., Molchanov I.N., Popov A.V., Chistyakova T.V., Yakovlev M.F. Parallel algorithms for solving problems of computational mathematics. Kiev: Naukova Dumka, 2008. 247 p. (in Ukrainian).

       18.     Sergienko I.V., Molchanov I.N., Khimich A.N. Intelligent technologies of high-performance computing. Cybern Syst Anal. 2010. 46 (5). P. 164–176. https://doi.org/10.1007/s10559-010-9265-3

       19.     Ilyin V.P. About some problems of "cloud" mathematical modeling. Bulletin of the South Ural State University. A series of computational mathematics and computer science. 2014. 3 (1). P. 68–79. (in Russian). https://doi.org/10.14529/cmse140106

       20.     Tarnavsky G.A., Aliev A.V. Mathematical simulation: principal segments, their peculiarities, and problem. Numerical Methods and Programming. 2007. 8. P. 297–310. https://en.num-meth.rcc.msu.ru/index.php/journal/article/view/271

       21.     Nemnyugin S.A., Stesik O.L. Parallel programming for multi-processor computer systems. St. Petersburg: BHV-Petersburg, 2002. 400 p. (in Russian).

       22.     Molchanov I.N. Machine methods for solving applied problems. Algebra, approximation of functions. Kiev: Naukova Dumka, 1987. 288 p. (in Ukrainian).

       23.     Wilkinson J.H. Rounding Errors in Algebraic Processes. London: H.W. Staat. Off, 1963. 161 p.

       24.     Wilkinson J.H., Reinsch C. Handbook for Automatic Computation. М.: Mashinostroyeniye, 1976. 389 p. (in Russian)

       25.     Voevodin V.V. Rounding errors and stability in direct methods of linear algebra. M.: Publishing. Computing Center of Moscow State University, 1969. 153 p. (in Russian).

       26.     Golovinsky A.L., Malenko A.L., Sergіnko I.V., Tulchinsky V.G. Energy-efficient supercomputer SKIT-4. Newsletter of the National Academy of Sciences of Ukraine. 2013. 2. P. 50–59. (in Ukrainian). https://doi.org/10.15407/visn2013.02.050



ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  Full text (in Ukrainian)  |  Next




Copyright © 2019-2020 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine,

National Academy of Sciences of Ukraine.

All rights reserved.