Optimization of linear placements for wirelength minimization with free sites
Optimization of linear placements for wirelength minimization with free sites
复制标题
利用空闲位点优化线性布局以实现线长最小化
DOI：
10.1109/aspdac.1999.760005
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
A. Zelikovsky
中科院分区：
文献类型：
--
作者：
A. Kahng;P. Tucker;A. Zelikovsky
我们研究了一类线性布局问题，在存在空白（额外的站点）的情况下，对给定的细胞行进行详细的布局优化。在这个单行放置问题中，单元格的顺序在行内是固定的；其他行中的所有单元格也是固定的。我们给出了单行问题的第一个解决方案：(i)具有时间复杂度O（m/sup 2/）的动态规划技术，其中m是给定行中与单元相关的网络数量，以及（ii）利用无线长度目标的凸性的O（m log m）技术。我们还提出了一种迭代启发式方法来改善一行内的单元排序；在应用(i)或（ii）之前，可以选择性地运行它。实验结果表明，当我们的方法应用于一个领先的行业放置工具的最终输出时，工业测试用例的平均带宽提高了6.5%。
We study a type of linear placement problem arising in detailed placement optimization of a given cell row in the presence of white-space (extra sites). In this single-row placement problem, the cell order is fixed within the row; all cells in other rows are also fixed. We give the first solutions to the single-row problem: (i) a dynamic programming technique with time complexity O(m/sup 2/) where m is the number of nets incident to cells in the given row, and (ii) an O(m log m) technique that exploits the convexity of the wirelength objective. We also propose an iterative heuristic for improving cell ordering within a row; this can be run optionally before applying either (i) or (ii). Experimental results show an average of 6.5% wirelength improvement on industry test cases when our methods are applied to the final output of a leading industry placement tool.