Towards Fast Implementation of Complex RNS Components on FPGAs
Abstract
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.
About the Authors
Sabbagh Molahosseini Amir
Islamic Azad University
Russian Federation
Russian Federation
Alsadat Emrani Azadeh
Islamic Azad University
Russian Federation
Russian Federation
References
1. A. Omondi and B. Premkumar, “Residue Number Systems: Theory and Implementations,” Imperial College Press, London, 2007.
2. 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.
3. T. Stouraitis and V. Paliouras, “Considering the alternatives in lowpower design,” IEEE Circuits and Devices, vol. 7, pp. 23-29, 2001.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.
9. 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.
10. 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.
11. 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.
12. 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.
13. 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.
14. 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.
Review
For citations:
Amir S.M., Azadeh A.E. Towards Fast Implementation of Complex RNS Components on FPGAs. Science. Innovations. Technologies. 2014;(4):86-95. (In Russ.)
Views:
23
Email this article 