| FBDD 1.0 User Manual | |
FBDD is a Binary Decision Diagram (BDD) [1] based combinational logic optimization system targeting area and runtime. It takes a gate level circuit described in Berkeley Logic Interchange Format (BLIF) and produces an area optimized circuit in BLIF and structural Verilog formats.
FBDD is inspired by the BDD-based Logic Synthesis system (BDS) developed at University of Massachusetts [2,3]. In contrast to traditional logic synthesis systems exemplified by SIS [4], which use cube set to represent logic functions of the gates, and literal count as the area metric, BDS uses BDD to represent logic functions, and the corresponding BDD node count as the area metric. A comprehensive set of decomposition methods exploiting the structural properties of BDDs have been developed in BDS, leading to good results in area for some benchmarks, and better runtime result in general.
FBDD builds a similar flow as BDS and implements its core set of decomposition algorithms. In addition, FBDD attempts to produce much better runtime and more competitive area based on two ideas. First, FBDD attempts to exploit the inherent regularity contained in logic networks to dramatically improve runtime by amortizing the cost of logic transformations over equivalent classes of subnetworks. Described in [6], this strategy is referred to as logic folding and is applied in almost all logic transformations in FBDD. Second, FBDD attempts to perform sharing extraction in the same spirit of SIS by explicitly enumerating divisors in each gate and selectively extracting those that profit area. Our algorithm, described in [5], performs multiple variable disjunctive extraction and operates directly on BDDs.
Before installing FBDD, you need to install the CUDD package by Fabio Somenzi [9].
FBDD performs only technology independent logic optimizations and needs an external technology mapper to complete the logic synthesis flow. For standard cell technology, one can use the Berkeley SIS mapper. For FPGA, one can use the UCLA rasp_syn mapper. Note that although the latter is not required to build and run FBDD, the path to the rasp_syn executable needs to be pointed to by the PATH environment variable in order to run the provided scripts and automatically produce benchmark results.
FBDD software uses the standard GNU build system based on the Autotool set (autoconf/automake) as well as the GCC compiler suite. A helpful tutorial is maintained by Eleftherios Gkioulekas.
To build FBDD in release mode, type the following under a Unix (e.g. solaris) or Unix-like environment (e.g., Linux or Cygwin for Windows):
>aclocal >autoheader >autoconf >automake >./configure --with-cudd=/your/cudd/path --with-prefix=/your/install/path >gmake
To build FBDD in debug mode:
>aclocal >autoheader >autoconf >automake >./configure --enable-debug --with-cudd=/your/cudd/path \ --with-prefix=/your/install/path >gmake
To install FBDD:
>gmake install
This should install the executable file fbdd on the path specified by the with-prefix argument during configuration.
FBDD performs a series of logic transformations on a logic network in an effort to improve its quality. It first performs the ``simplify'' operation to reduce the logic complexity of each gate. Since the gate logic functions are represented by BDDs, the simplification can be achieved by BDD variable reordering to find a BDD representation with less node count. It then performs the ``sweep'' operation to clean up the network by propagating constants, merging repeating support variables and removing dangling gates. This is followed by the ``eliminate'' operation to selectively collapsing some gates into their fanouts in order to remove redundancy between gates, after which another ``sweep'' operation is performed. Next, the ``sharing extraction'' operation and the ``decomposition'' operation are applied. The former identifies common logic expressions among and selectively extract them as new gates. The latter decomposes a large gate into smaller gates. The two operations are interleaved: extractions are performed first to find as much logic sharing as possible; when no more extractors can be found, decomposition is applied, which may lead to more extractors to be found. This process is repeated until the circuit is fully decomposed, after which another ``sweep'' pass is applied.
FBDD can be invoked as follows, where ckt.blif corresponds to the input logic network.
>fbdd [-options] ckt.blif
The default synthesis flow can be altered using the following options.
These options can be used to understand the contributions on synthesis quality for different logic transformations.
The following options configure the sharing extraction algorithm.
FBDD performs sharing extraction by matching disjunctive extractors
from among gates in the network. Disjunctive extractors are functions
with decompositions of the form
such that
and 
do not share supports. FBDD puts a limit on the size
of extractors considered. The maximum extractor size is specified
using the -maxextsize option and can be set from size 2 to 5.
Be warned however, that the runtime grows exponentially with the
extractor size. There is also a choice between two sharing extraction
algorithms. The exact algorithm -tweexact finds all extractors
up to the size specified. The fast algorithm -twefast only applies
when -maxextsize is 2. It sacrifices finding ALL two variable
extractors in exchange for, on average, a 3X runtime improvement. For
best area-runtime trade-off, We recommend running FBDD with default
options of -maxextsize=2 and -twefast. Our experimental
results show that the area penalty for using default options is
negligible. The extra options were left in to demonstrate this
finding.
FBDD takes a logic network description in Berkeley Logic Interchange Format (BLIF). BLIF is used widely as an academic standard.
FBDD supports the subset of BLIF that can specify a technology independent combinational or sequential logic network. All standard benchmarks are specified within this subset.
The supported commands include:
The unsupported commands include:
FBDD typically supports BLIF commands written out by SIS. If your circuit contains unsupported BLIF commands, you may be able to rewrite the circuit to work with FBDD by simply reading and then writing the circuit using SIS. Do this by typing:
>sis -sxc "read_blif ckt.blif; write_blif ckt.blif;"
FBDD outputs an optimized logic network either in BLIF format or a restricted form of verilog file. The latter can be used to interface with commercial CAD tools.
The MCNC and ITC benchmarks are included in this distribution. Also included are scripts to automate optimization with FBDD, apply FPGA and standard cell technology mapping, and tabulate the results in a report file. To run the benchmark scripts, type
>make benchmark
Both the fbdd and rasp_syn executables must be pointed to by the PATH environment variable.
Please send bug reports and comments to jzhu@eecg.toronto.edu.
The primary contributor of FBDD release 1.0 goes to Dennis Wu, who implemented the core algorithms and completed a master thesis [10] on the subject. Other contributors include Jianwen Zhu.