1

 MVSIS Group
 Minxi Gao,, JieHong Jiang, Yunjian Jiang,
Yinghua Li, Alan Mishchenko^{1}, Subarna Sinha,
 Tiziano Villa^{2}, and Robert
Brayton
 Dept. of Electrical Engineering and Computer Science University of
California, Berkeley

2

 Motivations: From binary to multivalue
 MV Networks & Design specification
 MVSIS optimizations
 Node simplification
 Algebraic extraction
 Pairing merging and encoding
 Network manipulations
 Demo
 New capabilities
 Conclusions

3

 Synchronous binary hardware synthesis
 Software synthesis from synchronous specifications
 Asynchronous hardware synthesis
 Multivalued devices?
 Currentmode CMOS devices
 Optical logic circuits

4

 Design and synthesis from multivalued logic
 MV is natural method of specification
 Larger design space

5

 Synchronous programming of embedded systems
 Esterel/Lustre/Signal
 Interactive FSM semantics
 Code generation from logic

6

 Multivalued currentmode MOS
 signed digit arithmetic
 Highspeed, Low supply voltage

7

 Network of MVnodes
 Each variable x_{n }has
its own range
{0, 1,…, p_{n}1}
 Values are treated uniformly
 MVliteral: x^{{0,2}}
 MVcube: x^{{0,2}}z^{{0,1}}
 MVrelation at each node (can be nondeterministic)

8

 BLIFMV subset
 Single output MV nodes
 Can be nondeterministic
 Flat network, no hierarchy (yet)
 Constant initial states (.reset)
 Extensions
 External don’t care networks (.exdc)
 Can have an external don’t care specified for each output
 Can specify datapaths

9

 MVSIS optimizations
 Node simplification
 Kernel and cube extraction/decomposition
 Pairing/Merging
 Encoding
 Network manipulations

10

 For each iset (MVinput, binary output)
 Twolevel: EspressoMV
 minimize an iset with a don’t care.
 a don’t care is an input for which the output can be any value.
 TwoLevel: ISOP (Minato)
 Fast method to build a cover of cubes of an iset from MDD of function
and MDD of don’t cares (method of Minato extended to MV).
 All isets at once
 QuineMcCluskey type ND
minimization
 Given a ND relation, generate a cover of all isets such that the
total number of cubes is minimum.

11

 Multilevel (using don’t cares  inputs for which output can be any
value)
 Compatible observability don’t cares
(CODC)
 Satisfiability don’t cares (SDC)
 External don’t cares (XDC)
 Generalization from binary case

12

 Using nondeterminism
 Derive Complete Flexibility at a node (an ND relation)
 Minimize ND relation
 Automatically finds best default
 Uses external specification (relation)

13


14

 Given an ND relation, e.g. the complete flexibility, its iset is the
set of input minterms that can produce output value i.
 Generate for each iset 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 each P_{i} is the cover for each iset.

15

 Kernel extraction
 Semialgebraic division
 Resubstitution
 Factoring/Decomposition

16

 Stands for Encode, Binary, Decode
 Use binary codes
to encode multivalued variable x, e.g
 Operate with fast binary implementations imported from SIS
 Convert (decode) back to multivalued

17

 Pair_decode/Merge
 Combine two or more nodes
 into a single node with more
values.
 Explore different combinations
 Encode
 Combine some isets
 combine isets where those values
 always appear together in
fanouts.

18

 Network manipulations
 mvsis> eliminate
 mvsis> collapse
 mvsis> sweep
 IO interface
 mvsis> read(write)_blifmv
 mvsis> read(write)_blif
 Verification
 mvsis> validate n # (uses
simulation)
 mvsis> verify
 mvsis> gen_vec
 mvsis> simulate
 mvsis> qcheck (quick check for ND network)

19


20


21


22


23


24


25


26


27


28


29


30


31


32


33

 Nondeterministic MV Networks
 Post Networks
 Delay Insensitive Asynchronous Synthesis

34

 MV logic networks important in various applications
 Presented MVSIS, an multivalued logic synthesis software infrastructure
 Release 1.1 on Linux and Windows platforms (as of May, 2002)
 Support registers
 External and sequential don’t cares
 Verification based on MDD representations
 software generation from Esterel
 use of complete flexibility
 nondeterminism

35

 MultiValued Logic Optimization on Post Logic Networks submitted to
ICCAD 2002
 Don’t Care Computations in Minimizing Extended Finite State Machines
with Presburger Arithmetic IWLS 2002
 Software Synthesis from Synchronous Specifications Using Logic
Simulation Techniques DAC 2002
 Simplification of NonDeterministic MultiValued Networks IWLS 2002
 A Boolean Paradigm in MultiValued Logic Synthesis IWLS 2002

36

