Variable Ordering Heuristics for Kronecker Lattice Diagrams

Project:

References:

1. Lattice Diagrams using Reed-Muller Logic -- Perkowski, Jeske and Xu (RM `97)
2. On Variable Ordering and Decomposition Type Choice in OKFDDs -- Dreschler, Becker and Jahnke
3. Multi-level Programmable Arrays for Sub-Micron Technology Based on Symmetries -- Perkowski, Jeske et. al
4. Polarized Pseudo-Kronecker Symmetry and synthesis of 2x2 Lattice Diagrams. -- Drucker, Files, Perkowski and Jeske

Motivation:

Rules for Merging Nodes

• Shannon - Shannon
• positive Davio - positive Davio
• negative Davio - negative Davio

• Reverse Shannon - Reverse Shannon
The proof for this is as follows:

Before merge:
R= bW ^ b'X
S= bY ^ b'Z
 where ^ denotes the xor operation.
After merge:
R=bW ^ b'(b'X ^ bY) = bW ^ b'X
Similarly 
S= b(b'X ^ by) ^ b'Z = bY ^ b'Z

• Reverse positive Davio - Reverse positive Davio
The proof for this is as follows:

Before merge:
R= bW ^ X
S= bY ^ Z
 where ^ denotes the xor operation.
After merge:
R= b(W ^ X ^Y) ^1(b'X ^ bY) = bW ^ bX^bY^b'X ^bY
  substituting b' = 1^b
R= bW ^bX ^(1^b)X = bW ^bX ^X ^bX = bW ^X
Similarly 
S= b(b'X ^ by) ^ b'Z = bY ^ b'Z

• Reverse negative Davio - Reverse negative Davio
Proof can be inferred in a similar manner to the above proofs.

Heuristic for Variable and Decomposition ordering

• We need to know the order in which the variables occur (Variable Ordering).
• we need to know the decomposition type (Shannon, pDavio or nDavio) applied at each level. This information is stored in a Decomposition Type List(DTL).

1. The algorithm uses a constant, k, to determine the extent to which he tree will favor Shannon or Davio expansions. User will arbitrarily choose a value for k where 0 <= k <= 0.5. This constant influences all the other calcuations for variable order and DTL. For k = 0 the tree degenerates to an OBDD with all decompostiuns are Shannon.For k = 0.5 the tree degenerated to a OFDD with all decompositions being Davio. obviously the value of k greatly influences the DTL and variable ordering so it should be chosen by an educated guess about the nature of the function being implemented. If the nature of the function does not have a direct correlation to k then we may need to try different values of k before getting a suitable value
2. calculate the nlit and plit values for each varaible. nlit and plit for each variable are a measure of how often it occurs in its complemented or uncomplemented form. For example let us assume a PLA which implements two functions f1 and f2 with 3 variables x1,x2,x3

   x1	x2	x3	f1	f2
   1	1	0	0	1
   1	0	0	0	1
   1	1	1	1	1

   then nlit for var[i]= sum of 1s in the f1 and f2 columns for which var[i] = 0
   then plit for var[i]= sum of 1s in the f1 and f2 columns for which var[i] = 1
   for example, plit for x2 = 1+2 = 3 and nlit for x2 = 1

   variable	nlit	plit
   x1	0	4
   x2	1	3
   x3	2	2

3. Calculate a weight for each variable and then sort the variables by their weight to get the variable ordering

4. Calculate a DTL by the the PLA heuristic

Objectives/Milestones:

• Familiarize myself with a Decision Diagram package like CUDD, PUMA or TUD DD.
• Add lattice diagram transformations to this package.
• Use this lattice package to explore variable ordering and its effects on size of lattice diagrams.
• compare results for various standard benchmarks to existing results from [1] and [2].
• Expand this investigation to lattice diagrams for multi-output functions.

Results (In Progress)

• Familiarize myself with a Decision Diagram package like CUDD, BuDDy, PUMA or TUD DD. These packagews were chosen for evaluation because they met many of my selection criteria listed below.

So far I have evaluated three DD packages for my project. The important considerations in my evaluation were:
• Ease of use, including easy downloading, installation, compiling and linking on SUN or HP Unix Workstation
• Good documentation with details of functions and usage
• Preferably C or C++ source code since I planned to develop the lattice extension in C++
• Some form of graphical visualization of the DDs
• A sample application or example that could read a specified function in BLIF or similar format.
1. CUDD: CU Decision Diagram Package
   This package has been developed by Prof. Somenzi at University of Colorado . Somenzi is co-author of the book "Logic synthesis and Verification Algorithms" which is the main text book for this course (EE572). I looked at this package first but found that it only supports 3 types of DDs . Namely BDDs (Binary Decision Diagrams), ADDs (Algebraic Decision Diagrams) and ZDDs (Zero-suppressed Decision Diagrams). The two basic structures for this package are DDNode and DDManager. The DDNode struct is the basic node which can have T and E pointers to its children (Then and Else). The same node can hold a value thereby acting as a terminal node. There are two functions to output the resultant diagram. Cudd_DumpBlif() writes a file in blif format. It is restricted to BDDs. The diagrams are written as a network of multiplexers. Cudd_DumpDot() produces input suitable to the graph-drawing program dot written by Eleftherios Koutsofios and Stephen C. North. The CUDD package comes with a sample application that can read BLIF files and form BDDs and dump the files in DOT format. After downloading and compiling this package and sample application I have reached the conclusion that this package is unsuitable for my project because it does not support OKFDDs. It has no Davio expansions and would require considerable modification to support lattice diagrams.

   BLIF

   BLIF format is an acronym for Berkeley Logic Interchange Format. The goal of BLIF is to describe a logic-level hierarchical circuit in textual form. A circuit is an arbitrary combinational or sequential network of logic functions. More information on BLIF is available at http://schof.colorado.edu/~ecen5139/5139/blif.html and http://www.ics.uci.edu/~rgupta/ics252/blif. A Blif2VHDl converter is also available in the public domain at http://rassp.scra.org/vhdl/tools/tools.html
   Here is an eample BLIF file that implements
   f = n1.n2'.n4' + n1.n2.n4 + n2.n3

   .model rcn25
   .inputs  n1 n2 n3 n4
   .outputs f
    
   .names n1 n2 n3 n4 f
   10-0 1
   11-1 1
   -11- 1
   
   

   DOT

   This is a format that can be read by a viewer tool "GraphWiz" developed at AT&T research. It can read a dot file and output a graphical view of the DD in postscript format. This can now be viewed using ghostview or other postscript viewers.Web Address is : http://www.research.att.com/sw/tools/graphviz
   Example of the output of a dot file for the BLIF example given above:
   % dot -Tps /usr2/cudd-2.1.2/nanotrav/myout -o my.ps
   
   
   
   
   
2. TUD Decision Diagram Package :
   This package has been developed at the Department of Electrical Engineering / Computer Systems in Darmstadt University of Technology (Germany).It is designed to handle OKFDDS and is interesting in that it also has a web interface to specify and view DDs. I tried to contact the developer to get more information about downloading the package but did not receive any timely responses and so reluctantly had to abandon the plan of using this package. Web Address of this package is http://www.rs.e-technik.tu-darmstadt.de/~sth/dd/dd.html
3. PUMA Decision Diagram Package This package has been developed at the Freiburg University (Germany).It is designed to handle OKFDDS and is written in C++. There is a sample application with it to demonstrate some of the packages capabilities. It utilizes some of the basic C++ features but most of the design appears to be closer to C. This is in many ways a limitation since it restricts the extensibility of the package which would have been possible with a proper C++ object-oriented design. Input can be read from BLIF format using OKFDD_Read_BLIF () function. It also has a useful XWindows interface to draw the DD with different coloring for Shannon, negative-Davio and positive-Davio nodes. The access to this display is via three functions
   • ulint XShowDD ( utnode* ROOT )
   
   Displays a tree with root specified in argument.
   • ulint XShowDD_all ( )
   
   Displays all trees registered with DD Manager.
   • ulint XShowDD_mult ( utnode** ROOTS )
   
   Displays all trees specified by the array of pointers ROOTS.
   
   Here is the resulting output for the example described above
   f = n1.n2'.n4' + n1.n2.n4 + n2.n3

   .i 4
   .o 1
   10-0 1
   11-1 1
   -11- 1
   

   
   
   
   The class utnode* is the basic structure element of the DDs in PUMA. A DD-Node consists of the following items:

   Item	Type and name
   Unique node number (ID-Number)	idnum of type ulint
   Variable label	label_i of type usint
   Low son of node	lo_p of type utnode*
   High son of node	hi_p of type utnode*
   Accessory field	link of type void*
   Reference counter	ref_c of type uchar
   Several protected items	...

   As can be seen, there are no parent pointers in this node. This may make it inapproriate for use as is and may require derivation of a LatticeNode class from this as the base class using C++ inheritance properties. Two additional utnode pointer to left_parent and right_parent will need to be introduced.



Conclusion

Based on my analysis I chose CUDD because of its very good documentaion, wealth of DD manipulation functions and a nice sample application for reading and writing BLIF files. I found CUDD easier to debug and compile than PUMA . This was the deciding factor in my choice.

• compare results for various standard benchmarks to existing results

The results of this project are somewhat hard to compare since this is a relatively new area of research. There are no results available for Kronecker Lattice Diagrams in current publications. As such any comparisons to existing results for OKFDDS or Shannon Lattices is like comparing oranges to apples. The various benchmarks like MCNC can be used to form the Kronecker lattices but the results of various heuristics developed as a result of this project can only be compared amongst themselves. The results of this project can serve as a starting point and act as an initial benchmark for comparing results from future research.

• Problems with applying the PLA Heuristic described in [2]s

Despite similarities etween OKFDDs and Lattice Diagrams, there are several differences which make the adaptation of the PLA heursistic described in [2] difficult.
• The Lattice Diagram has variable repetition which makes it much different from OKFDDD Variable Ordering.
• It can be proven that a lattice diagram will eventually be completed but a heuristic can not exactly predict when a lattice diagram is complete. A lattice diagram is considered complete when all nodes at the exterior are terminal nodes.
• The PLA Heuristic does not take into the account the possibility of "flipped" decompositions.
• The PLA heuristic uses the assumption that terminal nodes will be constants.

• Outline of our heuristic

Because of time limitations I could not implement this heuristic completely in an actual program but here is a broad outline. An appendix lists the actual source code developed so far.
1. Calculate variable and ordering and DTL according to the PLA heuristic described in [2] and oulined above.
2. Start from the top down and build the lattice diagram in a breadth-first manner.
3. At each level only one kind of decomposition can be applied. Perform decomposition like a normal OKFDD.
4. Merge adjacent non-isomorphic nodes using the six merging rules described earlier.
5. The DTL will be limited to Shannon, positive Davio and negative Davio but the heuristic will determine whether to use the normal or reverse version of that decomposition at a given level. This determination wil be made made at each level by using a look-ahead algorithm which will choose the reverse type of the decomposition if the lattice appears to be becoming skewed in one direction.
6. If a decomposition yields a single variable then no more decomposition to terminal nodes is necessary. In a layout-synthesis sense we have reached the point where a signal will be directly connected to the input of our computing element (namely a Davio gate or Shannon multiplexer).
• Pseudo-code for the heuristic:

enum Decomp {  //  >> Decomposition types <<

    N_Shan          =       0,      // Shannon            

    N_posD          =       1,      // positive Davio

    N_negD          =       2,      // negative Davio

    R_Shan          =       3,      // Reverse Shannon            

    R_posD          =       4,      //

    R_negD          =       5,

   };  



// These two functions would implement the PLA heuristic described in 

// the Dreshler and Becker OKFDD Oredering Heuristic paper



void read_literals(Decomp ** DTL, int ** VariableOrder,float k);

void pla_heuristic(Decomp ** DTL, int ** VariableOrder,,float k);



 // assuming no variable will be repeated more than 3 times

// We allocate space accordingly. In real code this could be allocated

//dynamically



int [3* NO_INPUTS] VariableOrder; // stores order in which variables occur



// Decomposition Type List can have six possible values

Decomp [3*NO_INPUTS] DTL; 



float k=0; // Arbitray constant k used in PLA Heuristic;



BEGIN

print Enter value of k;

Read k;

          

read_literals(Decomp ** DTL, int ** VariableOrder, float k);

pla_heuristic(Decomp ** DTL, int ** VariableOrder, float k);



latticeNode * root = Build_OKFDD();



// At this stage we have a correct Variable order for the first go 

// without any varaible repetition and a 

// DTL containing only normal decomposition types

// WE have constructed a OKFDD based on this info



// Now we ignore the root level since no merging occurs at 

// that level



// list template to store all the nodes left to right in a level

List level; 



// start merging from second level down

for(int i=1; i < NO_INPUTS; i++){



    fill_level(i, level);  // populate list with nodes from the level

    for (int j=0; j < level.size()-1; j++){

    merge_nodes(level[j], level[j+1], DTL[i]);

    }

}

Questions/comments to:junaid_omar@mentorg.com