Scalable algorithms for the integer arithmetics and rational calulations in heterogeneous computation environment
DOI:
https://doi.org/10.14529/cmse150206Keywords:
integer arithmetics, rational arithmetics, sclable alrorithms, position number system, reduntant number systemAbstract
Algorithmic analysis of large-scale problems that are sensitive to rounding errorsrequires precise rational calculations in the distributed computing environment.Enhanced efficiency of the software my be gained to heterogeneous computing systems that perform local basic arithmetic operations simultaneously using large number of ultralight threads. This paper examines the scalability algorithms for basic arithmetic operations and methods of its improvement.The possibility of increasing of the software efficiency using massive parallelism in heterogeneous computing systems is described. The use of reduntant number system allows you to perform the operation of algebraic addition in constant time and to construct scalable algorithms for all basic arithmetic operations. Scalability of the basic integer arithmetic algorithms can be easily transferred to a rational arithmetic.
References
Alt, R. On the accuracy of the solution of linear problems on the CELL processor / R. Alt, J.-L. Lamotte, S. Markov // Reliable Computing. 2011. Vol. 15. Pp. 112.
Beaumont, O. Linear interval tolerance problem and linear programming techniques / O. Beaumont, B. Philippe // Reliable Computing. 2001. Vol. 6, no. 4. Pp. 365390.
Coxson, G. E. Computing exact bounds on elements of an inverse interval matrix is NP-hard / G. E. Coxson // Reliable Computing. 1999. Vol. 5, no. 2. Pp. 137142.
Panyukov, A. V. Using massively parallel computations for absolutely precise solution of the linear programming problems / A. V. Panyukov, V. V. Gorbik // Automation and Remote Control. 2012. Vol. 73, no. 2. Pp. 276290.
Panyukov, A. V. Exact and guaranteed accuracy solutions of linear programming problems by distributed computer systems with mpi / A. V. Panyukov, V. V. Gorbik // Tambov University Reports. Series: Natural and Technical Sciences. 2010. Vol. 15, no. 4. Pp. 13921404.
Panyukov, A. V. Computing the best possible pseudo-solutions to interval linear systems of equations // 15th GAMM-IMACS International Symposium on Scientic Computing, Computer Arithmetic and Veried Numeric (SCAN'2012, Novosibirsk, Russia, September 23-29,
: Book of abstracts. Institute of Computational Technologies Publisher, 2012. Pp. 134135.
Panyukov, A. Polynomial solvability of n np-complete problems / A. Panyukov // ScienceOpenResearch. 2015.
Grotschel, M. The ellipsoid method and its consequences in combinatorial optimization / M. Grotschel, L. Lovasz, A. Schrijver // Combinatorica. 1981. Vol. 1, no. 2. Pp. 169-197.
The gnu mp bignum library. February 2013. http://gmplib.org/.
Golodov, V.A. Biblioteka klassov ¾Exact Computation 2.0¿ svidetel'stvo o gosudarstvennoj registracii programmy dlja JeVM 2013612818 ot 14 marta / V. Golodov, A. V. Panjukov // Programmy dlja JeVM, bazy dannyh, topologii integral'nyh mikroshem. Ocial'nyj bjulleten' Rossijskogo agentstva po patentam i tovarnym znakam. M.: FIPS, 2013. 3. P. 251.
Zolotovskij, V. Realizacija ¾dlinnyh vychislenij¿ na parallel'nyh strukturah / V. Zolotovskij, M. F. Gil'vanov // Izvestija vysshih uchebnyh zavedenij. Severo-Kavkazskij region. Serija: Tehnicheskie nauki. 2008. 4.
Parallel programming and computing platform | cuda | nvidia. Febbuary 2013. htpp: //www.nvidia.com/object/cuda_home.html.
Zheltov, S. A. Realizacija arifmeticheskih operacij s "dlinnymi"chislami na ustrojstvah gpgpu / S. A. Zheltov // Voprosy zashhity informacii. 2012. 3. Ñ. 24.
Orlov, D. Realizacija arifmetiki povyshennoj razrjadnosti na gracheskih processorah / D. Orlov // Programmnaja inzhenerija. 2012. 4. Ñ. 3343.
Dzegelenok, I. I. Algebraizacija chislovyh predstavlenij dlja obespechenija vysokotochnyh superkomp'juternyh vychislenij / I. I. Dzegelenok, Sh. A. Ocopkov // Vestnik Moskovskogo jenergeticheskogo instituta. 2010. 3. Ñ. 107116.
Knuth, D. E. The Art of Computer Programming / D. E. Knuth. 2 edition. Addison-Wesley Longman, 1981. Vol. 2. P. 688.
Panyukov, A. V. Application of redundant positional notations for increasing of arithmetic algorithms scalability // 15th GAMM-IMACS International Symposium on Scientic Computing,
Computer Arithmetic and Veried Numeric (SCAN'2012, Novosibirsk, Russia, September 23-29, 2012): Book of abstracts. Institute of Computational Technologies Publisher, 2012.
Panjukov, A. V. Slozhnost' nahozhdenija garantirovannoj ocenki reshenija priblizhenno zadannoj sistemy linejnyh algebraicheskih uravnenij / A. V. Panjukov, M. I. Germanenko // Izvestija Cheljabinskogo nauchnogo centra UrO RAN. 2000. 4. Ñ. 2130.
Panjukov, A. V. Realizacija bazovyh operacij celochislennoj arifmetiki v geterogennyh sistemah. /A.V. Panjukov, S. Lesovoj// Parallel'nye vychislitel'nye tehnologii (PaVT'2012). Trudy mezhdunarodnoj nauchnoj konferencii (Novosibirsk, 26 marta 30 marta 2012 g.).
Cheljabinsk: Izdatel'skij centr JuUrGU., 2012. Ñ. 7784.
Panjukov, A. V. Primenenie massivno-parallel'nyh vychislenij dlja realizacii osnovnyh operacij celochislennoj arifmetiki /A.V. Panjukov, S. Lesovoj// Vysokoproizvoditel'nye parallel'nye vychislenija na klasternyh sistemah (HPC - 2010). Materialy X Mezhdunarodnoj konferencii (g. Perm', 1 - 3 nojabrja 2010 g.). V 2-h tomah. Ò. 2. Perm': Izd-vo PermGTU, 2010. Ñ. 7784.
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.
Panjukov, A. V. Tehnika programmnoj realizacii algoritma reshenija sistemy linejnyh algebraicheskih uravnenij s interval'noj neopredelennost'ju v ishodnyh dannyh // "Parallel'nye vychislenija i zadachi upravlenija "PACO'2012. Shestaja mezhdunarodnaja konferencja,
Moskva, 24-26 oktjabrja. Trudy v 3 t. Ò. 2. Moskva: IPU RAN, 2012. Ñ. 155-166
