Directed Acyclic Graph-Based Datapath Synthesis Using Graph Isomorphism and Gate Reconfiguration

Abstract

Datapath synthesis is a crucial step in synthesis flow and aims at globally minimizing an area by identifying shareable logic structures. This paper introduces a novel Directed Acyclic Graph (DAG)-based datapath synthesis method based on graph isomorphism and gate reconfiguration. Unlike algorithms that identify common specification logic, our approach simplifies the problem by focusing on searching for common topology. Leveraging the concept of gate reconfiguration, our algorithm extends the applicability of DAG-based datapath synthesis by transforming a topology-equivalent network into a specification-equivalent network. Experimental results demonstrate up to 23.6% improvement when optimizing the adder–subtractor circuit, a scenario not addressed by existing DAG-based datapath synthesis algorithms.

Keywords

• datapath synthesis
• logic synthesis
• reconfigurable logic gates
• graph isomorphism
• area optimization