Module Placement Based on Resistive Network Optimization

A new constructive placement and partitioning method based on resistive network optimization is proposed. The objective function used is the sum of the squared wire length. The method has the feature which includes fixed modules in the formulation. The overall algorithm comprises the following subprograms: optimization, scaling, relaxation, partitioning and assignment. The method is efficient because it takes advantage of net-list sparsity and has a complexity of O[n1.4 log n]. Another added special feature is that irregular-size modules within cell rows are allowed. Thus the method is particularly useful in standard-cell and gate-array designs. Experimental results on four 4K gate-array placements are illustrated, and they are far superior than manual placements.