Welcome to the Decision Diagram-Package PUMA
Download PUMA!



Introduction and Theoretical Abstract



Decision Diagrams (in short DDs) are often used in CAD systems for the efficient representation and manipulation of Boolean functions. The most popular data structure in this context are Ordered Binary Decision Diagrams (in short OBDDs) that are used in many applications. Nevertheless, some relevant classes of Boolean functions cannot be represented efficiently by OBDDs. As one alternative Ordered Functional Decision Diagrams (in short OFDDs) have been introduced and in the meantime they are used in various applications of XOR-based logic synthesis.

Recently, Ordered Kronecker Functional Decision Diagrams (in short OKFDDs) have been introduced as a means for efficient representation and manipulation of Boolean functions. OKFDDs are a generalization of OBDDs and OFDDs as well and try to combine the advantages of both representations. The data structure allows to dynamically adapt the representation of a Boolean function to a given problem. Using OKFDDs it is possible to represent functions efficiently that only have exponentially sized OBDD and OFDD representations.

PUMA is a DD-Package for the efficient representation and manipulation of Boolean Functions with OKFDDs as well as Zero-Suppressed BDDs.





Example Program for PUMA


The following codelines show a typical frame program for an application using PUMA:

Calling the procedure OKFDD_Init initializes the main class dd_man and returns a pointer on it.
Some construction parameters are chosen and procedure OKFDD_Read_BLIF is called.
A couple of analyzations are performed and their results shown on display.
OKFDD_Quit frees the allocated memory resources.



// HEADER Files
// ------------
#include "tc_time.h"
#include "puma.h"

/* ========================================================= */
// Main-routine
/* ========================================================= */
int main(int argc, char *argv[])
{
	unsigned char		ut_hashsize	= 0;
	unsigned long		ct_hashsize	= 5003;
	unsigned long int	rc_cachesize	= 1000;
	unsigned char		ct_searchlen	= 3;
	unsigned short int	var_lim		= 20000;

	char 	                benchname[25] 	= "C7552.blif";

	// ---------------
	// Init DD-Manager
	// ---------------
        dd_man* dd_manager = OKFDD_Init( ut_hashsize ,
                                         ct_hashsize ,
                                         rc_cachesize,
                                         ct_searchlen,
                                         var_lim    );
	
	// --------------------------------
	// Set some construction parameters
	// --------------------------------
	dd_manager->OKFDD_Tempfactor  = 3;
	dd_manager->OKFDD_Siftfactor  = 3;
	dd_manager->OKFDD_Temproutine = 1;

	// -----------------------------------
	// Build benchmark (without orderfile)
	// -----------------------------------
	dd_manager->OKFDD_Read_BLIF( benchpath ,
                                     NULL      ,
                                     %INTERHAND,
                                     NULL      ,
                                     NULL     ); 

	// --------------------------
	// Show some OKFDD statistics
	// --------------------------
	cout << "All:  ";   dd_manager->OKFDD_Profile_all(TRUE);

	cout << "Vars: " << dd_manager->OKFDD_P_I 	 << "\n";
	cout << "Outs: " << dd_manager->OKFDD_P_O        << "\n";
	cout << "Size: " << dd_manager->OKFDD_Size_all() << "\n";

	// --------------------------- 
	// Show elapsed processor time
	// ---------------------------
	cout.precision(3);     cout << "Elapsed time [s]: ";
        cout << (float)(dd_manager->timer_stop)/100 << "\n";
                    
	[ - Perform action on OKFDDs - ]
                  
	// ----------------------------- 
	// Free Decision Diagram Manager
	// ----------------------------- 
	dd_manager->OKFDD_Quit();

        delete dd_manager;
};
/* ========================================================= */




Initialization of a PUMA-Manager


The procedure OKFDD_Init initializes PUMA`s main class dd_man. By calling this function several parameters are fixed for the whole lifespan of the package, that is to say, until the main class dd_man is freed by calling OKFDD_Quit. Due to the fact, that users shouldn`t have to fight for the knowledge of every single secret PUMA bears, many of the function parameters are default driven. This also holds for OKFDD_Init. The following table lists the arguments of the initialization function as well as their default values:


dd_man* dd_manager = new OKFDD_Init( ut_hashsize , 
                                     ct_hashsize ,
                                     rc_cachesize, 
                                     ct_searchlen, 
                                     var_lim     , 
                                     node_lim    , 
                                     mem_lim    );


Type Name Description Default value Suggested values
uchar ut_hashsize Initial unique tables size 0 [0 ... 13] (See [*] below)
ulint ct_hashsize Computed table (CT) size 5 003 [1 000 ... 15 000]
ulint rc_cachesize Recycling cachesize 1 000 [2 ... 1 000]
uchar ct_searchlen CT maximal searchlength 3 [3 ... 5]
usint var_limit Maximal # of variables 5 000 [100 ... 32 000]
ulint node_limit Maximal # of utnodes 1 000 000 000 [0 ... MAX_LONG]
ulint mem_limit Memory limit in Megabyte 10.000 [0 ... MAX_LONG]

[*] Value 0 correponds to the first, 13 to the last element of the ordered set {3, 7, 17, 31, 61, 127, 257, 509, 1021, 2053, 4099,8191, 16381, 32771, 65521}



PUMA manages a unique table for each primary input variable. These tables are dynamic in their size to shorten search-chains and uphold a balanced anchor-usage, thus reducing searchcosts at anchors and chains (especially during level exchange operations which have to inspect all utnodes in two neighbouring levels). The handling of an implosion (explosion) that is to say a resizing of an UT and rehashing of the elements in it is done if the lower (upper) bound OKFDD_Implode- / Explodefactor) is crossed.





Onscreen Informations of PUMA


PUMA can show a couple of informations during runtime. For convenience the user can select in which specific type of information (s)he is interested. The following table shows the bits and their meanings that can be set to 1 in the variable OKFDD_Outputflags in order to activate wanted output informations (The default values are written in bold style resulting in a total value of 2 097 191):



Bit Informations about ...
0General status
1Errors
2 Interleaving
3Ordering during DD construction
4Gates during DD constructions
5Status during DD constructions
6Node deallocation
7 Recycling cache
8 Unique table resizing
9Variable construction
10Unique table construction
11Leveldetermination of variables
12Fanins of circuit gates
18Ordering list
19DD sizes during reordering
20DD sizes after reordering
21DD sizes before reordering
22Cost comparison during reordering
23Variable names in structure analyzing functions





Manager-Variables


For easy reading basic variable types used in this document as well as in the source-code of PUMA are given in a short notation that is shown below:

Short notation Basic type
ucharunsigned char
usintunsigned short int
sintshort int
ulintunsigned long int
lintlong int
travinvoid (dd_man::*travin) (utnode*)
travexvoid (*travex) (dd_man*, utnode*)



In order to influence PUMA`s behaviour there exists a lot of manager variables that can be read and written. The following table lists them and describes their meanings.

IMPORTANT note for the following table:

This table isn`t complete! It shows a brief extract of the most interesting variables.

Type Variablename Description Default Suggested values
uchar OKFDD_Version_Wait See function OKFDD_Version TRUE {TRUE, FALSE}
uchar OKFDD_DTL_Default Default DT for new variables D_Shan See [*] below
uchar OKFDD_Interleaving Interleaving on / off FALSE {TRUE, FALSE}
uchar OKFDD_Explodefactor Explodefactor for unique tables 21 [2 ... 255]
uchar OKFDD_Implodefactor Imlodefactor for unique tables 5 [2 ... 255]
short OKFDD_Temproutine INTERHAND-Variable 0 [0 ... 5]
float OKFDD_Tempfactor INTERHAND-Variable 1.5 Value > 1.0
float OKFDD_Siftfactor INTERHAND-Variable 3.0 Value > 1.0
ulint OKFDD_Siftbase INTERHAND-Variable 10 000 [1 ... MAX_LONG]
travex OKFDD_Shell_Extension See function OKFDD_Shell NULL None
ulint OKFDD_Outputflags Output selection 2 097 191 [0 ... MAX_LONG]

