Analytical minimization of half-perimeter wirelength

Global placement of hypergraphs is critical in the top-down placement of large timing-driven designs. Placement quality is evaluated in terms of the half-perimeter wirelength (HPWL) of hyperedges in the original circuit hypergraph provided timing constraints are met. Analytical placers are instrumental in handling non-linear timing models, but have two important drawbacks: (a) corresponding optimization algorithms are typically slower than top-down methods driven by multi-level mincut partitioning, and (b) hyperedges must be represented with net models which imply a mismatch of objective functions, with the alternative of computationally expensive linear programming (LP). By comparing to optimal solutions produced by linear programming, we show that net models lead to solution quality loss. To address this problem, we present the first analytical algorithm that does not require net models and permits a direct inclusion of non-linear delay terms; this allows to avoid expensive linearization of delay terms. Our numerical engine utilizes well-known quadratically convergent Newton-type methods for speed; it produces solutions within 12% of the LP optimum. Empirical results are for industrial placement instances.