Premium
Module placement for large chips based on sparse linear equations
Author(s) -
Tsay RenSong,
Kuh Ernest S.,
Hsu ChiPing
Publication year - 1988
Publication title -
international journal of circuit theory and applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.364
H-Index - 52
eISSN - 1097-007X
pISSN - 0098-9886
DOI - 10.1002/cta.4490160406
Subject(s) - computer science , relaxation (psychology) , block (permutation group theory) , algorithm , convexity , mathematical optimization , mathematics , psychology , social psychology , geometry , financial economics , economics
There are many algorithms for automatic placement in IC layout design. However, as chips become increasingly larger and more complex, existing algorithms are no longer suitable. One major drawback in existing algorithms is that the sparsity inherent in the placement specification has not been taken into consideration properly. In this paper, we propose an efficient method of module placement for large and highly complex chips by repeatedly solving sparse linear equations. the resistive network analogy of the placement problem and the convexity of the objective function play a major role in our approach. Our method employs the SOR (successive over‐relaxation) method to solve the linear equations and uses a top‐down hierarchy in partitioning the chip. We have also devised an effective BGS (block Gauss‐Seidel) iteration scheme to achieve global optimum results. The method has been implemented and tried with a number of real chips. For a triple‐metal‐layer, 100K sea‐of‐gates with 26,000 instances, it takes 50 min on a VAX 8650 and yields excellent results in terms of total wire length.