1
|
- MVSIS Group
- Minxi Gao,, Jie-Hong Jiang, Yunjian Jiang,
Yinghua Li, Alan Mishchenko1, Subarna Sinha,
- Tiziano Villa2, and Robert
Brayton
- Dept. of Electrical Engineering and Computer Science University of
California, Berkeley
|
2
|
- 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
|
- Synchronous binary hardware synthesis
- Software synthesis from synchronous specifications
- Asynchronous hardware synthesis
- Multi-valued devices?
- Current-mode CMOS devices
- Optical logic circuits
|
4
|
- Design and synthesis from multi-valued 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
|
- Multi-valued current-mode MOS
- signed digit arithmetic
- High-speed, Low supply voltage
|
7
|
- Network of MV-nodes
- Each variable xn has
its own range
{0, 1,…, |pn|-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
|
- 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 optimizations
- Node simplification
- Kernel and cube extraction/decomposition
- Pairing/Merging
- Encoding
- Network manipulations
|
10
|
- 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
|
- 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
|
- Using non-determinism
- 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 i-set is the
set of input minterms that can produce output value i.
- Generate for each i-set all its primes, Pi
- Form covering table with one column for each pj in Pi
for all i
- One row for each minterm in the input space
- Solve minimum covering problem
- Primes chosen from each Pi is the cover for each i-set.
|
15
|
- Kernel extraction
- Semi-algebraic division
- Resubstitution
- Factoring/Decomposition
|
16
|
- 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
|
- Pair_decode/Merge
- Combine two or more nodes
- into a single node with more
values.
- Explore different combinations
- Encode
- Combine some i-sets
- combine i-sets 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
|
- Non-deterministic MV Networks
- Post Networks
- Delay Insensitive Asynchronous Synthesis
|
34
|
- 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
|
- 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
|
|