Масштабируемые алгоритмы целочисленной арифметики и организация поддержки рациональных вычислений в гетерогенных средах
Автор: Голодов Валентин Александрович, Панюков Анатолий Васильевич
Рубрика: Вычислительная математика
Статья в выпуске: 2 т.4, 2015 года.
Бесплатный доступ
Для алгоритмического анализа крупномасштабных проблем, чувствительных к ошибкам округления разрабатывается программное обеспечение, реализующее точные дробно-рациональные вычисления для распределенной вычислительной среды с интерфейсом MPI.Дальнейшее повышение эффективности программного обеспечения возможно за счет применения гетерогенных вычислительных систем, позволяющих выполнять локальные арифметические операции с числами сверхбольшой разрядности параллельно в большом числе процессов. В работе представлено исследование масштабируемости алгоритмов основных арифметических операций и методы ее повышения. Показана возможность повышения эффективности программного обеспечения за счет применения массового параллелизма в гетерогенных вычислительных системах. Использование избыточной позиционной системы счисления,предложенной в работе, позволяет выполнять операцию алгебраического сложения за константное время, что позволяет построить хорошо масштабируемые алгоритмы выполнения всех основных арифметических операций с целыми числами. Масштабируемость основных алгоритмов целочисленной арифметики легко переносится на дробно-рациональную арифметику.
Длинная арифметика, масштабирумые алгоритмы целочисленной арифметики, избыточная система счисления, рациональные вычисления
Короткий адрес: https://sciup.org/147160565
IDR: 147160565 | DOI: 10.14529/cmse150206
Список литературы Масштабируемые алгоритмы целочисленной арифметики и организация поддержки рациональных вычислений в гетерогенных средах
- 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.
