Objective

FBDD is a logic synthesis system being developed at the 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

The detailed results at the time of release (June, 2005) comparing FBDD against publicly accessible academic logic synthesis packages on MCNC and ITC are provided. The detailed results comparing FBDD against state-of-the-art commecial FPGA logic synthesis tools, including Altera Quartus, and Xilinx ISE, are provided for MCNC and ITC as well. 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. All comparative results are repeatable by the automated scripts provided in the FBDD distribution.

To summarize, FBDD reports significant area improvement over previous BDD-based logic synthesis packages, and significant speed up over all packages. In particular, it runs one order of magnitude faster than commercial tools.

		Academic Tools				Commercial Tools
Metric	Benchmark	FBDD	SIS	BDS	BDS-PGA	Altera Quartus	Xilinx ISE
		1.0	1.2	1.2	2.0	5.0spl	7.10li
Area	MCNC	100%	97.8%	113.1 %	116.5%	101.7%	119.4%
	ITC	100%	104.3%			97.6%	102.8%
Runtime	MCNC	1.0X	59.8X	1.80X	3.80X	33X	19X
	ITC	1.0X	31.7X			4.9X	50X

Software

The following software releases are tested on the Solaris, Linux and Cygwin platforms and available for download.

[1.1]      

Dennis Wu and Jianwen Zhu, ``FBDD logic synthesis system user manual (version 1.1),'' Department of Electrical and Computer Engineering, University of Toronto, Toronto, Canada, Aug. 2005.

[1.0]      

Dennis Wu and Jianwen Zhu, ``FBDD logic synthesis system user manual (version 1.0),'' Department of Electrical and Computer Engineering, University of Toronto, Toronto, Canada, June 2005.

Publications

[1]      

Andrew Ling, Jianwen Zhu, and Stephen Brown, ``Scalable synthesis and clustering techniques using decision diagrams,'' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, submitted 2006.

[2]      

Andrew Ling, Jianwen Zhu, and Stephen Brown, ``BddCut: Towards scalable symbolic cut enumeration,'' in Proceeding of Asia and South Pacific Design Automation Conference (ASPDAC), Yokohama, Japan, Jan. 2007.

[3]      

Dennis Wu and Jianwen Zhu, ``FBDD: A folded logic synthesis system,'' Tech. Rep. TR-07-01-05, Department of Electrical and Computer Engineering, University of Toronto, July 2005.

[4]      

Dennis Wu and Jianwen Zhu, ``FBDD: A folded logic synthesis system,'' in International Conference on ASIC (ASICON), Shanghai, China, Oct. 2005.

[5]      

Dennis Wu and Jianwen Zhu, ``BDD-based two-variable sharing extraction,'' in Proceeding of Asia and South Pacific Design Automation Conference (ASPDAC), Shanghai, China, January 2005.

[6]      

Dennis Wu and Jianwen Zhu, ``Folded logic decomposition,'' in International Workshop on Logic and Synthesis (IWLS), Laguna Beach, California, June 2003.

[7]      

Dennis Wu, ``Towards scalable BDD-based logic synthesis,'' M.S. thesis, Department of Electrical and Computer Engineering, University of Toronto, Toronto, Jan. 2005.

Contributors

Toronto Synthesis Group

Huimin Bian	Andrew Ling	Dennis Wu	Jianwen Zhu

License

GNU General Public License (GPL), Version 2

Copyright

/*
 * Copyright (c) 2005 The University of Toronto and the Synthesis Group.
 * All rights reserved.
 * 
 * This file is part of the FBDD.  The FBDD is free software, also known
 * as "open source;" you can redistribute it and/or modify it under the terms
 * of the GNU General Public License (GPL), version 2, as published by the Free
 * Software Foundation (FSF).  To explore alternate licensing terms, contact
 * the University of Toronto at jzhu@eecg.toronto.edu or +1-416-946-5971.
 * 
 * The FBDD is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE.  See the GPL for more details.  You should have
 * received a copy of the GPL along with the FBDD; see the file COPYING.  If
 * not, write to the FSF, 59 Temple Place #330, Boston, MA 02111-1307, USA.
 */

Web

http://www.eecg.toronto.edu/~jzhu/fbdd.html