Enhanced edge-based device migration under topology constraints

Ying Zhih Chuang*, De Shiun Fu, Yih-Lang Li

*Corresponding author for this work

Research output: Contribution to journalArticle


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.

Original languageEnglish
Pages (from-to)493-502
Number of pages10
JournalInternational Journal of Electrical Engineering
Issue number6
StatePublished - 1 Dec 2009


  • Constraint graph
  • Layout compaction
  • Layout migration
  • Layout topology

Fingerprint Dive into the research topics of 'Enhanced edge-based device migration under topology constraints'. Together they form a unique fingerprint.

  • Cite this