Parallel Algorithms of Integer Arithmetic in Radix Notations for Heterogeneous Computation Systems with Massive Parallelism

For the analysis of huge problems which are very sensitive to the rounding errors, the software providing rational calculations is developed. Software uses sf MPI interface for communication in the distributed computational environment. Improved efficiency of such software my be achieved by using heterogeneous computation systems. Local arithmetic operations with long numbers may be done in parallel mode with a lot of processes per one operation. This work introduces the research of increasing of the scalability of basic arithmetic operations.
Abilities of the massive parallelism for the heterogeneous computation systems for the efficiency improving are shown. Redundant numerical system with a constant time of the addition operation is introduced. It allows to design well scaled algorithms for all basic arithmetic operations with integer numbers. Scalability of the basic integer arithmetic algorithms is easy applied to rational arithmetic.

Keywords

integer computer arithmetic; heterogeneous computer system; radix notation; massive parallelism.

References

1. Beaumont O., Philippe B. Linear Interval Tolerance Problem and Linear Programming Ttechniques. Reliable Computing, 2001, vol. 6, no. 4, pp. 365-390.
2. Panyukov A.V., Gorbik V.V. Using Massively Parallel Computations for Absolutely Precise Solution of the Linear Programming Problems. Automation and Remote Control, 2012, vol. 73, no. 2, pp. 276-290.
3. Panyukov A.V. Exact and Guaranteed Accuracy Solutions of Linear Programming Problems by Distributed Computer Systems with mpi. Tambov University Reports. Series: Natural and Technical Sciences, 2010, vol. 15, no. 4, pp. 1392-1404.
4. Panyukov A.V., Golodov V.A.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, Novosibirsk, Russia, September 23-29, 2012): Book of abstracts, Institute of Computational Technologies Publisher, 2012, pp. 134-135.
5. Golodov V.A., Panyukov A.V. Library of Classes 'Exact Computation' Programs, Data Bases and Topologies of VLIS. Official bulletin of Russian Agenсy of Patients and Trademarks, Moscow, FIPS, 2013.
6. Panyukov A.V., Lesovoi S.Yu. Using of Massive Parallel Calculations for Integer Arithmetics Realisation. Vol. 2. Perm, PermGTU, 2010.
7. Panyukov A.V. 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, Novosibirsk, Russia, September 23-29, 2012): Book of abstracts, Institute of Computational Technologies Publisher, 2012.
8. Golodov V.A. Distributed Symbolic Rational-Fractional Calculations on the Processors of Series of x86 and x64. Proceeding of international conference 'Parallel computational technologies' (Novosibirsk, 2012, on March 26 to 30), Chelyabinsk: Publishing center of SUSU, 2012, p. 774.
9. Knuth D.E. The Art of Computer Programming. Addison-Wesley Longman, 1981, vol. 2, p. 688.