Partially-dependent functional decomposition with applications in FPGA synthesis and mapping

ABSTRACT

In this paper, we give a necessary and sufficient condition for the existence of partially-dependent functional decomposition and develop new algorithms to compute such decompositions. We apply our method to the synthesis and mapping for Xilinx XC4000 FPGA's which contain non-uniform sizes of LUT's in its architecture. We develop a new mapping algorithm named PDDMAP which uses CLB's to cover nodes on critical paths for depth minimization and uses LUT's to cover non-critical nodes for area minimization. On average, PDDMAP is able to reduce the depth by 13%with only 1% of increase in area comparing to the results by FlowMap followed by a CLB generation procedure match_4k. We also develop a post-mapping procedure named PDDSYN which resynthesizes mapping solutionsto reduce the mapping area. On average, PDDSYN is able to improve PDDMAP mapping solutions by 5% in depth and 7% in CLB count, and achieves 8% smaller depth and 11% fewer CLB count comparing to FlowSyn followed by match-4k.

REFERENCES

• 1: Ashenhurst, R. L., "The Decomposition of Switching Functions," Proc. lnt'l Symp. on Theory of Switching Functions, 1959.
• 2: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 3: Shih-Chieh Chang , Malgorzata Marek-Sadowska, Technology Mapping via Transformations of Function Graphs, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.159-162, October 11-14, 1992
• 4: 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
• 5: Cong, J. and Y. Ding, "FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup- Table Based FPGA Designs," IEEE Trans. on Computer- Aided Design, Vol. CAD-13(1)pp. 1-12, Jan. 1994.
• 6: Cong, J. and Y. Ding, "On Area/Depth Trade-off in LUT- Based FPGA Technology Mapping," IEEE Trans. on VLSI Systems, Vol. 2, June 1994.
• 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 , 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]
• 9: Cong, J. and Y.-Y. Hwang, "A Theory on Partially- Dependent Functional Decomposition with Application in LUT-based FPGA," in UCLA Computer Science Dept. Tech. Report CSD-950050, (December 1995).
• 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: 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
• 12: Juinn-Dar Huang , Jing-Yang Jou , Wen-Zen Shen, Compatible class encoding in Roth-Karp decomposition for two-output LUT architecture, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.359-363, November 05-09, 1995, San Jose, California, United States
• 13: 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
• 14: Yung-Te Lai , Massoud Pedram , Sarma B. K. Vrudhula, BDD based decomposition of logic functions with application to FPGA synthesis, Proceedings of the 30th international conference on Design automation, p.642-647, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165078]
• 15: Christian Legl , Bernd Wurth , Klaus Eckl, An Implicit Algorithm for Support Minimization during Functional Decomposition, Proceedings of the 1996 European conference on Design and Test, p.412, March 11-14, 1996
• 16: 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]
• 17: Roth, J. P. and R. M. Karp, "Minimization Over Boolean Graphs," IBM Journal of Research and Development, pp. 227-238, April 1962.
• 18: Rudell, R., Private Communication 1996.
• 19: 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]
• 20: Sentovich, E., K. Singh, L. Lavagno, C. Moon, R. Murgat, A. Saldanha, H. Savoj, P. Stephen, R. Brayton, and A, Sangiovanni-Vincentelli, "SIS: A System for Sequential Circuit Synthesis," U. C. Berkeley Technical Report UCB/ERL M92/41, May, 1992.
• 21: 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]
• 22: Xilinx, The Programmable Logic Data Book, Xilinx, San Jose, CA (1994).

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.7 INTEGRATED CIRCUITS

General Terms:
Algorithms, Performance, Theory