Structural gate decomposition for depth-optimal technology mapping in LUT-based FPGA designs

ABSTRACT

In this paper we study structural gate decomposition in general, simple gate networks for depth-optimal technology mapping using K-input Lookup-Tables (K-LUTs). We show that (1) structural gate decomposition in any K-bounded network results in an optimal mapping depth smaller than or equal to that of the original network, regardless of the decomposition method used; and (2) the problem of structural gate decomposition for depth-optimal technology mapping is NP-hard for K-unbounded networks when K≥3 and remains NP-hard for K-boundeds networks when K≥5. Based on these results, we propose two new structural gate decomposition algorithms, named DOGMA and DOGMA-m, which combine the level-driven node-packing technique (used in FlowMap) and the network flow-based labeling technique (used in Chortle-d) for depth-optimal technology mapping. Experimental results show that (1) among five structural gate decompostion algorithms, DOGMA-m results in the best mapping solutions; and (2) compared with speed_up(an algebraic algorithm) and TOS (a Boolean approach), DOGMA-m completes, decomposition of all tested benchmarks in a short time while speed_up and TOS fail in several cases. However, speed_up results in the smallest depth and area in the following technology mapping steps.

REFERENCES

• 1: ASHENHURST, R. L. 1959. The decomposition of switching functions. Ann. Comput. Lab. Harvard Univ. 29, 74-116.
• 2: Kuang-Chien Chen , Jason Cong , Yuzheng Ding , Andrew B. Kahng , Peter Trajmar, DAG-Map: Graph-Based FPGA Technology Mapping for Delay Optimization, IEEE Design & Test, v.9 n.3, p.7-20, July 1992 [doi>10.1109/54.156154]
• 3: Jason Cong , Yuzheng Ding, Beyond the combinatorial limit in depth minimization for LUT-based FPGA designs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.110-114, November 07-11, 1993, Santa Clara, California, United States
• 4: CONG, g. AND DING, Y. 1994a. Flowmap: An optimal technology mapping algorithm for delay optimization in lookup-table based fpga designs. IEEE Trans. Comput.-Aided Des. (Jan. 1994), 1-12.
• 5: CONG, J. AND DING, Y. 1994b. On area/depth trade-off in lut-based fpga technology mapping. IEEE Trans. Very Large Scale Integr. Syst. 2.
• 6: Jason Cong , Yuzheng Ding, On nominal delay minimization in LUT-based FPGA technology mapping, Integration, the VLSI Journal, v.18 n.1, p.73-94, Dec. 1994 [doi>10.1016/0167-9260(94)90012-4]
• 7: Jason Cong , Yuzheng Ding, Combinational logic synthesis for LUT based field programmable gate arrays, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.2, p.145-204, April 1996 [doi>10.1145/233539.233540]
• 8: 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]
• 9: Jason Cong , John Peck , Yuzheng Ding, RASP: a general logic synthesis system for SRAM-based FPGAs, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.137-143, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228390]
• 10: H. Allen Curtis, A Generalized Tree Circuit, Journal of the ACM (JACM), v.8 n.4, p.484-496, Oct. 1961 [doi>10.1145/321088.321091]
• 11: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 12: Robert Francis , Jonathan Rose , Zvonko Vranesic, Chortle-crf: Fast technology mapping for lookup table-based FPGAs, Proceedings of the 28th conference on ACM/IEEE design automation, p.227-233, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127670]
• 13: FRANCIS, R. J., ROSE, J., AND VRANESIC, Z. 1991b. Technology mapping of lookup table-based fpgas for performance. In Proceedings of the IEEE International Conference on Computer- Aided Design, IEEE Computer Society Press, Los Alamitos, CA, 568-571.
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: HOROWITZ, E. AND SAHNI, S. 1978. Fundamentals of Computer Algorithms. Computer Science Press, Inc., New York, NY.
• 16: Juinn-Dar Huang , Jing-Yang Jou , Wen-Zen Shen, An iterative area/performance trade-off algorithm for LUT-based FPGA technology mapping, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.13-17, November 10-14, 1996, San Jose, California, United States
• 17: Yung-Te Lai , Kuo-Rueih Ricky Pan , Massoud Pedram, FPGA Synthesis Using Function Decomposition, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.30-35, October 10-12, 1994
• 18: Christian Legl , Klaus Eckl , Bernd Wurth, Performance-Directed Technology-Mapping for LUT-Based FPGAs - What Role Do Decomposition and Covering Play?, Proceedings of the 6th International Workshop on Field-Programmable Logic, Smart Applications, New Paradigms and Compilers, p.14-23, September 23-25, 1996
• 19: Christian Legl , Bernd Wurth , Klaus Eckl, A Boolean approach to performance-directed technology mapping for LUT-based FPGA designs, Proceedings of the 33rd annual conference on Design automation, p.730-733, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240657]
• 20: MURGAI, R., SHENOY, N., BRAYTON, R. K., AND SANGIOVANNI-VINCENTELLI, A. 1991. Performance directed synthesis for table look up programmable gate arrays. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD '91, Santa Clara, CA, Nov. 11-14), IEEE Computer Society Press, Los Alamitos, CA, 572-575.
• 21: ROTH, J. P. AND KARP, R. M. 1962. Minimization over boolean graphs. IBM J. Res. Dev., 227-238.
• 22: Richard L. Rudell , Alberto Sangiovanni-Vincentelli, Logic synthesis for vlsi design, 1989
• 23: Prashant Sawkar , Donald Thomas, Performance directed technology mapping for look-up table based FPGAs, Proceedings of the 30th international conference on Design automation, p.208-212, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164672]
• 24: SENTOVICH, E., SINGH, K., LAVAGNO, L., MOON, C., MURGAI, R., SALDANHA, A., SAVOJ, H., STEPHAN, P., BRAYTON, R., AND SANGIOVANNI-VINCENTELLI, A. 1992. SIS: A system for sequential circuit synthesis. Tech. Rep. UCB/ERL M92/41. UC Berkeley, Berkeley, CA.
• 25: Albert Ren Rui Wang, Algorithms for multilevel logic optimization, University of California at Berkeley, Berkeley, CA, 1991
• 26: Bernd Wurth , Klaus Eckl , Kurt Antreich, Functional multiple-output decomposition: theory and an implicit algorithm, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.54-59, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217506]
• 27: Honghua Yang , D. F. Wong, Edge-map: optimal performance driven technology mapping for iterative LUT based FPGA designs, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.150-155, November 06-10, 1994, San Jose, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis
  B.7 INTEGRATED CIRCUITS

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
FPGA, computer-aided design of VSLI, decomposition, delay minimization, logic optimization, programmable logic, simplification, synthesis, system design, technology mapping