An Efficient Hierarchical Algorithm for Module Placement for Large Chips

In this paper, we mainly present a fast, stable and efficient module placement algorithm which is based on PROUD algorithm and its improved modified version. The PROUD algorithm uses a hierarchical decomposition technique and the solution of sparse linear systems based on a resistive network analogy. It has been shown that the PROUD algorithm can achieve a comparable design of the placement problems for very large circuits with the best placement algorithm based on simulated annealing, but with several order of magnitude faster. The modified PROUD, namely MPROUD algorithm by perturbing the coefficient matrices performs much faster that the original PROUD algorithm. Due to the instability and unguaranteed convergence of MPROUD algorithm, we propose a new convergent and numerically stable PROUD, namely Improved PROUD algorithm, denoted as IPROUD with attractive computational costs to solve the module placement problems by making use of the MINRES method based on Lanczos process. Experime..