摘 要： 讨论了分配问题匈牙利法在网络芯片功能验证中的应用，在建立了网络芯片模型的基础上提出验证需求，针对网络芯片验证的实际问题对匈牙利法进行了扩展和改进，提出了适应于分级流水芯片提高其功能验证效率的有效方式，改进后的匈牙利法具有更好的适用性。芯片验证结果证明了其可行性及其优越性。
关键词： 包交换；功能验证；匈牙利法；覆盖率
包交换又称分组交换，是一种传送数据的方法，将用户传送的数据包划分成一定长度的单元，每个单元称为一个分组。在每个分组的前面加上一个分组头，用以指明该分组发往何地址，然后由交换机根据每个分组的地址标志，将他们转发至目的地，这一过程称为分组交换。包交换处理分组的一般过程是：将收到的数据包先放入缓存，再查找转发表，找出到某个目的地址应从哪个端口转发，然后由交换机构将该数据包传递给适当的端口转发出去[1]。由于包交换功能复杂，其硬件设计达到百万门级，而验证百万门的设计是一件非常难的事情。目前进行功能验证有效的策略主要有两种[2]：一种是传统的功能验证方法，包括模拟验证、形式验证、基于断言的验证三种方法，其特点是基于特定测试向量的针对特定功能的定向功能验证；另一种是基于伪随机向量的针对覆盖率的随机功能验证。当然两种验证方法又有交叉。但针对一般的设计，其验证策略通常先进行定向功能验证，保证设计满足设计规范的功能要求，但其很难避免设计之外的缺陷及错误，也很难满足代码覆盖率的要求，所以需要进一步用随机测试向量进行随机验证[3]。但无论哪种策略在进行验证时，在顶层testbench加载激励时，不同的数据必然有自己特定的数据通道，但不同的数据通道在进行功能验证时，其效率是不同的，因而有必要从数据通道方面针对验证进行研究，以提高功能验证效率。
本文首先根据以上包交换工作过程构造定向功能验证模型，根据验证需求提出如何在满足需求的基础上高效地进行定向功能验证，并对结果进行分析。
1 模型概述
本文将整个包交换系统划分成三个部分，分别是输入缓存管理、查找管理和输出管理。模块之间数据通道采用分级流水管理的方式，假定输入缓存管理模块分为两个独立的功能模块，以分别处理不同类型的输入数据。数据处理完成后存入缓存，查找管理模块从缓存中读出数据包头信息进行分类管理，假定其同样有两个独立的功能模块。输出管理模块从查找模块读出包头信息，再从缓存模块读出输出的数据包信息，并将此数据包信息转发出去，在此假定模块也有两个独立的功能模块，此时建立系统模型输出管理如图1所示。
以上式（1）～式（3）为适用标准型用匈牙利法求解过程，但此处又有不同于匈牙利法的地方，有如下两点：
(1)求解过程遵照匈牙利法则，匈牙利法中未出现对无穷大数据的处理，而本例中效率系数出现无穷大数据。针对无穷大数据，其处理方式为其减去任何一个有限的数据保持不变仍为无穷大数据。
(2)对于虚构的行或列在适用法则时不用减去本身，因为减去自身则成为0，这样就会出错。如以上式（2）在进行行减，即将系数矩阵C的各行元素依次减去所在行的最小元素时，不适用于最后两行。如果适用则进行列减，即将系数矩阵C的各列元素依次减去所在列的最小元素时，不能得出有效的0元素，因为最后两行虚构行所有元素为0元素。
由式（3）可以看出此式中有效行中独立零元素的个数不等于矩阵的行数，不满足定理2，而式（3）此时也不适用于匈牙利法的计算步骤，针对此情况解决方案如下：
(1)对本文中构造的矩阵独立零元个数只需等于虚构前行、列中的小者即可得到一个最优方案；
(2)用圈0法找C′中独立的零元素；
(3)找C′中含未加标记的零元素个数最少的行(列)，从该行（列）中选效率系数最小的一个零元素加圈；
(4)把该圈0元素所在的行、列中的其他零元素划去。划去的0元素不计入式（1）统计每行、每列的0元素；
(5)反复执行式（1）～式（2）直到所有行、列的零元素全部被加了标志；
(6)去掉虚构的行或列，此时便得到最优解决方案。
具体如下所示：
4 结果分析
以上从系统的角度分析和提出如何最优地针对分级流水单一模块功能的验证方法，如果不进行最优化估算则会浪费大量资源进行无用的重复工作。以下将从验证效率、验证效果两个方面对比随机分配的验证和最优的验证效率之间的差别。验证效果主要从功能覆盖率和代码覆盖率两个方面进行说明。因为本文针对功能验证因而首先保证功能覆盖率，其次代码覆盖率主要包括以下五个方面：
(1)语句覆盖率：指验证程序能覆盖代码的行数与代码的全部行数之比。
(2)路径覆盖率：指验证程序通过的if…else或case结构的可能路径与设计中所有可能路径之比。
(3)表达式覆盖率：执行过的if…else分支或case分支与其所有分支之比。
(4)触发覆盖率：分析敏感变量中的信号是否唯一触发一个过程。
参考文献
[1] 谢希仁.计算机网络（第4版）[M].北京：电子工业出版社，2003：2-8.
[2] 杜慧敏，李宥谋，赵全良.基于Verilog的FPGA设计基础[M].西安：西安电子科技大学出版社，2006：134-136.
[3] 任宇，王以伍.VLSI设计中一种新型的功能验证方法[J]. 微计算机信息，2006，12(2)：285-287.
[4] 冯晓慧，刘三阳.工程设计中的最优化计算方法[M].西安：西安电子科技大学出版社，2006：219-222.
[5] 张良，陈全润，张明晖.等.“一人多事”的分派问题[R].山东：教育部精品课山东大学运筹，2002：8-9.