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 placement tools. Thismethodology iterates between two basic steps: solving sparse systems of linear equationsto achieve a continuous placement solution, and “legalization” of the placement bytransportation or partitioning. Our work, which extends [5], studies implementationchoices and underlying motivations for the quadratic placement methodology. We firstrecall some observations from [5], e.g., that (i) Krylov subspace engines for solvingsparse linear systems are more effective than traditional successive over-relaxation(SOR) engines [33] and (ii) that correlation convergence criteria can maintain solutionquality while using substantially fewer solver iterations. The focus of our investigation isthe coupling of numerical solvers to iterative partitioners that is a hallmark of thequadratic placement methodology. We provide evidence that this coupling may havehistorically been motivated by the pre-1990’s weakness of min-cut partitioners, i.e.,numerical engines were needed to provide helpful hints to weak min-cut partitioners. Inparticular, we show that a modern multilevel FM implementation [2] derives no benefitfrom such coupling. We also show that most insights obtained from study of individualmin-cut partitioning instances (within the top-down placement) also hold within theoverall context of a complete top-down placer implementation