Topologically constrained logic synthesis

ABSTRACT

SPFDs, a mechanism for expressing flexibility during logic synthesis, were first introduced for FPGA synthesis. They were then extended to general, combinational Boolean networks and later the concept of sequential SPFDs was introduced. In this paper, we explore the idea of using SPFDs for functional decomposition. A new type of functional decomposition called topologically constrained decomposition is introduced. An algorithm is provided for solving this problem using SPFDs. Preliminary experimental results are encouraging and indicate the feasibility of the approach. A scheme is also presented for generating instances of the topologically constrained decomposition problem.

REFERENCES

• 1: Shigeru Yamashita , Hiroshi Sawada , Akira Nagoya, A new method to express functional permissibilities for LUT based FPGAs and its applications, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.254-261, November 10-14, 1996, San Jose, California, United States
• 2: Subarnarekha Sinha , Robert K. Brayton, Implementation and use of SPFDs in optimizing Boolean networks, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.103-110, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288584]
• 3: Subarnarekha Sinha , Andreas Kuehlmann , Robert K. Brayton, Sequential SPFDs, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 4: E.M. Sentovich and R.K. Brayton. Multiple Boolean Relations. In International Workshop on Logic Synthesis, May 1993.
• 5: R.L. Ashenhurst. The Decomposition of Switching Functions. In International Symposium on Theory of Switching Functions, 1959.
• 6: M. Perkowski and S. Grygiel. A Survey of literature on Functions Decomposition. Technical Report, Department of Electrical Engineering, Portland State University, 1995.
• 7: Tsutomu Sasao , Robert K. Brayton, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2002
• 8: Information Theory Method for Flexible Network Synthesis, Proceedings of the 31st IEEE International Symposium on Multiple-Valued Logic, p.201, May 22-24, 2001
• 9: Lech Józwiak, Information Relationships and Measures in Application to Logic Design, Proceedings of the Twenty Ninth IEEE International Symposium on Multiple-Valued Logic, p.228, May 20-22, 1999
• 10: S. Sinha and R. Brayton. Improved Robust SPFD Computations. In International Workshop on Logic Synthesis, Jun 2001.
• 11: A. Mishchenko and R.K. Brayton. Simplification of Non-Deterministic Multi-Valued Networks. Submitted to International Workshop on Logic Synthesis, Jun 2002.
• 12: P. Chong, Y. Jiang, S. Khatri, F. Mo, S. Sinha and R. Brayton. Don't Care Wires in Logical/Physical Design. In International Workshop on Logic Synthesis, Jun 2000.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Sequential circuits

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Experimentation, Theory