A Fast Minimum Cost Flow Algorithm for Regenerating Optimal Layout of Functional Cells


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.12   pp.2589-2599
Publication Date: 1997/12/25
Online ISSN: 
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)>>
Buy this Article

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.