DDBDD: Delay-driven BDD synthesis for FPGAs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 (US)
Title of host publication2007 44th ACM/IEEE Design Automation Conference, DAC'07
Pages910-915
Number of pages6
DOIs
StatePublished - Aug 2 2007
Event2007 44th ACM/IEEE Design Automation Conference, DAC'07 - San Diego, CA, United States
Duration: Jun 4 2007Jun 8 2007

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X

Other

Other2007 44th ACM/IEEE Design Automation Conference, DAC'07
CountryUnited States
CitySan Diego, CA
Period6/4/076/8/07

Keywords

  • Binary decision diagrams
  • FPGA technology mapping
  • Linear expansion

ASJC Scopus subject areas

  • Hardware and Architecture
  • Control and Systems Engineering

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

  • Cite this

    Cheng, L., Chen, D., & Wong, M. D. F. (2007). DDBDD: Delay-driven BDD synthesis for FPGAs. In 2007 44th ACM/IEEE Design Automation Conference, DAC'07 (pp. 910-915). [4261313] (Proceedings - Design Automation Conference). https://doi.org/10.1109/DAC.2007.375294