Simultaneous logic decomposition with technology mapping in FPGA designs

ABSTRACT

Conventional technology mapping algorithms for SRAM-based Field Programmable Gate Arrays (FPGAs) are normally carried out on a fixed logic decomposition of a circuit. The impact of logic decomposition on delay and area of the technology mapping solutions is not well understood. In this paper, we present an algorithm named SLDMap that performs delay-minimized technology mapping on a large set of decompositions and simultaneously controls the mapping area under delay constraints. Our study leads to two conclusions: (1) For depth minimization, the best algorithms in conventional flow (dmig + CutMap) produce satisfactory results with a short runtime, even with a fixed decomposition; (2) When all the structural decompositions of the 6-bounded Boolean network are explored, SLDMap consistently outperforms the state-of-the-art separate flow (dmig + CutMap) by 12% in depth and 10% in area on average; it also consistently outperforms the state-of-the-art combined approach dogma by 8% in depth and 6% in area on average.

REFERENCES

• 1: Jason Cong , Yean-Yow Hwang, Structural gate decomposition for depth-optimal technology mapping in LUT-based FPGA design, Proceedings of the 33rd annual conference on Design automation, p.726-729, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240656]
• 2: Robert J. Francis , Jonathan Rose , Kevin Chung, Chortle: a technology mapping program for lookup table-based field programmable gate arrays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.613-619, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123418]
• 3: R. Murgai, N. Shenoy, R. K. Brayton and A. Sangiovanni- Vincentelli, Performance Directed Synthesis For Table Lookup Programmable Gate Arrays, IEEE International Conference on CAD, 1991, pp. 572-575.
• 4: 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]
• 5: J. Cong and Y. Ding, FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs, IEEE Trans. on Computer-Aided Design of Integrated Circuits And Systems, 1994, vol. 13, no. 1, pp. 1-12.
• 6: J. Cong and Y. Ding, On Area/Delay Trade-off in LUT-based FPGA Technology Mapping, IEEE Trans. on VLSI Systems, June 1994, vol. 2, no. 2, pp. 137-148.
• 7: 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]
• 8: A. Farrahi and M. Sarrafzadeh, Complexity of the Lookup-Table Minimization Problem for FPGA Technology Mapping, IEEE Trans. on Computer-Aided Design of Integrated Circuits And Systems, 1994, vol. 13, no. 11, pp. 1319-1332.
• 9: 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]
• 10: Eric Lehman , Yosinori Watanabe , Joel Grodstein , Heather Harkness, Logic decomposition during technology mapping, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.264-271, November 05-09, 1995, San Jose, California, United States
• 11: E. Lehman, Y. Watanabe, J. Grodstein and H. Harkness, Logic Decomposition during Technology Mapping, IEEE Trans. on Computer-Aided Design of Integrated Circuits And Systems, 1997, vol. 16, no. 8, pp. 813-834.
• 12: Dirk-Jan Jongeneel , Yosinori Watanbe , Robert K. Brayton , Ralph Otten, Area and search space control for technology mapping, Proceedings of the 37th conference on Design automation, p.86-91, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337321]
• 13: E. Sentovich, K. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. Stephan, R. Brayton and A. Sangiovanni-Vincentelli, SIS: A System for Sequential Circuit Synthesis, Electronics Research Laboratory, Memorandum No. UCB/ERL M92/41, 1992.
• 14: 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]
• 15: G. Chen and J. Cong, Simultaneous Logic Decomposition with Technology Mapping in FPGA Designs, UCLA Computer Science Department Technical Report CSD-200030.
• 16: 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]
• 17: Shipra Panda , Fabio Somenzi , Bernard F. Plessier, Symmetry detection and dynamic variable ordering of decision diagrams, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.628-631, November 06-10, 1994, San Jose, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Logic arrays
  B.7 INTEGRATED CIRCUITS

General Terms:
Algorithms, Design, Performance