门级到功能模块级子电路提取算法
文献类型：学位论文
| 作者 | 李长青 |
| 学位类别 | 工学博士 |
| 答辩日期 | 2007-06-05 |
| 授予单位 | 中国科学院研究生院 |
| 授予地点 | 中国科学院自动化研究所 |
| 导师 | 彭思龙 |
| 关键词 | 子电路提取 子图同构 辐射路 赋标号算法 自相似度 subcircuit extraction subgraph isomorphism radiate path label algorithm degree of self-similarity |
| 其他题名 | the Subcircuit Extraction Algorithms from Gate Level to |
| 学位专业 | 模式识别与智能系统 |
| 中文摘要 | 随着集成电路规模的日益增大，从门级到功能模块级的子电路提取开始应用于EDA领域，相关算法将逐渐成为研究的热点。提取的目的是检测目标电路中是否含有指定功能或结构的模块，并确定该模块的数量和位置。但是，至今尚无高效的算法能够满足实际工程的需要。为了填补这一空白，本文提出了辐射路匹配算法和subGeminiⅡ算法。 辐射路匹配算法具有完备性和模糊搜索功能，并且有速度快、适于并行化等优点。该算法通过单个顶点的辐射路特征，将子图同构问题转化为顶点之间的匹配问题。在算法运行过程中，通过不断删除搜索空间中的非匹配顶点，大大降低了算法的时空复杂度。理论分析和试验结果表明，算法的时空复杂度与目标电路的逻辑门数和功能模块电路的逻辑门数均为线性关系。 subGeminiⅡ算法利用迭代赋标号的方法，能够快速地发现和匹配子电路，具有隐含的并行搜索特点。相对于subGemini算法，它有三方面大幅度改进：（1）把处理的对象由subGemini算法的无向图变成有向图；（2）构造三处迭代的核心公式（Hash函数），使之更加适合门级到功能级子电路的提取；（3）增加灵活地指定特殊顶点的功能，加快电路提取速度。subGeminiⅡ算法适合从门级到功能模块级的子电路提取，它的时间复杂度与目标电路图的顶点数和功能模块电路图的顶点数均为线性关系。 两个算法各有其优点和不足，选择合适的算法成为工程实践的重要问题。本文在电路结构特征的基础上，量化了电路表示图的顶点相似程度，并给出图的自相似度、迭代效率、稳定阶数和最终相似度等概念。通过深入分析影响算法运行效率的因素，我们提出详细了分析功能模块电路基础上选择子电路提取算法观点，以及选择子电路提取算法的原则和方法。 |
| 英文摘要 | Subcircuit extraction from gate level to functional level is arising in many EDA(Electronic Design Automation) contexts，and becoming a more critical issue with design size of very large scale integrated circuits growing rapidly. Its purpose is to detect whether a special functional module or structured one is in the object circuit, and to find the number and location(s) of the module. However, no efficient algorithm for this problem is suitable for real circuits as yet. To fill this blank, two high performance algorithms, radiate path matching and subGeminiⅡ, are proposed in this dissertation. The radiate path matching algorithm is complete, fast, suitable for parallel computation and with vague search option. It transforms the subgraph isomorphism problem into a matching problem between vertexes through the introduction of radiate path feature for every vertex. In the running process, the unmatched vertexes are deleted gradually from the searching space and thus the complexity of the algorithm is reduced significantly. Theoretical analysis and experiment results show that both the time and space complexity of our algorithm are only linearly dependent on the number of gates of the object circuit and that of the function module. SubGeminiⅡ can find the subcircuit very fast with iterative labeling method for it is a implicitly parallel search algorithm. Compared to subGemini algorithm, it has improved in three aspects as follows. 1. Circuit graph model is changed from undirected graph to directed one. 2. Three Hash functions, main iteration formulas are updated to adapt the extraction from gate level to functional level. 3. Vertexes can be specified arbitrarily to save run-time largely. subGeminiⅡ is very suitable for the subcircuit extraction from gate level to functional level because its time complexity is linearly dependent on the number of vertexes in the object circuit representing graph and that in the function module circuit representing graph. It is important for us to select suitable algorithms in the engineering practice, for each one has the pros and cons. Basing on structure features of the circuits, we can quantify similarity of vertexes in the representing graph. Therefore, several concepts, degree of self-similarity , iteration efficiency, stable rank and final degree of similarity , are proposed in this dissertation. From my point of view, selecting algorithms should make a reference to analysis result of subcircuit. For that reason, factors which affect the run-time have been analyzed deeply. As a result, principles and methods on selection of the subcircuit extraction algorithms have been put forward. |
| 语种 | 中文 |
| 其他标识符 | 200318014603010 |
| 源URL | [http://ir.ia.ac.cn/handle/173211/6002]  |
| 专题 | 毕业生_博士学位论文 |
| 推荐引用方式 GB/T 7714 | 李长青. 门级到功能模块级子电路提取算法[D]. 中国科学院自动化研究所. 中国科学院研究生院. 2007. |
入库方式： OAI收割
来源：自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。