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

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

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

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

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

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

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

Еще

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

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

IDR: 14336189

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

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.

Еще

Статья научная