FPGA technology mapping with encoded libraries andstaged priority cuts

ABSTRACT

Technology mapping is an important step in the FPGA CAD flow in which a network of simple gates is converted into a network of logic blocks. We consider enhancements to a traditional LUT-based mapping algorithm for an FPGA comprised of logic blocks which implement only a subset of functions of up to k variables--specifically, the logic block is a partial LUT, but it possesses more inputs than typical LUTs. Numerical results are presented to demonstrate the efficacy of our proposed techniques using real circuits mapped to a commercial FPGA architecture.

References

1. A. Abdollanhi and M. Pedram. A new canonical form for fast Boolean matching in logic synthesis and verification. In Proc. DAC, pages 379--384, 2005.
2. Actel Corporation. Axcelerator family FPGAs datasheet v2.6. Actel, 2005.
3. Altera Corporation. Stratix II Device Handbook, Volume 1. Altera, 2007.
4. D. Chai and A. Kuelmann. Building a better Boolean matcher and symmetry detector. In Proc. DATE, pages 1079--1084, 2006.
5. S. Chatterjee, A. Mishchenko, and R. Brayton. Factor cuts. In Proc. ICCAD, pages 143--150, 2006.
6. D. Chen and J. Cong. DAOmap: A depth-optimal area optimization mapping algorithm for FPGA designs. In Proc. ICCAD, pages 752--759, 2004.
7. S. Cho, S. Chatterjee, A. Mishchenko, and R. Brayton. Efficient FPGA mapping using priority cuts. In Proc. FPGA, 2007.
8. J. Cong and Y. Ding. FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based fpga designs. TCAD, 13(1):1--12, January 1994.
9. J. Cong and Y. Ding. Combinational logic synthesis for LUT based field programmable gate arrays. TODAES, 1(2):145--204, April 1996.
10. J. Cong and K. Minkovich. Improved SAT-based Boolean matching using implicants for LUT-based FPGAs. In Proc. FPGA, pages 139--147, 2007.
11. J. Cong, C. Wu, and Y. Ding. Cut ranking and pruning: enabling a general and efficient FPGA mapping solution. In Proc. FPGA, pages 29--35, 1999.
12. W. Gunther and R. Drechsler. ACTion: combining logic synthesis and technology mapping for mux based FPGAs. In Proc. EUROMICRO, pages 130--137, 2000.
13. Y. Hu, S. Das, S. Trimberger, and L. He. Design, synthesis and evaluation of heterogeneous FPGA with mixed LUTs and macro-gates. In Proc. ICCAD, pages 188--193, 2007.
14. Y. Hu, V. Shih, R. Majumdar, and L. He. Exploiting symmetry in SAT-based Boolean matching for heterogeneous FPGA technology mapping. In Proc. ICCAD, pages 350--353, 2007.
15. Y. Hu, V. Shih, R. Majumdar, and L. He. Exploiting symmetry in SAT-based Boolean matching for heterogeneous FPGA technology mapping. In Proc. IWLS, 2007.
16. M. Hutton, J. Schleicher, D. Lewis, B. Pedersen, R. Yuan, S. Kaptanoglu, G. Baeckler, B. Ratchev, K. Padalia, M. Bourgeault, A. Lee, H. Kim, and R. Saini. Improving FPGA performance and area using an adaptive logic module. In Proc. FPL, pages 135--144, 2004.
17. S. Jang, K. Chan, A. Mishchenko, and R. K. Brayton. WireMap: FPGA technology mapping for improved routability. In Proc. FPGA, pages 47--55, 2008.
18. E. Lehman, Y. Watanabe, J. Grodstein, and H. Harkness. Logic decomposition during technology mapping. TCAD, 16(8):2331--2340, August 1997.
19. D. Lewis, E. Ahmed, G. Baeckler, V. Betz, M. Bourgeault, D. Cashman, D. Galloway, M. Hutton, C. Lane, A. Lee, P. Leventis, S. Marquardt, C. McClintock, K. Padalia, B. Pedersen, G. Powell, B. Ratchev, S. Reddy, J. Schleicher, K. Stevens, R. Yuan, R. Cliff, and J. Rose. The Stratix II logic and routing architecture. In Proc. FPGA, pages 14--20, 2005.
20. A. Ling, D. Singh, and S. Brown. FPGA technology mapping: a study in optimality. In Proc. DAC, pages 427--432, 2005.
21. V. Manohararajah, S. D. Brown, and Z. G. Vranesic. Heuristics for area minimization in LUT-based FPGA technology mapping. TCAD, 25(11):2331--2340, November 2006.
22. M. Marik and A. Pal. Logic synthesis and technology mapping of mux-based FPGAs for high performance and low power. In Proc. TENCON, pages 419--422, 2004.
23. A. Mishchenko, S. Chatterjee, and R. Brayton. Improvements to technology mapping for LUT-based FPGAs. TCAD, 26(2):250--253, February 2007.
24. A. Mishchenko, S. Chatterjee, R. Jiang, and R. K. Brayton. FRAIGs: A unifying representation for logic synthesis and verification. Technical report, ERL technical report, UC Berkeley, March 2005.
25. A. Mishchenko, S. Cho, S. Chatterjee, and R. Brayton. Combinational and sequential mapping with priority cuts. In Proc. ICCAD, pages 354--361, 2007.
26. S. Safarpour, A. Veneris, G. Baecklet, and R. Yuan. Efficient SAT-based Boolean matching for FPGA technology mapping. In Proc. DAC, pages 466--471, 2006.
27. K. Yi and S. Y. Ohm. A fast and exact cell matching method for mux-based FPGA technology mapping. In Proc. ICCD, pages 319--320, 1999.

Index Terms

• Hardware

  • Electronic design automation

    • High-level and register-transfer level synthesis