A Novel General Graph-Based Simplex Algorithm Applied to IC Layout Compaction and Migration

Author

Said, Hazem ; Abbas, Hazem M. ; Shahein, Hussein I.

Author_Institution

Ain Sahms Univ., Cairo

fYear

2007

fDate

16-18 Dec. 2007

Firstpage

241

Lastpage

246

Abstract

In this paper, a novel method for solving the IC layout compaction problem is introduced. The solution supports all kinds of linear constraints and linear optimization functions. Graph-based techniques are employed so that all matrix operations in linear programming are replaced by much faster graph operations. The proposed algorithm outperforms all studied compaction methods by combining the generality of linear programming and the efficiency of graph-based methods. Correct and optimal migrated layouts were produced with significant improvement in performance.

Keywords

graph theory; integrated circuit layout; linear programming; IC layout compaction; IC layout migration; graph-based simplex algorithm; graph-based techniques; linear constraints functions; linear optimization functions; linear programming; Compaction; Constraint optimization; Design automation; Equations; Graph theory; Graphics; Integrated circuit layout; Integrated circuit technology; Linear programming; Testing; Graph Theory; IC layout; Layout Compaction; Linear Programming;

fLanguage

English

Publisher

ieee

Conference_Titel

Design and Test Workshop, 2007. IDT 2007. 2nd International

Conference_Location

Cairo

Print_ISBN

978-1-4244-1824-4

Electronic_ISBN

978-1-4244-1825-1

Type

conf

DOI

10.1109/IDT.2007.4437469

Filename

4437469