日志

装箱算法在版图设计上的应用

已有 69 次阅读| 2024-10-29 20:27 |个人分类:日记|系统分类:芯片设计| Python, 版图

装箱问题是一个经典的组合优化问题。简单地说,装箱问题就是将若干不同尺寸的物体互不重叠地放入有一定容量的箱子中以达到某种最佳目标。

二维的装箱问题恰恰跟我们版图工作中面积评估这类场景非常的类似。如已知各cell的大小或者底层instance level的大概大小，那么就可以利用此类算法估算最小占比的面积。如果需要加space 冗余，可以程序中size 给定的大小快速生成新的布局。

装箱的算法网上可以找到很多（禁忌搜索、蚁群算法、遗传算法和迭代局部搜索算法）。此处不介绍（看不懂），感兴趣的可以网上找找。这里发挥拿来主义，使用python 既有的包。直接使用。

下面是基于Custom Compiler设计平台Python接口做了一个简单的示例。用给定宽长模拟实际的Instance大小。对于python 脚本贴到console中注意选择Python类型，CC 同时支持tcl 和Python。变量rectangles对应的列表为需要摆放的object的大小(width, length).这里我列表中我放了14个。变量bins是填充的空间大小（如果设置过小摆放后会溢出）。