1


2

 What is an ND network
 Motivation
 Basic definitions
 Defining and comparing ND behaviors
 ND network operations and how they change behaviors
 Experimental observations
 Conclusions and future work

3

 Similar to a Boolean network except
 Each node has a single output multivalued variable
 Each node has a nondeterministic relation relating its input and
output values.

4

 Don’t cares are a form of nondeterminism. They generalize to
nondeterminism when considering multivalued logic
 Multivalued domains can be used to explore larger optimization spaces.
 ND arises naturally when considering the flexibility of implementing a
node in a network
 Given a ND relation, the minimum welldefined ND subrelation is always
smaller than the minimum deterministic one
 Can be used to compile software to evaluate logic

5

 Directed Acyclic Graph
 Each node represents a Boolean function
 Edge from node j to node k if the function at k depends syntactically on the variable y_{j} at the output of j
 Primary inputs (PI) X and outputs
(PO) Z
 All signals are binary
 External specification provides allowed input and output combinations (external
don’t cares)

6

 Network of MVnodes (PI, PO, internal)
 Each node is represented by an MV variable y_{n}_{ }with
its own range
{0, 1,…, p_{n}1}
 Internal node is represented by an MV nondeterministic relation

7


8

 Given an ND network, what is its behavior, i.e. what is the set of all
PI/PO pairs that are related?
 this question is not straightforward.
 For a deterministic, welldefined network, there is exactly one PO
vector for each PI vector
 however, if there are some external don’t cares, then there may be
several PO vectors for a PI vector,
 but don’t cares are well understood.

9

 Normal Simulation (NS)
 Normal Simulation made Compatible (NSC)
 Set Simulation (SS)

10

 Network is evaluated in topological order
 At each node its fanins have a specific vector of values.
 The relation at the node determines a set of possible output values of
that node
 One of these is chosen randomly and broadcast to the fanouts

11


12

 Like normal simulation except that each PO is handled separately.
 Take one PO, j, and look at the transitive fanin cone.
 Compute (X, z_{j} ) pairs using NS.
 Repeat for all PO

13


14

 Done in topological order.
 On each signal a set of values is
obtained
 At each node a vector of fanin sets is known.
 The output set of values for a node is the union of the sets obtained
for all fanin vectors in the cross product of the fanin sets

15


16

 Scattered simulation
 for each fanout one value is selected from the acceptable set.
 each fanout may have different values
 Example:

17

 is a general MV
Boolean relation
 relatively hard to compute and store
 and can be computed for each
output and They are symmetric Boolean
relations.
 can be obtained
by elimination in reverse topological order
 can be obtained by
elimination in topological order

18

 At each ND node introduce one MV parameter p_{i} with the same
range as the node output.
 Relation at node i is replaced by
 p_{i} controls the output
value of node i
 the operator m is a special BDD projection operator, defined by Bill
Lin, that projects onto the smallest allowed output value.
 R^{NS }can be obtained by
eliminating all internal nodes and existentially quantifying all
parameters.

19

 Can be specified by
 The initial network plus don’t cares
 e.g. in Boolean networks, we can give external don’t cares, one set
for each output.
 A separate specification (network or BDD or other)
 Notation:
 Requirement: conformity

20

 Can use any one of the behaviors
 For example, we may have
but If we
use consistently there is
no problem.
 Ultimately, in most applications we want a final deterministic network.
 If any behavior conforms, then it contains only correct deterministic ones

21

 Develop a theory of ND networks where
 a network can be manipulated using classical operations,
 {eliminate, optimize, decompose, …}
 all the intermediate networks conform to the external specification.
 we need to understand when a particular network operation may increase
a particular type behavior
 this might cause the network to not conform

22

 Eliminate a node
 Optimize a node
 Decompose a node
 Substitute one node into another
 Partially Encode a node
 Merge nodes

23


24


25


26


27

 Definition. A flexibility at node h is a relation R^{f}_{h} such that placing at h any welldefined deterministic
relation contained in R^{f}_{h} leads to a network that conforms to the external
specification.
 Definition. The complete flexibility (CF) is the maximum flexibility at
a node.

28


29


30

 If a network conforms, then any welldefined deterministic function
contained in is
acceptable at node j, for
 For NS or NSC, any ND relation will also be acceptable
 But for SS, it is possible that an ND relation contained in can cause the
network to not conform

31


32


33


34

 It is never smaller than the smallest ND representation
 There is no known algorithm for finding it.
 In contrast, there is a method for finding the smallest ND
representation

35

 Given an ND relation, e.g. the complete flexibility, its iset is the
set of input minterms that can produce output value i.
 For each iset, generate all its primes, P_{i}
 Form covering table with
 one column for each p_{j} in P_{i} for all i
 one row for each minterm in the input space
 Solve minimum covering problem
 Primes chosen from P_{k} is the cover for k^{th} iset.

36


37

 These ideas have been implemented in a system, MVSIS
 The SS behavior has been used throughout.
 it is the easiest to use computationally
 global behavior can be expressed locally at each node as a BDD of the
PI
 In the future we will experiment with using NSC behavior

38

 Conformity is rarely lost but it does happen. This usually happens
during node minimization.
 If we use an ND relation at the minimized node, then conformity is not
guaranteed (only deterministic SOP guarantees conformity using SS)
 Often conformity is automatically regained by minimizing the next node.
 If the CF at the next node is well defined, this means that the network
can be brought back to conformity.
 If it is not well defined, we leave the node relation alone and move to
the next node.
 We have never experienced a final network that does not conform to the
external specification.

39


40

 We believe NSC behavior will be superior.
 need to solve computation efficiency problems
 elimination in reverse topological order means that intermediate
variables have to be used (rather than only PI)
 which means that
it is easier to maintain conformity.
 implies that NSCCF contains more flexibility than SSCF
 however, elimination can cause nonconformity

41

