Статья

Название статьи СУММИРОВАНИЕ МНОГОКРАТНОЙ ТОЧНОСТИ НА ЦЕНТРАЛЬНЫХ И ГРАФИЧЕСКИХ ПРОЦЕССОРАХ С ИСПОЛЬЗОВАНИЕМ БИБЛИОТЕКИ MPRES
Автор К. С. Исупов, В. С. Князьков, А. С. Куваев
Рубрика РАЗДЕЛ III. МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
Месяц, год 08, 2018
Индекс УДК 004.222
DOI 10.23683/2311-3103-2018-8-191-203
Аннотация В научных расчетах часто требуется вычислять суммы больших массивов чисел с плавающей точкой. Суммирование лежит в основе многих базовых алгоритмов, таких как скалярное произведение, разложение функции в ряд Тейлора и численное интегрирование. Однако, из-за ошибок округления при использовании стандартной арифметики IEEE 754 вычисленный результат суммирования может оказаться крайне неточным. Одним из способов уменьшения ошибок округления является использование библиотек многократной точности, предоставляющих структуры данных и подпрограммы обработки чисел, длина которых превышает форматы IEEE 754. В статье рассматриваются алгоритмы высокоточного суммирования, реализованные в библиотеке MPRES (Multiple-Precision Residue-Based Arithmetic Library), которая позволяет выполнять операции с числами произвольной длины на центральных процессорах (CPU) и CUDA-совместимых графических процессорах видеокарты (GPU). В MPRES для представления многоразрядных мантисс чисел используется система остаточных классов (СОК). В этой системе число представляется в виде остатков от деления исходной величины на выбранные модули, а операции над многоразрядными числами разбиваются на группы операций меньшей разрядности над остатками, которые могут выполняться параллельно и без распространения переноса между остатками. В работе рассматривается алгоритм сложения многоразрядных чисел в MPRES, а также три алгоритма редукции (суммирования) массива чисел: (1) классическое рекурсивное суммирование, (2) попарное суммирование, (3) гибридное CPU-GPU суммирование. Эксперименты показывают, что наибольшей производительностью обладает гибридный блочно-параллельный алгоритм. С другой стороны, параллельное вычисление цифр (остатков) многоразрядных мантисс в СОК позволяет сократить время вычислений.

Скачать в PDF

