scienceitНаука. Инновации. ТехнологииScience. Innovations. Technologies2308-4758North-Caucasus Federal Universityscienceit-429Research ArticleФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИPHYSICAL AND MATHEMATICAL SCIENCESК быстрому выполнению комплексных компонентов системы остаточных классов на программируемых вентильных матрицахTowards Fast Implementation of Complex RNS Components on FPGAsAmirSabbagh MolahosseiniAmirSabbagh MolahosseiniSabbagh.iauk@gmail.comAzadehAlsadat EmraniAzadehAlsadat Emranisabbagh@iauk.ac.irИсламский университет АзадРоссияIslamic Azad UniversityRussian Federation201406092022048695Copyright © Amir S.M., Azadeh A.E., 20222022Amir S.M., Azadeh A.E.Amir S.M., Azadeh A.E.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://scienceit.elpub.ru/jour/article/view/429

Эффективное исполнение системы остаточных классов (RNS) в част-ности на программируемых вентильных матрицах (FPGA) очень важно в виду использования FPGA в некоторых современных вычислительных системах для достижения гибкости и малых временных затрат на разработку. Система остаточных классов со свойственным ей паралле-лизмом также может быть использована для увеличения производительности выполнения вы-числительных алгоритмов на FPGA. Однако комплексные RNS операции, такие как обратное преобразование вычетов в двоичную систему, определение знака, масштабирование, сравне-ние по величине и обнаружение переполнения до сих пор не были эффективно реализованы на FPGA. В данной работе мы предлагаем подход к увеличению скорости обратного преобра-зования на FPGA, используя параллельный сумматор. Это может быть первым шагом к быст-рому выполнению комплексных RNS операции на FPGA, при этом обратное преобразование также может быть использовано для решения других сложных RNS операций.

The efficient hardware implementation of RNS particularly on field program-mable gate array (FPGA) is very important due to the use of FPGAs in some modern computing systems to achieve flexibility and low time-to-market. The residue number system (RNS) with its inherent parallelism can also be used to enhance the performance of implementation of comput-ing algorithms on FPGAs. However, complex RNS operations such as residue to binary (reverse) conversion, sign detection, scaling, magnitude comparison and overflow detection have not been efficiently implemented on FPGAs until now. In this work, we try to address an approach to increase the speed of residue to binary conversion implementation on FPGAs using parallel-prefix adders. This can be a first step towards fast implementation of complex RNS operations on FPGAs, since residue to binary conversion can also be used to solve other difficult RNS operations.

