Theory and Algorithm for SPFD-Based Global Rewiring
Jason Cong · 2001
In this paper we present the theory and the algorithm for SPFDbased global rewiring (SPFD-GR), which allows us to replace a target wire globally in the circuit (by some wire possibly far away from the target). It successfully overcomes the limitation of the existing SPFD-based local rewiring (SPFD-LR) that can only replace a wire with another wire having the same sink node. We apply SPFD-GR to the post-mapping area reduction for LUTbased FPGAs under circuit depth restriction. Experimental results show that the rewiring ability of SPFD-GR, in terms of the number of target wires found to have alternative wires, is 1.45 and 3 times that of SPFD-LR and an ATPG algorithm (with a preliminary experimental flow), respectively, and the run time is quite acceptable. Using partitioning, the SPFD-GR algorithm scales well to large circuits with good synthesis quality. 1