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.   FBDD 1.0 SIS 1.2 BDS 1.2 BDS-PGA 2.0 Quartus LUT 100% 97.77% 113.13 % 116.45% 102.01% runtime 1.0X 57.71X 1.76X 3.68X 10.06X

Documentation	User manual
Download	The following releases have been tested on the Solaris, Linux and Cygwin platforms. Version Release File   Source fbdd-1.0.tar.gz FBDD 1.0 Solaris fbdd-1.0-sparc-sun-solaris2.8.tar.gz   Linux fbdd-1.0-i686-pc-linux-gnu.tar.gz   Cygwin fbdd-1.0-i686-pc-cygwin.tar.gz
Publications	The following publications are generated to date. D. Wu and J. Zhu. BDD-based Two-Variable Sharing Extraction. Asia-South Pacific Design Automation Conference (ASPDAC'05). Shanghai, China, January, 2005. D. Wu and J. Zhu. Folded Logic Decomposition. International Workshop on Logic and Synthesis (IWLS'03), Laguna Beach, CA, June, 2003. D. Wu. Towards a Scalable BDD-based Logic Synthesis. Master of Science Thesis, Electrical and Computer Engineering, University of Toronto, January, 2005.
Contributors	Toronto Synthesis Group 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. */
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.