Simplification of non-deterministic multi-valued networks

ABSTRACT

We discuss the simplification of non-deterministic MV networks and their internal nodes using internal flexibilities. Given the network structure and its external specification, the flexibility at a node is derived as a non-deterministic MV relation. This flexibility is used to simplify the node representation and enhance the effect of Boolean resubstitution. We show that the flexibility derived is maximum. The proposed approach has been implemented and tested in MVSIS [16]. Experimental results show that it performs well on a variety of MV and binary benchmarks.

REFERENCES

• 1: Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
• 2: R. K. Brayton. Compatible Observability Don't-Cares Revisited. Proc. of IWLS'01. pp. 121--126.
• 3: 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]
• 4: Jason Cong , Yizhou Lin , Wangning Long, SPFD-based global rewiring, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA [doi>10.1145/503048.503060]
• 5: C. Files , M. Perkowski, Multi-Valued Functional Decomposition as a Machine Learning Method, Proceedings of the The 28th International Symposium on Multiple-Valued Logic, p.173, May 27-29, 1998
• 6: J.-H. Jiang, Y. Jiang, and R. Brayton. An Implicit Method for Multi-Valued Network Encoding. Proc. of IWLS'01, pp. 127--131.
• 7: Yunjian Jiang , Robert K. Brayton, Don't cares and multi-valued logic network minimization, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 8: Yunjian Jiang , Robert K. Brayton, Logic optimization and code generation for embedded control applications, Proceedings of the ninth international symposium on Hardware/software codesign, p.225-229, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371735]
• 9: T. Hanyu, M. Kameyama. A 200 MHz Pipelined Multiplier Using 1.5 V-Supply Multiple-Valued MOS Current-Mode Circuits with Dual-Rail Source-Coupled Logic. IEEE J.Solid State Circuits, vol. 30, no 11, pp. 1239--1245, Nov. 1995.
• 10: A. Kondratyev. Design of Delay-Insensitive Combinational Logic through MV-Synthesis. Unpublished manuscript.
• 11: A. Mishchenko. An Experimental Evaluation of Algorithms for Computation of Internal Don't-Cares in Boolean Networks. Technical Report. Sept. 2001. http://www.ee.pdx.edu/~alanmi/research/net/DCcomparison.pdf
• 12: A. Mishchenko, R. K. Brayton. A Boolean Paradigm in Multi-Valued Logic Synthesis. Proc. IWLS '02, June 2002.
• 13: Abdul A. Malik , Robert K. Brayton , A. Richard Newton , Alberto L. Sangiovanni-Vincentelli, Reduced offsets for two-level multi-valued logic minimization, Proceedings of the 27th ACM/IEEE conference on Design automation, p.290-296, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123279]
• 14: S. Minato. Fast Generation of Irredundant Sum-of-Products Forms from Binary Decision Diagrams. Proc. of SASIMI'92 (Synthesis and Simulation Meeting and International Interchange), Kobe, Japan, pp. 64--73.
• 15: Shin-ichi Minato, Zero-suppressed BDDs for set manipulation in combinatorial problems, Proceedings of the 30th international conference on Design automation, p.272-277, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164890]
• 16: MVSIS Group. MVSIS. UC Berkeley. http://www-cad.eecs.berkeley.edu/mvsis/
• 17: Hamid Savoj , Robert K. Brayton, The use of observability and external don't cares for the simplification of multi-level networks, Proceedings of the 27th ACM/IEEE conference on Design automation, p.297-301, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123280]
• 18: H. Savoj. Improvements in Technology Independent Optimization of Logic Circuits. Proc. of IWLS'97.
• 19: Hamid Savoj, Don't cares in multi-level network optimization, University of California at Berkeley, Berkeley, CA, 1992
• 20: E. Sentovich, et al. "SIS: A System for Sequential Circuit Synthesis", Tech. Rep. UCB/ERI, M92/41, ERL, Dept. of EECS, Univ. of California, Berkeley, 1992.
• 21: Y. Watanabe, L. Guerra and R. K. Brayton. Logic Optimization with Multi-Output Gates. Proc. ICCD '93, pp. 416--420.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Multistep and multivalue methods

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

General Terms:
Algorithms, Experimentation, Theory