Масштабируемые алгоритмы целочисленной арифметики и организация поддержки рациональных вычислений в гетерогенных средах
Автор: Голодов Валентин Александрович, Панюков Анатолий Васильевич
Рубрика: Вычислительная математика
Статья в выпуске: 2 т.4, 2015 года.
Бесплатный доступ
Для алгоритмического анализа крупномасштабных проблем, чувствительных к ошибкам округления разрабатывается программное обеспечение, реализующее точные дробно-рациональные вычисления для распределенной вычислительной среды с интерфейсом MPI.Дальнейшее повышение эффективности программного обеспечения возможно за счет применения гетерогенных вычислительных систем, позволяющих выполнять локальные арифметические операции с числами сверхбольшой разрядности параллельно в большом числе процессов. В работе представлено исследование масштабируемости алгоритмов основных арифметических операций и методы ее повышения. Показана возможность повышения эффективности программного обеспечения за счет применения массового параллелизма в гетерогенных вычислительных системах. Использование избыточной позиционной системы счисления,предложенной в работе, позволяет выполнять операцию алгебраического сложения за константное время, что позволяет построить хорошо масштабируемые алгоритмы выполнения всех основных арифметических операций с целыми числами. Масштабируемость основных алгоритмов целочисленной арифметики легко переносится на дробно-рациональную арифметику.
Длинная арифметика, масштабирумые алгоритмы целочисленной арифметики, избыточная система счисления, рациональные вычисления
Короткий адрес: https://sciup.org/147160565
IDR: 147160565 | УДК: 681.3.06 | DOI: 10.14529/cmse150206
Scalable algorithms for the integerarithmetics and rational calculations in heterogeneous computation environment
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.
Список литературы Масштабируемые алгоритмы целочисленной арифметики и организация поддержки рациональных вычислений в гетерогенных средах
- 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. -P. 1-12.
- Beaumont, O. Linear interval tolerance problem and linear programming techniques/O. Beaumont, B. Philippe//Reliable Computing. -2001. -Vol. 6, No. 4. -P. 365-390.
- Coxson, G. E. Computing exact bounds on elements of an inverse interval matrix is NPhard/G. E. Coxson//Reliable Computing. -1999. -Vol. 5, No. 2. -P. 137-142. DOI: DOI: 10.1023/a:1009901405160
- 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. -P. 276-290. DOI: DOI: 10.1134/s0005117912020063
- 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. -P. 1392-1404.
- 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, Novosibirsk, Russia, September 23-29, 2012): Book of abstracts. -Institute of Computational Technologies Publisher, 2012. -P. 134-135.
- Panyukov, A. Polynomial solvability of n np-complete problems/A. Panyukov//ScienceOpen Research. -2015. https://www.scienceopen.com/document/vid/c0597241-52c2-47a7-8af0-dd09bbb57888 (дата обращения 13.03.2015).
- Gr¨otschel, M. The ellipsoid method and its consequences in combinatorial optimization/M. Gr¨otschel, L. Lov´asz, A. Schrijver//Combinatorica. -1981. -Vol. 1, No. 2. -P. 169-197. DOI: DOI: 10.1007/bf02579273
- The gnu mp bignum library. -February 2013. http://gmplib.org/(дата обращения 13.03.2015).
- Голодов, В. Библиотека классов «Exact Computation 2.0». Свидетельство о государственной регистрации программы для ЭВМ № 2013612818 от 14.03.2013/В. Голодов, А. В. Панюков//Программы для ЭВМ, базы данных, топологии интегральных микросхем. Официальный бюллетень Российского агентства по патентам и товарным знакам. -М.: ФИПС, 2013. -№ 3. -С. 251.
- Золотовский, В. Реализация «длинных вычислений» на параллельных структурах/В. Золотовский, М. Ф. Гильванов//Известия высших учебных заведений. Северо-Кавказский регион. Серия: Технические науки. -2008. -№ 4. -С. 9-13.
- Parallel programming and computing platform | cuda | nvidia. -February 2013. htpp://www.nvidia.com/object/cuda_home.html (дата обращения 13.03.2015).
- Желтов, С. А. Реализация арифметических операций с «длинными» числами на устройствах gpgpu/С. А. Желтов//Вопросы защиты информации. -2012. -№ 3. -С. 2-4.
- Орлов, Д. Реализация арифметики повышенной разрядности на графических процессорах/Д. Орлов//Программная инженерия. -2012. -№ 4. -С. 33-43.
- Дзегеленок, И. И. Алгебраизация числовых представлений для обеспечения высокоточных суперкомпьютерных вычислений/И. И. Дзегеленок, Ш. А. Оцопков//Вестник Московского энергетического института. -2010. -№ 3. -С. 107-116.
- Knuth, D. E. The Art of Computer Programming/D. E. Knuth. -2-nd edition. -Addison-Wesley Longman, 1981. -Vol. 2. -688 p.
- Panyukov, A. V. Application of redundant positional notations for increasing of arithmetic algorithms scalability/A. V. Panyukov//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.
- Панюков, А. В. Сложность нахождения гарантированной оценки решения приближенно заданной системы линейных алгебраических уравнений/А. В. Панюков, М. И. Германенко//Известия Челябинского научного центра УрО РАН. -2000. -№ 4. -С. 21-30.
- Панюков, А. В. Реализация базовых операций целочисленной арифметики в гетерогенных системах./А. В. Панюков, С. Ю. Лесовой//Параллельные вычислительные технологии (ПаВТ’2012). -Труды международной научной конференции (Новосибирск, 26 -30 марта 2012 г.). -Челябинск: Издательский центр ЮУрГУ, 2012. -С. 77-84.
- Панюков, А. В. Применение массивно-параллельных вычислений для реализации основных операций целочисленной арифметики/А. В. Панюков, С. Ю. Лесовой//Высокопроизводительные параллельные вычисления на кластерных системах (HPC -2010). Материалы X Международной конференции (г. Пермь, 1 -3 ноября 2010 г.). В 2-х томах. -Т. 2. -Пермь: Изд-во ПермГТУ, 2010. -С. 77-84.
- Голодов, В. А. Распределенные символические дробно-рациональные вычисления на процессорах серий x86 и x64/В. А. Голодов//Труды Международной конференции «Параллельные вычислительные технологии -2012» (Новосибирск, 2012, 26 -30 марта). -Челябинск: Издательский центр ЮУрГУ, 2012. -С. 774.
- Панюков, А. В. Техника программной реализации алгоритма решения системы линейных алгебраических уравнений с интервальной неопределенностью в исходных данных А. В. Панюков, В. А. Голодов//«Параллельные вычисления и задачи управления» PACO’2012. Шестая международная конференция, Москва, 2012 г., 24 -26 октября. Труды в 3 т. -Т. 2. -М.: ИПУ РАН, 2012. -С. 155-166.