[*] Decomposition types can be handled with the global names D_Shan, D_posD and D_negD



IMPORTANT note for the following table:

This table isn`t complete! It shows a brief extract of the most interesting READ_ONLY variables.

Type Variablename Description
usint OKFDD_PI_Order_Table[var] Returns the relative level of variable var
usint* OKFDD_Result Result table of several structure analyzing fts
usint* OKFDD_Result_2 Result table of several structure analyzing fts
ulint OKFDD_No_UTNodes Returns # of existing utnodes
ulint OKFDD_No_UTNodes_Per_Lvl[var] Returns # of existing utnodes with label var
ulint OKFDD_No_CTNodes Number of existing computed table entries
sint OKFDD_P_I Actual number of primary inputs
sint OKFDD_P_O Actual number of primary outputs
uchar* OKFDD_PI_DTL_Table[var] Returns DT of variable var
short* OKFDD_PI_Level_Table[var] Returns the relative level of variable var
short* OKFDD_PI_Order_Table Holds all variables in their actual ordering
utnode* OKFDD_ONE Terminal utnode ONE
utnode* OKFDD_ZERO Terminal utnode ZERO
utnode* OKFDD_Empty Combinational set { }
utnode* OKFDD_Base Combinational set { 0 }
utnode** OKFDD_ROOT[idx] Holds results of several synthesis fts
ulint OKFDD_Error OKFDD_Error holds current status of PUMA
ulint OKFDD_Now_size_i Number of currently existing utnodes
ulint OKFDD_Maxidx # of elements in OKFDD_PI_Level_Table
ulint OKFDD_Supported_Vars See function OKFDD_Support_(mult / all)





Error Messages


Due to wrong usage of PUMA`s manager-functions as well as user-defined or systembound resource limits there may arise errors which can prevent the correct termination of functions. These cases have to be spotted and PUMA has to react appropriately. In such cases the package behaves as follows:

PUMA outputs an error message (only if corresponding outputflag is selected)
OKFDD_Error is changed according to the following table
If the function returns a value it is set to NULL



Due to runtime and memory usage by protocolling operation steps (especially in recursive algorithms e.g. OKFDD_Synthesis) to prevent irreversible routines the package would suffer noticeable. Instead it was decided to output warnings before a critical memory limit is reached and no more resources are available including the message that following operations may not return the desired results.




Code Error name Description
0 Err_No_Error Function termination was correct
1 Err_Error Unclassified error occured
3 Err_Unknown_Op Unknown operation code for synthesis operation
5 Err_NULL_Op At least one given operand of a binary operation was NULL
7 Err_Namelength Name of variable too long
9 Err_Linelength BLIF-line too long
11 Err_Chain utnode not in correct chain
13 Err_Hashpos Hashposition in inspected unique table is empty
15 Err_Prime_ex Primary input or output already exists
17 Err_Primelimit Variable limit reached. Can`t create a new variable
19 Err_Evaluation OKFDD_Evaluate caused an error
21 Err_Outputmiss Primary ouput with given name doesn`t exist
23 Err_Orderfile Can`t interpret given orderfile
25 Err_Levelusage Levelorder due to multiple occurence of variables in orderfile corrupt
27 Err_Benchmark Can`t interpret given benchmark
29 Err_Overflow Memory limit reached
31 Err_Prime_miss Primary input or output doesn`t exist
33 Err_Dumporder Can`t create orderfile in function OKFDD_Dumporder





Some Package Internals


Data structure / The class utnode*:

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 ...



Improved Sifting Algorithms:

In the last few years several methods for dynamic variable ordering for OBDDs have been presented and intensively been studied. The most promising approach was the Sifting algorithm introduced by Rudell in `93. The PUMA-Package makes use of three similar but improved sifting techniques Sifting, Siftlight and DTL-Sifting. The first one is very much like the original Sifting which scans [To scan in this case means to reposition a variable in a specific level and calculate the size of the resulting DDs] for every variable all existing levels and then chooses the best one for the repositioning of the regarded variable. The second sifting procedure Siftlight is more restrictive and scans only neighbouring levels for improvement. Obviously it`s much faster but can only perform local optimization. The third algorithm uses Sifting with the additional characteristic that for every variable all existing levels are scanned with all decomposition types before it gets repositioned.

PUMA`s sifting approaches also differ in the selection strategy for the next sifting candidate, that is to say the next variable for a repositioning is determined more sophisticated. Overall we have three arguments to control the sifting process individually:

The sift-factor (SF) sets a factorial limit for the growth during a sifting process, because although the outcome will be improved, during sifting the DDs might explode if not kept at bay. Suggested values: [2, ... ,3]. The argument RA (possible values are `r` for relative and `a` for absolute) determines whether the given sift-factor should be treated as relative or absolute growth limit. In the case of a relative treatment, after each repositioning of a sifting variable the comparison size for the growing is actualized. In the case of an absolute treatment, the comparison size is the intial size of the DDs for the complete siftingprocess. METHOD sets the kind of choice for the next sifting candidate (variable). Possible values and their meaning are listed in the following table:

METHOD Description
Random `r` The random selection was introduced for comparison reasons.
Initial `i` The sifting variables are chosen in the order given before the sifting procedure starts.
Greatest `g` Chooses the variable in the level with the largest number of nodes
Loser first `l` Introduced with PUMA: Although the complete sifting process will reduce the number of DD-Nodes (or at least keep the same size if no improvement can be done) after each repositioning of a sifting variable there will occasionally be some levels that grow. The loser first strategy chooses the next sifting candidate as the variable in the level with the least increase in size.
Lookahead / Verify `v` Introduced with PUMA: Calculates the number of node eliminations due to the reduction rules of OKFDDs if a variable is repositioned in a specific level. It then chooses the best position according to the highest count result.

The `Lookahead / Verify` strategy proved to be the best known today and improves the efficiency, that is to say size reduction, independant of the used sifting method on average of about 15 % in comparison to the random method.



Interleaving

Interleaving is a heuristical method for the determination of a good initial variable order for multi-level benchmarks with several outputs.

A conventional strategy for a heuristical method is based on a depth-first-traversal (DFS) of the circuit topology. The DFS-Process is controlled by the means of priorities that classify the complexity of the subcircuits and the variable ordering is determined by the order of visited primary inputs (PIs). Since newly visited PIs are appended at the currently determined ordering this technique is called variable appending. Obviously primary outputs (POs) with a high priority will get a better subordering of PIs in comparison to POs with lower priorities.

The interleaving technique cares for this bad behaviour of the conventional method. The basic principle is to merge a determined subordering of each PO in the (by now calculated) existing ordering of the POs with higher priorities. PUMA has several additional parameters (although some are still for experimental purposes) to get a more sophisticated interleaving behaviour, but I don`t want to make things too complicated.



Memory management / Caching:

PUMA uses a 2-Level-Cache strategy to store unused nodes. The first level cache recycling cache holds all nodes that have an reference counter that equals 1 (which means there exists no more reference on it but itself). The reference counter is modified by the function OKFDD_Free_Node. The recycling cache is organized according the FIFO-Principle (queue). If a DD (represented by it`s root) is in this queue he will stay as long as no more than rc_cachesize new entries are made. If this number of new entries is reached the reference counter for the DDs root node is checked again and if still 1 (this has not to be the case since a new reference to this node might have arisen in the meantime) the node will be moved into the second cache called unique cache and all successors of it (sons ...) are checked likewise.

The unique cache holds all deleted nodes and provides their used memory space for new DD-Nodes without the time penalty of a new memory allocation calls. Only if this cache is empty (which doesn`t occur very often) new allocations must be done.

