全局布局器矩形框约束问题非线性共轭梯度算法的改进

发布时间：2018-06-01 06:25

本文选题：全局布局器 + 非线性共轭梯度　；参考：《上海交通大学》2015年硕士论文

【摘要】：全局布局器其实是一个矩形框约束问题。广泛使用的优化算法是无约束的共轭梯度算法。当我们使用无约束的共轭梯度算法求解最优解的过程中必然会有器件被放置到了可布局芯片面积之外。在实际工程应用时,就必须考虑什么时候对这些放置到可布局面积之外的非法放置器件做非单调梯度投影映射比较合适。我们通过案例数据收集并且通过Matlab图表分析发现了:1)这些非法放置器件概率趋势的特征2)根据这些趋势特征,在每一个布局分区结束并且一个新的布局分区开始之前,做一次非单调梯度投影的话是最实际也是最高效的。最后改进了现有的无约束非线性共轭梯度算法,并应用了一些数值计算的技巧,通过CG_DESCENT在一些Mesh设计上验证确实得到了更好的最终性能指标。当前无约束非线性共轭梯度算法被改善后具有了更快的收敛速度,并且这一加速的取得不会导致在函数或梯度评价的数量上的显著增加。改善当前无约束的非线性共轭梯度求解算法是非常有价值的,便于帮助客户缩短产品进入市场的时间周期和减少最后的总成本比如最后总的布局布线的导线长度。
[Abstract]:The global layout is actually a rectangular box constraint problem. The widely used optimization algorithm is the unconstrained conjugate gradient algorithm. When we use the unconstrained conjugate gradient algorithm to solve the optimal solution, it is inevitable that some devices will be placed outside the layout chip area. In practical engineering applications, it is necessary to consider when it is more appropriate to do non-monotone gradient projection mapping for these illegal placement devices placed beyond the lay-out area. We collected the case data and analyzed the Matlab chart to find the characteristics of the probability trend of these illegal placement devices. 2) based on these trend features, before each layout partition ends and a new layout partition begins, A non-monotone gradient projection is the most practical and efficient. Finally, the existing unconstrained nonlinear conjugate gradient algorithm is improved, and some numerical calculation techniques are applied. The results of CG_DESCENT are proved to be better in some Mesh designs. The current unconstrained nonlinear conjugate gradient algorithm has a faster convergence rate, and this acceleration will not result in a significant increase in the number of functions or gradient evaluations. It is very valuable to improve the current unconstrained nonlinear conjugate gradient algorithm, which can help the customer shorten the time period of the product entering the market and reduce the final total cost such as the length of the wire of the final total layout and wiring.
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TN47

【相似文献】