Метод умножения с масштабированием результата для высокоточных модулярно-позиционных интервально-логарифмических вычислений

Метод умножения с масштабированием результата для высокоточных модулярно-позиционных интервально-логарифмических вычислений

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

Журнал: Инженерные технологии и системы @vestnik-mrsu

Рубрика: Информационные системы

Статья в выпуске: 2, 2019 года.

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

Введение. Для решения задач моделирования, критичных к ошибкам округления (включая задачи вычислительной математики, математической физики, оптимального управления, биохимии, квантовой механики, математического программирования и криптографии), требуется точность от 100 до 1 000 десятичных цифр и более. Главным недостатком программных библиотек высокоточных вычислений является неприемлемое для практических задач снижение быстродействия, в особенности при выполнении операции умножения. Одним из способов повышения скорости вычислений над длинными числами является использование системы счисления в остаточных классах. В данной статье рассматривается новый, более быстрый по сравнению с аналогами метод выполнения операции умножения длинных чисел с масштабированием результата за счет применения оригинальной гибридной модулярно-позиционной интервально-логарифмической формы представления чисел с плавающей точкой. Материалы и методы. Для повышения скорости вычислений разработан новый способ организации числовой информации (модулярно-позиционная интервально-логарифмическая форма), в котором мантисса представлена в системе остаточных классов, а информация об абсолютной величине числа (характеристика) - в интервально-логарифмической системе счисления, что позволяет ускорить выполнение операций сравнения и масштабирования. Для сравнения модулярных чисел применяются положения интервального анализа; для масштабирования модулярных чисел - свойства логарифмической системы счисления, а также приближенные интервальные вычисления с использованием китайской теоремы об остатках. Результаты исследования. Разработан и запатентован новый быстрый метод умножения модулярных чисел с плавающей точкой, проведена оценка быстродействия разработанного метода, выполнено сравнение данного метода с классическими и конвейерными методами умножения длинных чисел. Обсуждение и заключение. Разработанный метод в 2,4-1,0 раза быстрее конвейерного метода умножения и в 6,4-12,9 раз - классических методов умножения.

Еще

Система остаточных классов, высокоточное вычисление, умножение чисел, масштабирование, интервальная арифметика, сравнение чисел, логарифмическая система счисления

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

IDR: 147220614   |   УДК: 004.272.34   |   DOI: 10.15507/2658-4123.029.201902.187-204

The multiplication method with scaling the result for high-precision residue positional interval logarithmic computations

Introduction. The solution of the simulation problems critical to rounding errors, including the problems of computational mathematics, mathematical physics, optimal control, biochemistry, quantum mechanics, mathematical programming and cryptography, requires the accuracy from 100 to 1 000 decimal digits and more. The main lack of high-precision software libraries is a significant decrease of the speed-in-action, unacceptable for practical problems, in particular, when performing multiplication. A way to increase computation performance over very long numbers is using the residue number system. In this work, we discuss a new fast multiplication method with scaling the result using original hybrid residue positional interval logarithmic floating-point number representation. Materials and Methods. The new way of the organizing numerical information is a residue positional interval logarithmic number representation in which the mantissa is presented in the residue number system, and information on an absolute value (the characteristic) in the interval logarithmic number system that makes it possible to accelerate performance of comparison and scaling is developed to increase the speed of calculations; to compare modular numbers, the provisions of interval analysis are used; to scale modular numbers, the properties of the logarithmic number system and approximate interval calculations using the Chinese reminder theorem are used. Results. A new fast multiplication method of floating-point residue-represented numbers is developed and patented; the authors evaluated the developed method speed-in action, compared the developed method with classical and pipelined multiplication methods of long numbers. Discussion and Conclusion. The developed method is 2.4-1.0 times faster than the pipelined multiplication method, and is 6.4-12.9 times faster than classical multiplication methods.

Еще

