Three-dimensional place and route for FPGAs

ABSTRACT

We present timing-driven partitioning and simulated annealing based placement algorithms together with a detailed routing tool for 3D FPGA integration. The circuit is first divided into layers with limited number of inter-layer vias, and then placed on individual layers, while minimizing the delay of critical paths. We use our tool as a platform to explore the potential benefits in terms of delay and wire-length that 3D technologies can offer for FPGA fabrics. Experimental results show on average a total decrease of 21% in wire-length and 24% in delay, can be achieved over traditional 2D chips, when five layers are used in 3D integration.

REFERENCES

• 1: A. J. Alexander, J. P. Cohoon, Jared L. Colflesh, J. Karro, and G. Robins, "Three-Dimensional Field-Programmable Gate Arrays", Proc. Intl. ASIC Conf., pp. 253--256, 1995.
• 2: A. J. Alexander, J. P. Cohoon, Jared L. Colflesh, J. Karro, E. L. Peters, and G. Robins, "Placement and Routing for Three-Dimensional FPGAs", Fourth Canadian Workshop on Field-Programmable Devices, pp. 11--18, 1996.
• 3: John Karro , James P. Cohoon, A Spiffy Tool for the Simultaneous Placement and Global Routing for Three-Dimensional Field-Programmable Gate Arrays., Proceedings of the Ninth Great Lakes Symposium on VLSI, p.230, March 04-06, 1999
• 4: 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
• 5: Alexander (Sandy) Marquardt , Vaughn Betz , Jonathan Rose, Using cluster-based logic blocks and timing-driven packing to improve FPGA speed and density, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.37-46, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296426]
• 6: Shamik Das , Anantha Chandrakasan , Rafael Reif, Design tools for 3-D integrated circuits, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119783]
• 7: Shamik Das , Anantha Chandrakasan , Rafael Reif, Three-Dimensional Integrated Circuits: Performance, Design Methodology, and CAD Tools, Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI'03), p.13, February 20-21, 2003
• 8: Fabrication Technologies for Three-Dimensional Integrated Circuits, Proceedings of the 3rd International Symposium on Quality Electronic Design, p.33, March 18-21, 2002
• 9: K. W. Lee, T. Nakamura, T. Ono, Y. Yamada, T. Mizukusa, H. Hashimoto, K. T. Park, H. Kurino, and M. Koyanagi, "Three-dimensional shared memory fabricated using wafer stacking technology", in Technical Digest of the International Electron Devices Meeting, pp. 165--168, 2000.
• 10: Arifur Rahman , Shamik Das , Anantha Chandraksan , Rafael Reif, Wiring requirement and three-dimensional integration of field-programmable gate arrays, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.107-113, March 31-April 01, 2001, Sonoma, California, United States [doi>10.1145/368640.368739]
• 11: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 12: Yangdong Deng , Wojciech P. Maly, Interconnect characteristics of 2.5-D system integration scheme, Proceedings of the 2001 international symposium on Physical design, p.171-175, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369763]
• 13: Pongstorn Maidee , Cristinel Ababei , Kia Bazargan, Fast timing-driven partitioning-based placement for island style FPGAs, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775984]
• 14: Yun-Cheng Ju , Resve A. Saleh, Incremental techniques for the identification of statically sensitizable critical paths, Proceedings of the 28th conference on ACM/IEEE design automation, p.541-546, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127729]
• 15: Brent Goplen , Sachin Sapatnekar, Efficient Thermal Placement of Standard Cells in 3D ICs using a Force Directed Approach, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.86, November 09-13, 2003 [doi>10.1109/ICCAD.2003.60]
• 16: Stefan Thomas Obenaus , Ted H. Szymanski, Gravity: Fast placement for 3-D VLSI, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.3, p.298-315, July 2003 [doi>10.1145/785411.785413]
• 17: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 18: Carl Ebeling , Larry McMurchie , Scott A. Hauck , Steven Burns, Placement and routing tools for the Triptych FPGA, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.4, p.473-482, Dec. 1995 [doi>10.1109/92.475966 ]
• 19: C. Ababei and K. Bazargan, "Non-contiguous Linear Placement for Reconfigurable Fabrics", Proc. Reconfigurable Architectures Workshop (RAW), 2004.