A high-level clustering algorithm targeting dual Vdd FPGAs

ABSTRACT

Recent advanced power optimizations deployed in commercial FPGAs, laid out a roadmap towards FPGA devices that can be integrated into ultra low power systems. In this article, we present a high-level design tool to support the process of mapping an application onto a FPGA device with dual supply voltages. Our main contribution in this paper is an algorithm, which creates voltage scaling ready clusters by utilizing the timing slack available in the designs. We propose to first create clusters of CLBs within a given CLB-level netlist. This clustering algorithm intends to group chains of CLBs possessing similar amounts of timing slack along their critical path together. Once these clusters are identified, they are placed onto respective V_dd partitions on the device. We have evaluated different dual V_dd fabrics and the potential gain in power consumption is explored. When a subset of the logic blocks on the device can be driven by low V_dd levels (either with a dedicated low V_dd supply or with a programmable selection between low and high V_dd levels for these blocks) this affects placement and routing. As a result the maximum frequency of the designs may be affected. In order to evaluate the overall impact of creating voltage islands, we measured the Energy-Delay Product for our benchmark designs. We observed that the Energy-Delay product can be decreased by 26.9% when the placement of the designs into different voltage levels is guided by our clustering algorithm.

REFERENCES

• 1: Akrout, C., Bialas, J., Canada, M., Cawthron, D., Corr, J., Davari, B., Floyd, R., Geissler, S., Goldblatt, R., Houle, R., Kartschoke, P., Kramer, D., McCormick, P., Rohrer, N., Salem, G., Schulz, R., Su, L., and Whitney, L. 1998. A 480 MHz RISC microprocessor in a 0.12 μm L_eff CMOS technology with copper interconnects. IEEE Solid-State Circ. 33, 11, 1609--1616.
• 2: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 3: Eduardo I. Boemo , Guillermo González de Rivera , Sergio López-Buedo , Juan M. Meneses, Some Notes on Power Management on FPGA-Based Systems, Proceedings of the 5th International Workshop on Field-Programmable Logic and Applications, p.149-157, September 01, 1995
• 4: Bozorgzadeh, E., Ghiasi, S., and Sarrafzadeh, M. 2004. Optimal integer delay budget assignment on directed acyclic graphs. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 23, 8, 1184--1199.
• 5: Brasen, D. and Saucier, G. 1998. Using cone structures for circuit partitioning into FPGA packages. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 17, 7, 592--600.
• 6: Pak K. Chan , Martine D. F. Schlag , Jason Y. Zien, Spectral-based multi-way FPGA partitioning, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.133-139, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201331]
• 7: Douglas Chang , Malgorzata Marek-Sadowska, Partitioning Sequential Circuits on Dynamically Reconfigurable FPGAs, IEEE Transactions on Computers, v.48 n.6, p.565-578, June 1999 [doi>10.1109/12.773794]
• 8: 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]
• 9: Chunhong Chen , Ankur Srivastava , Majid Sarrafzadeh, On gate level power optimization using dual-supply voltages, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.5, p.616-629, October 2001 [doi>10.1109/92.953496]
• 10: Deming Chen , Jason Cong , Yiping Fan, Low-power high-level synthesis for FPGA architectures, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871541]
• 11: Deming Chen , Jason Cong , Fei Li , Lei He, Low-power technology mapping for FPGA architectures with dual supply voltages, 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.968297]
• 12: Lerong Cheng , Phoebe Wong , Fei Li , Yan Lin , Lei He, Device and architecture co-optimization for FPGA power reduction, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065819]
• 13: Gayasen, A., Lee, K., Vijaykrishnan, N., Kandemir, M., Irwin, M. J., and Tuan, T. 2004a. A dual-VDD low power FPGA architecture. Field Programmable Logic and its Applications (FPL).
• 14: A. Gayasen , Y. Tsai , N. Vijaykrishnan , M. Kandemir , M. J. Irwin , T. Tuan, Reducing leakage energy in FPGAs using region-constrained placement, 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.968289]
• 15: Kinshuk Govil , Edwin Chan , Hal Wasserman, Comparing algorithm for dynamic speed-setting of a low-power CPU, Proceedings of the 1st annual international conference on Mobile computing and networking, p.13-25, November 13-15, 1995, Berkeley, California, United States [doi>10.1145/215530.215546]
• 16: Hamada, M., Takahashi, M., Arakida, H., Chiba, A., Terazawa, T., Ishikawa, T., Kanazawa, M., Igarashi, M., Usami, K., and Kuroda, T. 1998. A top-down low power design technique using clustered voltage scaling with variable supply-voltage scheme. Proceedings of the Custom Integrated Circuits Conference.
• 17: 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]
• 18: Anoop Iyer , Diana Marculescu, Power efficiency of voltage scaling in multiple clock, multiple voltage cores, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.379-386, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774629]
• 19: Kao, J. T. and Chandrakasan, A. P. 2000. Dual-threshold voltage techniques for low-power digital circuits. IEEE J. Solid-State Circ. 35, 7, 1009--1018.
• 20: Roman Kužnar , Franc Brglez , Krzysztof Kozminski, Cost minimization of partitions into multiple devices, Proceedings of the 30th international conference on Design automation, p.315-320, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164910]
• 21: 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]
• 22: 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]
• 23: 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]
• 24: 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]
• 25: Hao Li , Srinivas Katkoori , Wai-Kei Mak, Power minimization algorithms for LUT-based FPGA technology mapping, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.9 n.1, p.33-51, January 2004 [doi>10.1145/966137.966139]
• 26: Lin, Y. and He, L. 2006a. Dual-V_dd interconnect with chip-level time slack allocation for FPGA power reduction. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 25, 10, 2023--2034.
• 27: Yan Lin , Yu Hu , Lei He , Vijay Raghunat, An efficient chip-level time slack allocation algorithm for Dual-Vdd FPGA power reduction, Proceedings of the 2006 international symposium on Low power electronics and design, October 04-06, 2006, Tegernsee, Bavaria, Germany [doi>10.1145/1165573.1165613]
• 28: Yan Lin , Fei Li , Lei He, Routing track duplication with fine-grained power-gating for FPGA interconnect power reduction, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120984]
• 29: Huiqun Liu , D. F. Wong, Circuit partitioning for dynamically reconfigurable FPGAs, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.187-194, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296456]
• 30: Mondal, S. and Ogrenci Memik, S. 2005. A low power FPGA routing architecture. Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS).
• 31: Mukherjee, R. and Ogrenci Memik, S. 2004. Power-driven partitioning. In Proceedings of the Field Programmable Logic and its Applications (FPL).
• 32: Kara K. W. Poon , Steven J. E. Wilton , Andy Yan, A detailed power model for field-programmable gate arrays, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.2, p.279-302, April 2005 [doi>10.1145/1059876.1059881]
• 33: Ruchir Puri , Leon Stok , John Cohn , David Kung , David Pan , Dennis Sylvester , Ashish Srivastava , Sarvesh Kulkarni, Pushing ASIC performance in a power envelope, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776032]
• 34: Tajana Simunic , Luca Benini , Andrea Acquaviva , Peter Glynn , Giovanni De Micheli, Dynamic voltage scaling and power management for portable systems, Proceedings of the 38th conference on Design automation, p.524-529, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379016]
• 35: Supamas Sirichotiyakul , Tim Edwards , Chanhee Oh , Jingyan Zuo , Abhijit Dharchoudhury , Rajendran Panda , David Blaauw, Stand-by power minimization through simultaneous threshold voltage selection and circuit sizing, Proceedings of the 36th ACM/IEEE conference on Design automation, p.436-441, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309975]
• 36: Kimiyoshi Usami , Mark Horowitz, Clustered voltage scaling technique for low-power design, Proceedings of the 1995 international symposium on Low power design, p.3-8, April 23-26, 1995, Dana Point, California, United States [doi>10.1145/224081.224083]
• 37: Kimiyoshi Usami , Mutsunori Igarashi, Low-power design methodology and applications utilizing dual supply voltages, Proceedings of the 2000 conference on Asia South Pacific design automation, p.123-128, January 2000, Yokohama, Japan [doi>10.1145/368434.368590]
• 38: Wang, Q. and Vrudhula, S. 2002. Algorithms for minimizing standby power in deep submicron, dual-V_t CMOS circuits. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 21, 3, 306--318.
• 39: Zhi-Hong Wang , En-Cheng Liu , Jianbang Lai , Ting-Chi Wang, Power minization in LUT-based FPGA technology mapping, Proceedings of the 2001 conference on Asia South Pacific design automation, p.635-640, January 2001, Yokohama, Japan [doi>10.1145/370155.370569]
• 40: Chingwei Yeh , Min-Cheng Chang , Shih-Chieh Chang , Wen-Bone Jone, Gate-level design exploiting dual supply voltages for power-driven applications, Proceedings of the 36th ACM/IEEE conference on Design automation, p.68-71, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309873]

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
Dynamic power, clustering, field programmable gate arrays, partitioning, placement, voltage scaling