Residue number system (RNS)Field programmable gate array FPGA)Parallel prefix addersСистема остаточных классов (RNS)программируе-мая вентильная матрица (FPGA)параллельный сумматорReferencesA. Omondi and B. Premkumar, “Residue Number Systems: Theory and Implementations,” Imperial College Press, London, 2007.A. Omondi and B. Premkumar, “Residue Number Systems: Theory and Implementations,” Imperial College Press, London, 2007.J. Chen and J. Hu, “Energy-Efficient Digital Signal Processing via Volt-age-Over scaling-Based Residue Number System,” IEEE Trans. Very Large Scale Integration (VLSI) Systems, vol. 21, no. 7, pp. 1322-1332, 2013.J. Chen and J. Hu, “Energy-Efficient Digital Signal Processing via Volt-age-Over scaling-Based Residue Number System,” IEEE Trans. Very Large Scale Integration (VLSI) Systems, vol. 21, no. 7, pp. 1322-1332, 2013.T. Stouraitis and V. Paliouras, “Considering the alternatives in lowpower design,” IEEE Circuits and Devices, vol. 7, pp. 23-29, 2001.T. Stouraitis and V. Paliouras, “Considering the alternatives in lowpower design,” IEEE Circuits and Devices, vol. 7, pp. 23-29, 2001.C.H. Vun, A.B. Premkumar and W. Zhang, “A New RNS based DA Ap-proach for Inner Product Computation,” IEEE Trans. Circuits and Systems-I, vol. 60, no. 8, pp. 2139-2152, 2013.C.H. Vun, A.B. Premkumar and W. Zhang, “A New RNS based DA Ap-proach for Inner Product Computation,” IEEE Trans. Circuits and Systems-I, vol. 60, no. 8, pp. 2139-2152, 2013.J.C. Bajard, L.S. Didier and T. Hilair, “p-Direct Form transposed and Residue Number Systems for Filter implementations,” In Proc. of IEEE International Midwest Symposium on Circuits and Systems, 2011, pp. 1-4.J.C. Bajard, L.S. Didier and T. Hilair, “p-Direct Form transposed and Residue Number Systems for Filter implementations,” In Proc. of IEEE International Midwest Symposium on Circuits and Systems, 2011, pp. 1-4.M. Esmaeildoust, D. Schinianakis, H. Javashi, T. Stouraitis, and K. Navi, “Efficient RNS Implementation of Elliptic Curve Point Multiplication Over GF(p),” IEEE Trans. Very Large Scale Integration (VLSI) Systems, vol. 21, no. 8, pp. 1545-1549, 2013.M. Esmaeildoust, D. Schinianakis, H. Javashi, T. Stouraitis, and K. Navi, “Efficient RNS Implementation of Elliptic Curve Point Multiplication Over GF(p),” IEEE Trans. Very Large Scale Integration (VLSI) Systems, vol. 21, no. 8, pp. 1545-1549, 2013.S. Pontarelli, G.C. Cardarilli, M. Re and A. Salsano, “Optimized Implementation of RNS FIR Filters Based on FPGAs,” Journal of Signal Processing Systems, vol. 67, no. 3, pp. 201-212, 2012.S. Pontarelli, G.C. Cardarilli, M. Re and A. Salsano, “Optimized Implementation of RNS FIR Filters Based on FPGAs,” Journal of Signal Processing Systems, vol. 67, no. 3, pp. 201-212, 2012.D.H.K. Hoe, C. Martinez, and S.J. Vundavalli, “Design and characterization of parallel prefix adders using FPGAs,” In Proc. of IEEE South-eastern Symposium on System Theory, 2011, pp. 168-172.D.H.K. Hoe, C. Martinez, and S.J. Vundavalli, “Design and characterization of parallel prefix adders using FPGAs,” In Proc. of IEEE South-eastern Symposium on System Theory, 2011, pp. 168-172.K. Navi, A.S. Molahosseini and M. Esmaeildoust, “How to Teach Res-idue Number System to Computer Scientists and Engineers,” IEEE Trans. Education, vol. 54, no. 1, pp. 156-163, 2011.K. Navi, A.S. Molahosseini and M. Esmaeildoust, “How to Teach Res-idue Number System to Computer Scientists and Engineers,” IEEE Trans. Education, vol. 54, no. 1, pp. 156-163, 2011.A.S. Molahosseini, S. Sorouri and A.A. Emrani Zarandi, “Research Challenges in Next-Generation Residue Number System Architectures,” In Proc. of IEEE International Conference on Computer Science and Education, 2012, pp. 1658-1661.A.S. Molahosseini, S. Sorouri and A.A. Emrani Zarandi, “Research Challenges in Next-Generation Residue Number System Architectures,” In Proc. of IEEE International Conference on Computer Science and Education, 2012, pp. 1658-1661.A.S. Molahosseini, K. Navi, C. Dadkhah, O. Kavehei, S. Timarchi, “Efficient Reverse Converter Designs for the New 4-Moduli Sets {2n-1, 2n, 2n+1, 22n+1-1} and {2n-1, 2n+1, 22n, 22n+1} Based on New CRTs,” IEEE Trans. Circuits and Systems-I, vol. 57, no. 4, pp.823-835, 2010.A.S. Molahosseini, K. Navi, C. Dadkhah, O. Kavehei, S. Timarchi, “Efficient Reverse Converter Designs for the New 4-Moduli Sets {2n-1, 2n, 2n+1, 22n+1-1} and {2n-1, 2n+1, 22n, 22n+1} Based on New CRTs,” IEEE Trans. Circuits and Systems-I, vol. 57, no. 4, pp.823-835, 2010.A.S. Molahosseini and K. Navi, “A Reverse Converter for the Enhanced Moduli Set {2n-1, 2n+1, 22n, 22n+1-1} Using CRT and MRC,” in Proc. of IEEE Computer Society Annual Symposium on VLSI, 2010, pp. 456- 457.A.S. Molahosseini and K. Navi, “A Reverse Converter for the Enhanced Moduli Set {2n-1, 2n+1, 22n, 22n+1-1} Using CRT and MRC,” in Proc. of IEEE Computer Society Annual Symposium on VLSI, 2010, pp. 456- 457.R.A. Patel, M. Benaissa and S. Boussakta, “Fast Parallel-Prefix Architectures for Modulo 2n-1 Addition with a Single Representation of Zero,” IEEE Trans. Computers, vol. 56, no. 11, pp. 1484-1492, 2007.R.A. Patel, M. Benaissa and S. Boussakta, “Fast Parallel-Prefix Architectures for Modulo 2n-1 Addition with a Single Representation of Zero,” IEEE Trans. Computers, vol. 56, no. 11, pp. 1484-1492, 2007.P.M. Kogge and H.S. Stone, “A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations,” IEEE Trans. Computers, vol. 22, no. 8, pp. 783-791, 1973.P.M. Kogge and H.S. Stone, “A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations,” IEEE Trans. Computers, vol. 22, no. 8, pp. 783-791, 1973.

The authors declare that there are no conflicts of interest present.