Analytical engines are unnecessary in top-down partitioning-based placement

The top-down "quadratic placement" methodology is rooted in such works as [ 36, 9, 32] and is reputedly the basis of commercial and in-house VLSI place ment tools. This methodology iterates between two basic steps: solving spar se systems of linear equations to achieve a continuous placement solution, and "legalization" of the placement by transportation or partitioning. Our work, which extends [5], studies implementation choices and underlying moti vations for the quadratic placement methodology, We first recall some obser vations from [5]. e.g,, that (i) Krylov subspace engines for solving sparse linear systems are more effective than traditional successive over-relaxat ion (SOR) engines [33] and (ii) that correlation convergence criteria can m aintain solution quality while using substantially fewer solver iterations. The focus of our investigation is the coupling of numerical solvers to ite rative partitioners that is a hallmark of the quadratic placement methodolo gy. We provide evidence that this coupling may have historically been motiv ated by the pre-1990's weakness of min-cut partitioners, i.e., numerical en gines were needed to provide helpful hints to weak min-cut partitioners. In particular, we show that a modern multilevel FM implementation [2] derives no benefit from such coupling. We also show that most insights obtained fr om study of individual min-cut partitioning instances (within the top-down placement) also hold within the overall context of a complete top-down plac er implementation.