These newly introduced cache strategies proved to be more efficient than block allocation methods which have to occassionally run defragmentation algorithms in order to tighten allocated resources.





Extract of Manager Functions


Structure Maintenance Functions

OKFDD_Cachecut OKFDD_Free_Fct_Cache OKFDD_Free_Node
OKFDD_Get_Root OKFDD_Get_Variable OKFDD_Read_BLIF
OKFDD_Remove_Prime OKFDD_Setthis OKFDD_Shell
OKFDD_Store_Root OKFDD_Version OKFDD_Quit
...

Synthesis and Combinational Functions

OKFDD_Exists OKFDD_Forall OKFDD_Substitution
OKFDD_Synthesis OKFDD_ITE ...

Structure Analyzing Functions

OKFDD_1_PC (_all /_mult) OKFDD_Cofactor OKFDD_DTL (_all /_mult)
OKFDD_Dumporder OKFDD_Evaluate OKFDD_Identity
OKFDD_ID OKFDD_Label OKFDD_No_Dead_UTNodes
OKFDD_PI_Table OKFDD_PO_Root_Table OKFDD_PO_Table
OKFDD_Profile (_all /_mult) OKFDD_SAT_all OKFDD_SAT_all_n
OKFDD_SAT_Count OKFDD_Satisfiability OKFDD_Size (_all /_mult)
OKFDD_Support (_all /_mult) OKFDD_Type ...

Traversal Functions

OKFDD_Traverse (_all /_mult)


Zero Suppressed BDD Functions

OKFDD_to_ZSBDD ZSBDD_1_PC (_mult) ZSBDD_Multi_Op
ZSBDD_Single_Op


Reordering Functions

OKFDD_Blockshift OKFDD_DD_to_BDD OKFDD_DD_to_FDD
OKFDD_DTL_Chg_Bottom OKFDD_DTL_Friedman OKFDD_DTL_Permutation
OKFDD_DTL_Sifting OKFDD_Friedman OKFDD_GAC_4_DTL
OKFDD_Inversion OKFDD_Levelexchange OKFDD_Levelshift
OKFDD_Levelswap OKFDD_Permutation OKFDD_Sifting
OKFDD_Siftlight OKFDD_Sort OKFDD_Winpermutation
OKFDD_Winsift ...

Graphic functions

XShowDD (_all /_mult)




void OKFDD_Cachecut ( uchar PERCENTAGE )

Reduces the size of the unique cache to the given PERCENTAGE.

Tips for function usage:

Intended to free nodes in the unique cache after the number of existing nodes has largely decreased (thus the number of nodes in the unique cache has largely increased) and the size variation reaches a somewhat stable status. E.g. this behaviour can be observed after an intensive reordering procedure. The function should be handled with care because if the cache is cut short too often, the caching efficiency gets lost.



void OKFDD_Free_Fct_Cache ( void )

Clears the recycling cache.

Tips for function usage:

Intended to free DDs in the recycling cache after a huge number of DDs was created that are no longer of importance. E.g. this behaviour can be observed after a couple of intensive synthesis operations. The function should be handled with care because if the cache is cleared too often, the caching efficiency gets lost.



void OKFDD_Free_Node ( utnode* ROOT )

The reference counter of the given DD ROOT is decremented by one and if equal to 1 (which means there exists no more reference on it but itself) the node is stored in the recycling cache.

Tips for function usage:

As a general rule note this: Imagine the function call OKFDD_Store_Root as an open bracket. Then every call of OKFDD_Free_Node symbolizes the closing one. Thus at the end of your application there shouldn`t exist an unclosed bracket if everything works properly.

More details about caching are given here.



utnode* OKFDD_Get_Root ( char* PO_NAME[name_limit] )

If existent the root of the DD that corresponds to the given PO_NAME is returned. If not NULL is the returned value.

Tips for function usage:

This function increments the reference counter of the returned DD thus keep in mind to use OKFDD_Free_Node to free the root node if it isn`t needed anymore.



utnode* OKFDD_Get_Variable ( char* PI_NAME[name_limit], uchar POS_NEG )

For the given PI_NAME a node with the functionality f = variable (if POS_NEG is positive) or f = NOT (variable) (if POS_NEG is negative) is returned. If the variable with the given name doesn`t exist a new variable with the given PI_NAME and a corresponding variable label is created before.

Tips for function usage:

This function increments the reference counter of the returned DD; thus keep in mind to use OKFDD_Free_Node to free the root node if it isn`t needed anymore.



void OKFDD_Read_BLIF ( char* FILE, char* ORDER, travex EXTERN, usint* LABELS, uchar* DTL )

The BLIF-File given by FILE is interpreted and the correponding DDs are constructed. If an orderfile ORDER is specified (if ORDER is not NULL) the ordering and decomposition types of the variables are set in the described manner. Missing or noninterpretable files result in error messages and the setting of the error corresponding flag in the manager variable OKFDD_Error. Alternatively you can make use of the arguments LABELS and DTL and thus give the ordering and decomposition type list.

Tips for function usage:

To get a good impression of the function features (especially the here left out argument EXTERN and the fields LABELS, DTL) you should take a look in the chapters `Frequently Asked Questions` Question 2.2. and Question 2.4.



void OKFDD_Remove_Prime ( usint PO_LABEL )

For the primary output stored by PO_LABEL (either done by OKFDD_Store_Root or OKFDD_Read_BLIF) the corresponding DD is freed and it`s PO_LABEL eliminated.

Tips for function usage:

Sorry, no tips available.



void OKFDD_Setthis ( usint* LABELS, uchar* DTL )

The ordering and/or decomposition types are changed according to the given fields LABELS and DTL. If one setting should be kept the argument has to be NULL.

Tips for function usage:

Example:

Let`s say you want to build DDs with order and DTL 3pD 4S 2nD 1S:

You make a call of OKFDD_Read_BLIF(FILENAME,NULL,NULL,LABELS,DTL) where thus resulting for our example in ...
			              Index 0  1  2  3  4  (label)
 LABELS holds (watch the position):	    4  3  1  2  -
 DTL    holds (variable label is index):    -  S  nD pD S


void OKFDD_Shell ( void )

The shell is intended as a convenient and easy way to manipulate DDs online. To expand the capabilities of the shell with user defined functions link the manager variable OKFDD_Shell_Extension on an external function and call it with the shell command `E`.

Tips for function usage:

Simple tip: Try this function by calling the demonstration program puma_shell in the following way:

puma_shell -f BLIFFILE -sh

In the shell the command `h` will give you a list of all commands.



usint OKFDD_Store_Root ( utnode* ROOT )

For the DD ROOT a primary output variable is created; thus it gets possible to reference the DD by a variable name or variable label (which is returned). The reference counter of the DD is incremented by one. See also OKFDD_Free_Node.

Tips for function usage:

By storing the DD it is included in the inspection list of several structure analyzing functions like OKFDD_Profile_all, OKFDD_DTL_all, OKFDD_Support_all, OKFDD_Size_all or OKFDD_Traverse_all.



void OKFDD_Version ( void )

Returns some package informations.

Tips for function usage:

Sorry, no tips available.



void OKFDD_Quit ( void )

Closes the manager after freeing all resources.

Tips for function usage:

Simple tip: If your application quits after this function anyway, just skip this one.



utnode* OKFDD_Exists ( utnode* ROOT, usint PI_LABEL )

For the given DD ROOT the existential quantification ...

f = ROOT(PI_LABEL = 0) + ROOT(PI_LABEL =1)

is returned and stored in the manager variable OKFDD_ROOT[0].

Tips for function usage:

