1	"MVSIS Group" MVSIS Group Minxi Gao,, Jie-Hong Jiang, Yunjian Jiang, Yinghua Li, Alan Mishchenko¹, Subarna Sinha, Tiziano Villa², and Robert Brayton Dept. of Electrical Engineering and Computer Science University of California, Berkeley
2	Outline Motivations: From binary to multi-value MV Networks & Design specification MVSIS optimizations Node simplification Algebraic extraction Pairing merging and encoding Network manipulations Demo New capabilities Conclusions
3	Motivations Synchronous binary hardware synthesis Software synthesis from synchronous specifications Asynchronous hardware synthesis Multi-valued devices? Current-mode CMOS devices Optical logic circuits
4	Motivation – synchronous hardware Design and synthesis from multi-valued logic MV is natural method of specification Larger design space
5	Motivation – software synthesis Synchronous programming of embedded systems Esterel/Lustre/Signal Interactive FSM semantics Code generation from logic
6	Motivation – multi-valued devices Multi-valued current-mode MOS signed digit arithmetic High-speed, Low supply voltage
7	Functional Semantics (MV-Network) Network of MV-nodes Each variable x_nhas its own range {0, 1,…, \|p_n\|-1} Values are treated uniformly MV-literal: x^{0,2} MV-cube: x^{0,2}z^{0,1} MV-relation at each node (can be non-deterministic)
8	Design Specification BLIF-MV subset Single output MV nodes Can be non-deterministic 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 Optimization MVSIS optimizations Node simplification Kernel and cube extraction/decomposition Pairing/Merging Encoding Network manipulations
10	MV-SOP Minimizers For each i-set (MV-input, binary output) Two-level: Espresso-MV minimize an i-set with a don’t care. a don’t care is an input for which the output can be any value. Two-Level: ISOP (Minato) Fast method to build a cover of cubes of an i-set from MDD of function and MDD of don’t cares (method of Minato extended to MV). All i-sets at once Quine-McCluskey type ND minimization Given a ND relation, generate a cover of all i-sets such that the total number of cubes is minimum.
11	Node Simplification Multi-level (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	Node Simplification Using non-determinism Derive Complete Flexibility at a node (an ND relation) Minimize ND relation Espresso ISOP QM Automatically finds best default Uses external specification (relation)
13	Computing Complete Flexibility at a node
14	Quine-McCluskey type ND relation minimization Given an ND relation, e.g. the complete flexibility, its i-set is the set of input minterms that can produce output value i. Generate for each i-set 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 i-set.
15	Algebraic Decompositions Kernel extraction Semi-algebraic division Resubstitution Factoring/Decomposition
16	EBD Algebraic Decompositions Stands for Encode, Binary, Decode Use binary codes to encode multi-valued variable x, e.g Operate with fast binary implementations imported from SIS Convert (decode) back to multi-valued
17	Pairing Merging and Encoding Pair_decode/Merge Combine two or more nodes into a single node with more values. Explore different combinations Encode full and partial encode Combine some i-sets combine i-sets where those values always appear together in fanouts.
18	Other Commands 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	Design Flow Typical design flow
20	Example #1 Matrix multiplication (3 values)
21	Demo simulated live
22
23
24
25
26
27
28
29
30
31
32
33	New Capabilities Non-deterministic MV Networks Post Networks Delay Insensitive Asynchronous Synthesis
34	Conclusions MV logic networks important in various applications Presented MVSIS, an multi-valued 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 non-determinism
35	Some Recent Publications Multi-Valued 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 Non-Deterministic Multi-Valued Networks IWLS 2002 A Boolean Paradigm in Multi-Valued Logic Synthesis IWLS 2002
36