Fast and Robust Quadratic Placement Combined with an Exact Linear Net Model
Fast and Robust Quadratic Placement Combined with an Exact Linear Net Model
复制标题
DOI：
10.1145/1233501.1233537
复制
发表时间：
2006-11
期刊：
影响因子：
--
通讯作者：
Peter Spindler;F. Johannes
中科院分区：
文献类型：
--
作者：
Peter Spindler;F. Johannes
本文提出了一种鲁棒的二次布局方法，它提供了高质量的布局和良好的计算效率。在力导向二次布局中，将模块在芯片上分布的附加力分解为两个力：保持力和移动力。这两种力都是在没有任何经验的情况下确定的。基于这种新的系统力的实现，我们表明，我们的迭代布局算法收敛到一个无干扰的位置。此外，我们的下单服务器还能有效地支持工程变更单（ECO）。为了处理CPU时间和放置质量之间的重要权衡，提出了确定性质量控制。此外，提出了一种新的线性网络模型，它精确地模拟了二次布局的二次成本函数中的半周长线长（HPWL）。HPWL通常是网络长度的线性度量，并且表示对路由线长的有效且常见的估计。与经典的团网模型相比，我们的线性网模型减少了75%的内存使用，CPU时间的23%和8%的netlength，这是衡量的HPWL的所有网络。使用ISPD-2005基准套件进行比较，我们的砂矿与新的线性网络模型相结合，净长度仅高出5.9%，但比APlace快16倍，APlace在该基准中提供了最佳的净长度。与Capo相比，我们的砂矿网长低9.2%，速度快5.4倍。在最近的ISPD-2006布局比赛中，质量主要取决于网络长度和CPU时间，我们的布局器与新的网络模型一起产生了优异的成绩
This paper presents a robust quadratic placement approach, which offers both high-quality placements and excellent computational efficiency. The additional force which distributes the modules on the chip in force-directed quadratic placement is separated into two forces: hold force and move force. Both of these forces are determined without any heuristics. Based on this novel systematic force implementation, we show that our iterative placement algorithm converges to an overlap-free placement. In addition, engineering change order (ECO) is efficiently supported by our placer. To handle the important trade-off between CPU time and placement quality, a deterministic quality control is presented. In addition, a new linear net model is proposed, which accurately models the half-perimeter wirelength (HPWL) in the quadratic cost function of quadratic placement. HPWL in general is a linear metric for netlength and represents an efficient and common estimation for routed wirelength. Compared with the classical clique net model, our linear net model reduces memory usage by 75%, CPU time by 23% and netlength by 8%, which is measured by the HPWL of all nets. Using the ISPD-2005 benchmark suite for comparison, our placer combined with the new linear net model has just 5.9% higher netlength but is 16times faster than APlace, which offers the best netlength in this benchmark. Compared to Capo, our placer has 9.2% lower netlength and is 5.4times faster. In the recent ISPD-2006 placement contest, in which quality is mainly determined by netlength and CPU time, our placer together with the new net model produced excellent results