On The Engineering of a Stable Force-Directed Placer

[摘要] Analytic and force-directed placement methods that simultaneously minimize wire length and spread cells are receiving renewed attention from both academia and industry.However, these methods are by no means trivial to implement---to date, published works have failed to provide sufficient engineering details to replicate results.This dissertation addresses the implementation of a generic force-directed placer entitled FDP.Specifically, this thesis provides (1) a description of efficient force computation for spreading cells, (2) an illustration of numerical instability in this method and a means to avoid the instability, (3) metrics for measuring cell distribution throughout the placement area, and (4) a complementary technique that aids in minimizing wire length.FDP is compared to Kraftwerk and other leading academic tools including Capo, Dragon, and mPG for both standard cell and mixed-size circuits.Wire lengths produced by FDP are found to be, on average, up to 9% and 3% better than Kraftwerk and Capo, respectively.All told, this thesis confirms the validity and applicability of the approach, and provides clarifying details of the intricacies surrounding the implementation of a force-directed global placer.

[发布机构] University of Waterloo

[效力级别] VLSI

[关键词] Electrical & Computer Engineering;VLSI;CAD;placement;partitioning;quadratic;optimization;force;forces;BoxPlace;circuit;clustering;placer;FDP