【作者】 黎芳芳；

【导师】 施国勇； 李浩斌；

【作者基本信息】 上海交通大学 ， 集成电路工程， 2015， 硕士

【摘要】 全局布局器其实是一个矩形框约束问题。广泛使用的优化算法是无约束的共轭梯度算法。当我们使用无约束的共轭梯度算法求解最优解的过程中必然会有器件被放置到了可布局芯片面积之外。在实际工程应用时,就必须考虑什么时候对这些放置到可布局面积之外的非法放置器件做非单调梯度投影映射比较合适。我们通过案例数据收集并且通过Matlab图表分析发现了:1)这些非法放置器件概率趋势的特征2)根据这些趋势特征,在每一个布局分区结束并且一个新的布局分区开始之前,做一次非单调梯度投影的话是最实际也是最高效的。最后改进了现有的无约束非线性共轭梯度算法,并应用了一些数值计算的技巧,通过CG_DESCENT在一些Mesh设计上验证确实得到了更好的最终性能指标。当前无约束非线性共轭梯度算法被改善后具有了更快的收敛速度,并且这一加速的取得不会导致在函数或梯度评价的数量上的显著增加。改善当前无约束的非线性共轭梯度求解算法是非常有价值的,便于帮助客户缩短产品进入市场的时间周期和减少最后的总成本比如最后总的布局布线的导线长度。更多还原

【Abstract】 Global placement in fact is one box constraint problem while the widely used optimization method is the unconstraint nonlinear conjugate gradient(CG) algorithm. When we apply the unstrained CG to solve the bonding box constrained placement problem, there must be some cells are put outside of the chip. We call these cells illegal cells. Then when to project the illegal cells in is the key.Through the Matlab analysis using the collected outliner percentage statistics on many designs, we found 1) the same trend and character for the outliners 2) figured out one practical and efficient method is to project in the outliners at the end of each partition level. After improving current unconstrained nonlinear CG algorithm and applying some mathematic skills, the final quality metrics are proven to be better on average through the verification on the Mesh designs using CG_DESCENT.We improved current unconstraint conjugate gradient(CG) algorithm with faster convergence rate, and this speedup is achieved without significant increasing in the number of function or gradient evaluations. It is worthy to improve current unconstrained CG solver algorithm so that we can help customers to shorten the time-to-market period and reduce the final total cost like wire length at the same time.更多还原