DDBDD: delay-driven BDD synthesis for FPGAs

Lei Cheng, Deming Chen, Martin D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

15 Citations (Scopus)


In this paper, we target FPGA performance optimization using a novel BDD (binary decision graph)-based synthesis approach. Most of previous works have focused on BDD size reduction during logic synthesis. In this work, we concentrate on delay reduction and conclude that there is a large optimization margin through BDD synthesis for FPGA performance optimization. Our contributions are threefold: (1) we propose a gain-based clustering and partial collapsing algorithm to prepare the initial design for BDD synthesis for better delay; (2) we use a technique named linear expansion for BDD decomposition, which in turn enables a dynamic programming algorithm to efficiently search through the optimization space for the BDD of each node in the clustered circuit; (3) we consider special decomposition scenarios coupled with linear expansion for further improvement on quality of results. Experimental results show that we can achieve a 95% gain in terms of network depths, and a 20% gain in terms of routed delay, with a 22% area overhead on average compared to a previous state-of-art BDD-based FPGA synthesis tool, BDS-pga.

Original languageEnglish
Title of host publication44th ACM/IEEE Design Automation Conference - Proceedings 2007
PublisherAssociation for Computing Machinery (ACM)
Number of pages6
ISBN (Print)9781595936271, 1595936270
Publication statusPublished - 23 Jan 2007
Event44th ACM/IEEE Design Automation Conference, DAC 2007 - San Diego, United States
Duration: 4 Jun 20078 Jun 2007
https://www.dac.com/About/Conference-Archive/44th-DAC-2007 (Conference website )
https://www.dac.com/portals/0/documents/archive/2007/44thfinal.pdf (Conference programme )
https://dl.acm.org/doi/proceedings/10.1145/1278480 (Conference proceedings)

Publication series

NameACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)0738-100X


Conference44th ACM/IEEE Design Automation Conference, DAC 2007
Country/TerritoryUnited States
CitySan Diego
Internet address

Scopus Subject Areas

  • Hardware and Architecture
  • Control and Systems Engineering

User-Defined Keywords

  • FPGA technology mapping
  • binary decision diagrams
  • linear expansion


Dive into the research topics of 'DDBDD: delay-driven BDD synthesis for FPGAs'. Together they form a unique fingerprint.

Cite this