For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Fast Minimum Cost Flow Algorithm for Regenerating Optimal Layout of Functional Cells
Itthichai ARUNGSRISANGCHAI Yuji SHIGEHIRO Isao SHIRAKAWA Hiromitsu TAKAHASHI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1997/12/25
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: VLSI Design Technology and CAD
VLSI, fabrication technology, mask pattern, LP, flow,
Full Text: PDF(870.3KB)>>
A new flow algorithm is described on the basis of the primal-dual method, which is to be adopted dedicatedly for the regeneration of optimal layouts for functional cells of the standard-cell level. In advance of discussing this main theme, the present paper first outlines a practical scheme of reusing those layouts which have been once generated for functional cells in an old fabrication technology, and then formulates an optimization problem for regenerating optimal layouts of functional cells under the constraints incurred by the renewal of design rules. An efficient algorithm proposed here aims at solving this optimization problem with the use of solution concepts for the minimum cost flow problem. A part of experimental results is also shown, which indicates that the proposed altorithm is the fastest for this optimization problem.