《数字逻辑辅助分析工具-复旦大学微电子学院》由会员分享，可在线阅读，更多相关《数字逻辑辅助分析工具-复旦大学微电子学院（7页珍藏版）》请在金锄头文库上搜索。
1、数字逻辑功能提取器潘日华 童家榕 唐璞山复旦大学电子工程系CAD实验室，上海（200433）【摘要】本文介绍一种数字逻辑功能提取工具DLFE（Digital Logic Function Extractor ）。该工具能帮助用户从平面化的底层逻辑网表中提取出一套功能明确、易于理解和验证的层次化电路图；在提取的过程中也实现了对电路的功能分析。它采用人机结合的方法，由用户识别功能块（完成一定功能的子电路），由软件实时生成网表中用户选择的那部分电路的电路图，帮助用户识别功能块；并在网表中搜寻与用户识别出的功能块同构的实例，通过归并把电路提高到更高的层次。整个过程是自下而上，不断迭代的，最后将得到层次
2、化的电路图。实验表明，该工具对电路处理后得到的电路图具有功能性明确、划分适当、易于理解的特点。关键字：数字逻辑功能提取，电路图生成，电路同构匹配一、前 言数字逻辑功能提取就是分析给定的电路（以文本形式的网表表示），用层次化的方法提取各级功能模块，同时完成逻辑图的绘制。进行功能提取有助于对电路的理解和验证，一方面，基于功能划分的电路易于理解和改进；另一方面，基于功能划分的电路比较容易进行验证、定位错误以及再设计。传统上人们在分析电路时希望有一套完整的电路图，（虽然高层设计语言的出现提供了另一种理解方式，但是电路图的作用仍然是无法完全代替的），事实上在很多情况下没有可用的电路图，如用 VHDL等高
3、层设计语言设计得到的电路和未知电路的时候，往往只有电路的逻辑连接关系即网表，因此为了分析这类电路，需要有工具来帮助用户从网表产生电路图。在八十年代就有人研究过怎样从网表生成电路图，他们提出了各种关于美观的电路图的可量化标准，如信号流方向自左向右或自上向下，线交叉数目，线弯曲数等等。文献 1和3 提出了减少相邻两个器件列之间线交叉数的算法，文献2介绍了深度优先遍历实现单信号流的算法，文献 4 还考虑到用总线归并和调节器件朝向、可变引脚的位置来优化电路图的可理解性。这些算法在生成电路图上是比较有效的。现有的很多软件也包括实现电路图生成的工具，如Workview 的Viewgen 5，Candenc
4、e的SchGen 6，在对适当规模的网表进行处理时，也能生成很好的电路图。但是这些算法和工具都忽略了电路图中的器件数，即图的规模和电路图所表示的电路的功能性也应该是目标函数之一。对于较大的电路，如果直接进行电路图生成，不但花费的时间迅速增加，而且生成的电路图由于规模太大不利于理解，我们可以想象一下一个由门（而不是触发器）构成的四位计数器的电路图的可阅读程度。至于毫无功能性可言的随机电路不管怎么画都无法理解。另一方面，功能明显、规模较小，可以弥补前面所说的线交叉、线弯曲、对称性等目标函数上的不足。因此对于大规模的电路来说，用层次化的电路图表示比较合适，而且每一层的每一个子电 路都要有明确的功能。
5、为此，我们设计了 DLFE 工具，采用功能块识别、自下而上归并的方法来实现上面所说的目标。这里所说的功能块泛指完成一定功能（可以是各种级别）的电路，功能块识别是个交互的过程，功能块的判断由用户完成，工具为用户提供浏览整个电路的手段以帮助识别。归并就是用一个符号来代替相应的子电路。层次化电路图的提取过程就是功能块识别、归并的迭代过程。这个过程中虽然没有提到单个电路图生成，但是单个电路图的生成在功能块识别过程中是不断被调用的。应该指出的是，虽然在前面把拥有电路图作为分析的一个前提，但是在 DLFE 工具的使用过程中，这两者实际上是统一的，构造层次化电路图这个过程也是对电路进行分析的过程，体现在功能
6、块识别过程中；两者都是自下而上，对部分电路分析的结果使我们不必考虑该部分电路的内部实现，只要知道它是完成什么功能就可以了，下一步分析就可以在更高的基础上进行，这恰恰也完成了对层次化电路图中某个子电路的构造。而且是相互促进的，分析的结果有利于生成层次化电路图，而已生成的电路图又有利于分析。二、总体策略在大多数电路的设计过程中，一般采取自上向下、层层细分的方法，把一个系统划分为几个子系统，把子系统划分为模块，依次类推。要处理的输入网表往往是通过这种设计方法得到的底层电路实现，对它进行分析时，根据设计过程，可以有自下而上的逆过程，把简单的门归并成功能块，把功能块归并成模块，模块归并成系统。要达到电路
7、图的功能性要求，对软件来说比较困难，因为很难归纳出具有功能性的电路的数学表达式，而且电路的功能在不同层次上种类繁多，不计其数。 DLFE 工具并不试图自动寻找功能块，而是通过交互式环境提供各种浏览电路的手段，帮助用户找到功能块的一个实例。再由工具找出剩下的实例，用更高层 的单元替换。因此 DLFE 工具主要完成两个功能：帮助用户找到功能块的一个实例（功能块的制作）； 寻找剩下的实例并用符号来替换它们（功能块的匹配和替换）。工具的使用过程就是制作、替换的反复迭代，如图21所示。图 21三、功能块的制作功能块的制作，首先要帮助用户找到功能块的实例，然后需要对找到的实例加工，使它具有普遍性。这是因为
8、实例是具体应用，属于特殊情况。如有可能不同输入引脚所代表的线网在某个应用中连接不同线网，而在另一个应用中连接相同线网；或者一个输入引脚代表的线网连接电源线，需要区分这个连接是功能块内部的固定连接，还是外部的输入。对寻找实例，工具提供对输入网表的浏览和实时电路图生成支持。浏览分为按名字选取和按连接关系选取两种。前者用于提供一个初始点，用户可以从整个电路的输入、输出引脚开始，或者从特殊器件开始。后者基于一个功能块中所有器件都是相连的（即连通图），那么按照连接关系可以发现整个功能块。工作流程如图31所示。图 31浏览操作实际上是为用户在输入电路上开了个窗口，要求用户所看到的内容与实际没有偏差，因此有
9、以下选取规则：a.选中器件还选中该器件所连的所有线网，但这些线网只连接已在工作区内的器件，若还连接工作区外的器件，则用虚拟的 INPUT 或 OUTPUT代表，成为边界线网。b.选中边界线网（即选中INPUT或OUTPUT代表的线网）就选中该线网所连的所有器件。c.删除器件还将删除相应线网与器件的连接，并不删除整个线网，只有线网不连接 任何工作区中的器件时才删除。这样，就能保证除了边界线网外，工作区内容与输入网表严格一致。下面的一组图例是制作异或门功能块的过程，可以更好地说明整个制作过程：图 32 图 33图 341. 选择器件D1得到图32；2. 选择左图的N3线网后得到图33；3. 选择中
10、图的N4或N5线网将得到图34，4. 删除器件D4可以得到图33，整个过程可逆。找到一个实例后，还要对其进行修正，使它具有普遍性。具有普遍性的模块可以适应不同用法，一方面减少制作和替换的时间，另一方面增加电路的可理解性。为此提供以下修正方法：1、器件和边界线网都可以重新命名，其中， 器件名不允许相同。2、一个连接两个以上工作区内器件的输入线网可以打碎成两个不同的输入线网。3、不同输入线网改为相同名字时将合并为一个。4、连接GND或VDD的输入端不作为功能块的输入端，而作为内部连接。反之，改为其它名字时将作为功能块输入端。修正后的电路与输入的总网表不再一致，不能进行选择操作。每一个选择操作完成后
11、，都要对工作区内容重新生成电路图。在设计电路图生成算法时， 假定工作区内器件数和线网数都不会超过一百个（实际数量会更少），交互式操作的时间要求很容易满足。重点考虑信号流方向、线交叉、对称性等目标函数，通过以下几个步骤实现电路图生成：1、对工作区内容从最终输出端开始，从输出向输入进行深度优先遍历，确 定每个器件的逻辑列号，实现单一信号流方向；2、通过加入虚拟器件的方法把跨列线网转化为相邻两列之间的线网，所谓 虚拟器件即一根连线；3、确定每列内器件顺序，即逻辑行号，使线网交叉最少；4、计算每个器件的物理纵坐标，满足对称性要求；5、在两列之间的通道进行布线，使线网交叉最少，统计通道宽度；6、设置器件
12、线网物理横坐标。四、功能块的匹配和替换功能块制作好以后，就有了一个样本，可以在输入的电路中寻找同构的子电路，这个过程 称为匹配。如果找到实例，功能块中的每个器件和线网在输入网表中都会有对应的器件或线网，成之为对应关系。匹配的算法是在样本网表和输入电路的网表中分别作“相同”的遍历，所谓“相同”即两个当前器件或线网是否匹配。遍历过程中两个当前器件或线网不匹配时则中止匹配过程，反之建立两个器件或线网的对应关系，当整个样本网表都已遍历完且没有碰到不匹配，认为找到一个实例。对输入电路处理一遍后可以找到所有实例。1、功能块匹配算法：1.1、确定初始节点1.2、若初始节点为线网，进行线网匹配1.3、若初始节
13、点为器件，进行器件匹配1.2线网匹配算法：1.2.1、除边界线网外，线网连接数（一个器件的一个引脚为一个连接）是否一致；1.2.2、是否都是VDD或GND，VDD和GND不能和其它线网建立对应关系。1.2.3、若线网已建立对应关系，检查与当前线网对是否相符；1.2.4、把两个线网的对应关系推入匹配堆栈；1.2.5、线网所连每个器件是否匹配成功（1.3 ），若都成功返回两个线网匹配；1.2.6、反之从堆栈中弹出并撤消对应关系，返回不匹配。1.3器件匹配算法：1.3.1、类型是否一致；1.3.2、若器件已建立对应关系，检查与当前器件对是否一致；1.3.3、把两个器件的对应关系推入匹配堆栈；1.3.
14、4、相同引脚所连的线网对是否匹配（1.2），若存在等价引脚组（如与门的 输入端），还要对组内引脚所连线网进行排列，看是否存在一个可能匹配。1.3.5、若存在一个可能匹配，返回两个器件匹配；1.3.6、反之 从堆栈中弹出并撤消对应关系，返回不匹配。算法操作过程中用到一个数据结构匹配堆栈，匹配进行到某个线网或器件时，先假定两个器件或线网可以匹配，把它们的匹配关系推入堆栈，继续进行后面的遍历和匹配。后建立的对应 关系若和以前的对应关系矛盾（1.2.3和1.3.2），将不再遍历下去，而是从堆栈中弹出自己的对应关系并回溯到上一节点（器件或线网），试验下一个可能组合（1.2.5和1.3.4）。由于匹配中遍
15、历是以样本网表为依据的，所以算法的空间复杂性和时间复杂性都是由样本的特性决定。下面是算法复杂性的讨论，假定样本中有c个器件、n个线网：空间复杂性即匹配堆栈的大小，为O（c+n）；遍历样本网表的过程相当于为网表产生一个生成树，最坏情况下一次匹配的时间复杂性T1与生成树的高度和宽度有直接关系，而不是器件数、线网数。这样一次匹配的复杂性与具体的电路以及遍历的顺序有关，由于篇幅所限，关于T1详细的计算和讨论将在以后的文章里进行。在一个输入网表中寻找某种样本的所有实例时，假定从线网开始匹配，总网表中有 N个线网，Ti为与第i根线网匹配的时间，匹配的时间复杂性T为与输入网表中线网总数成线性关系。每次匹配到一个实例后，可以用一个符号来代替相应的子电路。由于匹配记录了样本中每个器件和线网在总网表中对应的器件和线网，所以只需删除这些器件和内部线网，加入一个代表功能块的新器件，连接新器件和边界线网（新器件的引
