Exploiting residue number system for power-efficient digital signal processing in embedded processors

ABSTRACT

2's complement number system imposes a fundamental limitation on the power and performance of arithmetic circuits, due to the fundamental need of cross-datapath carry propagation. Residue Number System (RNS) breaks free of these bonds by decomposing a number into parts and performing arithmetic operations in parallel, significantly reducing the breadth of carry propagation. Consequently, RNS arithmetic has been proposed as a solution to improve the power-efficiency of arithmetic hardware. However, limitations of the expressiveness of RNS in terms of arithmetic operations together with overheads related to interaction with 2's complement arithmetic make programmable processor design that takes advantage of these benefits challenging.

In this paper we meet this challenge by multi-tier synergistic co-design of architecture, micro-architecture, hardware components, as well as compilation techniques. Our experiments not only demonstrate simultaneous improvement of up to 30% in performance and 57% reduction in functional unit power consumption, but also that most of these benefits can be exploited with automatically generated code.

REFERENCES

• 1: B. P. Amos Omondi. Residue Number Systems Theory and Implementation. Imperial College Press, 2007.
• 2: T. Austin. Simplescalar. http://www.simplescalar.com/.
• 3: J. Bajard, S. Duquesne, M. Ercegovac, and N. Meloni. Residue systems efficiency for modular products summation: Application to elliptic curves cryptography. Proc. SPIE, 6313:631304, 2006.
• 4: R. Chaves and L. Sousa. RDSP: A RISC DSP based on residue number system. In Proc. Europ. Symp. Dig. Syst. Des., pages 128--135, Sep. 2003.
• 5: R. Chaves and L. Sousa. Improving residue number system multiplication with more balanced moduli sets and enhanced modular arithmetic structures. IET Comp.s & Dig. Techn., 1(5):472--480, Sept. 2007.
• 6: C. Galuzzi and K. Bertels. The instruction-set extension problem: A survey. In Int'l Workshop Applied Reconf. Comp. (ARC), pages 209--220, March 2008.
• 7: M. Griffin and F. Taylor. A residue number system reduced instruction set computer (RISC) concept. In Proc. Inter. Conf. Acoust., Speech, & Sign. Proc., pages 2581--2584, 1989.
• 8: N. Homma, Y. Watanabe, T. Aoki, and T. Higuchi. Formal design of arithmetic circuits based on arithmetic description language. IEICE Trans. Fundamentals, E89--A:3500---3509, 2006.
• 9: H.T.Vergos. A 200-MHz RNS core. In Proc. Europ. Conf. Circ. Theory & Des., August 2001.
• 10: W. K. Jenkins and B. J. Leon. The use of residue number systems in the design of finite impulse response digital filters. IEEE Trans. Circ. & Syst., CAS-24:191--201, 1977.
• 11: D. Kannan, A. Shrivastava, S. Bhardwaj, and S. Vrudhul. Power reduction of functional units considering temperature and process variations. In Proc. VLSI Design, volume 0, pages 533--539, Los Alamitos, CA, USA, 2008.
• 12: P. V. A. Mohan. Residue Number Systems: Algorithms and Architectures. Kluwer Academic Publishers, Norwell, MA, 2002.
• 13: A. Molahosseini, K. Navi, O. Hashemipour, and A. Jalali. An efficient architecture for designing reverse converters based on a general three-moduli set. J. Syst. Archit., 54(10):929--934, 2008.
• 14: S. J. Piestrak and K. S. Berezowski. Architecture of efficient RNS-based digital signal processor with very low-level pipelining. In Proc. IET Irish Sign. & Syst. Conf., pages 127--132, Galway, Ireland, 18--19 June 2008.
• 15: S. J. Piestrak and K. S. Berezowski. Design of residue multipliers-accumulators using periodicity. In Proc. IET Irish Sign. & Syst. Conf., pages 380--385, Galway, Ireland, 18--19 June 2008.
• 16: J. Ramirez, A. Garcia, S. Lopez-Buedo, and A. Lloris. RNS-enabled digital signal processor design. IEEE Electr. Lett., 38(6):266--268, 2002.
• 17: S.J.Piestrak. Design of residue generators and multioperand modular adders using carry-save adders. IEEE Trans. Computers, 43(1):68--77, Jan 1994.
• 18: M. A. Soderstrand, W. K. Jenkins, G. A. Jullien, and F. J. Taylor. Residue number system arithmetic: Modern Applications in Digital Signal Processing. IEEE Press, Piscataway, NJ, USA, 1986.
• 19: T. Tomczak. Fast sign detection for RNS (2n - 1; 2n; 2n + 1). IEEE Trans. Circ. and Syst. I, 55(6):1502--1511, July 2008.
• 20: T.Stouratitis and V.Paliouras. Considering the alternatives in low-power design. IEEE Circ. & Dev., pages 23--29, 2001.
• 21: Y. Wang. Residue-to-binary converters based on new Chinese Remainder Theorems. IEEE Trans. Circ. Syst. II, pages 197--206, Mar 2000.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures
          Subjects: Pipeline processors**

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures
          Subjects: RISC/CISC, VLIW architectures
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems; Microprocessor/microcomputer applications

General Terms:
Algorithms, Design, Performance

Keywords:
compiler, per-, power, processor, residue number system