FBDD: Scalable Logic Synthesis |
Logo | |||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Objective | FBDD is a logic synthesis system being developed at University of Toronto. The primary objective of the project is to scale the logic synthesis algorithm runtime by one order of magnitude, while producing competitive synthesis quality. |
||||||||||||||||||
Background | Despite decades of efforts and successes in logic synthesis, algorithm runtime has never been taken as a first class objective. In general, designers and CAD developers are willing to trade longer runtime for area, delay and power. As design complexity soars and million gate designs become common, as deep submicron effects dominate and frequently invoking logic synthesis within a low-level physical design environment, or a high-level architectural exploration environment become mandatory, it becomes necessary to revisit the fundamental logic synthesis infrastructure and algorithms, polynomial at best, such that they can keep up with the growth of circuit complexity, exponential as dictated by Moore's law. | ||||||||||||||||||
Ideas | We rebuilt a proven synthesis flow pioneered by the Binary Decision Diagram (BDD) based Logic Synthesis System (BDS) developed at University of Massachusetts. On top of the baseline synthesis flow, we implemented two new ideas in our first software release, FBDD 1.0, as a first step towards our objective. To scale runtime, we employ a new strategy, called logic folding, such that isomorphic subnetworks are identified and folded into equivalent classes, on which the cost of ALL logic transformations can be amortized. To be competitive in area, we devise a fast sharing extraction algorithm that can be made exact, polynomial and incremental. | ||||||||||||||||||
Results | For Field Programmable Gate Array (FPGA)
technology, for academic benchmarks, FBDD 1.0 is able to produce comparable area result against commercial tools, while running 10X times faster. The detailed results at the time of release (June,
2005), comparing against publicly accessible logic synthesis packages,
are provided for for MCNC, and
ITC
respectively. Comparative
charts for the MCNC benchmark are provided for FPGA
lut count
and
runtime. To summarize, FBDD
1.0 reports slight area gain for all packages except SIS, and
significant speed up for all packages. Note that all packages are run
with their default options. And benchmarks that fail or do not
terminate within four hours in the other packages are discarded for
the statistics.
|
Documentation | User manual | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Download | The following releases have been tested on the Solaris, Linux and Cygwin platforms.
|
|||||||||||||||
Publications | The following publications are generated to date.
|
|||||||||||||||
Contributors | Toronto Synthesis Group | |||||||||||||||
License | GNU General Public License (GPL), Version 2 | |||||||||||||||
Copyright |
|
|||||||||||||||
Logo Side Note | FBDD is an acronym for folded binary decision diagram, the central data structure used in our logic synthesis system. The animated logo, a folding diagram, is taken from Erik Demaine's interesting page on paper folding. |