Power minization in LUT-based FPGA technology mapping

ABSTRACT

In this paper, we consider the problem of lookup table (LUT) based FPGA technology mapping for power minimization in combinational circuits. The problem has been previously proved to be NP-hard, and hence we present an efficient heuristic algorithm for it. The main idea of our algorithm is to exploit the "cut enumeration" technique to generate possible mapping solutions for the sub-circuit rooted at each node. However, for the consideration of both run time and memory space, only a fixed-number of solutions are selected and stored by our algorithm. To facilitate the selection process, a method that correctly calculates the estimated power consumption for each mapped sub-circuit is developed. The experimental results indicate that our algorithm reduces the average power consumption by up to 14.18%, and the average number of LUTs by up to 6.99% over an existing method.

REFERENCES

• 1: Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
• 2: Chau-Shen Chen , TingTing Hwang , C. L. Liu, Low power FPGA design—a re-engineering approach, Proceedings of the 34th annual conference on Design automation, p.656-661, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266312]
• 3: Kuang-Chien Chen , Jason Cong , Yuzheng Ding , Andrew B. Kahng , Peter Trajmar, DAG-Map: Graph-Based FPGA Technology Mapping for Delay Optimization, IEEE Design & Test, v.9 n.3, p.7-20, July 1992 [doi>10.1109/54.156154]
• 4: J. Cong and Y. Ding, "FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs," 1EEE Trans. on Computer-Aided Design of Integrated Circztits and Systems, pp. 1 - 12, Jan. 1994.
• 5: J. Cong and Y. Ding," On Area/Depth Trade-Off in LUT-based FPGA Technology Mapping," 1EEE Trans. on VLSI Systems, pp. 137-148, Jun. 1994.
• 6: Jason Cong , Yean-Yow Hwang, Simultaneous depth and area minimization in LUT-based FPGA mapping, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.68-74, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201322]
• 7: Jason Cong , Chang Wu , Yuzheng Ding, Cut ranking and pruning: enabling a general and efficient FPGA mapping solution, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.29-35, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296425]
• 8: A.H. Farrahi and M. Sarrafzadeh, "Complexity of the Lookup-Table Minimization Problem for FPGA Technology Mapping," 1EEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 1319-1332, Nov. 1994.
• 9: 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
• 10: Robert J. Francis , Jonathan Rose , Kevin Chung, Chortle: a technology mapping program for lookup table-based field programmable gate arrays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.613-619, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123418]
• 11: Robert Francis , Jonathan Rose , Zvonko Vranesic, Chortle-crf: Fast technology mapping for lookup table-based FPGAs, Proceedings of the 28th conference on ACM/IEEE design automation, p.227-233, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127670]
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: Juinn-Dar Huang , Jing-Yang Jou , Wen-Zen Shen, An iterative area/performance trade-off algorithm for LUT-based FPGA technology mapping, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.13-17, November 10-14, 1996, San Jose, California, United States
• 14: Jan-Min Hwang , Feng-Yi Chiang , TingTing Hwang, A re-engineering approach to low power FPGA design using SPFD, Proceedings of the 35th annual conference on Design automation, p.722-725, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277225]
• 15: Kevin Karplus, Xmap: A technology mapper for table-lookup field-programmable gate arrays, Proceedings of the 28th conference on ACM/IEEE design automation, p.240-243, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127672]
• 16: Balakrishna Kumthekar , Luca Benini , Enrico Macii , Fabio Somenzi, In-place power optimization for LUT-based FPGAs, Proceedings of the 35th annual conference on Design automation, p.718-721, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277224]
• 17: Rajeev Murgai , Yoshihito Nishizaki , Narendra Shenoy , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Logic synthesis for programmable gate arrays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.620-625, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123421]
• 18: R. Murgai, N. Shenoy, R. K. Brayton, and A. Sangiovanni-Vincentelli, "Improved Logic Synthesis Algorithms for Table Look Up Architectures," Proc. Int. Conf. on Computer-Aided Design, pp. 564- 567, 1991.
• 19: R. Murgai, N. Shenoy, R. K. Brayton, and A. Sangiovanni-Vincentelli, "Performance Directed Synthesis for Table Look Up Programmable Gate Arrays," Prvc. Int. Conf. on Computer-Aided Design, pp. 572- 575, 1991.
• 20: F. Najm, "Transition Density: A New Measure of Activity in Digital Circuits," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 310-323, Feb. 1993.
• 21: R Sawkar and D. Thomas, "Tcchnology Mapping for Table-Look-Up Based Field Programmable Gate Arrays," Proc. Int. Workshop on Field Programmable Gate Arrays, pp. 83-88, 1992.
• 22: 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
• 23: C.-C. Wang and C.-R Kwan, "Low Power Technology Mapping by Hiding High-Transition Paths in Invisible Edges of LUT-Based FPGAs", Proc. lnt. Symp. on Circuits and Systems, pp. 1536-1539, 1997.
• 24: Nam-Sung Woo, A heuristic method for FPGA technology mapping based on the edge visibility, Proceedings of the 28th conference on ACM/IEEE design automation, p.248-251, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127675]
• 25: Xilinx, The Prvgrammable Gate Arrays Data Book, Xilinx, San Jose, CA, 1992.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic
  B.8 Performance and Reliability

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

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