Compatible class encoding in hyper-function decomposition for FPGA synthesis

ABSTRACT

Recently, functional decomposition has been adopted for LUT based FPGA technology mapping with good results. In this paper, we propose a novel method for functional multiple-output decomposition. We first address a compatible class encoding method to minimize the compatible classes in the image function. After the encoding algorithm is applied, the decomposability will be improved in the subsequent decomposition of the image function. The above encoding algorithm is then extended to encode multiple-output functions through the construction of a hyper-function. Common sub-expressions among these multiple-output functions can be extracted during the decomposition of the hyper-function. Therefore, we can handle the multiple-output decomposition in the same manner as the single-output decomposition. Experimental results show that our algorithms are very promising.

REFERENCES

• 1: Wen-Zen Shen , Juinn-Dar Huang , Shih-Min Chao, Lambda set selection in Roth-Karp decomposition for LUT-based FPGA technology mapping, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.65-69, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217508]
• 2: Jie-Hong Jiang, Jing-Yang Jou, Juinn-Dar Huang and Jung-Shang Wei, "BDD Based Lambda Set Selection in Roth-Karp Decomposition for LUT Architecture," Proc. ASP-DAC, pp.259-264, January 1997.
• 3: Rajeev Murgai , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Optimum functional decomposition using encoding, Proceedings of the 31st annual conference on Design automation, p.408-414, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196440]
• 4: Yung-Te Lai, Kuo-Rueih Ricky Pan and Massoud Pedram, "OBDD- Based Function Decomposition: Algorithms and Implementation," IEEE Trans. CAD, vol. 15, pp.977,990, August 1996.
• 5: 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]
• 6: 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
• 7: 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
• 8: Hiroshi Sawada , Takayuki Suyama , Akira Nagoya, Logic synthesis for look-up table based FPGAs using functional decomposition and support minimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.353-358, November 05-09, 1995, San Jose, California, United States
• 9: Daniel D. Gajski, Nikil D. Dutt, Allen C-H Wu and Steve Y-L Lin, High-Level Synthesis, Kluwer Ac. Pub., 1992.
• 10: 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]
• 11: R. K. Brayton, R. Rudell, A. Sangiovanni-Vincentelh and A. R. Wang, "MIS: A Multiple-Level Logic Optimization System," IEEE Trans. on CAD, pp.1062-1081, Nov. 1987.
• 12: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 13: R.L. Ashenhurt, "The Decomposition of Switching Functions," Ann. !Computation Lab. of Harvard Univ., vol.29, pp.74-116, 1959.
• 14: I.P. Roth and R. M. Karp, "Minimization Over Boolean Graphs," IBM Journal, pp.227-238,1962.

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.8 Performance and Reliability

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications

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