Enhanced edge-based device migration under topology constraints

Conventional approaches for generating constraint graphs only consider space utilization and, therefore, generate a compact cell layout with most changes in the shape and topology of interconnections. Moreover, conventional constraint-graph-based migration algorithms cannot handle 45° wires. This work presents a novel enhanced edge-based constraint-graph compaction algorithm that prevents distortion of the original shape and topology of digital devices. Based on the edge-based algorithm, a pseudo 45° edge model is integrated into a novel device migration framework. This model strengthens the proposed device migration framework to handle 45° wires. Furthermore, a novel and effective wire-extraction algorithm is utilized to identify the interconnection between devices. Experimental results demonstrate that the proposed device migration algorithm can rapidly yield a compact layout that conforms to new design rules without layout distortion.