Ключевые слова Компьютерная арифметика; высокоточные вычисления; суммирование; система остаточных классов; программирование на графических процессорах.
Библиографический список 1. Kornerup P., Lefèvre V., Louvet N., Muller J. On the Computation of Correctly Rounded Sums // IEEE Transactions on Computers. – 2012. – Vol. 61, No. 3. – P. 289-298.
2. Higham N.J. Accuracy and stability of numerical algorithms. – Philadelphia, USA: SIAM, 2002. – 680 p.
3. Priest D.M. Algorithms for arbitrary precision floating point arithmetic // Proceedings of the 10th IEEE Symposium on Computer Arithmetic. Grenoble, France: IEEE. – 1991.
– P. 132-143.
4. Higham N.J. The Accuracy of Floating Point Summation // SIAM Journal on Scientific Computing. – 1993. – Vol. 14, No. 4. – P. 783-799.
5. Anderson I.J. A Distillation Algorithm for Floating-Point Summation // SIAM Journal on Scientific Computing. – 1999. – Vol. 20, No. 5. – P. 1797-1806.
6. Zhu Y.-K., Yong J.-H., Zheng G.-Q. A New Distillation Algorithm for Floating-Point Summation // SIAM Journal on Scientific Computing. – 2005. – Vol. 26, No. 6. – P. 2066-2078.
7. Ogita T., Rump S.M., Oishi S. Accurate Sum and Dot Product // SIAM Journal on Scientific Computing. – 2005. – Vol. 26, No. 6. – P. 1955-1988.
8. Rump S.M. Ultimately Fast Accurate Summation // SIAM Journal on Scientific Computing.
– 2009. – Vol. 31, No. 5. – P. 3466-3502.
9. Goodrich M.T., Eldawy A. Parallel Algorithms for Summing Floating-Point Numbers // Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures. – Pacific Grove, California, USA: ACM, 2016. – P. 13-22.
10. Demmel J., Nguyen H.D. Fast reproducible floating-point summation // Proceedings of the 21st IEEE Symposium on Computer Arithmetic (ARITH). – Austin, Texas: IEEE, 2013. – P. 163-172.
11. Demmel J., Nguyen H.D. Parallel reproducible summation // IEEE Transactions on Computers. – 2015. – Vol. 64, No. 7. – P. 2060-2070.
12. Collange S., Defour D., Graillat S., Iakymchuk R. Numerical reproducibility for the parallel reduction on multi- and many-core architectures // Parallel Computing. – 2015. – Vol. 49.
– P. 83-97.
13. Neal R.M. Fast Exact Summation Using Small and Large Superaccumulators // Technical report, University of Toronto. – 2015. – URL: http://www.cs.toronto.edu/~radford/ftp/xsum.pdf (дата обращения 08.10.2018).
14. Kadric E., Gurniak P. and DeHon A. Accurate Parallel Floating-Point Accumulation // IEEE Transactions on Computers. – 2016. – Vol. 65, No. 11. – P. 3224-3238.
15. ReproBLAS: Reproducible BLAS. – URL: https://bebop.cs.berkeley.edu/reproblas/index.php (дата обращения 31.10.2018).
16. ExBLAS – Exact BLAS. – URL: https://exblas.lip6.fr/ (дата обращения 31.10.2018).
17. Bailey D.H., Barrio R., Borwein J.M. High-precision computation: Mathematical physics and dynamics // Applied Mathematics and Computation. – 2012. – Vol. 218, No. 20. – P. 10106-10121.
18. Joldes M., Muller J.M., Popescu V. Implementation and Performance Evaluation of an Extended Precision Floating-Point Arithmetic Library for High-Accuracy Semidefinite Programming // Proceedings of the 24th IEEE Symposium on Computer Arithmetic (ARITH).
– London, UK: IEEE, 2017. – P. 27-34.
19. Zhao K., Chu X. GPUMP: a Multiple-Precision Integer Library for GPUs // Proceedings of the 2010 10th IEEE International Conference on Computer and Information Technology (CIT 2010). – Bradford, UK: IEEE, 2010. – P. 1164-1168.
20. Lu M., He B., Luo Q. Supporting extended precision on graphics processors // Proceedings of the Sixth International Workshop on Data Management on New Hardware (DaMoN’10). – Indianapolis, Indiana, USA: ACM, 2010. – P. 19-26.
21. Isupov K., Kuvaev A., Popov M., Zaviyalov A. Multiple-Precision Residue-Based Arithmetic Library for Parallel CPU-GPU Architectures: Data Types and Features // Lecture Notes in Computer Science. – Springer, 2017. – Vol. 10421. – P. 196-204.
22. Hida Y., Li X.S., Bailey D.H. Algorithms for quad-double precision floating point arithmetic // Proceedings of the 15th IEEE Symposium on Computer Arithmetic. – Vail, CO, USA: IEEE, 2001. – P. 155-162.
23. Bailey D.H., Hida Y., Li X.S., Thompson B. ARPREC: An arbitrary precision computation package // Technical report, Lawrence Berkeley National Lab. – 2002. – URL: https://www.osti.gov/biblio/817634 (дата обращения 25.10.2018).
24. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. – М.: Сов. Радио, 1968. – 440 с.
25. Omondi A., Premkumar B. Residue number systems: theory and implementation. – London: Imperial College Press, 2007. – 312 p.
26. Mohan P.A. Residue Number Systems. Theory and Applications. – Cham: Birkhäuser, 2016.
– 351 p.
27. Dalton B., Wang A., Blainey B. SIMDizing pairwise sums: a summation algorithm balancing accuracy with throughput // Proceedings of the 2014 Workshop on Programming Models for SIMD/Vector Processing (WPMVP’14). – Orlando, Florida, USA: IEEE, 2014. – P. 65-70.
28. Harris M. Optimizing parallel reduction in CUDA. – URL: https://developer.download.nvidia.com/assets/cuda/files/reduction.pdf (дата обращения: 04.11.2018).
29. Isupov K., Knyazkov V. Interval Estimation of Relative Values in Residue Number System // Journal of Circuits, Systems and Computers. – 2018. – Vol. 27, No. 1. – P. 1850004.
30. Hauser J.R. Handling Floating-Point Exceptions in Numeric Programs // ACM Transactions on Programming Languages and Systems. – 1996. – Vol. 18, No. 2. – P. 139-174.
31. Исупов К.С., Князьков В.С., Куваев А.С. Эффективное масштабирование в системе остаточных классов с использованием интервальных оценок // Вычислительные технологии. – 2018. – Т. 23, № 3. –С. 39-57.
32. McNamee J.M. A comparison of methods for accurate summation // ACM SIGSAM Bull.
– 2004. – Vol. 38, No. 1. – P. 1-7.
33. Fousse L., Hanrot G., Lefèvre V., Pélissier P., Zimmermann P. MPFR: a multiple-precision binary floating-point library with correct rounding // ACM Transactions on Mathematical Software. – 2007. – Vol. 33, No. 2. Article No. 13.

Comments are closed.