The reference counter of the returned result is incremented by one, thus OKFDD_Free_Node should be called to free the DD if it isn`t needed anymore.



utnode* OKFDD_Forall ( utnode* ROOT, usint PI_LABEL )

For the given DD ROOT the universal quantification ...

f = ROOT(PI_LABEL = 0) * ROOT(PI_LABEL =1)

is returned and stored in the manager variable OKFDD_ROOT[0].

Tips for function usage:

The reference counter of the returned result is incremented by one, thus OKFDD_Free_Node should be called to free the DD if it isn`t needed anymore.



utnode* OKFDD_Substitution ( utnode* ROOT, usint PI_LABEL, utnode* SUB_ROOT )

For the given DD ROOT the variable PI_LABEL is substituted by the DD SUB_ROOT thus ...

f = ROOT(PI_LABEL = SUB_ROOT)

is returned and stored in the manager variable OKFDD_ROOT[0].

Tips for function usage:

The reference counter of the returned result is incremented by one thus OKFDD_Free_Node should be called to free the DD if it isn`t needed anymore.



utnode* OKFDD_Synthesis ( uchar OP_CODE, utnode* OP_1, utnode* OP_2 )

The given operands OP_1 and OP_2 are combined according the operation code OP_CODE and the result is returned and stored in the manager variable OKFDD_ROOT[0]. The following operation codes exist:

Name Description
C_ID OP_1
C_NOT NOT (OP_1)
C_OR OP_1 + OP_2
C_NOR NOT (OP_1 + OP_2)
C_AND OP_1 * OP_2
C_NAND NOT (OP_1 * OP_2)
C_XOR OP_1 x OP_2
C_EQUI NOT (OP_1 x OP_2)
C_IMPF OP_2 => OP_1
C_NIMF NOT (OP_2 => OP_1)
C_IMPG OP_1 => OP_2

Note: `+` denotes OR, `*` denotes AND, `=>` denotes implication and `x` denotes XOR

Tips for function usage:

The reference counter of the returned result is incremented by one, thus OKFDD_Free_Node should be called to free the DD if it isn`t needed anymore.



utnode* OKFDD_ITE ( utnode* F_IF, utnode* G_THEN, utnode* H_ELSE )

The three given operands are combined according the function f = F*G + NOT( F )*H and the result is returned and stored in the manager variable OKFDD_ROOT[0].

Tips for function usage:

The reference counter of the returned result is incremented by one, thus OKFDD_Free_Node should be called to free the DD if it isn`t needed anymore.



ulint OKFDD_1_PC ( utnode* ROOT, char* DUMPFILENAME)
ulint OKFDD_1_PC_all ( uchar SHARED, char* DUMPFILENAME)
ulint OKFDD_1_PC_mult ( utnode** ROOTS, uchar SHARED, char* DUMPFILENAME)

The number of 1-paths of the given DD ROOT (in the case of OKFDD_1_PC_mult DDs in the NULL-terminated field ROOTS / in the case of OKFDD_1_PC_all DDs that were constructed with OKFDD_Read_BLIF or stored with OKFDD_Store_Root) are determined and returned. If DUMPFILENAME isn`t NULL the paths are stored in the given file. If SHARED is `1` the counting is performed shared.

Tips for function usage:

Don`t mess up the counting of 1-paths with the searching of satisfiable variable settings. After all you are operating with OKFDDs and not only BDDs.



void OKFDD_Cofactor ( utnode* ROOT, usint PI_LABEL )

For the given DD ROOT the functions

f = ROOT(PI_LABEL = 0) and f = ROOT(PI_LABEL = 1)

are stored in the manager variable OKFDD_ROOT[0] and OKFDD_ROOT[1].

Tips for function usage:

The reference counters of the results are incremented by one, thus OKFDD_Free_Node should be called to free the DDs if they aren`t needed anymore.



void OKFDD_DTL ( utnode* ROOT, uchar SHOW_RESULTS)
void OKFDD_DTL_all ( uchar SHOW_RESULTS)
void OKFDD_DTL_mult ( utnode** ROOTS, uchar SHOW_RESULTS)

The decomposition types of all variables supported by DD ROOT (in the case of OKFDD_DTL_mult DDs in the NULL-terminated field ROOTS / in the case of OKFDD_DTL_all DDs that were constructed with OKFDD_Read_BLIF or stored with OKFDD_Store_Root) are determined and stored in the field OKFDD_Result_2 (terminated by zero-entry). Simultaneously OKFDD_Result holds all variables in order of their appearence (also terminated by zero-entry). If SHOW_RESULTS is `1` the analyzation results are displayed on screen.

Tips for function usage:

Sample output for OKFDD_DTL_all and benchmark `rd53`:
All:  DTL_LIST:

...1: Label 00005 is of type negative_Davio
...2: Label 00001 is of type Shannon       
...3: Label 00003 is of type positive_Davio
...4: Label 00002 is of type Shannon       
...5: Label 00004 is of type Shannon       

Number of supported vars: 5


void OKFDD_Dumporder ( char* DUMPFILENAME)

The actual variable ordering and DTL of all supported variables are stored in the file DUMPFILENAME. The output file can be used to reconstruct the current settings by using OKFDD_Read_BLIF.

Tips for function usage:

For getting used to the function try e.g. some dumps within the shell.

Sample dump:
# PUMA * OKFDD_Manager V2.21 Copyright (C)'95 by A. HETT & K. NOWAK
# 
# ORDER_file for CIRCUIT < ./rd53 >

# Number of PIs: 00005
# Number of POs: 00003

.order
00002 S
00004 S
00003 P
00005 S
00001 N
.end


uchar OKFDD_Evaluate ( utnode* ROOT, usint* PI_LABELS )

The given DD ROOT is evaluated for all variables set on TRUE that are listed in the NULL-terminated field PI_LABELS. Nonmentioned variables are assumed to be set on FALSE. If the evaluation results in terminal ONE then `1` is returned otherwise `0`.

Tips for function usage:

Evaluation example:

We assume that we want to evaluate a DD with the variables a to e with the corresponding variable labels 1 to 5 and PI_LABLES holds (starting from index 0) [1, 2, 4, 0] then the evaluation is done for the following cube:

cube = a * b * NOT (c) * d * NOT(e).



uchar OKFDD_Identity ( utnode* OP_1, utnode* OP_2 )

Checks the given operands OP_1 and OP_2 for equivalence. If they are identical TRUE is returned otherwise FALSE.

Tips for function usage:

Sorry, no tips available.



ulint OKFDD_ID ( utnode* ROOT )

The unique ID-number of the given DD-Node ROOT is returned.



usint OKFDD_Label ( utnode* ROOT )

The variable label of the given DD-Node ROOT is returned.



usint OKFDD_No_Dead_UTNodes ( void )

The number of dead DD-Nodes is calculated and returned.



usint OKFDD_PI_Table ( usint X )

The variable label of the X-th created variable is returned.



utnode* OKFDD_PO_Root_Table ( usint PO_LABEL )

The DD stored by PO_LABEL is returned.



usint OKFDD_PO_Table ( usint X )

The PO_Label of the X-th stored DD is returned.



void OKFDD_Profile ( utnode* ROOT, uchar SHOW_RESULTS )
void OKFDD_Profile_all ( uchar SHOW_RESULTS )
void OKFDD_Profile_mult ( utnode** ROOTS, uchar SHOW_RESULTS )

A histogram of all variables supported by DD ROOT (in the case of OKFDD_Profile_mult DDs in the NULL-terminated field ROOTS / in the case of OKFDD_Profile_all DDs that were constructed with OKFDD_Read_BLIF or stored with OKFDD_Store_Root) is created and the number of variable appearances stored in the field OKFDD_Result_2 (terminated by zero-entry). Simultneously OKFDD_Result holds all variables in order of their appearence (also terminated by zero-entry). If SHOW_RESULTS is `1` the analyzation results are displayed on screen.

Sample output for OKFDD_Profile_all and benchmark `rd53`:
All:  PROFILE_LIST:

