Поиск оптимальных весов для функции ядра Акушского

Владислав Вячеславович Луценко, Дмитрий Евгеньевич Горлачев, Никита Михайлович Мирный, Михаил Григорьевич Бабенко

Аннотация


Современные вычислительные задачи, связанные с обработкой больших чисел, требуют не только высокой точности, но и значительной скорости. В этом контексте использование системы остаточных классов предлагает подход к параллельной обработке больших данных, применяемый в криптографии, обработке сигналов и искусственных нейронных сетях. Несмотря на преимущества системы остаточных классов, ее распространение замедленно в связи с вычислительной сложностью так называемых немодульных операций системы остаточных классов. Одним из универсальных инструментов для реализации немодульных операций является функция ядра Акушского. В работе исследуется функция ядра Акушского как инструмент для определения позиционной характеристики числа в системе остаточных классов. Для поиска оптимальных весов функции ядра предложено применение метода Монте-Карло и генетического алгоритма. Экспериментальные результаты демонстрируют, что генетический алгоритм обеспечивает более стабильные результаты при увеличении количества модулей, в то время как метод Монте-Карло эффективен на малых размерностях. Генетический алгоритм в среднем на 38% быстрее метода Монте-Карло, что делает его предпочтительным выбором. Дополнительно проведено сравнение времени вычисления функции ядра с оптимальными весами и функции Пирло. Результаты показали, что функция ядра с оптимальными весами в среднем на 14% быстрее функции Пирло.

Ключевые слова


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

Полный текст:

PDF

Литература


Schoinianakis D. Residue arithmetic systems in cryptography: a survey on modern security applications. Journal of Cryptographic Engineering. 2020. Vol. 10, no. 3. P. 249–267. DOI: 10.1007/s13389-020-00231-w.

Cardarilli G.C., Nunzio L.D., Fazzolari R. An RNS-based initial absolute position

estimator for Electrical Encoders. IEEE Access. 2023. Vol. 11. P. 98586–98595. DOI: 10.1109/access.2023.3312619.

Mohan P.V.A. Residue number systems: algorithms and architectures. Springer Science & Business Media, 2002.

Omondi A.R., Premkumar A.B. Residue number systems: theory and implementation. World Scientific, 2007. Vol. 2.

Bajard J.C., Eynard J. RNS Approach in Lattice-Based Cryptography. Embedded Systems Design with Special Arithmetic and Number Systems. 2017. P. 345–368. DOI: 10.1007/978-3-319-49742-6_13.

Valueva M.V., Nagornov N.N., Lyakhov P.A., et al. Application of the residue number system to reduce hardware costs of the convolutional neural network implementation. Mathematics and Computers in Simulation. 2020. Vol. 177. P. 232–243. DOI: 10.1016/j.matcom.2020.04.031.

Roohi A., Taheri M.R., Angizi S., et al. Rnsim: Efficient deep neural network accelerator using residue number systems. 2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD). IEEE, 2021. P. 1–9. DOI: 10.1109/iccad51958.2021.9643531.

Lutsenko V., Babenko M., Deryabin M. Construction of Akushsky Core Functions Without Critical Cores. Mathematics. 2024. Vol. 12, no. 21. P. 3399. DOI: 10.3390/math12213399.

Lutsenko V.V., Babenko M.G., Khamidov M.M. High speed method of conversion numbers from residue number system to positional notation. Proceedings of the Institute for System Programming of the RAS. 2024. Vol. 36, no. 4. P. 117–132. DOI: 10.15514/ispras-2024-36(4)-9.

Shiriaev E., Kucherov N., Babenko M., et al. Fast operation of determining the sign of a number in RNS using the Akushsky core function. Computation. 2023. Vol. 11, no. 7. P. 124. DOI: 10.3390/computation11070124.

Lutsenko V., Geryugova A., Babenko M., et al. High-Speed Parity Number Detection Algorithm in RNS Based on Akushsky Core Function. International Conference on Communication and Computational Technologies / eds. by S. Kumar, S. Hiranwal, R. Garg, S.D. Purohit. Cham: Springer, Singapore, 2024. P. 491–504. DOI: 10.1007/978-981-97-7423-4_38.

Lutsenko V.V., Babenko M.G., Chernykh A.N., Lapina M.A. Optimization of a number division algorithm in the residue number system based on the Akushsky core function. Proceedings of ISP RAS. 2023. Vol. 35, no. 5. P. 157–168. (in Russian) DOI: 10.15514/ispras-2022-35(5)-11.

Wang Y. Residue-to-binary converters based on new Chinese remainder theorems. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing. 2000. Vol. 47, no. 3. P. 197–205. DOI: 10.1109/82.826745.

Akushskiy I.Ya., Burtsev V.M., Pak I.T. About new positional characteristic of nonpositional code and its application. Theory of Coding and Optimisation of Complex Systems. Alma-Ata, Nauka, KazSSR. 1977. P. 8–16. (in Russian)

Metropolis N., Ulam S. The Monte Carlo method. Journal of the American Statistical Association. 1949. Vol. 44. no. 247. P. 335–341.

Kroese D.P., Brereton T., Taimre T., et al. Why the Monte Carlo method is so important today. Wiley Interdisciplinary Reviews: Computational Statistics. 2014. Vol. 6, no. 6. P. 386–392. DOI: 10.1002/wics.1314.

Shiriaev E., Kucherov N., M Babenko M., et al. Algorithm for determining the optimal weights for the Akushsky core function with an approximate rank. Applied Sciences. 2023. Vol. 13, no. 18. P. 10495. DOI: 10.3390/app131810495.

Kureichik V.M. Genetic algorithms. Izvestiya Yuzhny Federal University. Technical Sciences. 1998. Vol. 8, no. 2. P. 4–7. (in Russian)

Mirjalili S. Evolutionary algorithms and neural networks. Studies in Computational Intelligence. 2019. Vol. 780, no. 1. P. 43–53. DOI: 10.1007/978-3-319-93025-1.

Pirlo G., Impedovo D. A new class of monotone functions of the residue number system. International Journal of Mathematical Models and Methods in Applied Sciences. 2013. Vol. 7, no. 9. P. 802–809.




DOI: http://dx.doi.org/10.14529/cmse250202