Global placer中框约束问题非线性共轭梯度算法的改进.pdfVIP

【l】国集成 电路 设 计 China Integrated C ircuit Globalplacer中框约束问题非线性 共轭梯度算法的改进 黎芳芳 (上海交通大学微电子学院，上海，200240) 摘要：Globa1placer其实是一个矩形框约束问题。关于如何改进当前的无约束非线性共轭梯度算法 来应用于矩形框约束问题，本文提出了一个实用的改进方法并且通过一些数学方法解决了程序实现执 行中数据精度和稳定性问题。改善当前无约束的共轭梯度求解算法是非常有价值的，可以帮助客户缩 短产品进入市场的时间周期和减少最后的总成本如最后总的布局布线的导线长度。 关键词：globalplacer；非线性；共轭梯度；映射；大规模集成 电路 1 简介 布局布线中最重要的一步。而且对于布局布线工具 来说，在T程可接受的运行时间之内得到一个较好 随着集成电路的规模越来越大，完全的人工布 的解 比如较好的全局导线长度是非常重要的。当同 局布线已经不太现实。许多的自动布局布线的商业 样大小的芯片面积能容纳越来越多的器件时，开发 工具软件应运而生。对于大规模集成电路来说，由于 设计高效的数字算法无论是在理论上还是实际应用 要摆放器件数 目之多使得布局布线这个问题本身就 中都变得尤为重要。现在广泛应用的globalplacer的 拥有其固有的复杂度以及相应的计算困难度。为了 算法是无约束的共轭梯度算法。但可布局的芯片面 简化问题，现在大部分布局布线工具分成三步来处 积本身就是我们在求解最优解时的一个约束条件。 理 ：globalplacer，Legalization和 Detailedplacement。 由于多数芯片面积是矩形的，简称 globalplacer这个 Globalplacer在保证所有器件平均相互覆盖率不超 约束问题为矩形框约束问题。当我们使用无约束的 过标准许可范围内的情况下对标准库器件进行摆放 共轭梯度算法求得最优解的过程中必然会有器件被 以达到全局的导线长度最优。从globalplacer处得到 放置到了可布局芯片面积之外，我们称这些放置到 全局最优解之后，Legalization被用来解掉所有的相 可布局面积之外的器件为非法放置器件。在实际工 互覆盖。最后，Detailedplacement会查看是否还能在 程应用时，就必须考虑什么时候做非单调梯度投影 局部通过比如重新交换排序一些器件的方法来得到 比较合适。 更优一点的解。一个好的初始解是非常重要的因为 对于矩形框约束 问题 ，一个有效集合算法 后续步骤都是在这个初始解上面再进行进一步的处 (ASA)已经被提出lj【。这个算法主要 由无约束优化 理和优化的。所以Globalplacer通常被认为是 自动 步骤和非单调梯度投影构成。在沿着根据共轭梯度 h ●●^ ，^… … ^ ；… … 一 产生的下降方向，ASA每走一步都通过非单调梯度 近似逼近 ： 投影映射来确保所有器件都被合法的摆放回了可布 生 觇 (1og Ilke log Ijke + 局的芯片面积之内。对于大规模集成电路来说 ，如 且 果在每一步都做非单调梯度投影的话，工具的运行 l0g uke +l0g uke ) (1) 时间将会变长。这也意味着最优解的收敛速