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

关键词: 控制数据流图, SoC, 验证, 深度优先搜索算法

Abstract: With the increasing of ASIC complexity and the demand for time to market, great challenges for SoC(system on chip)design and verification have to be faced. CDFG(control data flow graph)can be used in system modeling, software and hardware partition, synthesis and verification. Aiming at the final goal of SoC verification, the paper discusses the system verification based on CDFG by raising the level of abstraction, a new verification flow is presented. By analyzing CDFG’s definition and its representation, the tree creating algorithm based on depth first search principle, CDFG division algorithm and CDFG searching algorithm are given. Then some examples of these algorithms are illustrated, which specify the operation of these algorithms in SoC verification flow.

Key words: Control data flow graph(CDFG), System on chip (SoC), Verification, Depth first search algorithm (DFS)