...1: Label 00003 has  3 nodes         PPPPPPPPPPPPPPPPPPPP
...2: Label 00005 has  4 nodes      SSSSSSSSSSSSSSSSSSSSSSSSSS
...3: Label 00002 has  5 nodes  NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
...4: Label 00004 has  3 nodes         SSSSSSSSSSSSSSSSSSSS
...5: Label 00001 has  1 nodes                  SS

Number of supported vars: 5


void OKFDD_SAT_all ( utnode* ROOT, char METHOD )
void OKFDD_SAT_all_n ( usint PO_LABEL, char METHOD , char* DUMPFILENAME )

The given DD ROOT is analyzed and all satisfiable variable settings are counted and (in the case of OKFDD_SAT_all_n) stored in the file DUMPFILENAME. METHOD can have one of the following values:

METHOD Description
1Show results
2Store results
3Show and store results



void OKFDD_SAT_Count ( utnode* ROOT )

The given DD ROOT is analyzed and all satisfiable variable settings are counted. The difference to the function OKFDD_SAT_all using METHOD 1 is that the counting is done with a faster algorithm after the OKFDD is transformed into a BDD. After the calculation the OKFDD is restored.



void OKFDD_Satisfiability ( utnode* ROOT, usint* PI_LABELS, uchar* SETTING )

The given DD ROOT is analyzed and a satisfiable variable setting determined. The result is stored in the way of a variable list (in PI_LABELS terminated with a zero-entry) and the setting of the listed variables (in SETTING terminated with a zero-entry).

Tips for function usage:

The size of both given fields should be at least equal to OKFDD_P_I + 1.



ulint OKFDD_Size ( utnode* ROOT, uchar SHOW_RESULTS )
ulint OKFDD_Size_all ( void )
ulint OKFDD_Size_mult ( utnode** ROOTS, uchar SHOW_RESULTS )

The number of DD-Nodes of the DD ROOT (in the case of OKFDD_Size_mult DDs in the NULL-terminated field ROOTS / in the case of OKFDD_Size_all DDs that were constructed with OKFDD_Read_BLIF or stored with OKFDD_Store_Root) is returned. In the case of multiple DDs the counting of nodes is performed shared.



void OKFDD_Support ( utnode* ROOT, uchar SHOW_RESULTS )
void OKFDD_Support_all ( uchar SHOW_RESULTS )
void OKFDD_Support_mult ( utnode** ROOTS, uchar SHOW_RESULTS )

The support of variables by DD ROOT (in the case of OKFDD_Support_mult DDs in the NULL-terminated field ROOTS / in the case of OKFDD_Support_all DDs that were constructed with OKFDD_Read_BLIF or stored with OKFDD_Store_Root) is determined and all supported variables stored (in order of appearance) in the field OKFDD_Result (terminated by zero-entry). If SHOW_RESULTS is `1` the analyzation results are displayed on screen.

Sample output for OKFDD_Support_all and benchmark `rd53`:
All:  SUPPORT_LIST:

...1: Label 00003
...2: Label 00005
...3: Label 00002
...4: Label 00004
...5: Label 00001

Number of supported vars: 5


uchar OKFDD_Type ( utnode* ROOT )

The given DD ROOT is analyzed and a classification of the decomposition types of all supported variables is returned:

Classification Description
Type_ZERO DD is terminal ZERO
Type_ONE DD is terminal ONE
Type_S DD is a BDD
Type_P DD is a pFDD
Type_Mix_S_P DD is a mixed Shannon- & positive Davio-DD
Type_N DD is a nFDD
Type_Mix_S_N DD is a mixed Snannon- & negative Davio-DD
Type_Mix_P_N DD is a FDD
Type_Mix_S_P_N DD has all 3 decomposition types


Example sourcecode:

if (OKFDD_Type(ROOT) == Type_S) cout << "Root is a BDD";


ulint OKFDD_Traverse ( utnode* ROOT, uchar ORDER, travin INT, travex EXT )
ulint OKFDD_Traverse_all ( uchar ORDER, travin INT, travex EXT )
ulint OKFDD_Traverse_mult ( utnode** ROOTS, uchar ORDER, travin INT, travex EXT )

The DD ROOT (in the case of OKFDD_Traverse_mult DDs in the NULL-terminated field ROOTS / in the case of OKFDD_Traverse_all DDs that were constructed with OKFDD_Read_BLIF or stored with OKFDD_Store_Root) is/are traversed, that is to say every DD-Node of the inspected DDs is visited exactly once. For every visited DD-Node an internal (manager-) and an external (user-function) may be called.

Tips for function usage:


Every (internal or external) subfunction that manipulates the DDs (in a way that new nodes are created, existing ones are deleted) or subfunctions that also traverse the DDs may destroy internal marks that are used for the traversal process: So if you intend to perform such things I suggest that you take a closer look at the sourcecode of the traversal functions and make a clone of them that suits your desires.



A useful internal subfunction is Trav_Show which will give a visualization of each DD-Node entries. The following example will show a possible screen output of it in combination with OKFDD_Traverse_all and the benchmark `rd53`:

Call and result:
dd->OKFDD_Traverse_all( T_Preorder,
                        (travin)&dd->Trav_Show,
                        (travex)NULL            );


Node <...1141-003 P >   Lo [...1261-005 S ] - Hi [...1262-005 S *]
Node <...1261-005 S >   Lo [......1-000 T ] - Hi [...1266-002 N  ]
Node <...1266-002 N >   Lo [...1252-004 S ] - Hi [...1252-004 S *]
Node <...1252-004 S >   Lo [......1-000 T ] - Hi [...1248-001 S  ]
Node <...1248-001 S >   Lo [......1-000 T ] - Hi [......1-000 T *]
Node <...1262-005 S >   Lo [...1266-002 N ] - Hi [...1267-002 N  ]
Node <...1267-002 N >   Lo [...1258-004 S ] - Hi [...1253-004 S *]
Node <...1258-004 S >   Lo [...1248-001 S ] - Hi [...1248-001 S *]
Node <...1253-004 S >   Lo [...1248-001 S ] - Hi [......1-000 T *]
Node <...1143-003 P >   Lo [...1263-005 S ] - Hi [...1264-005 S  ]
Node <...1263-005 S >   Lo [...1270-002 N ] - Hi [...1271-002 N *]
Node <...1270-002 N >   Lo [...1253-004 S ] - Hi [...1258-004 S *]
Node <...1271-002 N >   Lo [...1252-004 S ] - Hi [...1258-004 S  ]
Node <...1264-005 S >   Lo [...1272-002 N ] - Hi [...1272-002 N *]
Node <...1272-002 N >   Lo [...1258-004 S ] - Hi [......1-000 T  ]
Node <...1139-003 P >   Lo [...1264-005 S ] - Hi [......1-000 T  ]
      |        |  |         |        |  |         |        |  | |
                                                                |
     ID    Label DT        ID    Label DT        ID    Label DT |
                                                                
                                                 Complemented Edge

     <    FATHER    >      <    LOW_SON   >       <   HIGH_SON   >



utnode* OKFDD_to_ZSBDD ( utnode* ROOT )

For the given DD ROOT a functional equivalent ZSBDD is constructed that exists in parallel to the original DD. To achieve this coexistence for every real variables there exists clone variables that will be used in the ZSBDDs.



ulint ZSBDD_1_PC ( utnode* ROOT )
ulint ZSBDD_1_PC_mult ( utnode** ROOTS, uchar SHARED )

The number of combinatorial elements of the given ZSBDD ROOT (in the case of ZSBDD_1_PC_mult DDs in the NULL-terminated field ROOTS) is determined and returned. If SHARED is `1` the counting is performed shared.



utnode* ZSBDD_Multi_Op ( uchar OP_CODE, utnode* OP_1, utnode* OP_2 )

The given operands OP_1 and OP_2 are combined according to the operation code OP_CODE and the result is returned and stored in the manager variable OKFDD_ROOT[0]. The following operation codes exist:

