Исследование специальных наборов модулей системы остаточных классов
Владислав Вячеславович ЛУЦЕНКО,
Михаил Дмитриевич КРАВЦОВ,
Дмитрий Евгеньевич ГОРЛАЧЕВ,
Никита Михайлович МИРНЫЙ https://doi.org/10.15514/ISPRAS-2025-37(3)-7
Аннотация
В статье рассматриваются современные подходы к повышению производительности вычислительных систем на основе системы остаточных классов. Цель исследования – анализ специальных наборов модулей системы остаточных классов, которые позволяют проводить ключевые вычислительные операции, такие как сложение, обратное преобразование и определение знака, с минимальными затратами. Экспериментальные результаты показали, что базис {2^n-1,2^n,2^n+1} оказался наиболее эффективным среди трех модульных наборов. Данный базис является перспективным для использования в высокопроизводительных вычислительных системах.
Ключевые слова
система остаточных классов,
специальные наборы модулей,
Китайская теорема об остатках,
функция ядра Акушского.
При поддержке: Работа выполнена при поддержке Российского научного фонда (проект № 22-71-10046).
Об авторах
Владислав Вячеславович ЛУЦЕНКО
Северо-Кавказский федеральный университет
Россия
Россия
Аспирант, кафедры вычислительной математики и кибернетики факультета математики и компьютерных наук имени профессора Н.И. Червякова ФГАОУ ВПО «Северо-Кавказский федеральный университет». Сфера научных интересов: высокопроизводительные вычисления, система остаточных классов, умный город, нейронные сети, интернет вещей.
Михаил Дмитриевич КРАВЦОВ
Региональный центр «Сириус 26»
Россия
Россия
Является учеником регионального центра выявления, поддержки и развития способностей и талантов детей и молодежи Ставропольского края «Сириус 26». Сфера научных интересов: высокопроизводительные вычисления, система остаточных классов, компьютерные науки.
Дмитрий Евгеньевич ГОРЛАЧЕВ
Северо-Кавказский федеральный университет
Россия
Россия
Студент Северо-Кавказского Федерального университета, факультет математики и компьютерных наук имени профессора Н.И. Червякова. Сфера научных интересов: математика и компьютерные науки.
Никита Михайлович МИРНЫЙ
Северо-Кавказский федеральный университет
Россия
Россия
Студент Северо-Кавказского Федерального университета, факультет математики и компьютерных наук имени профессора Н.И. Червякова. Сфера научных интересов: математика и компьютерные науки.
Список литературы
1. Horowitz M., Grumbling E. Quantum Computing: Progress and Prospects. 2019.
2. Reuther A., Michaleas P., Jones M., Gadepally V., Samsi S., Kepner J. AI Accelerator Survey and Trends. In Proceedings of the 2021 IEEE High Performance Extreme Computing Conference (HPEC); IEEE, 2021; pp. 1–9.
3. Mohan P.V.A. Residue Number Systems; Springer International Publishing: Cham, 2016, ISBN 978-3-319-41383-9.
4. Амербаев В. М. Теоретические основы машинной арифметики. АлмаАта: Наука, 1976. 324 с. / Amerbayev V.M. Theoretical Foundations of Machine Arithmetic. Alma-Ata, Science 1976, 324 (in Russian).
5. Krasnobayev V., Kuznetsov A., Yanko A., Kuznetsova T. The Analysis of the Methods of Data Diagnostic in a Residue Number System. Computer Modeling and Intelligent Systems 2020, 2608, 594–609, doi:10.32782/cmis/2608-46.
6. Guo Z., Gao Z., Mei H., Zhao M., Yang J. Design and Optimization for Storage Mechanism of the Public Blockchain Based on Redundant Residual Number System. IEEE Access 2019, vol. 7, pp. 98546–98554, doi:10.1109/ACCESS.2019.2930125.
7. Su Y., Yang B.-L., Yang C., Zhao S.-Y. ReMCA: A Reconfigurable Multi-Core Architecture for Full RNS Variant of BFV Homomorphic Evaluation. IEEE Transactions on Circuits and Systems I: Regular Papers 2022, vol. 69, pp. 2857–2870, doi:10.1109/TCSI.2022.3163970.
8. Cardarilli G.C., Nunzio L.D., Fazzolari R., Nannarelli A., Petricca M., Re M. Design Space Exploration Based Methodology for Residue Number System Digital Filters Implementation. IEEE Transactions on Emerging Topics in Computing 2022, vol. 10, pp. 186–198, doi:10.1109/TETC.2020.2997067.
9. Chervyakov N.I., Molahosseini A.S., Lyakhov P.A., Babenko M.G., Deryabin M.A. Residue-to-Binary Conversion for General Moduli Sets Based on Approximate Chinese Remainder Theorem. International Journal of Computer Mathematics 2017, vol. 94, pp. 1833–1849, doi:10.1080/00207160.2016.1247439.
10. Omondi A.R., Premkumar A.B. Residue Number Systems: Theory And Implementation; World Scientific, 2007, ISBN 978-1-908979-11-7.
11. Chervyakov N., Babenko M., Tchernykh A., Kucherov N., Miranda-López V., Cortés-Mendoza J.M. AR-RRNS: Configurable Reliable Distributed Data Storage Systems for Internet of Things to Ensure Security. Future Generation Computer Systems 2019, vol. 92, pp. 1080–1092, doi:10.1016/j.future.2017.09.061.
12. Lutsenko V., Zgonnikov M. Fault Tolerant System for Data Storage, Transmission and Processing in Fog Computing Using Artificial Neural Networks. In Current Problems of Applied Mathematics and Computer Systems. Lecture Notes in Networks and Systems. Springer Nature Switzerland: Cham, 2024, vol. 1044, pp. 199–212, ISBN 978-3-031-64009-4.
13. Valueva M.V., Nagornov N.N., Lyakhov P.A., Valuev G.V., Chervyakov N.I. Application of the Residue Number System to Reduce Hardware Costs of the Convolutional Neural Network Implementation. Mathematics and Computers in Simulation 2020, vol. 177, pp. 232–243, doi:10.1016/j.matcom.2020.04.031.
14. Roohi A., Taheri M., Angizi S., Fan D. RNSiM: Efficient Deep Neural Network Accelerator Using Residue Number Systems. In Proceedings of the 2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD), November 2021, pp. 1–9.
15. Molahosseini A.S., Navi K. Study of the Reverse Converters for the Large Dynamic Range Four-Moduli Sets; InTech Press, 2011.
16. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. М., Советское радио, 1968, 440 c. / Akushsky I. Ya., Yuditsky D. I. Computer arithmetic in residual classes. Moscow, Soviet Radio, 1968, 440 p. (in Russian).
17. Shiriaev E., Kucherov N., Babenko M., Nazarov A. Fast Operation of Determining the Sign of a Number in RNS Using the Akushsky Core Function. Computation, 2023, vol. 11, issue 124, doi:10.3390/computation11070124.
18. Burgess N. Scaling an RNS Number Using the Core Function. In Proceedings of the 16th IEEE Symposium on Computer Arithmetic, 2003. Proceedings.; IEEE Comput. Soc: Santiago de Compostela, Spain, 2003, pp. 262–269.
19. Луценко В.В., Бабенко М.Г., Черных А.Н., Лапина М.А. Оптимизация алгоритма деления чисел в системе остаточных классов на основе функции ядра Акушского. Труды ИСП РАН, том 35, вып. 5, 2023 г., стр. 157–168. / Lutsenko V.V., Babenko M.G., Tchernykh A.N., Lapina, M.A. Optimization of a Number Division Algorithm in the Residue Number System Based on the Akushsky Core Function. Proceedings of the Institute for System Programming of the RAS, 2023, vol. 35, issue 5, pp. 157–168. (in Russian), DOI: 10.15514/ISPRAS–2023–35(5)–11.
20. Lutsenko V., Babenko M. High Speed Method of Conversion Numbers from Residue Number System to Positional Notation.
21. Lutsenko V., Zgonnikov M. Investigation of Neural Network Methods for Error Detection and Correction in the Residue Number System. In AISMA-2024: International Workshop on Advanced Information Security Management and Applications. Lecture Notes in Networks and Systems; Springer Nature Switzerland: Cham, 2024, vol. 863, pp. 194–206 ISBN 978-3-031-72170-0.
22. Shiriaev E., Kucherov N., Babenko M., Lutsenko V., Al-Galda S. Algorithm for Determining the Optimal Weights for the Akushsky Core Function with an Approximate Rank. Applied Sciences, 2023, vol. 13, 10495.
23. Szabo N.S., Tanaka R.I. Residue Arithmetic and Its Applications to Computer Technology, 1967.
24. Premkumar A.B. An RNS to Binary Converter in a Three Moduli Set with Common Factors. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 1995, vol. 42, pp. 298–301.
25. Pourbigharaz F. A Signed-Digit Architecture for Residue to Binary Transformation. IEEE Transactions on Computers, 1997, vol. 46, pp. 1146–1150.
26. Hiasat A.A., Abdel-Aty-Zohdy S.H. Residue-to-Binary Arithmetic Converter for the Moduli Set 2^k,2^k-1,2^(k-1)-1. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 1998, 45, 204–209.
27. Mathew J., Radhakrishnan D., Srikanthan T. Fast Residue-to-Binary Converter Architectures. In Proceedings of the 42nd Midwest Symposium on Circuits and Systems (Cat. No. 99CH36356). IEEE, 1999; vol. 2, pp. 1090–1093.
28. Molahosseini A.S., Navi K., Rafsanjani M.K. A New Residue to Binary Converter Based on Mixed-Radix Conversion. In Proceedings of the 2008 3rd International Conference on Information and Communication Technologies: From Theory to Applications, 2008, pp. 1–6.
29. Hariri A., Navi K., Rastegar R. A New High Dynamic Range Moduli Set with Efficient Reverse Converter. Computers & mathematics with applications 2008, vol. 55, pp. 660–668.
30. Molahosseini A.S., Navi K., Hashemipour O., Jalali A. An Efficient Architecture for Designing Reverse Converters Based on a General Three-Moduli Set. journal of Systems Architecture, 2008, vol. 54, pp. 929–934.
31. Hosseinzad M., Navi K. A New Moduli Set for Residue Number System in Ternary Valued Logic. Journal of Applied Sciences, 2007, vol. 7, pp. 3729–3735.
32. Bhardwaj M., Srikanthan T., Clarke C.T., Center M.D., Microelectronics S. Reverse Converter for the 4-Moduli Superset {2^n-1,2^n,2^n+1,2^(n+1)+1}. In Proceedings of the Proceedings of the IEEE Conference on Computer Arithmetic; Citeseer, 1999, vol. 14, pp. 168–175.
33. Vinod A.P., Premkumar A.B. A memoryless reverse converter for the 4-moduli superset {2^n-1,2^n,2^n+1,2^(n+1)-1}. J circuit syst comp, 2000, vol. 10, pp. 85–99, doi:10.1142/S0218126600000044.
34. Cao B., Chang C.-H., Srikanthan T. An Efficient Reverse Converter for the 4-Moduli Set {2^n-1,2^n,2^n+1,2^2n-1} Based on the New Chinese Remainder Theorem. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 2003, vol. 50, pp. 1296–1303.
35. Sheu M.-H., Lin S.-H., Chen C., Yang S.-W. An Efficient VLSI Design for a Residue to Binary Converter for General Balance Moduli {2^n-1,2^n+1,2^n-3,2^n+3}. IEEE Transactions on Circuits and Systems II: Express Briefs, 2004, vol. 51, pp. 152–155.
36. Zhang W., Siy P. An Efficient Design of Residue to Binary Converter for Four Moduli Set (2^n-1,2^n+1,2^2n-2,2^(2n+1)-3) Based on New CRT II. Information Sciences, 2008, vol. 178, pp. 264–279.
37. Molahosseini A.S., Navi K., Dadkhah C., Kavehei O., Timarchi S. Efficient Reverse Converter Designs for the New 4-Moduli Sets {2^n-1,2^n+1,2^n,2^2n+1} and {2^n-1,2^n+1〖,2〗^2n,2^(2n+1)-1} Based on New CRTs. IEEE Transactions on Circuits and Systems I: Regular Papers 2009, vol. 57, pp. 823–835.
38. Patronik P., Piestrak S.J. Design of Reverse Converters for General RNS Moduli Sets {2^k,2^n-1,2^n+1,2^(n+1)-1} and {2^k,2^n-1,2^n+1,2^(n+1)+1} (n Even). IEEE Transactions on Circuits and Systems I: Regular Papers, 2014, vol. 61, pp. 1687–1700.
39. Hiasat A.A. VLSI Implementation of New Arithmetic Residue to Binary Decoders. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2005, vol. 13, pp. 153–158.
40. Cao B., Chang C.-H., Srikanthan T. A Residue-to-Binary Converter for a New Five-Moduli Set. IEEE Transactions on Circuits and Systems I: Regular Papers, 2007, vol. 54, pp. 1041–1049.
41. Molahosseini A.S., Dadkhah C., Navi K. A. New Five-Moduli Set for Efficient Hardware Implementation of the Reverse Converter. IEICE Electronics Express, 2009, vol. 6, pp. 1006–1012.
42. Pettenghi H., Chaves R., Sousa L. RNS Reverse Converters for Moduli Sets with Dynamic Ranges up to (8n+1) -Bit. IEEE Transactions on Circuits and Systems I: Regular Papers, 2012, vol. 60, pp. 1487–1500.
43. Pettenghi H., Paludo R., Matos R., Lyakhov P.A. Efficient RNS Reverse Converters for Moduli Sets with Dynamic Ranges Up to (10n+1)(10N+1)-Bit. Circuits, Systems, and Signal Processing, 2018, vol. 37, pp. 5178–5196.
Рецензия
Для цитирования:
ЛУЦЕНКО В.В., КРАВЦОВ М.Д., ГОРЛАЧЕВ Д.Е., МИРНЫЙ Н.М. Исследование специальных наборов модулей системы остаточных классов. Труды Института системного программирования РАН. 2025;37(3):107-120. https://doi.org/10.15514/ISPRAS-2025-37(3)-7
For citation:
LUTSENKO V.V., KRAVTSOV M.D., GORLACHEV D.E., MIRNY N.M. Research of Special Sets of Moduli of the Residue Number System. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2025;37(3):107-120. (In Russ.) https://doi.org/10.15514/ISPRAS-2025-37(3)-7
Послать статью по эл. почте 