Арифметика многократной точности на основе систем остаточных классов

Исупов Константин Сергеевич, Князьков Владимир Сергеевич; Isupov Konstantin, Knyazkov Vladimir

Научные статьи \ Общие вопросы науки и культуры \ Информационные технологии. Вычислительная техника. Обработка данных \ Прикладные информационные (компьютерные) технологии. Методы основанные на применении компьютеров

Арифметика многократной точности на основе систем остаточных классов

Автор: Исупов Константин Сергеевич, Князьков Владимир Сергеевич

Журнал: Программные системы: теория и приложения @programmnye-sistemy

Рубрика: Методы оптимизации и теория управления

Статья в выпуске: 1 (28) т.7, 2016 года.

Бесплатный доступ

В работе рассматриваются алгоритмы высокоточной арифметики, основанные на использовании многомодульных систем остаточных классов (СОК) для представления мантисс чисел с плавающей точкой произвольной разрядности; порядок хранится в двоичной системе счисления. Такое представление обеспечивает большой динамический диапазон и допускает эффективное распараллеливание арифметических операций над цифрами многоразрядных мантисс по модулям СОК, что хорошо согласуется с особенностями архитектуры современных параллельных вычислительных систем. Дополнительно, в числовой формат включена атрибутивная информация, которая обеспечивает быструю оценку величины мантиссы, масштабированной относительно произведения модулей, и способствует ускоренному выполнению целого ряда проблемных для СОК немодульных процедур, таких как сравнение, контроль переполнения диапазона, округление и пр. Представлены результаты экспериментальной оценки точности и быстродействия алгоритмов, а также эффективности использования SIMD

Еще

Высокоточные вычисления, компьютерная арифметика, параллельные алгоритмы, система остаточных классов

Короткий адрес: https://sciup.org/14336189

IDR: 14336189

Parallel multiple-precision arithmetic based on residue number system

The paper considers algorithms of high-precision arithmetic based on the use of multimodular residual class systems (SOK) for the representation of mantissas of numbers with a floating point of arbitrary digit capacity; the order is stored in binary notation. Such a representation provides a large dynamic range and allows efficient parallelization of arithmetic operations over digits of multi-digit mantissas on SOK modules, which agrees well with the features of the architecture of modern parallel computing systems. Additionally, attribute information is included in the numerical format, which provides a quick estimate of the magnitude of the mantissa scaled with respect to the product of the modules, and facilitates the accelerated implementation of a number of non-modular procedures, such as comparison, overflow control, rounding, etc., which are problematic for SOK. and speed of algorithms, as well as the efficiency of using SIMD

Еще

Список литературы Арифметика многократной точности на основе систем остаточных классов