Name Description
ZS_Union Union of OP_1 and OP_2
ZS_Intsec Intersection of OP_1 and OP_2
ZS_Diff OP_1 - OP_2



utnode* ZSBDD_Single_Op ( uchar OP_CODE, usint PI_LABEL, utnode* OP )

For the given operand OP the operation according to the operation code OP_CODE is performed, the result returned and stored in the manager variable OKFDD_ROOT[0]. The following operation codes exist:

Name Description
ZS_Sub1 Determines the subset of OP for PI_LABEL = 1
ZS_Sub0 Determines the subset of OP for PI_LABEL = 0
ZS_Change Returns OP if PI_Label is inverted



void OKFDD_Blockshift ( usint START, usint DESTINATION, usint BLOCKLENGTH )

The given block of neighbouring levels with the length BLOCKLENGTH starting at level START is shifted to level DESTINATION.

Tips for function usage:

Possible levels for the arguments START and DESTINATION are from the interval [0 ... OKFDD_P_I - 1].



void OKFDD_DD_to_BDD ( usint TOP, usint BOTTOM, char METHOD )
void OKFDD_DD_to_FDD ( usint TOP, usint BOTTOM, char METHOD )
void OKFDD_DD_to_NDD ( usint TOP, usint BOTTOM, char METHOD )

The decomposition types of all variables in the given level-window [TOP ... BOTTOM] are set to D_Shan (in case of FDD to D_posD / in case of NDD to D_negD). If METHOD is `1` the original variable ordering in the window is kept.

Tips for function usage:

Possible levels for the arguments TOP and BOTTOM are from the interval [0 ... OKFDD_P_I - 1].
If no ordering restrictions are given (METHOD is left on `0`) the procedure works at it`s best.



void OKFDD_DTL_Chg_Bottom ( usint LEVEL, uchar DT )

The decomposition type of the variable in the given LEVEL is set to DT.

Tips for function usage:

Possible levels for the argument LEVEL are from the interval [0 ... OKFDD_P_I - 1].



void OKFDD_DTL_Friedman ( usint TOP, usint BOTTOM )

For the given level-window [TOP ... BOTTOM] an exact minimization regarding variable ordering and DTL is performed according to an improved version of an algorithm introduced by Friedman.

Tips for function usage:

Possible levels for the arguments TOP and BOTTOM are from the interval [0 ... OKFDD_P_I - 1].



void OKFDD_DTL_Permutation ( usint TOP, usint BOTTOM )

For the given level-window [TOP ... BOTTOM] an exact minimization regarding variable ordering and DTL is performed.

Tips for function usage:

Possible levels for the arguments TOP and BOTTOM are from the interval [0 ... OKFDD_P_I - 1].



void OKFDD_DTL_Sifting ( usint TOP, usint BOTTOM, float SF, char RA, char METHOD )

For the given leve-lwindow [TOP ... BOTTOM] a heuristical minimization regarding variable ordering and DTL is performed according to an improved version of the algorithm Sifting introduced by Rudell. The meaning of the last three arguments SF, RA and METHOD is given with the description of the improved Sifting algorithms.

Tips for function usage:

Possible levels for the arguments TOP and BOTTOM are from the interval [0 ... OKFDD_P_I - 1].



void OKFDD_Friedman ( usint TOP, usint BOTTOM )

For the given level-window [TOP ... BOTTOM] an exact minimization regarding variable ordering is performed according to an algorithm introduced by Friedman.

Tips for function usage:

Possible levels for the arguments TOP and BOTTOM are of the interval [0 ... OKFDD_P_I - 1].



void OKFDD_GAC_4_DTL ( usint TOP, usint BOTTOM, uchar OP_CODE, travin INT, travex EXT )

Generates OKFDDs with all (specified) combinations of DTLs in the given levelwindow [TOP ... BOTTOM] and is capable of calling internal and/or external subfunctions to analyze the constructions. The OP_CODE specifies what kind of decomposition types are allowed. Possible codes are:

GAC_S_N_P, GAC_S_P, GAC_S_N and GAC_P_N

The letters `S` (Shannon), `P` (positive Davio) and `N` (negative Davio) denote the decomposition types that shall be used. E.g. if you want to modify a BDD using only Davio-Types you would choose GAC_P_N as OP_CODE. (This is possible independant of the initially given DTs (in this case BDD that is to say only Shannon-Nodes). Here OKFDDs for all DT-combinations with a given ordering are constructed and after each construction an internal (INT) and/or external (EXT) function is called to perform an action (like measuring the size).

Tips for function usage:

Possible levels for the arguments TOP and BOTTOM are from the interval [0 ... OKFDD_P_I - 1].
For an example how to use OKFDD_GAC_4_DTL you should take a look at the Frequently Asked Questions section Question 2.6.



void OKFDD_Inversion ( usint TOP, usint BOTTOM )

For the given level-window [TOP ... BOTTOM] the current variable order is inverted.

Tips for function usage:

Possible levels for the arguments TOP and BOTTOM are from the interval [0 ... OKFDD_P_I - 1].



void OKFDD_Levelexchange ( usint LEVEL )

The variables in level LEVEL and LEVEL + 1 exchange their positions.

Tips for function usage:

Possible levels for the argument LEVEL are from the interval [0 ... OKFDD_P_I - 2].



void OKFDD_Levelshift ( usint START, usint DESTINATION )

The variable in level START is shifted to level DESTINATION.

Tips for function usage:

Possible levels for the arguments START and DESTINATION are from the interval [0 ... OKFDD_P_I - 1].



void OKFDD_Levelswap ( usint LEVEL_1, usint LEVEL_2 )

The variables in level LEVEL_1 and LEVEL_2 exchange their positions.

Tips for function usage:

Possible levels for the arguments LEVEL_1 and LEVEL_2 are from the interval [0 ... OKFDD_P_I - 1].



void OKFDD_Permutation ( usint TOP, usint BOTTOM )

For the given level-window [TOP ... BOTTOM] an exact minimization regarding variable ordering is performed.

Tips for function usage:

Possible levels for the arguments TOP and BOTTOM are from the interval [0 ... OKFDD_P_I - 1].



void OKFDD_Sifting ( usint TOP, usint BOTTOM, float SF, char RA, char METHOD )

For the given level-window [TOP ... BOTTOM] a heuristical minimization regarding variable ordering is performed according to an Sifting algorithm introduced by Rudell. The meaning of the last three arguments SF, RA and METHOD is given with the description of the improved Sifting algorithms.

Tips for function usage:

Possible levels for the arguments TOP and BOTTOM are from the interval [0 ... OKFDD_P_I - 1].



void OKFDD_Siftlight ( usint TOP, usint BOTTOM, char METHOD )

For the given level-window [TOP ... BOTTOM] a heuristical minimization regarding variable ordering is performed according to a modified version of an Sifting algorithm introduced by Rudell. The difference to the original Sifting version is that each variable is only shifted through it`s neighbourhood as long as the overall size gets lower or stays the same. The meaning of the last argument METHOD is given with the description of the improved Sifting algorithms.

Tips for function usage:

Possible levels for the arguments TOP and BOTTOM are from the interval [0 ... OKFDD_P_I - 1].



void OKFDD_Sort ( usint TOP, usint BOTTOM, uchar DT )

For the given level-window [TOP ... BOTTOM] the current variable order is sorted according to their initial ordering. Additionally the decomposition type of each variable is set to DT.

Tips for function usage:

Possible levels for the arguments TOP and BOTTOM are from the interval [0 ... OKFDD_P_I - 1].



void OKFDD_Winpermutation ( usint TOP, usint BOTTOM, usint SIZE, usint OVERLAP )

The given level-window [TOP ... BOTTOM] is divided in subwindows of size SIZE and an overlapping of OVERLAP. For each subwindow an exact minimization regarding variable ordering is performed.

Tips for function usage:

