基于结点属性函数的大规模集成电路的核值计算方法

摘要

本发明涉及一种基于结点属性函数的大规模集成电路的核值计算方法，其采用赋权超图对电路进行数学建模，将电路线网转换到赋权超图，并保存为赋权超图文件，然后启动赋权超图的核值计算程序，采用改进的压缩存储格式对赋权超图进行存储，并基于结点属性函数计算结点的核值，将所有结点的核值结果存储在赋权超图核值文件中。采用本发明的核值计算方法，不仅能有效地提高核值计算的效率，还有利于在赋权超图的结点匹配过程中，改善结点匹配的性能。

主权项

一种基于结点属性函数的大规模集成电路的核值计算方法，其特征在于，具体步骤如下：步骤1，用硬件描述语言描述该电路，生成该电路的源代码；步骤2，词法分析，从左到右一个个读入该电路的源代码，对构成源代码的字符流进行扫描和分解，从而识别出一个个单词；步骤3，语法分析，在词法分析的基础上将单词序列分解成各类语法短语，依据硬件描述语言的语法规则，确定整个字符流是否构成一个语法上正确的硬件描述语言程序；步骤4，语义分析，在语法分析的基础上审核源代码有无语义错误，为中间代码生成阶段收集类型信息；步骤5，中间代码生成，在语法分析和语义分析的基础上，将源代码生成中间代码，用内部中间格式表示；步骤6，赋权超图文件生成，基于中间代码构造文本描述的电路对应的线网，经过电路线网到赋权超图的转换之后，保存为赋权超图文件；步骤7，赋权超图核值计算，启动赋权超图核值计算程序，读取赋权超图文件，采用改进的压缩存储格式对赋权超图进行存储，对生成的赋权超图中每个结点，基于结点属性函数计算其核值，将所有结点的核值结果存储在赋权超图核值文件中；上述的步骤6中，所述的赋权超图文件生成的步骤如下：步骤6.1，基于中间代码构造电路源代码描述电路对应的线网，生成完整电路线网；一个完整的电路线网看作是一个根模块，它由层次化的子模块实例和电路逻辑单元通过信号互连构成，且每个子模块内部由端口、电路逻辑单元、嵌套子模块的实例通过信号连接构成；步骤6.2， 从根模块开始，递归遍历层次化线网的模块，为每个电路逻辑单元编号；步骤6.3 ，从根模块开始，递归遍历层次化线网的模块，为每个电路逻辑单元之间的信号编号，并确立每个信号x的连接方式，实现到赋权超图的转换；其中，电路线网中的电路逻辑单元用赋权超图的结点表示，电路线网中的信号用赋权超图的超边表示；结点的权值代表电路逻辑单元的大小，超边的权值代表电路逻辑单元之间信号连线的权值；i为赋权超图中结点的编号，取值范围为1到电路线网中电路逻辑单元的总个数；j为赋权超图中超边的编号，取值范围为1到电路线网中信号的总个数；步骤6.4， 将转换得到的赋权超图保存为赋权超图文件；上述的步骤7中，所述的赋权超图核值计算的步骤如下：步骤7.1，读取赋权超图文件，采用改进的压缩存储格式对赋权超图进行存储；步骤7.2，计算出所有结点的属性函数值；步骤7.3，对所有结点的属性函数值进行非严格降序的计数排序；步骤7.4，按照结点属性函数值的非严格降序次序访问每个结点，计算每个结点v的核值；步骤7.5，将所有结点的核值结果存储在赋权超图核值文件中；上述的步骤6.3中，所述的确立信号x连接方式的步骤如下：步骤6.3.1，依次处理信号x的每个管脚连接，支持跨层次连接，寻找到连接端的电路逻辑单元y；步骤6.3.2，如果电路逻辑单元y已经存在信号x的连接中，则忽略该电路逻辑单元y；否则在信号x的连接中增加该电路逻辑单元y；上述的步骤7.1中，所述的赋权超图的改进压缩存储格式如下：步骤7.1.1，使用xadj数组存储每个结点所有邻接超边列表的起始位置信息，即第i条结点的终止位置为第i+1条结点的起始位置减1，且xadj数组的大小为赋权超图中的结点个数加1， xadj数组最后一个元素用于存放最后一条结点的终止位置；步骤7.1.2，使用adjncy数组存储每个结点所有邻接超边的列表信息，第i条结点的邻接超边列表存储在adjncy数组中，从adjncy[xadj[i]]到adjncy[xadj[i+1]‑1]；步骤7.1.3，使用eptr数组存储每条超边所包含的结点列表的起始位置信息，即第j条超边的终止位置为第j+1条超边的起始位置减1，且eptr数组的大小为赋权超图中的超边个数加1， eptr数组最后一个元素用于存放最后一条超边的终止位置；步骤7.1.4，使用eind数组存储每条超边所包含结点的列表信息，第j条超边的邻接结点列表存储在eind数组中，从eind[eptr[j]]到eind[eptr[j+1]‑1]；步骤7.1.5，使用vwgts数组存储结点的权值信息，且vwgts数组的大小为赋权超图中的结点个数；步骤7.1.6，使用hewgts数组存储超边的权值信息，且hewgts数组的大小为赋权超图中的超边个数；上述的步骤7.4中，所述的结点v的核值计算的步骤如下：步骤7.4.1，将结点v的属性函数值作为核值输出；步骤7.4.2，将结点v从所在的超边e中删除；步骤7.4.3，如果超边e删除结点v后，仍包含两个及以上结点，则超边e仍然存在，否则删除超边e；步骤7.4.4，重新计算结点v的邻接结点u的属性函数值；步骤7.4.5，更新邻接结点u属性函数值的非严格降序计数排序的次序。