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

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

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

Журнал: Программные системы: теория и приложения @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.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp