摘要
在EDA布局设计问题中,有一类的布局场景特点为:初始模块为矩形,但是大小不一,模块的布局即使压缩后也存在空位,要求通过变形以填充空位并取得面积更优的布局.已有技术一般是将模块间位置关系描述成某种拓扑关系,再建立约束条件并利用启发式算法求解.但是这类算法一般求解时间较长,并且容易陷入局部最优.本文通过一个完整的算法流程实现了布局快速优化,包括利用简单扫描线算法进行X、Y双向压缩初始布局、建立Y向树和X向树、建立有约束方程以及采用拉格朗日松弛法求解等环节.实验表明,本文算法求解速度快,填充后布局面积利用率较高,较好地满足了此类电路设计的需要.
维普
万方数据