On The Engineering of a Stable Force-Directed Placer

Electrical & Computer Engineering;VLSI;CAD;placement;partitioning;quadratic;optimization;force;forces;BoxPlace;circuit;clustering;placer;FDP

Vorwerk, Kristofer

University of Waterloo

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

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/863/1/kpvorwer2004.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

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.