边界约束下的增量式布图规划算法

Incremental floorplanning algorithm with boundary constraints

快速地在局部范围内调整布图已经成为一种设计需要。该文提出了一种二阶段法来实现边界约束下的增量式布图规划算法。根据已有布图规划建立松弛推移图,直观描述各模块之间"空白区"和松弛量的情况;同时建立模块交换图,记录所有具有形状相似特征的模块集合,基于这2个图进行增量式布图规划。第1阶段,基于推移图和交换图调整布图规划,使其满足边界约束。第2阶段,再次利用交换图进行互连性能优化。实验结果表明该算法在较短的时间里不仅对原有布图规划进行了有效调整满足了给定的所有的几何约束,而且还保证了芯片的面积和线长效果。

Quick incremental local floorplan modifications are becoming necessary with new developments in technology. This paper introduces a two-stage strategy to solve the incremental floorplanning problem with boundary constraints. The algorithm first builds the slack push graph and module exchange graph according to the initial floorplan. The slack push graph describes the dead spaces between any blocks and the slack push distance for each module. The module exchange graph identifies those modules having the same size characteristics. The algorithm uses these two graphs to satisfy the boundary constraints and then optimizes the design using the module exchange graph. The algorithm satisfies all boundary constraints while maintaining total area and wire length.