Масштабируемые алгоритмы целочисленной арифметики и организация поддержки рациональных вычислений в гетерогенных средах

Анатолий Васильевич Панюков, Валентин Александрович Голодов

Аннотация


Для алгоритмического анализа крупномасштабных проблем, чувствительных к ошибкам округления разрабатывается программное обеспечение,  реализующее точные дробно-рациональные вычисления для распределенной вычислительной среды с интерфейсом MPI. Дальнейшее повышение эффективности программного обеспечения возможно за счет применения гетерогенных вычислительных систем, позволяющих выполнять локальные арифметические  операции с числами сверхбольшой разрядности параллельно в большом числе процессов. В работе представлено исследование масштабируемости  алгоритмов основных арифметических операций и методы ее повышения. Показана возможность повышения эффективности программного  обеспечения за счет применения массового параллелизма в гетерогенных вычислительных системах. Использование избыточной позиционной системы счисления, предложенной в работе, позволяет выполнять операцию алгебраического сложения за константное время, что позволяет  построить хорошо масштабируемые алгоритмы выполнения всех основных арифметических операций с целыми числами. Масштабируемость основных алгоритмов целочисленной арифметики легко переносится на дробно-рациональную арифметику.

Ключевые слова


длинная арифметика; масштабирумые алгоритмы целочисленной арифметики; избыточная: система счисления; рациональные вычисления

Полный текст:

PDF

Литература


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




DOI: http://dx.doi.org/10.14529/cmse150206