Energy and switch area optimizations for FPGA global routing architectures

ABSTRACT

Low energy and small switch area usage are two important design objectives in FPGA global routing architecture design. This article presents an improved MCF model based CAD flow that performs aggressive optimizations, such as topology and wire style optimization, to reduce the energy and switch area of FPGA global routing architectures. The experiments show that when compared to traditional mesh architecture, the optimized FPGA routing architectures achieve up to 10% to 15% energy savings and up to 20% switch area savings in average for a set of seven benchmark circuits.

REFERENCES

• 1: Christoph Albrecht, Provably good global routing by a new approximation algorithm for multicommodity flow, Proceedings of the 2000 international symposium on Physical design, p.19-25, May 2000, San Diego, California, United States [doi>10.1145/332357.332368]
• 2: Albrecht, C., Kahng, A., Mandoiu, I., and Zelikovsky, A. 2007. Multicommodity flow algorithms for buffered global routing. In Approximation Algorithms and Metaheuristics, Chapter 80.
• 3: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 4: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 5: Brown, S., Khellah, M., and Lemieux, G. 1996. Segmented routing for speed-performance and routability in field-programmable gate arrays. J. VLSI Des. 4, 4, 275--291.
• 6: Stephen Brown , Muhammad Khellah , Zvonko Vranesic, Minimizing FPGA Interconnect Delays, IEEE Design & Test, v.13 n.4, p.16-23, December 1996 [doi>10.1109/54.544532]
• 7: Robert C. Carden, IV , Chung-Kuan Cheng, A global router using an efficient approximate multicommodity multiterminal flow algorithm, Proceedings of the 28th conference on ACM/IEEE design automation, p.316-321, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127687]
• 8: Carden, R., Li, J., and Cheng, C. 1996. A global routing with a theoretical bound on the optimum solution. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 15, 208--216.
• 9: Hongyu Chen , Rui Shi , Chung-Kuan Cheng , David M. Harris, Surfliner: A Distortionless Electrical Signaling Scheme for Speed of Light On-Chip Communications, Proceedings of the 2005 International Conference on Computer Design, p.497-502, October 02-05, 2005 [doi>10.1109/ICCD.2005.102]
• 10: Paul Chow , Jonathan Rose , Soon Ong Seo , Kevin Chung , Gerard Páez-Monzón , Immanuel Rahardja, The design of an SRAM-based field-programmable gate array—part I: architecture, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.7 n.2, p.191-197, June 1999 [doi>10.1109/92.766746]
• 11: Choy, N., Chin, S., Lee, C., Poon, K., Lamoureux, J., Yan, A., Wilton, S., Ang, S.-S., and Luk, W. Power modeling for FPGA's. http://www.ece.ubc.ca/stevew/powermodel.html.
• 12: Philip Christie , Dirk Stroobandt, The interpretation and application of Rent's rule, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.6, p.639-648, Dec. 2000 [doi>10.1109/92.902258]
• 13: Cong, J. and Ding, Y. 1994. Flowmap: An optimal technology mapping algorithm for delay optimization in lookup-table based fpga designs. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 1--12.
• 14: Joni Dambre , Dirk Stroobandt , Jan Van Campenhout, Toward the accurate prediction of placement wire length distributions in VLSI circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.4, p.339-348, April 2004 [doi>10.1109/TVLSI.2004.825851]
• 15: André DeHon , Raphael Rubin, Design of FPGA interconnect for multilevel metallization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.10, p.1038-1050, October 2004 [doi>10.1109/TVLSI.2004.827562]
• 16: Donath, W. E. 1981. Wire length distribution for placements of computer logic. IBM J. Resear. Devel. 25, 152--155.
• 17: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 18: Yuanfang Hu , Hongyu Chen , Yi Zhu , Andrew A. Chien , Chung-Kuan Cheng, Physical Synthesis of Energy-Efficient Networks-on-Chip Through Topology Exploration and Wire Style Optimizationz, Proceedings of the 2005 International Conference on Computer Design, p.111-118, October 02-05, 2005 [doi>10.1109/ICCD.2005.84]
• 19: Yuanfang Hu , Yi Zhu , Hongyu Chen , Ronald Graham , Chung-Kuan Cheng, Communication latency aware low power NoC synthesis, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147058]
• 20: Hutton, M., Rose, J., Grossman, J., and Cornei, D. 1998. Characterization and parameterized generation of synthetic combinational benchmark circuits. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 17, 10, 985--996.
• 21: Khellah, M., Brown, S., and Vranesic, Z. 1994. Minimizing interconnection delays in array-bassed fpgas. In Proceedings of the Custom Integrated Circuits Conference. 181--184.
• 22: Seokjin Lee , Hua Xiang , D. F. Wong , Richard Y. Sun, Wire type assignment for FPGA routing, 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.611828]
• 23: Lemieux, G., Lee, E., Tom, M., and Yu, A. 2004. Directional and single-driver wires in FPGA interconnect. In Proceedings of the IEEE International Conference on Field-Programmable Technology. 41--48.
• 24: Kurt Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs, Information Processing Letters, v.27 n.3, p.125-128, March 25, 1988 [doi>10.1016/0020-0190(88)90066-X]
• 25: 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]
• 26: Sentovich, E. and Al, E. 1992. Sis: A system for sequential circuit analysis. Tech. rep. No. UCB/ERL M92/41, University of California, Berkeley.
• 27: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
• 28: Michael Shyu , Guang-Ming Wu , Yu-Dong Chang , Yao-Wen Chang, Generic Universal Switch Blocks, IEEE Transactions on Computers, v.49 n.4, p.348-359, April 2000 [doi>10.1109/12.844347]
• 29: Yang, S. 1991. Logic synthesis and optimization benchmarks, version 3.0. Tech. rep. Microelectronics Center of North Carolina.
• 30: Andy Ye , Jonathan Rose, Using bus-based connections to improve field-programmable gate array density for implementing datapath circuits, 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.1046194]
• 31: Ye, A., Rose, J., and Lewis, D. 2003. Architecture of datapath-oriented coarse-grain logic and routing for FPGAs. In Proceedings of the Custom Integrated Circuits Conference. 61--64.

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.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Algorithms, Design, Performance

Keywords:
FPGA, global routing, low power