Analytical Engines are Unnecessary in Top-down Partitioning-based Placement
Autor: | Charles J. Alpert, Dennis J.-H. Huang, Tony F. Chan, Igor L. Markov, Andrew Caldwell, M. S. Moroz, Andrew B. Kahng |
---|---|
Jazyk: | angličtina |
Rok vydání: | 1999 |
Předmět: |
Very-large-scale integration
Mathematical optimization Theoretical computer science multi-level min-cut partitioning Computer science Linear system Context (language use) Krylov subspace Solver System of linear equations Computer Graphics and Computer-Aided Design lcsh:QA75.5-76.95 Quadratic placement Quadratic equation Hardware and Architecture Convergence (routing) lcsh:Electronic computers. Computer science Electrical and Electronic Engineering hierarchical top-down placement |
Zdroj: | VLSI Design, Vol 10, Iss 1, Pp 99-116 (1999) |
ISSN: | 1563-5171 |
Popis: | 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. This methodology iterates between two basic steps: solving sparse 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 motivations for the quadratic placement methodology. We first recall some observations from [5], e.g., that (i) Krylov subspace engines for solving sparse linear systems are more effective than traditional successive over-relaxation (SOR) engines [33] and (ii) that correlation convergence criteria can maintain solution quality while using substantially fewer solver iterations. The focus of our investigation is the coupling of numerical solvers to iterative partitioners that is a hallmark of the quadratic placement methodology. We provide evidence that this coupling may have historically 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. In particular, we show that a modern multilevel FM implementation [2] derives no benefit from such coupling. We also show that most insights obtained from study of individual min-cut partitioning instances (within the top-down placement) also hold within the overall context of a complete top-down placer implementation. |
Databáze: | OpenAIRE |
Externí odkaz: |