Метод умножения с масштабированием результата для высокоточных модулярно-позиционных интервально-логарифмических вычислений
Автор: Коржавина Анастасия Сергеевна, Князьков Владимир Сергеевич
Журнал: Инженерные технологии и системы @vestnik-mrsu
Рубрика: Информационные системы
Статья в выпуске: 2, 2019 года.
Бесплатный доступ
Введение. Для решения задач моделирования, критичных к ошибкам округления (включая задачи вычислительной математики, математической физики, оптимального управления, биохимии, квантовой механики, математического программирования и криптографии), требуется точность от 100 до 1 000 десятичных цифр и более. Главным недостатком программных библиотек высокоточных вычислений является неприемлемое для практических задач снижение быстродействия, в особенности при выполнении операции умножения. Одним из способов повышения скорости вычислений над длинными числами является использование системы счисления в остаточных классах. В данной статье рассматривается новый, более быстрый по сравнению с аналогами метод выполнения операции умножения длинных чисел с масштабированием результата за счет применения оригинальной гибридной модулярно-позиционной интервально-логарифмической формы представления чисел с плавающей точкой. Материалы и методы. Для повышения скорости вычислений разработан новый способ организации числовой информации (модулярно-позиционная интервально-логарифмическая форма), в котором мантисса представлена в системе остаточных классов, а информация об абсолютной величине числа (характеристика) - в интервально-логарифмической системе счисления, что позволяет ускорить выполнение операций сравнения и масштабирования. Для сравнения модулярных чисел применяются положения интервального анализа; для масштабирования модулярных чисел - свойства логарифмической системы счисления, а также приближенные интервальные вычисления с использованием китайской теоремы об остатках. Результаты исследования. Разработан и запатентован новый быстрый метод умножения модулярных чисел с плавающей точкой, проведена оценка быстродействия разработанного метода, выполнено сравнение данного метода с классическими и конвейерными методами умножения длинных чисел. Обсуждение и заключение. Разработанный метод в 2,4-1,0 раза быстрее конвейерного метода умножения и в 6,4-12,9 раз - классических методов умножения.
Система остаточных классов, высокоточное вычисление, умножение чисел, масштабирование, интервальная арифметика, сравнение чисел, логарифмическая система счисления
Короткий адрес: https://sciup.org/147220614
IDR: 147220614 | DOI: 10.15507/2658-4123.029.201902.187-204
Список литературы Метод умножения с масштабированием результата для высокоточных модулярно-позиционных интервально-логарифмических вычислений
- 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.
