时序功能块的提取.doc

-专业文档，值得下载!-专业文档，值得珍藏！-时序功能块的提取潘日华童家榕唐璞山（复旦大学电子工程系ICCAD实验室，上海200433）【摘要】文章介绍了基于功能块提取器（DLFE）工具的时序功能块提取工具和方法。整套工具用于从版图中构造层次化电路，以利于电路的验证和理解。时序功能块提取通过时序功能块的普遍特征来定位时序功能块，避免了手工定位的盲目性，大大加快了构造层次化电路的速度。实验证明，工具对时序模块的提取是十分有效的。关键词：功能块提取时序功能块逻辑验证1引言通常的集成电路验证中，在大规模生产之前，必须检验版图和设计电路图的一致性。一般的方法是将设计电路图打碎至最底层，然后与版图比较1。验证方法基于图的同构，虽然有很多优化，其复杂性仍然是非多项式的。在电路的规模比较小时，这样的算法可以胜任。但是随着电路规模的不断增长，验证耗费的时间和成本逐渐变得不能忍受。层次化验证的方法2，虽然每一个子电路仍然采取同构的验证方法，但是通过对电路的划分，可以将时间复杂性由非多项式向多项式转化。例如对较大的N来说，若分为a块，exp(N)远大于a*exp(N/a)。因此，如果能从版图中构造出层次化的电路图，将大大加快验证过程。另一方面，设计的电路图是按功能划分的，若要将提取出的电路图和设计电路图比较，必须按功能从版图中提取层次化电路图。现有的软件中还没有按功能提取层次化电路的工具。不同的电路由于应用领域不同，各自的功能块截然不同，很难用一个算法来自动识别，或者是算法只能识别某一类型的功能块。本文所介绍的工具也不试图设计一个能自动识别任何功能块的算法，而是采用人机结合的方法。分别利用人脑的识别能力和计算机的计算能力，共同完成功能块的提取。在此之前，我们已经设计了交互式的功能块提取器（DLFE）工具3，实现了电路的可视化和层次化的基本机制。用户可以通过可视化工具浏览电路，制作功能块的样本，然后用工具在整个电路中搜寻并替换所有同构的样本的实例。自下而上的逐步构造出层次化的电路图，同时完成对电路的功能分析。但是DLFE工具在功能块寻找和定位方面有所欠缺，很大程度上依赖于用户自己通过浏览去搜-专业文档，值得下载!-专业文档，值得珍藏！-寻样本，有一定的偶然性，与用户的经验也有很大关系。因此我们在DLFE的基础上开发了帮助用户寻找和定位时序功能块的工具。它根据时序模块的普遍特征来搜寻可能的功能块，具有很高的准确性。且不依赖于已有的模块库，不受模块实现方式的影响，可以应用于各种电路。在工具辅助下，避免了手工查找的盲目性和随机性，大大加快了构造层次化电路图的速度。文章第2节介绍了时序模块的普遍特征，第3节介绍如何根据这些特征来定位时序模块，第4节介绍算法的实现和复杂性，第5节列举了具体的例子和效果。2时序功能块的特征通过对大量时序功能块的总结归纳，我们发现时序功能块具有一些共同的特征。图1所示的电路是一个典型的时序功能块，下面以它为例介绍时序功能块的基本特征。DQQSETCLRDQQSETCLRDQQSETCLRDQQSETCLRQ0Q1Q2Q3CP图1一个典型的时序功能块核心器件在模块中起核心作用的器件。如图1中用深灰色表示的的触发器。另外如十六位定时器中的四位计数器等等都属于核心器件。全局线网在功能上控制器件的行为的线网，在连接关系上它连接了所有的核心器件。如图1中用粗线表示的时钟信号。又如复位信号和双向计数器的计数方向信号都是全局线网。相关和相关路径一个模块中，核心器件A到核心器件B之间存在一条数据通路，那么A和B是相关的，这条路径称为相关路径。如图1中的虚线就是其中的一条相关路径。关系特征如果相关路径用连线来表示，核心器件用圆来表示，模块中所有相关路径就构成了模块的关系特征。如图2是四位计数器的触发器之间的关系图，图3是四位移位寄存器的触发器关系图。-专业文档，值得下载!-专业文档，值得珍藏！-ABCD图2四位同步计数器关系图ABCD图3四位移位计数器关系图关系特征可以用作功能块的特征和辨别功能块的依据，虽然不能保证具有某种特征的模块一定是实现某种功能的模块，但可以肯定不具有这种特征的模块不是实现某种功能的模块。如不具有图2特征的模块肯定不是四位同步计数器。根据以上这些特点，我们可以假定：核心器件和所有相关路径包含的器件（如图1中浅灰色器件）构成模块的主体。经验表明，对大部分时序功能块来说，这个假定是成立的。工具将基于这个假定来提取时序功能块。以上的几个概念和假定，虽然比较模糊，而且不一定在任何情况下都成立，但是它们在大部分情况下都是很有效的。3时序功能块的提取时序功能块的提取根据上一节介绍的时序功能块的普遍特征来定位功能块。提取工作分三步完成：核心器件和全局线网的提取、核心器件之间的关系分析、功能块主体的提取。这里要说明的是，此后所说的“核心器件”、“全局线网”等都应是“可能的核心器件”、“可能的全局线网”，并不是严格意义上的核心器件、全局线网。“可能的”核心器件和全局线网将覆盖真正的核心器件和全局线网，判断和区分工作由用户完成。3.1核心器件和全局线网的提取核心器件和全局线网的提取将建立功能块的框架，以排除大量的无关器件，缩小处理范围。由于工具自己不能分别核心器件和普通器件，用户需要输入核心器件类型集合。另外还要引入一个定义：关键引脚核心器件连接全局线网的引脚。引入关键引脚是要从核心器件找到全局线网。一般来说，全局线网不仅连接了所-专业文档，值得下载!-专业文档，值得珍藏！-有的核心器件，而且都连接着相同的引脚。如时钟信号连接了CP引脚，复位信号连接了RZ引脚。核心器件和全局线网的提取基于这样一个假设：功能块的全局线网所连的核心器件包含且仅包含该功能块的核心器件。即不包含其它功能块里的核心器件。对实际版图上的电路来说，这个假定是合理的。由于驱动能力的限制，虽然一个线网可以在逻辑上连接了很多模块的核心器件，但在实际电路中，必须加多个驱动器件。一般地，这些驱动器件都位于模块的输入位置，从而隔离了不同模块之间的核心器件。如在图4中，N1和N2分别是功能块B和C的全局线网，虽然在逻辑上是相同的，但在实际电路中，它们并不直接相连。AAAABCDN1N2N3图4驱动器件的隔离作用3.2核心器件关系分析分析核心器件关系采用穷举的方法，在一定范围内，若两个核心器件之间存在通路，则这两个器件存在关系。核心器件关系分析就是要找出功能块内所有的这样的关系。通过这些核心器件关系信息，用户可以初步判断功能块的功能。如果模块的输出在模块外部反馈回模块本身，分析出的关系不仅包含模块内核心器件之间的关系，还包括模块外的关系。由此定位出的功能块将包含模块外部的器件，影响到提取的准确性。解决这一问题的办法是绕开它，如果电路中有多个这种功能块，那么最好的解决办法是找一个不受反馈干扰的功能块实例的关系图，然后利用工具的匹配和替换功能3来找出所有实例，反馈的连线自然会被排除在外。另一种办法是逐步缩小遍历深度（算法中的可控参数），使得反馈线路不在遍历范围内。3.3功能块主体的提取功能块主体的提取把某个关系图对应的子电