BDS - BDD based decomposition tool


BDS is a logic optimization program developed at the University of Massachusetts, Amherst. It is an experimental tool for BDD-based logic synthesis, developed by Congguang Yang as part of his Ph.D. thesis.
For details see the BDS-1.2 webpage.

BDS is based on a new theoretical foundation, namely a structural decomposition of the BDD of the logic function. Unlike traditional methods based on algebraic factorization, it allows for both algebraic and Boolean logic decomposition of type AND, OR, XOR, and MUX. In this tool, BDD is used as the sole platform to carry out all procedures in the synthesis flow.

[cited from the BDS-1.2 webpage]

BDS is no longer supported by the University of Massachusetts, Amherst. Therefore, upon agreement of the authors, BDS is now maintained by the Czech Technical University in Prague and published at this webpage.

Currently a version BDS-1.2.15 is available at this webpage - see Download

Major Enhancements

  • Some bugs corrected
  • CUDD 2.5.0 support
  • Singularities in input BLIF files handled
  • Enhanced algorithm control (possibility of switching off different types of decomposition)

Newly added switches

    These switches are given in bold in the manual.

Detailed revision history

 *  01: at the BDS_VERBODE_MOST level, BDD size before and after reorder reported
 *      (manual loop discovery)
 *  02: -xdelta and x-decomp disqualification introduced
 *  03: -xhardcore backported from bds-pga, -dir introduced
 *  04: -xhardcore option removed, -sid -ged -bhc -xhc -cft introduced
 *  05: bug in BDS_GetFileHead corrected
 *  06: bnet.c, loptUtil.c: Cudd_DumpBlif usage conforming CUDD 2.4.2
 *      eliminate.c: BDS_EliminateNodeOrNot crashed on constant outputs
 *  07: bnet.c: CR LF resistance in BLIF import
 *      lopt.c: BDS_CheckTerminal(), bug overriding ftnode value
 *      loptUtil.c: BDS_GetFileHead() changed to BDS_GetEntireFileHead(), BDS_GetFileHead() changed
 *      export.c: error message on opening output file enhanced 
 *      local.c: bdsConvertDummy2RealRecursive() no conversion on constant nodes
 *      ftree.c: BDS_ExtractSharingOnFtreeRecursive() proper treatment of constant nodes
 *  08: local.c: trivial mistake in the previous mod
 *  09: export.c: bdsDumpFtreeBlifOneNodelsList(): constant ftree nodes detected
 *      export.c: bdsDumpFtreeBlifOneNodelsList(): inputs to PO nodes from Bnet not PIvariables 
 *      export.c: bdsDumpFtreeBlifOneNode(): constant ftree nodes detected; 
 *              constant node semantics taken over from Bnet_PrintNetwork()
 *      export.c: bdsDumpFtreeBlifOneNode(): outputs connected to constant generators 
 *              output these generators and mark them visited. bdsDumpFtreeBlif() has
 *              to erase the marks; net->nodes useless (chain corrupted - where?)
 *      export.c: bdsDumpFtreeBlifOneNode(): inputs to PO nodes from Bnet not PIvariables 
 *      lopt.c: BDS_CheckTerminal(), bug in constant bdd detection (introduced in 1.2.07)
 *      prepare.c: bdsBuildVarNameAssocLocal() only PIs and POs(why?) collected into PIvariables
 *      bnet.[ch]: bnodeTypes added for debugging purposes
 *	bnet.h: constant node semantics recorded in comments
 *	main.c: bdsDumpFtreeBlif() in export.c assumes that net->outputs[i] corresponds to FTNode[i];
 *		enforce this in FTNode construction
 *      loptUtil.c: BDS_CreateRunDir() puts the entire year into the name, not years since 1900;
 *              considered too cryptic after 2000
 *  10: prepare.c: bdsBuildVarNameAssocLocal(): BDD variables collected into PIvariables
 * 		only when the Bnode is a PI, PO, or internal (not constant). Bug introduced 
 *		in 1.2.09.
 *	main.c: -v option introduced
 *  11: main.c: alter poName2poIndex to store pointers into FTreeNode not indices (easier 64 bit portability)
 *      export.c, debug.c, cutptl.c: alter fprintf() formats to use '%p' not '0x%x'. 
 *		Do not cast its operand to unsigned. Affects output produced by BDS_DumpBddBlif() -
 *		some names have '0x' in front of them. should not affect BLIF conformance.
 *  12: export.c: bdsDupFtreeBlifOneNode(),  bdsDupFtreeBlifOneNodelsList():
 *              code for constant primary outputs and buffers/inverters between 
 *              primary inputs and outputs rewritten again, with the assumption that internal
 *              constant generators have been deleted by constant propagation
 *              (closer to the original, deleting most of the code from 1.2.09)
 *      export.c: bdsDumpFtreeBlif(), BDS_DumpFtreeBlif(): any node is collected as output
 *              if it has an entry in FactorTreeNode2BnetNode (affects intermediate BLIF outputs)
 *      bulid.c: BDS_BuildLocalNodeBDD(), BuildGlobalNodeBDD(): employ the DFS manner
 *              of BDD construction to do constant propagation
 *      main.c: in the main processing loop, skip BDDs that correspond to internal constant
 *              generators - they are not needed any more
 *      debug.h: new file, debug function prototypes (also from lopt.h), debug control
 *              (compile-time)
 *      debug.c: functions for tabelating factorization tree nodes
 *      lopt.h: debug-related macros and prototypes moved to debug.h
 *      main.c, ftree.c, export.c, lopt.c, sweep.c, minimize.c: altered #ifdef DEBUG to #if DEBUG_ACTIVE(ddd)
 *              (see debug.h)
 *  13: bnet.c: unreasonable limitation on list size in readList(). Code rewritten,
 *		based on REALLOC.
 *  14: winfake.h, winfake.c: replacement functions for windows compilation
 *      export.c: BDS_DumpSingleFTree(): added code for constant generator
                as an emergency measure (the EQN files can be invalid)