Welcome to the
Decision
Diagram-Package
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 ... |
0 | General status |
1 | Errors |
2 |
Interleaving |
3 | Ordering during DD construction |
4 | Gates during DD constructions |
5 | Status during DD constructions |
6 | Node deallocation |
7 |
Recycling cache |
8 |
Unique table resizing |
9 | Variable construction |
10 | Unique table construction |
11 | Leveldetermination of variables |
12 | Fanins of circuit gates |
18 | Ordering list |
19 | DD sizes during reordering |
20 | DD sizes after reordering |
21 | DD sizes before reordering |
22 | Cost comparison during reordering |
23 | Variable 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 |
uchar | unsigned char |
usint | unsigned short int |
sint | short int |
ulint | unsigned long int |
lint | long int |
travin | void (dd_man::*travin) (utnode*) |
travex | void (*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
Synthesis and Combinational Functions
Structure Analyzing Functions
Traversal Functions
Zero Suppressed BDD Functions
Reordering Functions
Graphic functions
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 |
1 | Show results |
2 | Store results |
3 | Show 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
- Where can I get a documentation of PUMA ?
- I want some quickstart information about PUMA !
- I want some examples for quick constructions of OKFDDs !
- I can`t find the command to read a BLIF from the user-shell !
- What about the computational complexities of synthesis operations ?
Ordering and DTL
- How can I optimize the ordering and DTL of OKFDDs ?
- How to build OKFDDs with a predefined ordering and DTL ?
- How do I activate Interleaving ?
- How do I activate the Interrupthandler ? What is INTERHAND?
- Why does PUMA take so much time for the calculation of DDs
with known good orderings and/or DTLs?
- Is there a way to get an optimized OKFDD under an arbitrarily chosen
ordering ? (Can I optimize the DTL for a given ordering ?)
Miscellaneous
- 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:
- You can set a decomposition type list (DTL) and ordering for setup.
or
- You can use (default for multi-level-benchmarks like e.g. c7552.blif)
interleaving (choosing option `-i` in puma_shell deactivates it)
which will overrule your given DTL and ordering and heuristically
determines a good initial variable ordering
or
- You can activate the interrupt_handler to optimize DURING construction
(See also Question 2.4. for more details)
After the DDs are built you can perform optimization with several
procedures. An extract follows:
Heuristics:
- Sifting tries to optimize variable ordering
- Siftlight tries to optimize variable ordering (better runtime)
- DTL-Sifting tries to optimize variable ordering and DTL
- etc.
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.