基于CDFG的SoC验证方法及其分割与搜索算法

随着芯片复杂度以及市场对集成电路上市时间要求的不断提高,对SoC设计方法和验证方法带来了巨大的挑战。控制数据流图可用于系统建模、软硬件功能划分、系统综合与验证等多个环节。该文针对SoC验证的需要,利用CDFG,研究了基于CDFG的验证体系,给出了CDFG的几种定义,讨论了CDFG的表示方法,提出了基于CDFG的验证流程,研究了基于DFS的生成树算法、CDFG的分割算法和CDFG的搜索算法,并以实例说明了这些算法在验证流程中的作用。

一种有向图的特殊搜索算法及其实现

针对图像组合系统中所用无环有向图的特殊的搜索要求,提出了有别于DFS和BFS及它们的简单嵌套、组合的算法,利用了DFS、DFS直接回溯等功能,实现了一个特殊的图搜索算法。

寻找λ-边连通子图的一次遍历搜索算法

寻找图的λ-边连通子图时,可利用深度优先搜索算法,但需要经过λ次的遍历搜索过程才能完成。基于图的邻接矩阵储存结构特点,提出了一种新的搜索算法,可以通过一次遍历搜索过程得到图的λ-边连通子图。对比深度优先搜索算法,新算法结构简单,容易实现,大大提高了算法的执行效率。这种搜索算法也可以用于判定图的连通性。