Gain-based technology mapping for minimum runtime leakage under input vector uncertainty

ABSTRACT

The gain-based technology mapping paradigm has been successfully employed for finding minimum delay and minimum area mappings. However, existing gain-based technology mappers fail to find circuits with minimal leakage power. In this paper, we introduce algorithms and modeling strategies that enable efficient gain-based technology mapping for minimum leakage power. The proposed algorithm is probability-aware and can rigorously take into account input state probability distribution to generate a circuit mapping with minimum leakage at a given percentile. Minimizing leakage at high percentiles is essential for minimizing peak leakage, which strongly influences the cooling limits and packaging costs.The algorithms have been tested on the ISCAS85 benchmark suite. Results indicate that the mappings produced by the new algorithm consume, on average 14% lesser leakage power at the 99% percentile with 1% delay penalty when compared with the approaches used in previous gain-based mappers [2]. Also, compared to a dominant-state mapper, our approach produces mappings with 15% lesser mean value of leakage. The new algorithm also reduces leakage at high quantiles by 12.8% on average, compared to a dominant state leakage minimizing mapper and the maximum savings can be as high as 21.49% across the benchmarks. Compared to the bin based mapper [10], the runtime of the algorithm is 15X faster.

REFERENCES

• 1: Ivan E. Sutherland , Robert F. Sproull, Logical effort: designing for speed on the back of an envelope, Proceedings of the 1991 University of California/Santa Cruz conference on Advanced research in VLSI, p.1-16, April 1991
• 2: Bo Hu , Yosinori Watanabe , Alex Kondratyev , Malgorzata Marek-Sadowska, Gain-based technology mapping for discrete-size cell libraries, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775979]
• 3: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• 4: Joel Grodstein , Eric Lehman , Heather Harkness , Bill Grundmann , Yosinatori Watanabe, A delay model for logic synthesis of continuously-sized networks, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.458-462, November 05-09, 1995, San Jose, California, United States
• 5: K. Chaudhary , M. Pedram, A near optimal algorithm for technology mapping minimizing area under delay constraints, Proceedings of the 29th ACM/IEEE conference on Design automation, p.492-498, June 08-12, 1992, Anaheim, California, United States
• 6: M. Iyer et al, "Wavefront technology mapping," International Workshop on Logic synthesis, 1998.
• 7: Chang-woo Kang , Massoud Pedram, Technology mapping for low leakage power and high speed with hot-carrier effect consideration, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119812]
• 8: Dongwoo Lee , David Blaauw, Static leakage reduction through simultaneous threshold voltage and state assignment, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775881]
• 9: Sumit Roy , Krishna Belkhale , Prithviraj Banerjee, An &agr;-approxmimate algorithm for delay-constraint technology mapping, Proceedings of the 36th ACM/IEEE conference on Design automation, p.367-372, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309960]
• 10: Richard L. Rudell , Alberto Sangiovanni-Vincentelli, Logic synthesis for vlsi design, 1989
• 11: Shekhar Borkar , Tanay Karnik , Siva Narendra , Jim Tschanz , Ali Keshavarzi , Vivek De, Parameter variations and impact on circuits and microarchitecture, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775920]
• 12: P. Kudva et al, "Gain-based logic synthesis," Proc. of ICCAD tutorial, 2000.
• 13: E. Acar et al, "Leakage and leakage sensitivity computation for combinational logic," Journal of Low Power Electronics, Volume 1, Number 2, 2005.
• 14: S. H. Gunther et al, "Managing the impact of increasing microprocessor power consumption," Intel Technology Journal, Q1, 2001.
• 15: Dirk-Jan Jongeneel , Yosinori Watanbe , Robert K. Brayton , Ralph Otten, Area and search space control for technology mapping, Proceedings of the 37th conference on Design automation, p.86-91, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337321]
• 16: Yuji Kukimoto , Robert K. Brayton , Prashant Sawkar, Delay-optimal technology mapping by DAG covering, Proceedings of the 35th annual conference on Design automation, p.348-351, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277142]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

General Terms:
Algorithms, Performance

Keywords:
leakage, logical effort, technology mapping