Combinational and sequential mapping with priority cuts

ABSTRACT

An algorithm for technology mapping of combinational and sequential logic networks is proposed and applied to mapping into K-input lookup-tables (K-LUTs). The new algorithm avoids the hurdle of computing all K-input cuts while preserving the quality of the results, in terms of area and depth. The memory and runtime of the proposed algorithm are linear in circuit size and quite affordable even for large industrial designs. For example, computing a good quality 6-LUT mapping of an AIG with IM nodes takes 150Mb of RAM and 1 minute on a typical laptop. An extension of the algorithm allows for sequential mapping, which searches the combined space of all possible mappings and retimings. This leads to an 18--22% improvement in depth with a 3--5% LUT count penalty, compared to combinational mapping followed by retiming.

REFERENCES

• 1: Berkeley Logic Synthesis and Verification Group, ABC: A System for Sequential Synthesis and Verification, Release 70319. http://www.eecs.berkeley.edu/~alanmi/abc/
• 2: J. Cong and Y. Ding, "FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs", IEEE Trans. CAD, vol. 13(1), Jan. 1994, pp. 1--12.
• 3: J. Cong and Y. Ding, "On area/depth trade-off in LUT-based FPGA technology mapping," IEEE Trans. VLSI, vol. 2(2), Jun. 1994, pp 137--148.
• 4: Jason Cong , Yean-Yow Hwang, Simultaneous depth and area minimization in LUT-based FPGA mapping, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.68-74, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201322]
• 5: 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]
• 6: 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]
• 7: N. Een, A. Mishchenko, and N. Sorensson, "Applying logic synthesis to speedup SAT", Proc. SAT '07 (to appear).
• 8: A. Farrahi and M. Sarrafzadeh, "Complexity of lookup-table minimization problem for FPGA technology mapping," IEEE Trans. CAD, vol. 13(11), Nov. 1994, pp. 1319--1332.
• 9: IWLS 2005 Benchmarks. http://iwls.org/iwls2005/benchmarks.html
• 10: Chi-Chou Kao , Yen-Tai Lai, An efficient algorithm for finding the minimal-area FPGA technology mapping, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.1, p.168-186, January 2005 [doi>10.1145/1044111.1044121]
• 11: V. Manohara-rajah, S. D. Brown, and Z. G. Vranesic, "Heuristics for area minimization in LUT-based FPGA technology mapping," Proc. IWLS '04, pp. 14--21.
• 12: A. Mishchenko, S. Chatterjee, and R. Brayton, "Improvements to technology mapping for LUT-based FPGAs". IEEE Trans. CAD, Vol. 26(2), Feb 2007, pp. 240--253. http://www.eecs.berkeley.edu/~alanmi/publications/2006/tcad06_map.pdf
• 13: A. Mishchenko, S. Chatterjee, R. Brayton, and P. Pan, "Integrating logic synthesis, technology mapping, and retiming", ERL Technical Report, EECS Dept., UC Berkeley, Dec. 2006. http://www.eecs.berkeley.edu/~alanmi/publications/2006/dac06_int.pdf
• 14: Peichen Pan , Chih-Chang Lin, A new retiming-based technology mapping algorithm for LUT-based FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.35-42, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275118]
• 15: Deshanand P. Singh , Valavan Manohararajah , Stephen D. Brown, Incremental retiming for FPGA physical synthesis, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065694]