Possible levels for the arguments TOP and BOTTOM are from the interval [0 ... OKFDD_P_I - 1].



void OKFDD_Winsift ( usint TOP, usint BOTTOM, usint SIZE, usint OVERLAP )

The given levelwindow [TOP ... BOTTOM] is divided in subwindows of size SIZE and an overlapping of OVERLAP. For each subwindow a heuristical minimization regarding variable ordering is performed according to an algorithm Sifting introduced by Rudell.

Tips for function usage:

Possible levels for the arguments TOP and BOTTOM are from the interval [0 ... OKFDD_P_I - 1].




ulint XShowDD ( utnode* ROOT )
ulint XShowDD_all ( )
ulint XShowDD_mult ( utnode** ROOTS )

The DD ROOT (in the case of XShowDD_mult DDs in the NULL-terminated field ROOTS / in the case of XShowDD_all DDs that were constructed with OKFDD_Read_BLIF or stored with OKFDD_Store_Root) is/are visualized in a separate window.

Tips for function usage:

You can adjust the presentation window in size and can close it by following the instruction in the top-line text of the window. Explanations of the visualizations follow:

The white nodes denote Shannon-nodes, the red ones denote positive and the blue ones negative Davio-nodes. In the node the variable number that corresponds to the used variable can be seen. Right beside the nodes is their ID-Number. The blue lines denote the low- and the red lines the high-edges. White edges denote root-pointers. The red and white dots on the edges denote a complement mark. The terminal ONE node is depicted by a black box.

To see the full-scale visualization of the sample (benchmark 'rd53') below just leftclick the small picture. Then right-click and choose 'Back in Frame' to get back to this point.







Frequently Asked Questions


General problems

  1. Where can I get a documentation of PUMA ?
  2. I want some quickstart information about PUMA !
  3. I want some examples for quick constructions of OKFDDs !
  4. I can`t find the command to read a BLIF from the user-shell !
  5. What about the computational complexities of synthesis operations ?
Ordering and DTL

  1. How can I optimize the ordering and DTL of OKFDDs ?
  2. How to build OKFDDs with a predefined ordering and DTL ?
  3. How do I activate Interleaving ?
  4. How do I activate the Interrupthandler ? What is INTERHAND?
  5. Why does PUMA take so much time for the calculation of DDs with known good orderings and/or DTLs?
  6. Is there a way to get an optimized OKFDD under an arbitrarily chosen ordering ? (Can I optimize the DTL for a given ordering ?)
Miscellaneous

  1. What about calculating AND/XOR-expressions for each node of the DDs ?



1.1. Where can I get a documentation of PUMA ?


Well, you are reading it at the moment. No other english version exists.




1.2. I want some quickstart information about PUMA !


To get a rough impression of the capabilities of PUMA you should activate the user-shell after construction of a small benchmark (for the beginning) and play a little bit with the functions. So try for example the following:

puma_shell -f rd53 -sh

where `-sh` activates the user-shell and `-f ` builds DDs out of the given benchmark.

In the user shell type `h` to get a list of commands you can activate.

E.g. try some Sifting (Siftlight `l`, Sifting `s` or DTL-Sifting `S`) or type in a command to analyze the DDs (e.g. Profile `0` or Traversal `3`). The profile will give you a rough structural representation of the DDs (a kind of histogram). The symbols `S` (Shannon), `P` (positive Davio) or `N` (negative Davio) in the bars denote the decomposition types (DTs) of the variables. For example if you use the above mentioned call `puma_shell -f rd53 -sh` you will see `pure` BDDs (Shannon-Graphs). If you try to optimize the variable ordering and DT-list (e.g. with DTL-Sifting) you possibly get some Davio-types.




1.3. I want some examples for quick constructions of OKFDDs !


I will show you some examples to build DDs out of BLIFs. Try the following commands after compilation of the puma-library and the puma_shell:

Command End size
puma_shell -f C7552.blif 8481
puma_shell -f C5315.blif 84267
puma_shell -f C5315.blif -tr 2 2897
puma_shell -f C1355.blif -tr 2 -tf 1.8 -sb 1000 30833
puma_shell -f C1355.blif -tr 3 -tf 1.8 -sf 2 -i 19045


See Question 2.4. for more details about the used options.




1.4. I can`t find the command to read a BLIF from the user-shell !


The answer to your problem is very simple. The interactive user shell OKFDD_Shell (which is for example called from the demo program puma_shell with the option `-sh`) is meant only for manipulations and analyzations of already existent DDs. There IS NO option to read in BLIF-files in OKFDD_Shell. This has to be done before.
All things you can do in the shell are listed by typing `h` at the shell-prompt Command > !

To interact with DDs you first have to construct them. Therefore the option `-f` was introduced for puma_shell. It reads your specified BLIF by calling the function OKFDD_Read_BLIF.

E.g.: puma_shell -sh -f rd53 reads the benchmark `rd53`, constructs the corresponding DDs then enters the shell.

If you don`t want to use the demo programs, you have to include the following lines in your sourcecode:
>   // Init manager
>   // ------------
>   dd_man* dd = OKFDD_Init();
>
>   // Read BLIF-File
>   // --------------
>   dd->OKFDD_Read_BLIF("filename",NULL,NULL);
>
>   // Enter shell
>   // -----------
>   dd->OKFDD_Shell();



1.5. What about the computational complexities of synthesis operations ?


I could make things easy and say most of them have exponential runtime but that wouldn`t be fair. Because of the three decomposition types there exists a complicate mixture in practical terms although the theory would tell you otherwise. So in detail:

Operation Complexity
AND, OR for BDDs: O(|F|*|G|) if no result is calculated more than once this implies a perfectly working computed table (CT) which is hypothetical but in practice nearly given.
AND, OR for OKFDDs: In worst case exponential (like BDDs without a CT). The usage of our CT is quite efficient so in practical experiments we never came across a real exponential behaviour.
NOT for OKFDDs: O(|1|) due to complemented edges.

Existential quantification: Since it uses the OR operation everything is said above.


These statements don`t look very promising but in fact theory and practice are VERY different and mostly the operations work very fast.




2.1. How can I optimize the ordering and DTL of OKFDDs ?


You have to distinguish between the possibilities during construction and the things you can do afterwards:

The construction currently (PUMA_V2.21) works as follows:
After the DDs are built you can perform optimization with several procedures. An extract follows:

Heuristics: Exact algorithms:


2.2. How to build OKFDDs with a predefined ordering and DTL ?


With PUMA V2.21 the Reader-Function OKFDD_Read_BLIF has changed in a way to give you a more convenient approach in setting a special order and/or DTL. As you can see in the following function declaration I added the fields Label_Table and DTL_Table which can be filled with the data that matches the entries of an order-file (dump) that is to say the first column holds the levels of the variables and the second column holds D_Shan, D_posD and D_negD - entries (0,1 and 2) at the index position variable - 1 (see example) to represent the desired decomposition types:
// ----------------------------------------------------------
// Header for OKFDD-Builder-Routines / Reads given order too
// (External_function is called after each gate construction)
// ----------------------------------------------------------
void OKFDD_Read_BLIF ( char*    Filename          = NULL,
                       char*    Ordername         = NULL,
                       travex   External_Function = NULL,
                       usint*   Label_Table       = NULL,
                       uchar*   DTL_Table         = NULL );
Example:

Assume you want to build DDs with variable order and DTL 3pD 4S 2nD 1S:

You make a call of OKFDD_Read_BLIF(FILENAME,NULL,NULL,LABELS,DTL) where
			              Index 0  1  2  3  4  (label - 1)
 LABELS holds (watch the position):	    4  3  1  2  -
 DTL    holds (variable label-1 is index):  S  nD pD S  -
                                                  |  |
            Label 3 shall get D_posD and level 1 -+  |
            Label 4 shall get D_Shan and level 2 ----+

You may also have noticed that in the argument-list of OKFDD_Read_BLIF there exists an entry External_Function. Take a look at Question 2.4. for more details about it.




2.3. How do I activate Interleaving ?


Well the question should rather be: How do I DEACTIVATE Interleaving ?

Since PUMA_V2.21 Interleaving is ALREADY ACTIVATED in `puma_shell`, so option `-i` now turns it OFF. So be aware of this default-change in `puma_shell`.




2.4. How do I activate the Interrupthandler ? What is INTERHAND?


During construction it`s possible to interrupt the process (after each gate translation from BLIF -> OKFDD) and call a reordering procedure (e.g. Siftlight, Sifting, DTL-Sifting ...) or whatever you like. The function that is called to handle this can be set with the argument External_Function of OKFDD_Read_BLIF. I suggest to use a prepared (external function) I named INTERHAND. If you take a look at the source-code `puma_shell.c` you will see how it is called and what parameters can be set (this is also shown if you execute puma_shell -h).

