A stochastic bitwidth estimation technique for compact and low-power custom processors

ABSTRACT

There is an increasing trend toward compiling from C to custom hardware for designing embedded systems in which the area and power consumption of application-specific functional units, registers, and memory blocks are heavily dependent on the bit-widths of integer operands used in computations. The actual bit-width required to store the values assigned to an integer variable during the execution of a program will not, in general, match the built-in C data types. Thus, precious area is wasted if the built-in data type sizes are used to declare the size of integer operands. In this paper, we introduce stochastic bit-width estimation that follows a simulation-based probabilistic approach to estimate the bit-widths of integer variables using extreme value theory. The estimation technique is also empirically compared to two compile-time integer bit-width analysis techniques. Our experimental results show that the stochastic bit-width estimation technique dramatically reduces integer bit-widths and, therefore, enables more compact and power-efficient custom hardware designs than the compile-time integer bit-width analysis techniques. Up to 37% reduction in custom hardware area and 30% reduction in logic power consumption using stochastic bit-width estimation can be attained over ten integer applications implemented on an FPGA chip.

REFERENCES

• 1: Kiran Bondalapati , Viktor K. Prasanna, Dynamic Precision Management for Loop Computations on Reconfigurable Architectures, Proceedings of the Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.249, April 21-23, 1999
• 2: Brase, C. H. and Brase, C. P. 2001. Understanding Basic Statistics, 2nd Ed. Houghton Mifflin, Boston, MA.
• 3: Mihai Budiu , Majd Sakr , Kip Walker , Seth Copen Goldstein, BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.969-979, August 29-September 01, 2000
• 4: Celoxica 2002. Handel-C Language Reference Manual, Version 3.1, 2002.
• 5: Yun Cao , Hiroto Yasuura, Quality-driven design by bitwidth optimization for video applications, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119883]
• 6: D. C. Cronquist , P. Franklin , S. G. Berg , C. Ebeling, Specifying and Compiling Applications for RaPiD, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.116, April 15-17, 1998
• 7: Bruce A. Draper , A. P. Wim Böhm , Jeffrey Hammes , Walid A. Najjar , J. Ross Beveridge , Charlie Ross , Monica Chawathe , Mitesh Desai , José Bins, Compiling SA-C Programs to FPGAs: Performance Results, Proceedings of the Second International Workshop on Computer Vision Systems, p.220-235, July 07-08, 2001
• 8: Claire F. Fang , Rob A. Rutenbar , Tsuhan Chen, Fast, Accurate Static Analysis for Fixed-Point Finite-Precision Effects in DSP Designs, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.275, November 09-13, 2003 [doi>10.1109/ICCAD.2003.68]
• 9: Claire Fang Fang , Rob A. Rutenbar , Markus Püschel , Tsuhan Chen, Toward efficient static analysis of finite-precision effects in DSP applications via affine arithmetic modeling, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775960]
• 10: Jan Frigo , Maya Gokhale , Dominique Lavenier, Evaluation of the streams-C C-to-FPGA compiler: an applications perspective, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.134-140, February 2001, Monterey, California, United States [doi>10.1145/360276.360326]
• 11: Altaf Abdul Gaffar , Oskar Mencer , Wayne Luk , Peter Y. K. Cheung, Unifying Bit-Width Optimisation for Fixed-Point and Floating-Point Designs, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.79-88, April 20-23, 2004
• 12: Rajiv Gupta , Eduard Mehofer , Youtao Zhang, A Representation for Bit Section Based Analysis and Optimization, Proceedings of the 11th International Conference on Compiler Construction, p.62-77, April 08-12, 2002
• 13: W. H. Harrison, Compiler Analysis of the Value Ranges for Variables, IEEE Transactions on Software Engineering, v.3 n.3, p.243-250, May 1977 [doi>10.1109/TSE.1977.231133]
• 14: Holloway, G. and Young, C. 2002. The flow analysis and transformation libraries of machine SUIF. In Proceedings of 2nd SUIF Compiler Workshop (Aug.), Stanford University, Stanford, CA.
• 15: Kim, S., Kum, K., and Sung, W. 1998. Fixed-point optimization utility for C and C++ based digital signal processing programs. IEEE Trans. Circuits Syst. 45, 11 (Nov.).
• 16: Kinnison, R. R. 1985. Applied Extreme Value Statistics. Macmillan, New York.
• 17: Averill M. Law , David M. Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1999
• 18: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 19: Mahlke, S., Ravindran, R., Schlansker, M., Schreiber, R., and Sherwood, T. 2001. Bitwidth cognizant architecture synthesis of custom hardware accelerators, HPL-2001-209 Technical Rep. (Aug.).
• 20: A. Nayak , M. Haldar , A. Choudhary , P. Banerjee, Precision and error analysis of MATLAB applications during automated hardware synthesis for FPGAs, Proceedings of the conference on Design, automation and test in Europe, p.722-728, March 2001, Munich, Germany
• 21: OPEN SYSTEMC INITIATIVE 2003. SystemC 2.0.1 Language Reference Manual Revision 1.0, 2003.
• 22: Özer, E., Nisbet, A. P., and Gregg, D. 2004. Stochastic bit-width approximation using extreme value theory for customizable processors. In Proceedings 13th International Conference on Compiler Construction (CC) (Mar.), LNCS 2985, Barcelona, Spain.
• 23: Jason R. C. Patterson, Accurate static branch prediction by value range propagation, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.67-78, June 18-21, 1995, La Jolla, California, United States
• 24: Rahul Razdan , Michael D. Smith, A high-performance microarchitecture with hardware-programmable functional units, Proceedings of the 27th annual international symposium on Microarchitecture, p.172-180, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192749]
• 25: Rolf-Dieter Reiss , Michael Thomas, Statistical analysis of extreme values, Birkhauser Verlag, Basel, Switzerland, 1997
• 26: Darko Stefanovic , Margaret Martonosi, On Availability of Bit-Narrow Operations in General-Purpose Applications, Proceedings of the The Roadmap to Reconfigurable Computing, 10th International Workshop on Field-Programmable Logic and Applications, p.412-421, August 27-30, 2000
• 27: Mark Stephenson , Jonathan Babb , Saman Amarasinghe, Bidwidth analysis with application to silicon compilation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.108-120, June 18-21, 2000, Vancouver, British Columbia, Canada
• 28: Markus Willems , Volker Bürsgens , Holger Keding , Thorsten Grötker , Heinrich Meyr, System level fixed-point design based on an interpolative approach, Proceedings of the 34th annual conference on Design automation, p.293-298, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266105]
• 29: Wilson, R. P., French, R. S., Wilson, C. S., Amarasinghe, S., Anderson, J. M., Tjiang, S. W. K., Liao, S. W., Tseng, C. W., Hall, M. W., Lam, M. S., and Hennessy, J. L. 1994. SUIF: An infrastructure for research on parallelizing and optimizing compilers, Technical. Rep. Computer Systems Laboratory, Stanford University, CA.
• 30: XILINX 2002, Xilinx Virtex-II Architecture Manual, Sep. 2002.
• 31: H. Yamashita , H. Yasnura , F. N. Eko , Cao Yun, Variable size analysis and validation of computation quality, Proceedings of the IEEE International High-Level Validation and Test Workshop (HLDVT'00), p.95, November 08-10, 2000

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions; Random number generation

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.0 General

General Terms:
Design, Experimentation

Keywords:
Bit-width analysis, FPGA, custom hardware, extreme value theory, statistical estimation