| 主权项 |
一种基于无网格模型的集成电路模块到模块的布线方法，其特征在于，包括以下步骤：(1)读入布线区域内的障碍信息、待布线网信息和工艺信息；(2)依据上述障碍信息建立障碍列表；(3)将障碍列表中的每一个多边形障碍都转化为矩形障碍；(4)将障碍列表中的每个矩形障碍的边界进行扩展；(5)依据步骤(4)构造二维不均匀网格阵列；(6)将起始模块和终止模块分别转化为起始点集和终止点集；(7)采用A*算法进行路径搜索具体实现步骤如下：7.1创建待扩展点的链表，保存所有已生成而未考察的点；以及封闭链表，记录已访问过的点；7.2将起始点集合中的所有点按照该点到终止点集合中点的最短距离有序地列入待扩展点的链表中；7.3在上述待扩展点的链表中读取估价值最小的点n，并判断点n是否是终止点集合中；是，结束搜索，不是，继续下面的步骤；7.4对点n进行扩展，并对扩展后得到的点x进行判断：若点x在待扩展点的链表中，比较点x的不同路径的估价值，若该估价值小于待扩展点的链表中的估价值，用该估价值更新待扩展点的链表中的估价值；若点x在封闭链表中，比较点x的不同路径的估价值，若该估价值小于封闭链表中的估价值，用该估价值更新封闭链表中的估价值，并将点x放入待扩展点的链表中；若点x既不在待扩展点的链表中，也不在封闭链表中；求解点x的估价值，并将点x放入待扩展点的链表中；7.5将点n放入到封闭列表中；7.6按照估价值将待扩展点的链表中的各点进行排序，重复步骤7.3～7.6；(8)输出搜索结果。 |