Список литературы Метод умножения с масштабированием результата для высокоточных модулярно-позиционных интервально-логарифмических вычислений

  • Reproducible and accurate matrix multiplication / R. Iakymchuk [et al.] // Scientific Computing, Computer Arithmetic, and Validated Numerics. SCAN 2015 / Eds. M. Nehmeier, J. Wolff von Gudenberg, W. Tucker. Lecture Notes in Computer Science. 2016. Vol. 9553. P. 126-137. DOI: 10.1007/978-3-319-31769-4_11
  • Voros A. Discretized Keiper/Li approach to the Riemann hypothesis // Experimental Mathematics. 2018. P. 1-18. DOI: 10.1080/10586458.2018.1482480
  • solveME: fast and reliable solution of nonlinear ME models / L. Yang [et al.] // BMC Bioinfor-matics. 2016. Vol. 17. P. 391. DOI: 10.1186/s12859-016-1240-1
  • Panzer E. Algorithms for the symbolic integration of hyperlogarithms with applications to Feynman integrals // Computer Physics Communications. 2015. Vol. 188. P. 148-166. DOI: 10.1016/j.cpc.2014.10.019
  • Miltenberger M., Ralphs T., Steffy D. E. Exploring the numerics of branch-and-cut for mixed integer linear optimization // Operations Research Proceedings 2017. Operations Research Proceedings (GOR (Gesellschaft fur Operations Research e.V.)) / Eds. N. Kliewer, J. Ehmke, R. Borndorfer. Cham: Springer, 2018. P. 151-157. DOI: 10.1007/978-3-319-89920-6_21
  • Computer discovery and analysis of large Poisson polynomials / D. H. Bailey [et al.] // Experimental Mathematics. 2017. Vol. 26, no. 3. P. 349-363.
  • DOI: 10.1080/10586458.2016.1180565
  • Pan B., Wang Y., Tian S. A high-precision single shooting method for solving hypersensitive optimal control problems // Mathematical Problems in Engineering. 2018. Vol. 2018. Article ID 7908378.
  • DOI: 10.1155/2018/7908378
  • 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. 10.1142/ S0218126618500044
  • DOI: 10.1142/S0218126618500044
  • GRAPE-MPs: implementation of an SIMD for quadruple/hexuple/octuple-precision arithmetic operation on a structured ASIC and an FPGA / N. Nakasato [et al.] // 2012 IEEE 6th International Symposium on Embedded Multicore SoCs. IEEE, 2012. P. 75-83.
  • DOI: 10.1109/MCSoC.2012.31
  • Application of GRAPE9-MPX for high precision calculation in particle physics and performance results / H. Daisaka [et al.] // Procedia Computer Science. 2015. Vol. 51. P. 1323-1332.
  • DOI: 10.1016/j.procs.2015.05.317
  • El-Araby E., Gonzalez I., El-Ghazawi T. Bringing high-performance reconfigurable computing to exact computations // 2007 International Conference on Field Programmable Logic and Applications / Eds. K. Bertels [et al.]. IEEE, 2007. P. 79-85.
  • DOI: 10.1109/FPL.2007.4380629
  • Lei Y., Dou Y., Zhou J. FPGA-specific custom VLIW architecture for arbitrary precision floatingpoint arithmetic // IEICE Transactions on Information and Systems. 2011. Vol. 94, no. 11. P. 2173-2183.
  • DOI: 10.1587/transinf.E94.D.2173
  • Fast modular arithmetic on the Kalray MPPA-256 processor for an energy-efficient implementation of ECM / M. Ishii [et al.] // IEEE Transactions on Computers. 2017. Vol. 66, issue 12. P. 2019-2030.
  • DOI: 10.1109/TC.2017.2704082
  • Schulte M. J., Swartzlander E. E. A family of variable-precision interval arithmetic processors // IEEE Transactions on Computers. 2000. Vol. 49, issue 5. P. 387-397.
  • DOI: 10.1109/12.859535
  • Asif S., Kong Y. Highly parallel modular multiplier for elliptic curve cryptography in residue number system // Circuits, Systems, and Signal Processing. 2017. Vol. 36, issue 3. P. 1027-1051.
  • DOI: 10.1007/s00034-016-0336-1
  • Kong Y., Lai Y. Low latency modular multiplication for public-key cryptosystems using a scalable array of parallel processing elements // 2013 IEEE 56th International Midwest Symposium on Circuits and Systems (MWSCAS). IEEE, 2013. P. 1039-1042.
  • DOI: 10.1109/MWSCAS.2013.6674830
  • Coleman J. N., Che Ismail R. LNS with co-transformation competes with floating-point // IEEE Transactions on Computers. 2016. Vol. 65, issue 1. P. 136-146.
  • DOI: 10.1109/TC.2015.2409059
  • Kouretas I., Basetas C., Paliouras V. Low-power logarithmic number system addition/subtraction and their impact on digital filters // IEEE Transactions on Computers. 2013. Vol. 62, issue 11. P. 2196-2209.
  • DOI: 10.1109/TC.2012.111
  • The European logarithmic microprocesor / J. N. Coleman [et al.] // IEEE Transactions on Computers. 2008. Vol. 57, issue 4. P. 532-546.
  • DOI: 10.1109/TC.2007.70791
  • Bigou K., Tisserand A. Single base modular multiplication for efficient hardware RNS implementations of ECC // Cryptographic Hardware and Embedded Systems - CHES 2015 / Eds. T. Guneysu, H. Handschuh. Lecture Notes in Computer Science. 2015. Vol. 9293. P. 123-140.
  • DOI: 10.1007/978-3-662-48324-4_7
  • Bajard J.-C., Eynard J., Merkiche N. Montgomery reduction within the context of residue number system arithmetic // Journal of Cryptographic Engineering. 2018. Vol. 8, issue 3. P. 189-200.
  • DOI: 10.1007/s13389-017-0154-9
  • Czyzak M., Smyk R., Ulman Z. Pipelined scaling of signed residue numbers with the mixed-radix conversion in the programmable gate array // Poznan University of Technology Academic Journals. Electrical Engineering. 2013. No. 76. P. 89-99. URL: https://yadda.icm.edu.pl/baztech/element/bwmeta1. element.baztech-5d0a87e2-2459-476f-8c7e-2d72d07072f2/c/Czyzak.pdf
  • A fully RNS based ECC processor / S. Asif [et al.] // Integration. 2018. Vol. 61. P. 138-149.
  • DOI: 10.1016/j.vlsi.2017.11.010
  • Pipelined FPGA coprocessor for elliptic curve cryptography based on residue number system / P. M. Matutino [et al.] // 2017 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS) / Eds. Y. Patt, S. K. Nandy. IEEE, 2017. P. 261-268. https://
  • DOI: 10.1109/SAMOS.2017.8344638
  • Коржавина А. С., Князьков В. С. Методы расширения базиса в системе остаточных классов: обзор и анализ вычислительной сложности // Современные наукоемкие технологии. 2017. № 12. С. 37-42. URL: https://www.top-technologies.ru/ru/article/view?id=36868
  • Harvey D., van der Hoeven J., Lecerf G. Even faster integer multiplication // Journal of Complexity. 2016. Vol. 36. P. 1-30.
  • DOI: 10.1016/j.jco.2016.03.001
  • Chang C. H., Low J. Y. S. Simple, fast, and exact RNS scaler for the three-moduli set (2n - 1, 2n, 2n 1) // IEEE Transactions on Circuits and Systems I: Regular Papers. 2011. Vol. 58, issue 11. P. 2686-2697.
  • DOI: 10.1109/TCSI.2011.2142950
  • Hiasat A. Efficient RNS scalers for the extended three-moduli set (2n - 1, 2n p, 2n 1) // IEEE Transactions on Computers. 2017. Vol. 66, issue 7. P. 1253-1260.
  • DOI: 10.1109/TC.2017.2652474
  • Kong Y., Phillips B. Fast scaling in the residue number system // IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2009. Vol. 17, issue 3. P. 443-447. https://doi.oig/
  • DOI: 10.1109/TVLSI.2008.2004550
  • Meyer-Base U., Stouraitis T. New power-of-2 RNS scaling scheme for cell-based IC design // IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2003. Vol. 11, issue 2. P. 280-283.
  • DOI: 10.1109/TVLSI.2003.810799
  • Johansson F. Arb: efficient arbitrary-precision midpoint-radius interval arithmetic // IEEE Transactions on Computers. 2017. Vol. 66, issue 8. P. 1281-1292.
  • DOI: 10.1109/TC.2017.2690633
  • Revol N. Introduction to the IEEE 1788-2015 standard for interval arithmetic // Numerical Software Verification. NSV 2017 / Eds. A. Abate, S. Boldo. Lecture Notes in Computer Science. 2017. Vol. 10381. P. 14-21.
  • DOI: 10.1007/978-3-319-63501-9_2
  • Osinin I. A modular-logarithmic coprocessor concept // 2017 International Conference on High Performance Computing & Simulation (HPCS). IEEE, 2017. P. 588-594.
  • DOI: 10.1109/HPCS.2017.93
  • Способ организации выполнения операции умножения двух чисел в модулярно-логариф-мическом формате представления с плавающей точкой на гибридных многоядерных процессорах: пат. 2666285 Рос. Федерация: МПК G 06 F 7/483, G 06 F 7/487 / Князьков В. С., Коржави-на А. С.; заявитель и патентообладатель ФГБОУ ВО «Вятский государственный университет». № 2017135775/22; заявл. 06.10.2017; опубл. 06.09.2018, Бюл. № 25.
Еще
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp