Optimization of polynomial datapaths using finite ring algebra

ABSTRACT

This article presents an approach to area optimization of arithmetic datapaths at register-transfer level (RTL). The focus is on those designs that perform polynomial computations (add, mult) over finite word-length operands (bit-vectors). We model such polynomial computations over m-bit vectors as algebra over finite integer rings of residue classes Z₂^m. Subsequently, we use the number-theoretic and algebraic properties of such rings to transform a given datapath computation into another, bit-true equivalent computation. We also derive a cost model to estimate, at RTL, the area cost of the computation. Using the transformation procedure along with the cost model, we devise algorithmic procedures to search for a lower-cost implementation. We show how these theoretical concepts can be applied to RTL optimization of arithmetic datapaths within practical CAD settings. Experiments conducted over a variety of benchmarks demonstrate substantial optimizations using our approach.

REFERENCES

• 1: Allenby, R. J. B. T. 1983. Rings, Fields, and Groups: An Introduction to Abstract Algebra. E. J. Arnold.
• 2: Arvind , Xiaowei Shen, Using Term Rewriting Systems to Design and Verify Processors, IEEE Micro, v.19 n.3, p.36-46, May 1999 [doi>10.1109/40.768501]
• 3: Chen, C. and Huang, C. 2001. On the architecture and performance of a hybrid image rejection receiver. IEEE J. Select. Areas Commun. 19, 6, (Jun.) 1029--1040.
• 4: Zhibo Chen, On polynomial functions from Zn1×Zn2× &ldots;×Znr to Zm , Discrete Mathematics, v.162 n.1-3, p.67-76, Dec. 25, 1996 [doi>10.1016/0012-365X(95)00305-G]
• 5: Zhibo Chen, On polynomial functions from Zn to Zm, Discrete Mathematics, v.137 n.1-3, p.137-145, Jan. 20, 1995 [doi>10.1016/0012-365X(93)E0162-W]
• 6: G. Constantinides , P. Cheung , W. Luk, Heuristic datapath allocation for multiple wordlength systems, Proceedings of the conference on Design, automation and test in Europe, p.791-797, March 2001, Munich, Germany
• 7: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 8: Groute, I. A. and Keane, K. 2000. M(VH)DL: A Matlab to VHDL conversion toolbox for digital control. In IFAC Symposiun on Computer-Aided Control System Design (Salford, UK).
• 9: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 10: Anup Hosangadi , Farzan Fallah , Ryan Kastner, Energy Efficient Hardware Synthesis of Polynomial Expressions, Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design, p.653-658, January 03-07, 2005 [doi>10.1109/ICVD.2005.90]
• 11: A. Hosangadi , F. Fallah , R. Kastner, Factoring and eliminating common subexpressions in polynomial expressions, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.169-174, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382566]
• 12: Huang, C.-Y. and Cheng, K.-T. 2001. Using word-level atpg and modular arithmetic constraint solving techniques for assertion property checking. IEEE Trans. Comput. Aided. Des. 20, 381--391.
• 13: Hungerbuhler, N. and Specker, E. 2006. A generalization of the smarandache function to several variables. Integers: Electron. J. Combin. Num. Theory 6, A23, 1--11.
• 14: Jeraj, J. 2005. Adaptive estimation and equalization of non-linear systems. Ph.D. thesis, University of Utah, Salt Lake City, Utah.
• 15: Keller, G. and Olson, F. 1968. Counting polynomial functions (mod pⁿ). Duke Math. J. 35, 835--838.
• 16: Kempner, A. J. 1921. Polynomials and their residual systems. Amer. Math. Soc. Trans. 22, 240--288.
• 17: Kempner, A. J. 1918. Miscellanea. Amer. Math. Month. 25, 201--210.
• 18: Israel Koren, Computer Arithmetic Algorithms, A. K. Peters, Ltd., Natick, MA, 2001
• 19: Kum, K. and Sung, W. 1998. Word-Length optimization for high-level synthesis of DSP systems. In International Workshop Signal Processing Systems (SIPS). Piscataway, NJ.
• 20: Lucas, E. 1883. Question nr. 288. Mathesis 3, 232.
• 21: Maple. 2007. Maple. http://www.maplesoft.com.
• 22: Mathews, V. J. and Sicuranza, G. L. 2000. Polynomial Signal Processing. Wiley-Interscience, New York.
• 23: Daniel Menard , Daniel Chillet , François Charot , Olivier Sentieys, Automatic floating-point to fixed-point conversion for DSP code generation, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581674]
• 24: Peymandoust, A. and DeMicheli, G. 2003. Application of symbolic computer algebra in high-level data-flow synthesis. IEEE Trans. Comput. Aided. Des. 22, 9, 1154--11656.
• 25: David Power , Sabin Tabirca , Tatiana Tabirca, Java concurent program for the Samarandache function, Smarandache Notions Journal, v.13 n.1-2-3, p.72-84, Spring 2002
• 26: D. K. Pradhan, A Theory of Galois Switching Functions, IEEE Transactions on Computers, v.27 n.3, p.239-248, March 1978 [doi>10.1109/TC.1978.1675077]
• 27: D. K. Pradhan , S. Askar , M. Ciesielski, Mathematical framework for representing discrete functions as word-level polynomials, Proceedings of the Eighth IEEE International Workshop on High-Level Design Validation and Test Workshop, p.135, November 12-14, 2003
• 28: T. L. Rajaprabhu , A. K. Singh , A. M. Jabir , D. K. Pradhan, MODD for CF: a representation for fast evaluation of multiple-output functions, Proceedings of the High-Level Design Validation and Test Workshop, 2004. Ninth IEEE International, p.61-66, November 10-12, 2004 [doi>10.1109/HLDVT.2004.1431237]
• 29: Namrata Shekhar , Priyank Kalla , Florian Enescu, Equivalence verification of arithmetic datapaths with multiple word-length operands, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 30: N. Shekhar , P. Kalla , F. Enescu , S. Gopalakrishnan, Equivalence verification of polynomial datapaths with fixed-size bit-vectors using finite ring algebra, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.291-296, November 06-10, 2005, San Jose, CA
• 31: Singmaster, D. 1974. On polynomial functions (mod m). J. Num. Theory 6, 345--352.
• 32: Smarandache, F. 1980. A function in number theory. Analele Univ. Timisoara, Fascicle 1, 17, 79--88.
• 33: James Smith , Giovanni De Micheli, Polynomial circuit models for component matching in high-level synthesis, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.6, p.783-800, 12/1/2001 [doi>10.1109/92.974892]
• 34: James Smith , Giovanni De Micheli, Polynomial methods for allocating complex components, Proceedings of the conference on Design, automation and test in Europe, p.45-es, January 1999, Munich, Germany [doi>10.1145/307418.307492]
• 35: James Smith , Giovanni De Micheli, Polynomial methods for component matching and verification, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.678-685, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289115]
• 36: Synopsys. 2007. Synopsys module compiler and designware library. htpp://www.synopsys.com.
• 37: Mitchell Aaron Thornton , D. Michael Miller , Rolf Drechsler, Spectral Techniques in VLSI CAD, Kluwer Academic Publishers, Norwell, MA, 2001
• 38: Ajay K. Verma , Paolo Ienne, Towards the automatic exploration of arithmetic-circuit architectures, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147027]
• 39: A. K. Verma , P. Ienne, Improved use of the carry-save representation for the synthesis of complex arithmetic circuits, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.791-798, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382683]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Data-path design

General Terms:
Algorithms

Keywords:
High-level synthesis, arithmetic datapaths, finite ring algebra, modulo arithmetic, polynomial datapaths