利用公共子序列求解固定边框布图问题

摘要

提出一种新的固定边框的布图算法.该算法采用SP表示方法,以公共子序列为基础,在随机搜索过程中限定布图宽度的变化,从而使减小芯片面积的目标与固定边框的目标在一定程度上取得一致.与现有的固定边框布图算法相比,文中算法在边框更紧凑、宽长比更大的条件下具有更高的成功率和更短的运行时间.此外,文中算法在布图初始阶段就可以对固定边框的合理性进行评估,避免了因给定的边框不合理而带来的时间上的浪费.