Navin Vemuri
Abstract
Contemporary FPGA synthesis is a multiphase process that involves technology-independent logic optimization followed by FPGA-specific mapping to a target FPGA technology. Conventional technology-independent transformations target standard cells and are unable to optimize circuits with constraints and goals specific to FPGA architectures. This article describes an FPGA-specific logic synthesis approach, which unites multilevel logic transformation, decomposition, and optimization techniques into a single synthesis framework. This system performs network transformation, decomposition, and optimization at an early stage to generate a network that can be directly mapped onto FPGAs. Our techniques are built upon a BDD-based logic decomposition system. With this system, both AND-OR decompositions and AND-XOR decompositions can be identified, resulting in large area savings for synthesized XOR-intensive circuits. To induce good decompositions, a maximum fanout free cone (MFFC) -based partial clustering and collapsing technique is used. This step is followed by an area-minimizing variable partitioning heuristic that decomposes collapsed nodes into LUT-feasible subfunctions. As a postprocessing step, a performance-driven resynthesis phase is performed to alleviate increased delay caused by excessive logic sharing. We compare the quality of results obtained using our techniques with those of academic (BoolMap, SIS) and industry (Altera Quartus) FPGA synthesis tools. Experimental results indicate that the circuits generated by our techniques are not only smaller, but are also significantly faster than those synthesized by conventional FPGA synthesis tools. Furthermore, the computation times required by our techniques are significantly smaller than those of previous techniques.
- Ashenhurst, R. L. 1959. The decomposition of switching functions. In Proceedings of the International Symposium on Theory of Switching Functions, 74--116.Google Scholar
- Babba, B. and Crastes, M. 1992. Automatic synthesis on table lookup-based FPGAs. In Proceedings of the Euro-ASIC (May), 25--31.Google Scholar
- Brayton, R. K., Hachtel, G. D., McMullen, C. T., and Sangiovanni-Vincentelli, A. L. 1984. Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic, Hingham, Mass. Google Scholar
- Brayton, R. K., Rudell, R., Sangiovanni-Vincentelli, A., and Wang, A. R. 1987. MIS: A multiple-level logic optimization system. IEEE Trans. Comput. Aided Des., 1062--1081.Google ScholarDigital Library
- Bryant, R. E. 1986. Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C-35, 677--691. Google Scholar
- Chang, S. C., Marek-Sadowska, M., and Hwang, T. T. 1996. Technology mapping for TLU FPGA's based on decomposition of binary decision diagrams. Proc. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst., 1226--1236. Google Scholar
- Chen, G. and Cong, J. 2001. Simultaneous logic decomposition with technology mapping in FPGA designs. In Proceedings of the International Symposium on Field Programmable Gate Arrays (February), 48--55. Google Scholar
- Chen, K. C., Cong, J., Ding, Y., Kahng, A. B., and Trajmar, P. 1992. DAG-Map: Graph-based FPGA technology mapping for delay optimization. In IEEE Design and Test of Computers (Sept.), 7--20. Google Scholar
- Cong, J. and Ding, Y. 1993. Beyond the combinatorial limit in depth minimization for LUT-based FPGA designs. In Proceedings of the 1993 IEEE/ACM International Conference on CAD (Santa Clara, Calif., November), 110--114. Google Scholar
- Cong, J. and Ding, Y. 1994. Flowmap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. CAD 13, 1--12.Google ScholarDigital Library
- Cong, J., Li, Z., and Bagrodia, R. 1994. Acyclic multi-way partitioning of boolean networks. In Proceedings of DAC, 670--675. Google Scholar
- Cong, J., Peck, J., and Ding, Y. 1996. RASP: A general logic synthesis system for SRAM-based FPGAs. In Proceedings of the ACM 4th International Symposium on FPGAs, 137--143. Google Scholar
- Coudert, O. and Madre, J. 1990. A unified framework for the formal verification of sequential circuits. In Proceedings of ICCAD, 126--129.Google Scholar
- DeMicheli, G. 1994. Synthesis and Optimization of Digital Circuits. McGraw-Hill, Hightstown, NJ. Google Scholar
- Eckl, K., Legl, C., and Wurth, B. 1996. TOS Version 2.2: User Manual. Institute of Elec. Design Automation, Technical University of Munich.Google Scholar
- Filo, D., Yang, J. C., Mailhot, F., and De Micheli, G. 1991. Technology mapping for two output based FPGAs. In Proceedings of EDAC, 534--538. Google Scholar
- Francis, R., Rose, J., and Chung, K. 1990. Chortle: A technology mapping for lookup table-based field programmable gate arrays. In Proceedings of the of the Design Automation Conference, 613--619. Google Scholar
- Francis, R., Rose, J., and Vranesic, Z. 1995. Chortle-crf: Fast technology mapping for lookup table-based FPGAs. In Proceedings of the International Symposium on Theory of Switching Functions, 74--116. Google Scholar
- Hactel, G. D. and Somenzi, F. 1996. Logic Synthesis and Verification Algorithms. Kluwer Academic, Dordrecht, The Netherlands. Google Scholar
- Jiang, J.-H., Jout, J.-Y., Huang, J.-D., and Wei, J.-S. 1997. A variable partitioning algorithm of BDD for FPGA technology mapping. IEEE Trans. Fund. E80-Ad, 10 (Oct.), 1813--1819.Google Scholar
- Karplus, K. 1991. XMAP: A technology mapper for table-lookup based FPGAs. In Proceedings of DAC, 240--243. Google Scholar
- Lai, Y. T., Pedram, M., and Vrudhula, S. 1993. BDD based decomposition of logic functions with application to FPGA synthesis. In Proceedings of the Thirtieth Design Automation Conference (June), 642--647. Google Scholar
- Legl, C., Wurth, B., and Eckl, K. 1996. A Boolean approach to performance-directed technology mapping for LUT-based FPGA designs. In Proceedings of the Design Automation Conference, 74--116. Google Scholar
- Murgai, R., Brayton, R. K., and Sangiovanni-Vincentelli, A. 1995. Logic Synthesis for Field-Programmable Gate Arrays. Kluwer Academic, Dordrecht, The Netherlands. Google Scholar
- Murgai, R., Nishizaki, Y., Brayton, R. K., and Sangiovanni-Vincentelli, A. 1990. Logic synthesis for programmable gate arrays. In Proceedings of DAC, 620--625. Google Scholar
- Narayan, A., Jain, J., Fujita, M., and Sangiovanni-Vincentelli, A. 1996. Partitioned-ROBDDs: A compact canonical and efficient representation for boolean functions. In Proceedings of ICCAD, 547--554. Google Scholar
- Roth, J. P. and Karp, R. M. 1962. Minimization over Boolean graphs. IBM J. Res. Dev. 6, 227--238.Google ScholarDigital Library
- Savage, J. E. 1976. The Complexity of Computing. Wiley Interscience, New York. Google Scholar
- Sawada, H., Suyama, T., and Nagoya, A. 1995. Logic Synthesis for look-up table based FPGAs using functional decomposition and support minimization. In Proceedings of the International Conference on Computer-Aided Design, 54--59. Google Scholar
- Sawkar, P. and Thomas, D. 1992. Area and delay mapping for table-look up based field programmable gate arrays. In Proceedings of the Design Automation Conference (June), 368--373. Google Scholar
- Sentovich, E. M., Singh, K. J., Lavagno, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., Stephan, P. H., Brayton, R. K., and Sangiovanni-Vincentelli, A. 1992. SIS: A system for sequential circuit synthesis. Tech. Rep. UCB/ERL M92/41 (March), Dept. of EECS, University of California, Berkeley.Google Scholar
- Sicard, P., Crastes, M., Sakouti, K., and Saucier, G. 1991. Automatic synthesis of Boolean functions on Xilinx and Alcatel programmable devices. In Proceedings of Euro ASIC, 142--145.Google Scholar
- Singh, K. J., Wang, A. R., Brayton, R. K., and Sangiovanni-Vincentelli, A. 1988. Timing optimization of combinational logic. IEEE Trans. Comput. Aided Des., 282--285.Google Scholar
- Stanion, T. and Sechen, C. 1995. A method for finding good Ashenhurst decompositions and its application to FPGA synthesis. In Proceedings of the 32nd ACM/IEEE Design Automation Conference, 74--116. Google Scholar
- Trimberger, S. 1994. Field Programmable Gate Array Technology. Kluwer Academic, Boston. Google Scholar
- Yang, C. 2000. BDD-based logic synthesis system. PhD Thesis, University of Massachusetts, Amherst. Google Scholar
- Yang, C., Singhal, V., and Ciesielski, M. J. 1999. BDD decomposition for efficient logic synthesis. In Proceedings of ICCD. Google Scholar
- Yang, C., Singhal, V., and Ciesielski, M. J. 2000. BDS: A BDD-based logic synthesis system. In Proceedings of DAC. Google Scholar
Index Terms
- BDD-based logic synthesis for LUT-based FPGAs
Recommendations
Combinational logic synthesis for LUT based field programmable gate arrays
The increasing popularity of the field programmable gate-array (FPGA) technology has generated a great deal of interest in the algorithmic study and tool development for FPGA-specific design automation problems. The most widely used FPGAs are LUT based ...
BDS-MAJ: a BDD-based logic synthesis tool exploiting majority logic decomposition
DAC '13: Proceedings of the 50th Annual Design Automation ConferenceDespite the impressive advance of logic synthesis during the past decades, a general methodology capable of efficiently synthesizing both control and datapath logic is still missing. Indeed, while synthesis techniques for random control logic (AND/OR-...
BDD Decomposition for Efficient Logic Synthesis
ICCD '99: Proceedings of the 1999 IEEE International Conference on Computer DesignA unified logic optimization method efficient at handling both AND/OR-intensive and XOR-intensive functions is proposed. The method is based on iterative BDD decomposition using various dominators. Detail analysis of decomposable BDD structures leading ...
Comments