Design, synthesis and evaluation of heterogeneous FPGA with mixed LUTs and macro-gates

ABSTRACT

Small gates, such as AND2, XOR2 and MUX2, have been mixed with lookup tables (LUTs) inside the programmable logic block (PLB) to reduce area and power and increase performance in FPGAs. However, it is unclear whether incorporating macro-gates with wide inputs inside PLBs is beneficial. In this paper, we first propose a methodology to extract a small set of logic functions that are able to implement a large portion of functions for given FPGA applications. Assuming that the extracted logic functions are implemented by macro-gates in PLBs, we then develop a complete synthesis flow for such heterogeneous PLBs with mixed LUTs and macro-gates. The flow includes a cut-based delay and area optimized technology mapping, a mixed binary integer and linear programming based area recovery algorithm to balance the resource utilization of macro-gates and LUTs for area-efficient packing, and a SAT-based packing. We finally evaluate the proposed heterogeneous FPGA using the newly developed flow and show that mixing LUT and macro-gates, both with 6 inputs, improves performance by 16.5% and reduces logic area by 30% compared to using merely 6-input LUTs.

REFERENCES

• 1: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 2: "The programmable gate array data book," Xilinx Inc., 1989.
• 3: Jason Cong , Hui Huang , Xin Yuan, Technology mapping and architecture evalution for k/m-macrocell-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.1, p.3-23, January 2005 [doi>10.1145/1044111.1044113]
• 4: "Xilinx datasheets," http://www.xilinx.com/literature.
• 5: A. Cosoroaba and F. Rivoallon, "Achieving higher system performance with the virtex-5 family of FPGAs," in http://www.xilinx.com/literature.
• 6: F. Li and L. He, "Power modeling and characteristics of field programmable gate arrays," TCAD, 2005.
• 7: http://iwls.org/iwls2005/benchmarks.html.
• 8: http://www.eecs.berkeley.edu/alanmi/abc/.
• 9: Jason Cong , Songjie Xu, Delay-optimal technology mapping for FPGAs with heterogeneous LUTs, Proceedings of the 35th annual conference on Design automation, p.704-707, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277221]
• 10: Jason Cong , Chang Wu , Yuzheng Ding, Cut ranking and pruning: enabling a general and efficient FPGA mapping solution, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.29-35, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296425]
• 11: Alireza Kaviani , Stephen Brown, Hybrid FPGA architecture, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.3-9, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228371]
• 12: J. Cong , Y. Ding, An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs, 1992 IEEE/ACM international conference proceedings on Computer-aided design, p.48-53, December 1992, Santa Clara, California, United States
• 13: J. Cong and Y. Ding, "On area/depth trade-off in LUT-based FPGA technology mapping," TVLSI, 1994.
• 14: 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]
• 15: V. Manohara-rajah, et al, "Heuristics for area minimization in LUT-based FPGA technology mapping," IWLS, 2004.
• 16: A. Mishchenko, et al, "Integrating logic synthesis, technology mapping, and retiming," IWLS, 2005.
• 17: Satrajit Chatterjee , Alan Mishchenko , Robert Brayton, Factor cuts, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233531]
• 18: A. Ling, et al, "Fpga logic synthesis using quantified boolean satisfiability," SAT 2005, pp. 444--450.
• 19: Sean Safarpour , Andreas Veneris , Gregg Baeckler , Richard Yuan, Efficient SAT-based Boolean matching for FPGA technology mapping, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147034]
• 20: Donald Chai , Andreas Kuehlmann, Building a better Boolean matcher and symmetry detector, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 21: 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]
• 22: E. M. Sentovich, et al, "SIS: A system for sequential circuit systhesis," Department of Electrical Engineering and Computer Science, Berkeley, CA 94720, 1992.
• 23: Jan M. Rabaey, Digital integrated circuits: a design perspective, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 24: http://www.mosek.com.
• 25: http://www.cs.chalmers.se/Cs/Research/FormalMethods/MiniSat/MiniSat.html.
• 26: Jianshe He, "Technology Mapping and Architecture of Heterogenous Field-Programmable Gate Arrays," M.A.Sc. Thesis, University of Toronto, 1993.
• 27: Kevin Chung, "Architecture and Synthesis of Field-Programmable Gate Arrays with Hard-wired Connections," Ph.D. Thesis, University of Toronto, 1994.