An efficient chip-level time slack allocation algorithm for Dual-Vdd FPGA power reduction

ABSTRACT

To reduce FPGA power, a linear programming (LP) based time slack allocation algorithm, EdTLC-LP, has been proposed recently for Vdd-programmable interconnects without using Vdd-level converters for mixed wire lengths. However, it takes a long time to solve the LP problem for time slack allocation. In this paper, we develop EdTLC-NW, a slack allocation algorithm based on min-cost network flow to reduce runtime. Compared to single Vdd FPGA with power-gating, EdTLC-LP and EdTLC-NW reduce interconnect power by 52.71% and 52.52%, respectively. EdTLC-NW achieves as good results as EdTLC-LP but runs 8X faster on average. Furthermore, the speedup increases for larger circuits and EdTLC-NW is 20X faster for the largest circuit.

REFERENCES

• 1: Kara K. W. Poon , Andy Yan , Steven J. E. Wilton, A Flexible Power Model for FPGAs, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.312-321, September 02-04, 2002
• 2: Fei Li , Deming Chen , Lei He , Jason Cong, Architecture evaluation for power-efficient FPGAs, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611844]
• 3: Julien Lamoureux , Steven J. E. Wilton, On the Interaction Between Power-Aware FPGA CAD Algorithms, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.701, November 09-13, 2003 [doi>10.1109/ICCAD.2003.106]
• 4: Jason H. Anderson , Farid N. Najm , Tim Tuan, Active leakage power optimization for FPGAs, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA [doi>10.1145/968280.968287]
• 5: Fei Li , Yan Lin , Lei He , Jason Cong, Low-power FPGA using pre-defined dual-Vdd/dual-Vt fabrics, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA [doi>10.1145/968280.968288]
• 6: Fei Li , Yan Lin , Lei He, FPGA power reduction using configurable dual-Vdd, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996767]
• 7: A. Gayasen, K. Lee, N. Vijaykrishnan, M. Kandemir, M. J. Irwin, and T. Tuan, "A dual-vdd low power FPGA architecture," in Proc. Intl. Conf. Field-Programmable Logic and its Application, August 2004.
• 8: Fei Li , Yan Lin , Lei He, Vdd programmability to reduce FPGA interconnect power, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.760-765, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382678]
• 9: J. H. Anderson , F. N. Najm, Low-power programmable routing circuitry for FPGAs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.602-609, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382647]
• 10: Yan Lin , Lei He, Leakage efficient chip-level dual-Vdd assignment with time slack allocation for FPGA power reduction, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065769]
• 11: Yan Lin , Fei Li , Lei He, Power modeling and architecture evaluation for FPGA with novel circuits for Vdd programmability, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA [doi>10.1145/1046192.1046218]
• 12: Yu Hu , Yan Lin , Lei He , Tim Tuan, Simultaneous time slack budgeting and retiming for dual-Vdd FPGA power reduction, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147036]
• 13: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 14: S. Ghiasi , E. Bozorgzadeh , S. Choudhuri , M. Sarrafzadeh, A unified theory of timing budget management, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.653-659, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382657]
• 15: Andrew V. Goldberg, An efficient implementation of a scaling minimum-cost flow algorithm, Journal of Algorithms, v.22 n.1, p.1-29, Jan. 1997 [doi>10.1006/jagm.1995.0805]
• 16: Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill, Inc., New York, NY, 1990
• 17: S. Yang, "Logic synthesis and optimization benchmarks, version 3.0," tech. rep., Microelectronics Center of North Carolina (MCNC), 1991.
• 18: David Lewis , Vaughn Betz , David Jefferson , Andy Lee , Chris Lane , Paul Leventis , Sandy Marquardt , Cameron McClintock , Bruce Pedersen , Giles Powell , Srinivas Reddy , Chris Wysocki , Richard Cliff , Jonathan Rose, The stratixπ routing and logic architecture, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611821]
• 19: M Berkelaar, lp-solver: a public domain (MI)LP solver. ftp://ftp.ics.ele.tue.nl/pub/lp_solve/.
• 20: "Xilinx product datasheets," in http://www.xilinx.com/literature.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design

Keywords:
FPGA, low power, time slack