Graph-based Simplex algorithm for minimizing the layout size and the delay on timing critical paths

Lih Yang Wang, Yen Tai Lai, Bin Da Liu, Ting Chung Chang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

In this paper, the layout compaction problem with performance consideration is studied. In our approach, the delay upper-bound of the timing critical paths is reduced first, then the layout size is minimized without increasing that delay bound. Either step is formulated as a linear programming problem, we propose a graph-based Simplex algorithm, which replaces most of the matrix operations with graph operations, to solve the problem. Both theoretical analysis and experimental results show that this algorithm is quite efficient.

Original languageEnglish
Title of host publicationProc 1993 IEEE ACM Int Conf Comput Aided Des
Editors Anon
PublisherPubl by IEEE
Pages703-708
Number of pages6
ISBN (Print)0818644923
Publication statusPublished - 1993 Dec 1
EventProceedings of the 1993 IEEE/ACM International Conference on Computer-Aided Design - Santa Clara, CA, USA
Duration: 1993 Nov 71993 Nov 11

Publication series

NameProc 1993 IEEE ACM Int Conf Comput Aided Des

Other

OtherProceedings of the 1993 IEEE/ACM International Conference on Computer-Aided Design
CitySanta Clara, CA, USA
Period93-11-0793-11-11

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Graph-based Simplex algorithm for minimizing the layout size and the delay on timing critical paths'. Together they form a unique fingerprint.

Cite this