S. Collange, D. Defour, S. Graillat, R. Iakymchuk. "Reproducible and Accurate Matrix Multiplication for High-Performance Computing", 16th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, SCAN’2014 (Wurzburg, Germany, 2014). P. 42-43.
S. Collange, D. Defour, S. Graillat, R. Iakymchuk. "Numerical Reproducibility for the Parallel Reduction on Multi-and Many-Core Architectures", Parallel Computing, 49 2015. P. 83-97.
J. Demmel, H. D. Nguyen. "Parallel Reproducible Summation", IEEE Transactions on Computers, V. 64. No. 7. 2015. P. 2060-2070.
A. Pescaru, E. Oanta, T. Axinte, A. D. Dascalescu. "Extended Precision Data Types for the Development of the Original Computer Aided Engineering Applications", IOP Conference Series: Materials Science and Engineering, V. 95. No. 1. 2015, URL: http://stacks.iop.org/1757-899X/95/i=1/a=012125.
D. H. Bailey, R. Barrio, J. M. Borwein. "High-Precision Computation: Mathematical Physics and Dynamics", Applied Mathematics and Computation, V. 218. No. 20. 2012. P. 10106-10121.
D. H. Bailey, J. M. Borwein. "High-Precision Arithmetic in Mathematical Physics", Mathematics, 3 2015. P. 337-367.
D. Viswanath, S. Sahut˘ oglu. "Complex Singularities and the Lorenz Attractor", SIAM Review, 52 2010. P. 294-314.
S. Leweke, E. von Lieres. "Fast Arbitrary Order Moments and Arbitrary Precision Solution of the General Rate Model of Column Liquid Chromatography With Linear Isotherm", Computers & Chemical Engineering, 84 2016. P. 350-362.
Y. He, C. Ding. "Using Accurate Arithmetics to Improve Numerical Reproducibility and Stability in Parallel Applications", The Journal of Supercomputing, 18 2001. P. 259-277.
C. F. Berger, Z. Bern, L. J. Dixon, C. F. Febres, D. Forde, H. Ita, D. A. Kosower, D. Maitre. "Automated Implementation of On-shell Methods for One-loop Amplitudes", Physical Review D, 78 2008.
J.-P. Merlet. "On the Real-Time Calculation of the Forward Kinematics of Suspended Cable-Driven Parallel Robots", 14th World Congress in Mechanism and Machine Science (Taipei, Taiwan, 2015).
В. Л. Якушев, В. Н. Симбиркин, А. В. Филимонов, П. А. Новиков, И. Н. Коньшин, Г. Б. Сушко, С. А. Харченко. Решение плохообусловленных симметричных СЛАУ для задач строительной механики параллельными итерационными методами//Вестник ННГУ, 2012, №4(1). С. 238-246.
R. Brent, P. Zimmermann. Modern Computer Arithmetic, Cambridge University Press, New York, NY, USA, 2010, 236 p.
Н. Н. Непейвода, И. Н. Григоревский, Е. П. Лилитко. О представлении действительных чисел//Программные системы: теория и приложения, Т. 5, №. 4(22). 2014. С. 105-121, URL: http://psta.psiras.ru/read/psta2014_4_105-121.pdf.
N. S. Szabo, R. I. Tanaka. Residue Arithmetic and its Application to Computer Technology, McGraw-Hill, New York, NY, USA, 1967, 236 p.
И. Я. Акушский, Д. И. Юдицкий. Машинная арифметика в остаточных классах, Сов. Радио, М., 1968, 440 с.
B. Parhami. Computer Arithmetic: Algorithms and Hardware Designs, Oxford University Press, Oxford, 2000, 490 p.
A. Omondi, B. Premkumar. Residue Number Systems: Theory and Implementation, Imperial College Press, London, UK, 2007, 312 p.
K. Isupov, V. Knyazkov. "A Modular-Positional Computation Technique for Multiple-Precision Floating-Point Arithmetic", Parallel Computing Technologies, Lecture Notes in Computer Science, vol. 9251, Springer International Publishing, 2015. P. 47-61.
К. С. Исупов, А. Н. Мальцев. Способ представления чисел с плавающей точкой большой разрядности, ориентированный на параллельную обработку//Вычислительные методы и программирование, Т. 15, №. 4. 2014. С. 631-643.
M. Akkal, P. Siy. "A New Mixed Radix Conversion Algorithm MRC-II", Journal of Systems Architecture, V. 53. No. 9. 2007. P. 577-586.
G. Dimauro, S. Impedovo, G. Pirlo. "A New Technique for Fast Number Comparison in the Residue Number System", IEEE Transactions on Computers, V. 42. No. 5. 1993. P. 608-612.
G. Pirlo, S. Impedovo. "A New Class of Monotone Functions of the Residue Number System", International Journal of Mathematical Models and Methods in Applied Sciences, V. 7. No. 9. 2013. P. 802-809.
J.-H. Yang, C.-C. Chang, C.-Y. Chen. "A High-Speed Division Algorithm in Residue Number System Using Parity-Checking Technique", International Journal of Computer Mathematics, V. 81. No. 6. 2004. P. 775-780.
C. Y. Hung, B. Parhami. "An Approximate Sign Detection Method for Residue Numbers and Its Application to RNS Division", Computers & Mathematics with Applications, V. 27. No. 4. 1994. P. 23-35.
J.-M. Muller, N. Brisebarre, F. de Dinechin, C.-P. Jeannerod, V. Lefèvre, G. Melquiond, N. Revol, D. Stehl´e, S. Torres. Handbook of Floating-Point Arithmetic, Birkhauser, Boston, 2010, 572 p.
U. Kulisch. Computer Arithmetic and Validity -Theory, Implementation and Applications, de Gruyter, Berlin, 2008, 409 p.
К. С. Исупов. Об одном алгоритме сравнения чисел в системе остаточных классов//Вестник АГТУ. Серия "Управление, вычислительная техника и информатика", 2014, №3. С. 40-49.
J. R. Hauser. "Handling Floating-Point Exceptions in Numeric Programs", ACM Transactions on Programming Languages and Systems, V. 18. No. 2. 1996. P. 139-174.
IEEE Standard for Floating-Point Arithmetic. Introduced 2008-08-29, Institute of Electrical and Electronics Engineers, New York, NY, USA, 2008, 70 p.
M. F. Cowlishaw. "Decimal Floating-Point: Algorism for Computers", 16th IEEE Symposium on Computer Arithmetic, ARITH-16’03, IEEE Computer Society, Washington, DC, USA, 2003. P. 140-147.
M. D. Ercegovac, T. Lang, Digital Arithmetic, The Morgan Kaufmann Series in Computer Architecture and Design, Morgan Kaufmann, San Francisco, 2004, 709 p.
L. Fousse, G. Hanrot, V. Lefèvre, P. P´elissier, P. Zimmermann. "MPFR: A Multiple-Precision Binary Floating-Point Library With Correct Rounding", ACM Transactions on Mathematical Software, V. 33. No. 2. 2007.
S. M. Rump. "Algorithms for Verified Inclusions -Theory and Practice", Reliability in Computing: The Role of Interval Methods in Scientific Computing, ed. R. E. Moore, Academic Press Professional, San Diego, CA, USA, 1988. P. 109-126.
W. Kahan. How Futile are Mindless Assessments of Roundoff in Floating-Point Computation, https://www.cs.berkeley.edu/~wkahan/Mindless.pdf, 2006.
I. Kong, E. E. Swartzlander. "A Goldschmidt Division Method With Faster Than Quadratic Convergenc", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, V. 19. No. 4. 2011. P. 696-700.

Еще