Power optimization using divide-and-conquer techniques for minimization of the number of operations

ABSTRACT

We develop an approach to minimizing power consumption of portable wireless DSP applications using a set of compilation and architectural techniques. The key technical innovation is a novel divide-and-conquer compilation technique to minimize the number of operations for general DSP computations. Our technique optimizes not only a significantly wider set of computations than the previously published techniques, but also outperforms (or performs at least as well as other techniques) on all examples. Along the architectural dimension, we investigate coordinated impact of compilation techniques on the number of processors which provide optimal trade-off between cost and power. We demonstrate that proper compilation techniques can significantly reduce power with bounded hardware cost. The effectiveness of all techniques and algorithms is documented on numerous real-life designs.

REFERENCES

• 1: A.R Chandrakasan, S. Sheng, and R.W. Broderson. Low-power CMOS digital design. IEEE J. of Solid- State Circuits, 27(4):473-484, 1992.
• 2: RD. Hoang and J.M. Rabaey. Scheduling of DSP programs onto multiprocessors for maximum throughput. IEEE Trans. on Signal Processing, 41 (6):2225- 2235, 1993.
• 3: I. Hong, M. Potkonjak, and R. Karri. Power optimization using divide-and-conquer techniques for minimization of the number of operations. Technical report, Computer Science Department, UCLA, 1997.
• 4: E.A. Lee and D.G. Messerschmitt. Synchronous dataflow. Proc. of the IEEE, 75(9):1235-1245, 1987.
• 5: C.E. Leiserson and J.B. Saxe. Retiming synchronous circuitry. Algorithmica, 6(1):5-35, 1991.
• 6: Keshab K. Parhi , David G. Messerschmitt, Static Rate-Optimal Scheduling of Iterative Data-Flow Programs Via Optimum Unfolding, IEEE Transactions on Computers, v.40 n.2, p.178-195, February 1991 [doi>10.1109/12.73588]
• 7: Miodrag Potkonjak , Jan Rabaey, Maximally fast and arbitrarily fast implementation of linear computations, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.304-308, November 1992, Santa Clara, California, United States
• 8: J. M. Rabaey , C. Chu , P. Hoang , M. Potkonjak, Fast Prototyping of Datapath-Intensive Architectures, IEEE Design & Test, v.8 n.2, p.40-51, April 1991 [doi>10.1109/54.82037]
• 9: Michael Sheliga , Edwin Hsing Mean Sha, Global node reduction of linear systems using ratio analysis, Proceedings of the 7th international symposium on High-level synthesis, p.140-145, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 10: D. Singh, J. Rabaey, M. Pedram, F. Catthoor, S. Rajgopal, N. Sehgal, and T. Mozdzen. Power conscious cad tools and methodologies: A perspective. Proc. of the IEEE, 83(4), 1995.
• 11: Mani Srivastava , Miodrag Potkonjak, Power optimization in programmable processors and ASIC implementations of linear systems: transformation-based approach, Proceedings of the 33rd annual conference on Design automation, p.343-348, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240583]
• 12: R.E. Tarjan. Depth first search and linear graph algorithms. SIAM J. on Computing, 1 (2): 146-160, 1972.
• 13: Vivek Tiwari , Sharad Malik , Andrew Wolfe, Power analysis of embedded software: a first step towards software power minimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.2 n.4, p.437-445, Dec. 1994 [doi>10.1109/92.335012]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Memory technologies

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Signal processing

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
DSP computations, architectural techniques, compilation, data flow graphs, divide-and-conquer compilation, portable wireless DSP applications, power consumption