Scalable algorithms for the integer arithmetics and rational calculations in heterogeneous computation environment

V. A. Golodov   ; A. V. Panyukov

Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 4 (2015) no. 2, pp. 71-88

Résumé

Algorithmic analysis of large-scale problems that are sensitive to rounding errors requires precise rational calculations in the distributed computing environment. Enhanced efficiency of thesoftware my be gained to heterogeneous computing systems that perform local basic arithmeticoperations simultaneously using large number of ultralight threads. This paper examines thescalability algorithms for basic arithmetic operations and methods of its improvement. Thepossibility of increasing of the software efficiency using massive parallelism in heterogeneouscomputing systems is described. The use of reduntant number system allows you to performthe operation of algebraic addition in constant time and to construct scalable algorithms for allbasic arithmetic operations. Scalability of the basic integer arithmetic algorithms can be easilytransferred to a rational arithmetic.

Détail

Keywords: integer arithmetics, rational arithmetics, sclable alrorithms, position number system, reduntant number system.

Bibliographie

[1] R. Alt, J.-L. Lamotte, S. Markov, “On the accuracy of the solution of linear problems on the CELL processor”, Reliable Computing, 15 (2011), 1–12 | MR

[2] O. Beaumont, B. Philippe, “Linear interval tolerance problem and linear programming techniques”, Reliable Computing, 6:4 (2001), 365–390 | MR

[3] G.E. Coxson, “Computing exact bounds on elements of an inverse interval matrix is NPhard”, Reliable Computing, 5:2 (1999), 137–142 | DOI | MR | Zbl

[4] A.V. Panyukov, V.V. Gorbik, “Using massively parallel computations for absolutely precise solution of the linear programming problems”, Automation and Remote Control, 73:2 (2012), 276–290 | DOI | MR | Zbl

[5] A.V. Panyukov, V.V. Gorbik, “Exact and guaranteed accuracy solutions of linear programming problems by distributed computer systems with MPI”, Tambov University Reports. Series: Natural and Technical Sciences, 15:4 (2010), 1392–1404

[6] Panyukov A.V., “Computing the best possible pseudo-solutions to interval linear systems of equations”, 15th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Verified Numeric (SCAN'2012), Book of abstracts (Novosibirsk, Russia, September 23-29, 2012), Institute of Computational Technologies Publisher, 2012, 134–135

[7] A. Panyukov, Polynomial solvability of n np-complete problems, , ScienceOpen Research, 2015 (data obrascheniya: 13.03.2015) https://www.scienceopen.com/document/vid/c0597241-52c2-47a7-8af0-dd09bbb57888

[8] M. Grötschel, L. Lovácute;asz, A. Schrijver, “The ellipsoid method and its consequences in combinatorial optimization”, Combinatorica, 1:2 (1981), 169–197 | DOI | MR | Zbl

[9] The gnu mp bignum library, , 2013 (data obrascheniya: 13.03.2015) http://gmplib.org/

[10] Golodov V.A., Panyukov A.V., “Class Library «Exact Computation 2.0», State Registration Certificate No 2013612818 for Computer Code”, Computer Codes, Data Bases, VLSI topologies. Official Bulletin of Russian Agency on Patents and trademarks, 3, FIPS, M., 2013, 251

[11] Zolotovskij V., Ghilvanov M., “Implementation of Long Calculations for Parallel Structures”, Proceedings of North Caucasian Scientific Center. Technical Sciences, 2008, no. 4, 9–13

[12] Parallel programming and computing platform | cuda | nvidia, , 2013 (data obrascheniya: 13.03.2015) http://www.nvidia.com/object/cuda_home.html

[13] Zheltov S.A., “Implementation of Long Arithmetics Operations for GPGPU devices”, Information Security Problems, 2012, no. 3, 2–4

[14] Orlov D., “Implementation of Long Arithmetics with GPU”, Software Engendering, 2012, no. 4, 33–43

[15] Dzegelenok I.I., Ocopkov Sh.A., “Algebraization of Number Representations for Implementation of High-precision Supercomputer Calculations”, Herald of Moscow Exegetical Institute, 2010, no. 3, 107–116

[16] D.E. Knuth, The Art of Computer Programming, v. 2, 2-nd edition, Addison-Wesley Longman, 1981, 688 pp. | MR | Zbl

[17] A.V. Panyukov, “Application of redundant positional notations for increasing of arithmetic algorithms scalability”, 15th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Verified Numeric (SCAN'2012), Book of abstracts (Novosibirsk, Russia, September 23–29, 2012), Institute of Computational Technologies Publisher, 2012

[18] Panyukov A. V., Germanenko M.I., “Complexity of Assured Estimating of Solution for Approximately Linear Algebraic Equations System”, Proceedings of Chelybinsk Scientific Center, 2000, no. 4, 21–30

[19] Panukov A.V., Lesovoy S., “Realization of Base Arithmetical Operations for Heterogeneous Systems”, Parallel Computational Technologies (PCT'2012), Proceedings of the International Conference (Novosibirsk, March, 26–30, 2012), Publishing Center of SUSU, Chelyabinsk, 2012, 77–84

[20] Panukov A.V., Lesovoy S., “Application Massive Parallel Calculations for Realization of Base Integer Arithmetic Operations”, High Performance Calculations with Cluster Systems (HPC-2010), X International Conference (Perm, 2010, November, 1–3), v. 2, PermGTU, Perm, 2010, 77–84

[21] Golodov V.A., “Distributed symbolic rational-fractional calculations on the processors of series of x86 and x64”, Parallel Computational Technologies (PCT'2012), Proceedings of the International Conference (Novosibirsk, March, 26–30, 2012), Publishing center of SUSU, Chelyabinsk, 2012, 774

[22] Panyukov A.V., Golodov V.A., “Software Engineering for Algorithm to Solve the Linear Algebraic Equation Set with Input Interval Uncertainties”, Parallel Computation and Management Problems (PACO'2012), VI International Conference, Conference Proceedings (Moscow, 2012, October, 24–26), v. 2, IPU RAN, M., 2012, 155–166