| This thesis presents an overview of a prototype standard-cell placer called Mongrel. Mongrel is a hybrid of several complementary optimization techniques which together have produced extremely promising results. The technical contributions of the thesis are summarized as follows.; (1) We adopt a middle-down methodology. The layout area is dissected into bins by a grid. The global placement problem is then to assign cells to bins obeying capacity constraints. After global placement we enter a detailed placement phase in which intra-row optimization is performed. (2) The main optimization tool during global placement is Relaxation-Based Local Search (RBLS). RBLS utilizes an analytical engine to drive a local search mechanism. One iteration can be roughly summarized as follows: Given a current global placement, a subset of the cells are selected and designated as mobile cells; using an analytical engine, the optimal relaxed placement (i.e., ignoring bin capacities) of the mobile cells is found (i.e., a linear program is solved); the information yielded by the relaxed placement is then used to induce a new legal placement via a legalization procedure. The best legal solution seen during the legalization phase becomes the next configuration and is accepted if it improves over the initial placement. The result is a powerful local search mechanism in which individual moves may result in complex modifications to the placement. For the approach to succeed, the analytical engine must be fast and the legalization procedure must be carefully designed. The former is achieved by adopting efficient network flow techniques. For the latter, we have developed a novel scheme which incorporates a global analysis procedure using the notion of wire-length gain and iteratively resolving constraint violations. (1) Iterative partitioning between neighboring bins is also used as a complementary fine-tuning technique for global placement. (2) In detailed placement, we are allowed to perturb the ordering of cells within each row. In this phase we propose a new technique called optimal interleaving and have also applied dynamic clustering.; Together these techniques form a powerful optimization procedure which has produced extremely promising results: compared with recently published work in placement a wire-length reduction (based on half-perimeter) of roughly 15--17 cases. |
