A Theory of Non-Deterministic Networks

ABSTRACT

Both non-determinism and multi-level networks compactlycharacterize the flexibility allowed in implementing a circuit.A theory for representing and manipulating non-deterministic(ND) multi-level networks is developed. The theory supports allthe network manipulations commonly applied to deterministicbinary networks, such as node minimization, elimination, anddecomposition. It is shown that an ND network's behavior can beinterpreted in three ways, all of which coincide when the networkis deterministic. Operations performed on an ND network areanalyzed under each interpretation for changes in a network'sbehavior. Modifications of a few operations are given which mustbe used to guarantee that a network's behavior does not violateits external specification. These modifications depend on whichbehavior is being used and the location of related non-determinism.This theory has been implemented in a system,MVSIS. We provide comparisons among the uses of the various behaviors.

REFERENCES

• 1: Daniel Brand, Verification of large synthesized designs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.534-537, November 07-11, 1993, Santa Clara, California, United States
• 2: 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
• 3: [3] A. Mishchenko, and R. Brayton, "A Boolean paradigm for multivalued logic synthesis", Proc. IWLS'02, June, 2002, pp. 173-177.
• 4: Alan Mishchenko , Robert Brayton, Simplification of non-deterministic multi-valued networks, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.557-562, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774654]
• 5: [5] A. Mishchenko, and R. Brayton, "A Theory of Non-Deterministic Networks", UC Berkeley Tech. Rep., ERL, EECS Dept., Feb. 2003.
• 6: [6] MVSIS Group. MVSIS. UC Berkeley. http://www-cad.eecs.berkeley.edu/mvsis/
• 7: [7] R. L. Rudell and A. Sangiovanni-Vincentelli, "Multiple-valued minimization for PLA optimization". IEEE Trans. CAD, Vol. 6(5), pp. 727-750, Sep. 1987.
• 8: [8] 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.
• 9: [9] Y. Watanabe, L. Guerra and R. K. Brayton, "Logic optimization with multi-output gates", Proc. ICCD '93, pp. 416-420.
• 10: Nina Yevtushenko , Tiziano Villa , Robert K. Brayton , Alex Petrenko , Alberto L. Sangiovanni-Vincentelli, Solution of parallel language equations for logic synthesis, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Design, Performance