The following manager-variables can be set to improve the construction of DDs (in many cases):

-tr <Temproutine>
-tf <Tempfactor> Determines the upper growth boundary that must be crossed to init a (new) Siftprocess. E.g. a setting of 1.5 activates a new siftprocess if the size reached 150% of it`s former value. Suggested values: [1.1, ... ,3]
-sf <Siftfactor> Sets a factorial limit for the growth during a siftprocess cause although the outcome will be improved, during sifting the DDs might explode if not kept at bay. Suggested values: [2, ... ,3]
-sb <Siftbase> Lower size boundary that has to be crossed to perform interruption and test the other parameters. Suggested values: [1000, ... , 10000]

For convenience you can use the `puma_shell` to activate and set the parameters but (of course) you can also set the manager-variables by your own (before calling OKFDD_Read_BLIF) and therefore combine your own functions with the given procedures to improve size reduction during construction.




2.5. Why does PUMA take so much time for the calculation of DDs with known good orderings and/or DTLs?


As you probably noticed (if you have the percentage bars activated during construction) most gates are handled in a fraction of a second but for some gates the process gets stuck. I analyzed several cases some time ago and came to the solution that the Computed Table in these cases can`t deliver useful entries to speed up the recursive synthesis algorithms simply because there aren`t any precalculated results for reusage. This effect occurs if very complex subgraphs are to be combined and maybe one of them has a very rarely used input variable or a completely new one. The obvious consequence is that the recursive synthesis algorithms have to do the whole work on their own. And that takes a lot of time if the subgraphs for e.g. an AND-gate with fanin 8 are very large. The assumption that it is EASY TO BUILD DDs IF the known SIZE AT THE END IS SMALL is NOT TRUE because the size that can be observed during construction (and this is the main reason I included the nice looking percentage bar, gate and size display) can get very very large!



Summary:

There is no (at least as far as I`m informed) guarantee to prevent large runtimes during construction with or without a good order and DTL. But with the combination of static and dynamic methods to vary or determine an order and DTL during construction they can be avoided in many cases .

Presuming PUMA_V2.21 is used here are some settings you should test. I hope they give you an impression of the methods and ideas to handle the formerly mentioned problems I have implemented, expanded and newly developed to squeeze the DDs.

Command End size
puma_shell -f C7552.blif 8481
puma_shell -f C5315.blif 84267
puma_shell -f C5315.blif -tr 2 2897
puma_shell -f C1355.blif -tr 2 -tf 1.8 -sb 1000 30833
puma_shell -f C1355.blif -tr 3 -tf 1.8 -sf 2 -i 19045

Of course you can also combine the dynamic methods (called by e.g. INTERHAND) with a predefined order and DTL.




2.6. Is there a way to get an optimized OKFDD under an arbitrarily chosen ordering ? (Can I optimize the DTL for a given ordering ?)


The answer is yes!

You can make use of a procedure called OKFDD_GAC_4_DTL. It generates OKFDDs for all (specified) combinations of DTLs and is capable of calling subfunctions to evaluate them.

Actually you can determine what kind of decomposition types are allowed (argument operationcode). These are the possible ones:

GAC_S_N_P, GAC_S_P, GAC_S_N and GAC_P_N

The letters `S` (Shannon), `P` (positive Davio) and `N` (negative Davio) denote the decomposition types that shall be used. E.g. if you want to optimize a BDD (keeping the current ordering) using only Davio-Types you would choose GAC_P_N for operationcode. (This is possible independant of the initially given DTs (in this case BDD that is to say only Shannon-Nodes). Here OKFDDs for all DT-combinations with a given ordering are constructed and after each construction an internal and/or external function is called to perform an action (like measuring the size).

Now a function call example (I propose for your application):

dd_manager->OKFDD_GAC_4_DTL( 0, OKFDD_Maxidx - 1, GAC_S_P_N, NULL, &TAKE_BEST);



Define globally:
>  #define unsigned short integer usint
>  #define unsigned long          ulong
>
>  long   minimum  = 10000000;
>  uchar* MINTABLE = new usint[dd_manager->OKFDD_Maxidx];
External_function `TAKE_BEST`:
>  void Take_best(	dd_man* dd,
>   			utnode* root)
>                       // root must be given but can be ignored here
>  {
>    // If actual OKFDD is better than all others -> Store DTL
>    // ------------------------------------------------------
>    if (dd->OKFDD_Now_size_i < minimum)
>    {
>      minimum = dd->OKFDD_Now_size_i;
>
>      // Store actual DTL-setting (in ordering of PI-Table)
>      // --------------------------------------------------
>      for(ulong loop = 0; loop < dd->OKFDD_Maxidx - 1; loop++)
>      {
>        MINTABLE[dd->OKFDD_PI_Table(loop)] =
>   	   dd->OKFDD_PI_DTL_Table[dd->OKFDD_PI_Table(loop)];
>      }
>    }
>  }


After calling OKFDD_GAC_4_DTL you have to set the best determined DTL by the following:

dd_manager->OKFDD_Setthis(NULL,MINTABLE);

The result is an DTL-optimized OKFDD with the given initial ordering of variables!




3.1. What about calculating AND/XOR-expressions for each node of the DDs ?


The following pseudo-algorithm seems to suit best:

Open package-manager by using dd_man* dd = OKFDD_Init();
Built DD out of BLIF-description by using dd->OKFDD_Read_BLIF(BLIF-filename,NULL,NULL);
Do some analyzations or calculations
Traverse DDs and call a function to calculate the AND/XOR-expression (dump it in two-level format)


Use this function call:
dd->OKFDD_Traverse_all(T_Preorder,(travin)NULL,&LAUNCHER)
with the subfunction `LAUNCHER`:
>  // Declaration
>  // -----------
>  void Launcher(dd_man*,utnode*)

...

>  // Actual function
>  // ---------------
>  void Launcher(dd_man* dd, utnode* root)
>  {
>    // Determine 1-Paths -> Write AND/XOR-expression in file
>    // -----------------------------------------------------
>    dd->OKFDD_1_PC(root,DUMPFILENAME);
> 
>    // Change DUMPFILENAME (increment counter or something like that)
>    // --------------------------------------------------------------
>    ...
>  }


The function OKFDD_1_PC will dump an AND/XOR-expression (for the given DD, represented by its node) like this (example for a node of a DD for `rd53`):

# PUMA * OKFDD_Manager V2.21 Copyright (C)'95 by A. HETT & K. NOWAK
# 
# 1_PC_file for CIRCUIT < ./rd53 >

# Number of PIs: 00005
# Number of POs: 00003

.order
00001 S
00002 S
00003 S
00004 S
00005 S
.end

.exor
01111 1
10111 1
11011 1
11101 1
1111- 1
.paths 0000000005
.end_exor
If the function OKFDD_1_PC doesn`t perform the action you want you can also write your own external subfunction and call it with the package-traversal-functions.