СУММИРОВАНИЕ МНОГОКРАТНОЙ ТОЧНОСТИ НА ЦЕНТРАЛЬНЫХ И ГРАФИЧЕСКИХ ПРОЦЕССОРАХ С ИСПОЛЬЗОВАНИЕМ БИБЛИОТЕКИ MPRES

К.С. Исупов; В.С. Князьков; А.С. Куваев

К.С. Исупов Вятский государственный университет
В.С. Князьков Вятский государственный университет
А.С. Куваев Вятский государственный университет

Ключевые слова: Компьютерная арифметика, высокоточные вычисления, суммирование;, система остаточных классов, программирование на графических процессорах

Аннотация

В научных расчетах часто требуется вычислять суммы больших массивов чисел с плавающей точкой. Суммирование лежит в основе многих базовых алгоритмов, таких как скалярное произведение, разложение функции в ряд Тейлора и численное интегрирование. Однако, из-за ошибок округления при использовании стандартной арифметики IEEE 754 вычисленный результат суммирования может оказаться крайне неточным. Одним из спо-собов уменьшения ошибок округления является использование библиотек многократной точности, предоставляющих структуры данных и подпрограммы обработки чисел, длина которых превышает форматы IEEE 754. В статье рассматриваются алгоритмы высо-коточного суммирования, реализованные в библиотеке MPRES (Multiple-Precision Residue-Based Arithmetic Library), которая позволяет выполнять операции с числами произвольной длины на центральных процессорах (CPU) и CUDA-совместимых графических процессорах видеокарты (GPU). В MPRES для представления многоразрядных мантисс чисел использу-ется система остаточных классов (СОК). В этой системе число представляется в виде остатков от деления исходной величины на выбранные модули, а операции над многораз-рядными числами разбиваются на группы операций меньшей разрядности над остатками, которые могут выполняться параллельно и без распространения переноса между остат-ками. В работе рассматривается алгоритм сложения многоразрядных чисел в MPRES, а также три алгоритма редукции (суммирования) массива чисел: (1) классическое рекурсив-ное суммирование, (2) попарное суммирование, (3) гибридное CPU-GPU суммирование. Экс-перименты показывают, что наибольшей производительностью обладает гибридный блочно-параллельный алгоритм. С другой стороны, параллельное вычисление цифр (остат-ков) многоразрядных мантисс в СОК позволяет сократить время вычислений.

Литература

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, pp. 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, pp. 132-143.
4. Higham N.J. The Accuracy of Floating Point Summation, SIAM Journal on Scientific Compu-ting, 1993, Vol. 14, No. 4, pp. 783-799.
5. Anderson I.J. A Distillation Algorithm for Floating-Point Summation, SIAM Journal on Scien-tific Computing, 1999, Vol. 20, No. 5, pp. 1797-1806.
6. Zhu Y.-K., Yong J.-H., Zheng G.-Q. A New Distillation Algorithm for Floating-Point Summa-tion, SIAM Journal on Scientific Computing, 2005, Vol. 26, No. 6, pp. 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, pp. 1955-1988.
8. Rump S.M. Ultimately Fast Accurate Summation, SIAM Journal on Scientific Computing, 2009, Vol. 31, No. 5, pp. 3466-3502.
9. Goodrich M.T., Eldawy A. Parallel Algorithms for Summing Floating-Point Numbers, Pro-ceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures. Pacific Grove, California, USA: ACM, 2016, pp. 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, pp. 163-172.
11. Demmel J., Nguyen H.D. Parallel reproducible summation, IEEE Transactions on Computers, 2015, Vol. 64, No. 7, pp. 2060-2070.
12. Collange S., Defour D., Graillat S., Iakymchuk R. Numerical reproducibility for the parallel re-duction on multi- and many-core architectures, Parallel Computing, 2015, Vol. 49, pp. 83-97.
13. Neal R.M. Fast Exact Summation Using Small and Large Superaccumulators, Technical re-port, University of Toronto, 2015. Available at: http://www.cs.toronto.edu/~ rad-ford/ftp/xsum.pdf (accessed 08 October 2018).
14. Kadric E., Gurniak P. and DeHon A. Accurate Parallel Floating-Point Accumulation, IEEE Transactions on Computers, 2016, Vol. 65, No. 11, pp. 3224-3238.
15. ReproBLAS: Reproducible BLAS. Available at: https://bebop.cs.berkeley.edu/reproblas/ in-dex.php (accessed 31 October 2018).
16. ExBLAS – Exact BLAS. Available at: https://exblas.lip6.fr/ (accessed 31 October 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, pp. 10106-10121.
18. Joldes M., Muller J.M., Popescu V. Implementation and Performance Evaluation of an Ex-tended Precision Floating-Point Arithmetic Library for High-Accuracy Semidefinite Pro-gramming, Proceedings of the 24th IEEE Symposium on Computer Arithmetic (ARITH). Lon-don, UK: IEEE. 2017, pp. 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, pp. 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). Indi-anapolis, Indiana, USA: ACM, 2010, pp. 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 Com-puter Science. Springer, 2017, Vol. 10421, pp. 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, pp. 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. Available at: https://www.osti.gov/biblio/817634 (accessed 25 October 2018).
24. Akushskiy I.Ya., Yuditskiy D.I. Mashinnaya arifmetika v ostatochnykh klassakh [Machine arithmetic in residual classes]. Moscow: Sov. Radio, 1968, 440 p.
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, pp. 65-70.
28. Harris M. Optimizing parallel reduction in CUDA. Available at: https://developer.download.nvidia.com/assets/cuda/files/reduction.pdf (accessed 04 November 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, pp. 1850004.
30. Hauser J.R. Handling Floating-Point Exceptions in Numeric Programs, ACM Transactions on Programming Languages and Systems, 1996, Vol. 18, No. 2, pp. 139-174.
31. Isupov K.S., Knyaz'kov V.S., Kuvaev A.S. Effektivnoe masshtabirovanie v sisteme ostatochnykh klassov s ispol'zovaniem interval'nykh otsenok [Effective scaling in the system of residual classes using interval estimates], Vychislitel'nye tekhnologii [Computational tech-nologies], 2018, Vol. 23, No. 3, pp. 39-57.
32. McNamee J.M. A comparison of methods for accurate summation, ACM SIGSAM Bull, 2004, Vol. 38, No. 1, pp. 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 Soft-ware, 2007, Vol. 33, No. 2, Article No. 13.