Biconditional Binary Decision Diagrams Software Package
Current version: 1.0 – First Release!
New version 1.1 – AIGER reader!
Brief Introduction to BBDDs:
Biconditional Binary Decision Diagrams (BBDDs) are a novel canonical BDD extension [1-3]. While original BDDs are based on the single-variable Shannon’s expansion, BBDDs employ a two-variable biconditional expansion, making the branching condition at each decision node dependent on two variables per time. Such feature improves the logic expressive power of the binary decision diagram. The following figure depicts the BBDD representation for 4 general Boolean functions.
BBDDs represent also the natural and native design abstraction for emerging technologies where the circuit primitive is a comparator, rather than a switch.
Package Description:
The BBDD package is a software written in C language (~8k lines) that reads a combinational Verilog file (flattened into Boolean primitives) and builds a BBDD representing it. The main features of the BBDD package are (i) strong canonical form pre-conditioning of stored BBDD nodes, (ii) recursive formulation of Boolean operations in terms of biconditional expansions, (iii) performance-oriented memory management and (iv) dedicated BBDD re-ordering techniques. The rationale driving the software implementation is explained in [1]. Technicalities appear in the package documentation and sources comments.
Typical Execution Flow:
A typical execution flow for the BBDD package is the following.
Sample input Verilog named xor2.v:
module top (
pa, pb,
pq );
input pa, pb;
output pq;
wire npa, npb, f1, f2;
invx g00(.a(pa), .O(npa));
invx g01(.a(pb), .O(npb));
andx g02(.a(pa), .b(npb), .O(f1));
andx g03(.a(npa), .b(pb), .O(f2));
orx g04(.a(f1), .b(f2), .O(pq));
endmodule
Compile and execution commands:
[lsi1mac11:~/Desktop/BBDDlatest] amaru% make
gcc -Wall -O3 -o BBDD ./source/*.c -I.
[lsi1mac11:~/Desktop/BBDDlatest] amaru% ./BBDD
EPFL, Integrated Systems Laboratory, CAD Group
Biconditional Binary Decision Diagram, BBDD v.1.0
bbdd 0> read xor2.v
Verilog stats: inputs: 2 – outputs: 1 – internal wires: 5.
Building BBDD:
<wwwwwwwwwwwwwwwwwwwwwwwwwwwwww> Size 4 Gate 6/6
BBDD built successfully in 0.000595 seconds
Final polishing:
Final polishing performed in 0.000012 seconds
BBDD contains 2 nodes
bbdd 1> write
Output verilog (and log) written successfully
bbdd 2> quit
[lsi1mac11:~/Desktop/BBDDlatest] amaru%
Output of the package:
//Written by the BBDD package Tue Feb 18 22:57:58 2014
module top (
pa, pb,
pq);
input pa, pb;
output pq;
wire one, node0;
assign node0 = (pb ^ pa) ? ~one : one;
assign one = 1;
assign pq = ~node0;
endmodule
Download link:
Contact:
Please contact me for any questions you might have about the BBDD package, at luca dot amaru at epfl dot ch. I am also happy to provide help in using/customizing the options for your intended application of the BBDD package.
Related publications:
[1] L. Amaru, P.-E. Gaillardon, G. De Micheli ,”An Efficient Manipulation Package for Biconditional Binary Decision Diagrams”, Design, Automation & Test in Europe Conference (DATE 2014), Dresden, Germany, 2014.
[2] L. Amaru, P.-E. Gaillardon, G. De Micheli, “Biconditional BDD: A Novel BDD Enabling Efficient Direct Mapping of DG Controllable Polarity FETs”, Functionality-Enhanced Devices Workshop (FED 2013), Lausanne, Switzerland, 2013.
[3] L. Amaru, P.-E. Gaillardon, G. De Micheli, “Biconditional BDD: A Novel Canonical BDD for Logic Synthesis targeting XOR-rich Functions”, Design, Automation & Test in Europe Conference (DATE 2013), Grenoble, France, 2013.