论文部分内容阅读
随着集成电路规模的日益增大,从门级到功能模块级的子电路提取开始应用于EDA领域,相关算法将逐渐成为研究的热点。提取的目的是检测目标电路中是否含有指定功能或结构的模块,并确定该模块的数量和位置。但是,至今尚无高效的算法能够满足实际工程的需要。为了填补这一空白,本文提出了辐射路匹配算法和subGeminiII算法。主要研究内容如下:
⑴辐射路匹配算法具有完备性和模糊搜索功能,并且有速度快、适于并行化等优点。该算法通过单个顶点的辐射路特征,将子图同构问题转化为顶点之间的匹配问题。在算法运行过程中,通过不断删除搜索空间中的非匹配顶点,大大降低了算法的时空复杂度。理论分析和试验结果表明,算法的时空复杂度与目标电路的逻辑门数和功能模块电路的逻辑门数均为线性关系。
⑵subGeminiII算法利用迭代赋标号的方法,能够快速地发现和匹配子电路,具有隐含的并行搜索特点。相对于subGemini算法,它有三方面大幅度改进:①把处理的对象由subGemini算法的无向图变成有向图;②构造三处迭代的核心公式(Hash函数),使之更加适合门级到功能级子电路的提取;③增加灵活地指定特殊顶点的功能,加快电路提取速度。subGeminiII算法适合从门级到功能模块级的子电路提取,它的时间复杂度与目标电路图的顶点数和功能模块电路图的顶点数均为线性关系。
⑶两个算法各有其优点和不足,选择合适的算法成为工程实践的重要问题。本文在电路结构特征的基础上,量化了电路表示图的顶点相似程度,并给出图的自相似度、迭代效率、稳定阶数和最终相似度等概念。通过深入分析影响算法运行效率的因素,提出详细了分析功能模块电路基础上选择子电路提取算法观点,以及选择子电路提取算法的原则和方法。