Enhancement of Incremental Design for FPGAs Using Circuit Similarity

Xiaoyu Shi1,  Dahua Zeng1,  Yu Hu2,  Guohui Lin1,  Osmar Zaiane1
1Department of Computing Science, University of Alberta, 2Department of Electrical and Computer Engineering, University of Alberta


This paper presents an efficient algorithm to detect the global topological similarity between two circuits. By applying the proposed circuit similarity algorithm in an incremental design flow, \emph{IDUCS} (incremental design using circuit similarity), the design and optimization effort in the previous design iterations is automatically captured and can be used to guide the next design iteration. IDUCS is able to identify the similarity between the original netlist and the modified one with aggressive resynthesis, which might destroy the naming and local structures of the original netlist. This is superior to the existing design preservation approaches such as naming and local topological matching. Furthermore, IDUCS simply inserts a plugin for circuit similarity detection, and therefore preserves the ``push-button'' feature, significantly simplifying the engineering complexity of incremental tasks. As a case study, we perform the proposed IDUCS process to generate the placement for a logically resynthesized netlist based on the placement of the original netlist and the circuit similarity between the original and the modified logic-level netlists. The experimental results show our IDUCS-based placement is 28X faster than versatile place and route (VPR) with comparable wire length and estimated critical delay.