Low power FPGA design—a re-engineering approach

ABSTRACT

In this paper, technology mapping algorithmsfor minimizing power consumption in FPGA design are studied.The technology mapping problem for power minimizationhas been shown to be NP-complete.Furthermore, thereare other important objectives, such as the number of PLBs(Programmable Logic Blocks), the number of levels and soon, that should also be optimized simultaneously.We proposea transformational approach in which we start with amapping solution which optimizes certain objective(s) (e.g., the number of PLBs.)The mapping solution is then transformedto reduce the power consumption while keeping thenumber of PLBs fixed.Our algorithm explores the possibilitiesof transforming the functionality of the PLBs so thatthe switching densities of the output edges of the PLBs willbe reduced, leading to a reduction in total power consumption.Our transformational approach can also be viewed as are-engineering approach in which power reduction is achievedthrough re-routing after the PLBs have been placed, utilizingeffectively the capability of a PLB to realize any booleanfunction of up to k variables.

REFERENCES

• 1: Vivek Tiwari , Pranav Ashar , Sharad Malik, Technology mapping for lower power, Proceedings of the 30th international conference on Design automation, p.74-79, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164581]
• 2: Yung-Te Lai , Massoud Pedram , Sarma B. K. Vrudhula, BDD based decomposition of logic functions with application to FPGA synthesis, Proceedings of the 30th international conference on Design automation, p.642-647, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165078]
• 3: Jason Cong , Yuzheng Ding, An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.48-53, November 1992, Santa Clara, California, United States
• 4: Martine D. F. Schlag , Jackson Kong , Pak K. Chan, Routability-Driven Techology Mapping for LookUp-Table-Based FPGAs, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.86-90, October 11-14, 1992
• 5: Jason Cong , Yuzheng Ding, On area/depth trade-off in LUT-based FPGA technology mapping, Proceedings of the 30th international conference on Design automation, p.213-218, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164675]
• 6: " The Programmable Gate Array Data Book," Xilinx Inc., 2069, Hamilton Ave., San Jose, CA-94125, U.S.A., 1989.
• 7: Amir H. Farrahi , Majid Sarrafzadeh, FPGA Technology Mapping for Power Minimization, Proceedings of the 4th International Workshop on Field-Programmable Logic and Applications: Field-Programmable Logic, Architectures, Synthesis and Applications, p.66-77, September 07-09, 1994
• 8: J. P. Roth and R. M. Karp, "Minimization over Boolean Graphs", IBM Your. of Research and Development, 1962, pp. 227-238.
• 9: Kuo-Hwa Wang and TingTing Hwang, "Exploiting Communication Complexity for Boolean Matching," to appear in IEEE Transactions on CAD.
• 10: Chao, T.-H., and Hsu, Y.-C. "Rectilinear Steiner Tree Construction by Local and Global Refinement," Proc. of ICCAD, 1990, pp. 432-435.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  C. Computer Systems Organization

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

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