FPGA technology mapping: a study of optimality

ABSTRACT

This paper attempts to quantify the optimality of FPGA technology mapping algorithms. We develop an algorithm, based on Boolean satisfiability (SAT), that is able to map a small subcircuit into the smallest possible number of lookup tables (LUTs) needed to realize its functionality. We iteratively apply this technique to small portions of circuits that have already been technology mapped by the best available mapping algorithms for FPGAs. In many cases, the optimal mapping of the subcircuit uses fewer LUTs than is obtained by the technology mapping algorithm. We show that for some circuits the total area improvement can be up to 67%.

References

1. Altera. Component selector guide ver 14.0, 2004.
2. R. K. Brayton and G. D. H. et al. VIS: a system for verification and synthesis. In Proceedings of the Eighth International Conference on Computer Aided Verification CAV, pages 428--432, 1996.
3. D. Chai, J. Jiang, Y. Jiang, Y. Li, A. Mishchenko, and R. Brayton. MVSIS 2.0 Programmer's Manual, UC Berkeley. Technical report, 2003.
4. J. Cong and Y. Ding. On area/depth trade-off in LUT-based FPGA technology mapping. In Design Automation Conference, pages 213--218, 1993.
5. J. Cong, J. Peck, and Y. Ding. RASP: A general logic synthesis system for SRAM-based FPGAs. In FPGA, pages 137--143, 1996.
6. J. Cong, C. Wu, and Y. Ding. Cut ranking and pruning: enabling a general and effcient fpga mapping solution. In Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, pages 29--35. ACM Press, 1999.
7. J. Cong, C. Wu, and Y. Ding. Cut ranking and pruning: Enabling a general and effcient FPGA mapping solution. In FPGA, pages 29--35, 1999.
8. F. Corno, M. Reorda, and G. Squillero. RT-level ITC 99 benchmarks and first ATPG results, 2000.
9. L. L. C. M. R. M. A. S. H. S. P. R. S. R. K. B. E. M. Sentovich, K. J. Singh and A. Sangiovanni-Vincentelli. SIS: A system for sequential circuit synthesis. Technical report, 1992.
10. A. Farrahi and M. Sarrafzadeh. Complexity of the Lookup-Table Minimization Problem for FPGA Technology Mapping. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13(11):1319--1332, 1994.
11. R. J. Francis, J. Rose, and K. Chung. Chortle: a technology mapping program for lookup table-based field programmable gate arrays. In Proceedings of the 27th ACM/IEEE conference on Design automation, pages 613--619. ACM Press, 1990.
12. W. L. Jason Cong, Joey Y. Lin. Spfd-based global rewiring. In Proceeding of International Symposium on FPGAs, pages 77--84, February 2002.
13. K. Keutzer. Dagon: Technology binding and local optimization by dag matching. In DAC, pages 341--347, 1987.
14. T. Larrabee. Test Pattern Generation Using Boolean Satisfiablity. IEEE Transactions on Computer-Aided Design, 11(1):6--22, 1992.
15. I. Levin and R. Y. Pinter. Realizing Expression Graphs using Table-Lookup FPGAs. In Proceedings of the European Design Automation Conference, pages 306--311, 1993.
16. M. W. Moskewicz, C. F. Madigan, Y. Zhao, L. Zhang, and S. Malik. Chaff: Engineering an Effcient SAT Solver. In Proceedings of the 38th Design Automation Conference (DAC'01), 2001.
17. M. D. F. Schlag, J. Kong, and P. K. Chan. Routability-driven techology mapping for lookup-table-based fpgas. In Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, pages 86--90. IEEE Computer Society, 1992.
18. Xilinx. Virtex-ii complete data sheet ver 3.3, 2004.
19. S. Yamashita, H. Sawada, and A. Nagoya. A new method to express functional permissibilities for LUT based FPGAs and its applications. In ICCAD, pages 254--261, 1996.
20. S. Yang. Logic synthesis and optimization benchmarks user guide version, 1991.

Index Terms

• Hardware

  • Integrated circuits

    • Logic circuits