[发明专利]一种VLSI布局规划中集中约束的实现方法

摘要

本发明属于集成电路计算机辅助设计技术领域，具体为一种VLSI布局规划中集中约束的实现方法。该方法结合B^*－tree的表示法、模拟退火算法以及线性规划算法。其步骤包括根据约束构造约束子树，连接各个子树构成允许的初始布局，采用模拟退火算法对面积等到因素进行优化；从初始布局得到线性规划的约束条件，构造线性规划矩阵，然后调用线性规划函数求解线性规划矩阵，进行压缩操作和软模块调整，从而得到优化布局结果。本方法用于实现平面布局中多个模块需要集中放置的约束，也可实现多个或整体划分上的集中约束。

主权项

1、一种VLSI布局规划中集中约束的实现方法，其特征在于具体步骤如下：(1)根据集中约束的要求构造允许的初始布局：首先将各个约束涉及的模块连接为子树，不涉及约束的模块单独划分为子树，然后将各个子树连接构成整体B*-tree；(2)采用模拟退火算法对全局因素进行优化：模拟退火中基本操作为旋转、交换、删除和插入，操作方法为：①旋转操作：交换某个模块的长宽；②当交换，删除，插入基本操作全部是在针对同一个子树的内部节点操作时，即交换两节点或删除节点和插入节点都在同一子树进行时，该类操作只针对节点进行；③当操作涉及两节点不在同一子树内时，则需要根据下面的判断完成相关操作：<1>针对交换操作：当其中一个节点为叶节点且另外一个节点对应子树的根节点之父节点与叶节点在同一子树中，交换其中对应叶节点和另一个节点对应整体子树；否则交换两节点对应子树的位置；<2>针对删除插入操作：删除对应子树，同时连接其他子树保持树的完整性，在插入子树中选择位置放置插入；优化过程中各模块长宽比不进行调整，全部当作硬模块处理，其中模拟退火的温度、迭代次数等控制参数可以根据对求解时间和求解质量的要求进行调整；当搜索不再收敛或已经达到终止温度时停止进一步搜索，取搜索中最优布局结果作为本步输出；(3)根据(2)步得到初始布局归纳出线性规划的约束条件；其中优化目标是在不改变原来相对位置条件下总面积最小，目标函数为：Minimize…f＝λ1·hc+λ2·wc，其中λ1，λ2分X别是模拟退火布局结果长宽比例，hc，wc为布局的长度和宽度；线性规划的变量是所有模块的位置xi，yi和长宽hi，w及总体布局的长宽hc，wc；所述归纳出的线性规划约束条件有四种：<1>模块自身长宽比的范围λmin＜hi/wi＜λmax；<2>模块之间的位置约束：xi+wi＜＝xj和yi+hi＜＝yj；<3>布局范围约束：xi+wi＜＝wc和yi+hi＜＝hc；<4>参数范围约束：xi，yi，wi，hi，wc，hc＞＝0；(4)得到线性规划的目标函数和约束条件后使用数学工具Matlab库函数对线性规划求取最优解，得到满足所有约束条件下面积最优时所有参数的数值：各个模块位置xi，yi，长宽hi，w及总体长宽hc，wc。