Xquasher: a tool for efficient computation of multiple linear expressions

ABSTRACT

Digital signal processing applications often require the computation of linear systems. These computations can be considerably expensive and require optimizations for lower power consumption, higher throughput, and faster response time. Unfortunately, system designers do not have the necessary tools to take advantage of the wide flexibility in ways to evaluate these expressions. Therefore, we address the problem of efficiently computing a set of linear systems through a tool, Xquasher, that is developed by us to enable elimination of large common subexpression from expressions with an arbitrary number of terms. Xquasher provides a methodology for efficient computation of both single and multiple linear expressions. We also introduce the concept of power set encoding which helps us to provide an effective optimization method and achieves significant improvement over previously published work. Our tool provides optimized designs with 15% less area with the cost of 3% increase in delay by reducing number of additions on average by 45%.

REFERENCES

• 1: M. Potkonjak, M. B. Srivastava, and A. P. Chandrakasan, "Multiple Constant Multiplications: Efficient and Versatile Framework and Algorithms for Exploring Common Subexpression Elimination," IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 1996.
• 2: H. T. Nguyen and A. Chattejee, "Number-splitting with shift-and-add decomposition for power and hardware optimization in linear DSP synthesis," IEEE Transactions on Very Large Scale Integration (Vlsi) Systems, vol. 8, pp. 419--24, 2000.
• 3: H. Safiri, M. Ahmadi, G. A. Jullien, and W. C. Miller, "A New Algorithm for the Elimination of Common Subexpressions in Hardware Implementation of Digital Filters by Using Genetic Programming," IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP), 2000.
• 4: A. Hosangadi, F. Fallah, and R. Kastner, "Common subexpression elimination involving multiple variables linear DSP synthesis," IEEE International Conference on Application-Specific Systems, Architectures and Processors, pp. 202--12, 2004.
• 5: A. Hosangadi, F. Farzan, and R. Kastner, "Optimizing high speed arithmetic circuits using three-term extraction," Design, Automation and Test in Europe, pp. 6, 2006.
• 6: R. Zimmermann, D. Q. Tran, "Optimized Synthesis of Sum-of-Products," Proceedings 37^th Asilomar Conference on Signals, Systems, and Computers, November 2003
• 7: Peter Tummeltshammer, James C. Hoe and Markus Püschel, "Time-Multiplexed Multiple Constant Multiplication", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 26, No. 9, pp. 1551--1563, 2007.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Algorithms, Design

Keywords:
DSP transforms, area optimization, common sub-expression elimination, linear expression, multiple constant multiplications