Physical synthesis for FPGA interconnect power reduction by dual-Vdd budgeting and retiming

ABSTRACT

Field programmable dual-Vdd interconnects are effective in reducing FPGA power. We formulate the dual-Vdd-aware slack budgeting problem as a linear program (LP) and a min-cost network flow problem, respectively. Both algorithms reduce interconnect power by 50% on average compared to single-Vdd interconnects, but the network-flow-based algorithm runs 11x faster on MCNC benchmarks. Furthermore, we develop simultaneous retiming and slack budgeting (SRSB) with flip-flop layout constraints in dual-Vdd FPGAs based on mixed integer linear programming, and speed-up the algorithm by LP relaxation and local legalization. Compared to retiming followed by slack budgeting, SRSB reduces interconnect power by up to 28.8%.

REFERENCES

• 1: Altera. 2006. The Stratix III devices. http://www.altera.com/literature/lit-stx3.jsp.
• 2: Unni Narayanan , Peichen Pan , C. L. Liu, Low power logic synthesis under a general delay model, Proceedings of the 1998 international symposium on Low power electronics and design, p.209-214, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280900]
• 3: 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]
• 4: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 5: BPTM. 2002. Berkeley predictive technology model. http://www.device.eecs.berkeley.edu/ptm/mosfet.html.
• 6: Noureddine Chabini , Ismaïl Chabini , El Mostapha Aboulhamid , Yvon Savaria, Unification of basic retiming and supply voltage scaling to minimize dynamic power consumption for synchronous digital designs, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA [doi>10.1145/764808.764865]
• 7: D. Chen , J. Cong, DAOmap: a depth-optimal area optimization mapping algorithm for FPGA designs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.752-759, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382677]
• 8: Jason Cong , Honching Li , Chang Wu, Simultaneous circuit partitioning/clustering with retiming for performance optimization, Proceedings of the 36th ACM/IEEE conference on Design automation, p.460-465, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309980]
• 9: Jason Cong , Sung Kyu Lim, Physical planning with retiming, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 10: Jason Cong , Chang Wu, An Improved Algorithm for Performance Optimal Technology Mapping with Retiming in LUT-Based FPGA Desig, Proceedings of the 1996 International Conference on Computer Design, VLSI in Computers and Processors, p.572-578, October 07-09, 1996
• 11: Jason Cong , Chang Wu, FPGA synthesis with retiming and pipelining for clock period minimization of sequential circuits, Proceedings of the 34th annual conference on Design automation, p.644-649, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266309]
• 12: Cong, J. and Wu, C. 1998a. An efficient algorithm for performance-optimal FPGA technology mapping with retiming. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 17, 9, 489--498.
• 13: Jason Cong , Chang Wu, Optimal FPGA mapping and retiming with efficient initial state computation, Proceedings of the 35th annual conference on Design automation, p.330-335, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277139]
• 14: Jason Cong , Xin Yuan, Multilevel global placement with retiming, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775887]
• 15: Robert Fischer , Klaus Buchenrieder , Ulrich Nageldinger, Reducing the Power Consumption of FPGAs through Retiming, Proceedings of the 12th IEEE International Conference and Workshops on Engineering of Computer-Based Systems, p.89-94, April 04-07, 2005 [doi>10.1109/ECBS.2005.58]
• 16: Gayasen, A., Lee, K., Vijaykrishnan, N., Kandemir, M., Irwin, M. J., and Tuan, T. 2004. A dual-VDD low power FPGA architecture. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL).
• 17: 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]
• 18: 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 ]
• 19: Hamada, M. 1998. A top-down low power design technique using clustered voltage scaling with variable supply-voltage scheme. In Proceedings of the IEEE Custom Integrated Circuits Conference (CICC).
• 20: Yu-Lung Hsu , Sying-Jyan Wang, Retiming-based logic synthesis for low-power, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566480]
• 21: Leiserson, C. L. and Saxe, J. B. 1991. Retiming synchronous circuitry. Algorithmica, 5--35.
• 22: David Lewis , Elias Ahmed , Gregg Baeckler , Vaughn Betz , Mark Bourgeault , David Cashman , David Galloway , Mike Hutton , Chris Lane , Andy Lee , Paul Leventis , Sandy Marquardt , Cameron McClintock , Ketan Padalia , Bruce Pedersen , Giles Powell , Boris Ratchev , Srinivas Reddy , Jay Schleicher , Kevin Stevens , Richard Yuan , Richard Cliff , Jonathan Rose, The Stratix II logic and routing architecture, 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.1046195]
• 23: 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]
• 24: 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]
• 25: 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]
• 26: 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]
• 27: Chuan Lin , Hai Zhou, Optimal wire retiming without binary search, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.452-458, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382619]
• 28: Lin, Y. and He, L. 2006. Dual-VDD interconnect with chip-level time slack allocation for FPGA power reduction. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst.
• 29: Lin, Y., Li, F., and He, L. 2005a. Circuits and architectures for field programmable gate array with configurable supply voltage. IEEE Trans. VLSI 13, 9, 1035--1047.
• 30: 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]
• 31: José Monteiro , Srinivas Devadas , Abhijit Ghosh, Retiming sequential circuits for low power, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.398-402, November 07-11, 1993, Santa Clara, California, United States
• 32: MOSEK. 2006. MOSEK Optimization Toolbox. http://www.mosek.com.
• 33: Pan, P., Karandikar, A. K., and Liu, C. L. 1998. Optimal clock period clustering for sequential circuits with retiming. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst.
• 34: Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill, Inc., New York, NY, 1990
• 35: Tzu-Chieh Tien , Hsiao-Pin Su , Yu-Wen Tsay , Yih-Chih Chou , Youn-Long Lin, Integrating logic retiming and register placement, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.136-139, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288591]
• 36: Gilson I. Wirth , Michele G. Vieira , Egas Henes Neto , F. G. L. Kastensmidt, Single event transients in combinatorial circuits, Proceedings of the 18th annual symposium on Integrated circuits and system design, September 04-07, 2005, Florianolpolis, Brazil [doi>10.1145/1081081.1081115]
• 37: Xilinx. 2005. Xilinx product datasheets. http://www.xilinx.com/literature.
• 38: Xilinx. 2006. Xilinx ISE software manuals and help. http://www.xilinx.com/support/sw_manuals/xilinx9/index.htm.
• 39: Yang, S. 1991. Logic Synthesis and Optimization Benchmarks, Version 3.0. Microelectronics Center of North Carolina (MCNC).
• 40: Chao-Yang Yeh , Malgorzata Marek-Sadowska, Delay budgeting in sequential circuit with application on FPGA placement, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775886]
• 41: Chao-Yang Yeh , Malgorzata Marek-Sadowska, Minimum-Area Sequential Budgeting for FPGA, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.813, November 09-13, 2003 [doi>10.1109/ICCAD.2003.95]

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
FPGA, Low power, retiming