BI-DECOMP-MV: A Decomposer for Multi-Valued Relations

This page presents the multi-valued (MV) decomposer BI-DECOMP-MV, Release 1.3, ported into MVSIS environment. The algorithms and implementation of the decomposer have been substantially revised. A detailed description of the decomposition approach can be found in [1]. Similar approaches to the decomposition of multi-valued relations are described in [2,3].

Distinctive Features

The approach to decomposition is very general and relies on encoding. Each value of the input/output variable is encoded using the smallest number of binary variables. This representation is known as Binary-Encoded Multi-Valued Decision Diagrams (BEMDDs). For a description with illustrative examples, see [4]. BEMDDs are different from other representations of MV functions and relations. In BEMDDs, the output values are encoded the same way as the input values, while other approaches use pure MDDs [5] or arrays of binary-encoded MDDs for each output value [6].

Due to the strategy of all-in-one encoding in BEMDDs, the MV relations can be efficiently processed using a standard BDD package that features boolean operations, quantification, and variable replacement. A new calculus of multi-valued relations with applications to MV decomposition have been developed [1]. The calculus includes such operations as upper/lower bound, upper/lower bound interval, upper/lower decrement/increment, etc.

The presented algorithm is called bi-decomposition because its basic step transforms a monolithic relation into a network of two smaller blocks whose outputs are connected using a two-input MAX or MIN gate. Recursive application of the algorithm results in a netlist that includes MV constants, generalized MV literals, and MV-input MV-output two-input MAX and MIN gates. However, using only these gates does not always lead to the decomposition of the finest granularity. In order to break down the remaining non-decomposable blocks, it is possible to use MV multiplexers. When multiplexers are used, the algorithm guarantees that the resulting network is composed of MUXes and the above listed gates only.

The decomposition algorithm reduces arbitrary multi-valued relation to an interval relation (for definition look up IWLS'01 paper). A limitation of the proposed approach is that it cannot treat non-interval relations, whose set of values in some vertices of the input space does not form a contiguous range. For example, if a ternary relation for some input combination has value set {0,2}, this relation is a non-interval relation. An open question is how often such relations appear in practical applications?

Applications of Multi-Valued Bi-Decomposition

• Multi-valued circuit design

If an MV circuit can be flattened by deriving its global MDDs, it can be processed by the above decomposition algorithm. The result is a new circuit with compatible functionality, composed of MAX/MIN/MUX gates.

• Data mining

Large amounts of numeric data are typical for many areas of human activity. In many cases, the problem is how to extract valuable information from the data. This problem is known as data mining (machine learning, knowledge discovery). Statistical methods can be used for the purpose, while decomposition provides an alternative approach. The original data can be represented as a multi-valued relation, and decomposition can be applied in order to find a function that is compatible with the relation. This function is typically much simpler than the original data representation. Treating it as an "explanation" of data can be considered as a way to gain knowledge.

BLIF-MV: The Input Data Format

• every specification begins with line ".model <model_name>"
• the number of values should be specified for each input, output, and intermediate signal using line ".mv <name> <num_values> that precedes the first appearance of the signal in a table
• there should be symbols "->" in the ".table" line before the name of the output signal

Source Code and Executable

A Windows executable of a stand-alone version of BI-DECOMP-MV is available for downloading and experimentation. For a summary of available command line options run the above executable without arguments.

BI-DECOMP-MV is programmed to make use of a variety of BDD packages. The available version of the source code provides the interface to the following packages: BuDDy, CUDD, CMU. The above Windows executable has been compiled with BuDDy. A preliminary experimentation shows that for the problem of representation and manipulation of multi-valued relation, BuDDy is faster than other packages.

Here is a default output of the decomposer for benchmark "matmul.mv":

# BI-DECOMP-MV: MVSIS Release 1.3. Last update: 10/14/01, by Alan Mishchenko.
# with BDD package "BuDDy", v.2.0, by Jorn Lind-Nielsen
# Program run date:  Sun Oct 14 17:06:27 2001
# Command line was:  mvsis.exe matmul.mv

REORDERING STATISTICS:

Variable reordering is not enabled

BI-DECOMPOSITION STATISTICS:

Co = Constants. Li = Literals. Ma = MAX gates. Mi = MIN gates. Mu = MUXes.
No = Non-decomposable. Re = Reused gates (fanout > 1). To = Li+Ma+Mi+Mu+No.
Cs = Cascades (logic levels). T = Runtime. Bdd = Bdd nodecount.

#01: Co= 2 Li=10 Ma= 7 Mi=10 Mu= 0 No= 4 Re= 2 To= 31 Cs= 8 T=0.00 Bdd=  37 Ok
#02: Co= 2 Li= 5 Ma= 7 Mi=10 Mu= 0 No= 4 Re= 7 To= 26 Cs= 8 T=0.01 Bdd=  74 Ok
#03: Co= 2 Li= 5 Ma= 6 Mi=10 Mu= 0 No= 4 Re= 6 To= 25 Cs= 8 T=0.01 Bdd= 111 Ok
#04: Co= 2 Li= 0 Ma= 6 Mi=10 Mu= 0 No= 4 Re=11 To= 20 Cs= 8 T=0.01 Bdd= 148 Ok
#=4. Co= 8 Li=20 Ma=26 Mi=40 Mu= 0 No=16 Re=26 To=102 Cs= 8

The decomposed network has been written into file "matmul_bidec.mv"

RUNTIME STATISTICS:

Reading         = 0.00 s.
Preparation     = 0.04 s.
GlobalMDDs      = 0.01 s.
Reordering      = 0.00 s.
Decomposition   = 0.03 s.
Verification    = 0.03 s.
CleanUp         = 0.00 s.

Verification: ok
 

References