一种基于存储器内建自测试的新型动态March算法设计

蔡志匡 余昊杰 杨 航 王子轩 郭宇锋

(南京邮电大学集成电路科学与工程学院 南京 210023)

1 引言

片上系统(System on Chip, SoC)大部分由嵌入式存储器组成，目前嵌入式存储器的面积约占总芯片面积的95%[1,2]。随着存储器生产工艺的不断演进，存储密度日益增加，生产出现缺陷的概率也增大[3,4]，因此针对存储器的测试就显得尤为重要。

存储器内建自测试(Memory Built-In Self-Test,MBIST)是一种被验证为可靠的存储器测试方法[5–7]，其中使用有效的March算法是测试存储器的关键[8]，MBIST控制器通常用于测试算法生成，以发现存储器中的缺陷及其类型[9]。在超深亚微米技术中，发生频率越来越高的动态故障可能导致测试逃逸，给客户带来无法估量的信誉和经济损失。然而，目前没有一种测试算法可以同时考虑所有故障模型，由工具配置的算法模型文件只能生成固定的算法电路，植入硅片的BIST电路在成片后将无法更改，难以完成算法的灵活调整[10]。上述种种问题激发了对新型测试算法和专用MBIST控制器电路的需求。

2 存储器故障模型与测试算法

2.1 存储器故障模型

研究存储器存储单元的故障模型是研究存储器测试算法的基础，故障模型一般可以大体分为静态故障和动态故障[11]。为了更好地验证提出算法的故障覆盖率，本文引入故障原语的概念。

2.1.1 存储器故障原语

想要指定某个存储器故障类型，必须指定敏化操作序列(S)、故障行为(F)和从故障存储单元中的读取值(R)，结合这3个信息就构成了描述故障模型和敏化条件的故障原语(Fault Primitive, FP)表达式：FP=[12]。用写干扰耦合故障(CFdsxw!x)中的一个子集进行举例说明：FPCFdsxw!x=<0w1,0/↑/–>,该故障原语表示在初始存储值为0的攻击单元(aggressor cell) a上进行写1操作，使得相邻的受害单元(victim cell)v的逻辑值发生非预期的0 到1 的跳变。对应的敏化操作序列为S={a(0w1),v(0)}，因为不需要读操作，R操作设置为“−”，故而故障行为和受害单元读取值F/R表示为v(1)/v(–)。

2.1.2 存储器静态故障与动态故障

静态故障。敏化序列中只需1次读或写操作的故障类型。例如固定故障(Stuck-At Fault, SAF)，表示无论对某个故障存储单元执行什么读写操作，它的存储值始终保持为逻辑0或逻辑1，对应故障原语：FPSAF=<0/1/->, <1/0/->[13]。存储器静态故障还包括转换故障(Transition Fault, TF)、读破坏故障(Read Destructive Fault, RDF)和耦合故障(Coupling Fault, CF)等。

动态故障。敏化序列中需要两次或两次以上读或写操作的故障类型。为了检测这种故障需要对存储单元电路执行多次的连续操作才能引发电路故障行为，故障原语表现为或[14]。常见的存储器中的动态故障类型有：动态读破坏故障(dynamic Read Destructive Fault,dRDF)、动态错误读故障 (dynamic Incorrect Read Fault, dIRF)、动态伪读破坏故障(dynamic Deceptive Read Destructive Fault, dDRDF)、动态干扰耦合故障 (dynamic disturb Coupling Faults, dCFds) 等，详细的静态/动态故障类型及其故障原语见表1。

表1 静态/动态故障原语

2.2 存储器March测试算法

存储器测试算法中应用最广泛的是March类算法[15]。最初的March算法相对简单，测试元素设计并不成熟，例如MATS+算法，复杂度仅5N(N为存储单元数)。直到1982年，经典的March C算法进入人们的视野：{↑↓(w0);↑(r0,w1);↑(r1,w0);↑↓(r0);↓(r0,w1); ↓(r1,w0);↑↓(r0)}，March C算法因其特定的升序和降序元素排列，使其具有可观的故障覆盖率和较低的时间复杂度，成为自提出之后大部分改进算法的基础算法。此外，还有一些面向动态故障的经典检测算法被提出，例如March AB和March RAW，两种算法对动态故障均有不同程度的覆盖。常见March算法的优势和局限性分析见表2。

表2 常见March算法与动态March算法的优势和局限性分析

为了后文表述更清晰，将March算法中的每个以分号相隔的元素，用从“M0”开始的标序表示，M0后面的元素则依次用M1, ···, M2表示，例如MATS++算法，M0, ↑↓(w0)，M1, ↑↓(r0,w1)，M2, ↑↓(r1,w0,r0)，其他常见March算法和本文提出的动态March算法的具体描述详见表3。

表3 常见March算法及动态March算法的具体描述与时间复杂度

3 动态March算法

3.1 动态March算法的推导

经典的动态故障检测算法March RAW对一些单单元和二单元的动态故障能有效的检测，但是仍存在一些动态故障覆盖不完全，如dRDFn(“n”为连续读取操作的次数), dDRDF, dWDF, dCFdsww, dCFdrd, dCFwd等。为了覆盖难以检测的dRDFn，新算法采用了n次读操作的Hammer算法(对同一个存储单元重复进行读或写操作的算法)：{↑↓(w0，r0n);↑↓(w1，r1n)}，并且在March C+和March RAW算法的基础上进行改进，结合了这3种测试算法的优点，并添加了一些读写元素形成新的动态March算法——Dynamic-RAWC，新算法可以有效地覆盖上述故障类型。此外，动态March算法的构成形式和普通March型算法不同，在保留了经典的存储器测试算法符号的基础上，本文提出用加粗的方式来描述不同算法共享的算法元素，通过在读元素右上角所加的字母“n”表示用户可配置的读写次数，以这种方式来突出算法的运行顺序是灵活和可配置的，它可以在不同的用户需求下通过指令调整所需的算法元素。例如，当Dynamic-RAWC调整为March C+算法的读写元素时，算法的总体时间复杂度非常低；当用户判定存储器当前处于容易发生一些动态故障的情况下，将故障覆盖率设置成第1优先级时，用户也可以自定义使用高复杂度的测试算法元素来覆盖一些难以检测的动态故障。

Dynamic-RAWC分为Dynamic-RAWC1和Dynamic-RAWC2(下文简称RAWC1和RAWC2)，两种算法均包含动态切换的功能，具体描述见表3。RAWC2是RAWC1的改进版本，故障覆盖率更高。鉴于RAWC1的算法元素相对较少且结构和RAWC2一致，因此本文保留RAWC1以方便直观地进行动态March算法的状态转移图和功能展示，若非特殊说明，文中提到的Dynamic-RAWC默认为RAWC2。

表3描述的Dynamic-RAWC中加粗的元素是March C+ 的算法元素，动态March算法操作的关键是通过算法状态机的变换来选择是否运行非加粗的算法元素。通过MBIST电路中动态控制模块的R_Times信号可以控制Hammer算法的读操作元素。当 R_Times 值为默认值 1 时，不运行多次读取操作的 Hammer算法。当 R_Times 的值为 n(n>1)时，在默认读操作后重复此操作n–1 次。这样就可以根据表3中的算法描述来计算时间复杂度。加粗的算法元素(March C+)单独运行时，复杂度为14N，运行所有算法元素时，RAWC1和RAWC2的复杂度分别为{24N+2nN, (0

3.2 动态March算法的故障覆盖率

3.2.1 动态March算法对静态故障的检测

故障覆盖率是检验存储器测试算法有效性的核心指标之一，可用数学表达式定义为

其中， FC即 为测试算法的故障覆盖率，分子NDF表示该算法能够检测到的故障类型个数，分母TF表示列入统计的存储器故障类型个数。此表达式用来衡量存储器测试算法对存储器故障的检测效果。分析本文列举的几种对比算法的故障覆盖率，当分母的数值一定时，分子的数值越大，表示对故障的覆盖率越高，即算法对故障的检测效果越好。通过推导故障原语可以发现，March C+算法对于静态故障的检测并不能覆盖到WDF、CFsxwx以及CFwd等故障，而March RAW算法和本文提出的改进算法Dynamic-RAWC算法则可以很好地检测到。用故障原语来验证这一结论：WDF的故障原语为<0w0/↑/–>, <1w1/↓/–>，敏化操作为写一个与当前存储单元内存储值相同的逻辑值，而March C+的算法元素中没有此敏化操作。写干扰状态耦合故障(CFsxwx)和写破坏耦合故障(CFwd)均与WDF类似，敏化这类故障需写入与当前状态相同的值，而March C+缺少相关读写元素，因此测不到此类故障。不同March算法对其他各类静态故障的覆盖情况见表4。

表4 不同March算法的静态故障覆盖率

3.2.2 动态March算法对动态故障的检测

对于dDRDF, dWDF, dCFdsww, dCFdrd,dCFwd等动态故障，与March RAW相比，本文提出的Dynamic-RAWC算法对这些故障覆盖得更加全面，动态故障覆盖率达到80.9%，相比March RAW提升了31.3%。以dDRDF故障为例，该故障的故障原语为：, , x, y取值为0, 1。由故障原语可知，想要敏化此类故障，必须要在写操作或者读操作的基础上紧接着进行1次读操作，此时读出来的数据与实际的值相反，而实际的值已经发生了跳变，因此，需要额外再进行1次读操作，对4种情况的，March RAW可以很好地覆盖，但是对于2种情况的，March RAW的M1, M2, M3, M4虽然有连续两次的读操作，但是仍缺少了1次读操作，导致不能检测到该类故障，本文提出的算法M1, M2, M3,M4均有至少连续3次的读操作，因此可以有效检测到该类故障。

动态故障dCFdsww作为dCFds故障的子类，它的故障原语有16种情况，敏化操作为在写操作后紧接着再进行1次写操作。对应的故障原语为, x, y, t, z取值为0, 1。从故障原语可以看出，要想敏化此类故障，使受害单元的存储值翻转，就必须要对攻击单元连续进行两次写操作。表1中列举的其他算法都不满足敏化的条件，均没有包含连续的写操作，而提出的Dynamic-RAWC算法在M1，M2中均在第1次写入操作后又加入了1次写操作，然后紧跟1次读操作，从而可以测出该故障。M3, M4具有对称性，因此整个算法可以对不论是升序还是降序的耦合类型故障均有一定的覆盖。不同March算法对其他各类动态故障的覆盖情况见表5。

表5 不同March算法的动态故障覆盖率

从表4和表5的数据可以看出，提出的Dynamic-RAWC算法对列出的静态故障类型的覆盖率为100%，对列出的动态故障的覆盖率为80.9%。对于一些特殊的动态故障，特别是Dynamic-RAWC优于经典March RAW算法的故障检测结果，在表5中最后一列以粗体形式标出，可以直观看出，提出的动态March算法有效地提高了故障覆盖率。

3.3 动态March算法的MBIST电路实现

动态March算法 Dynamic-RAWC的功能基于有限状态机实现，算法状态机是MBIST电路最核心的部分。以Dynamic-RAWC1为例，该算法的状态转移图见图1。由图1可知，算法的初始状态为IDLE状态，MBIST电路开始运行和结束运行都会在该状态下循环等待指令，结束状态为DONE状态，该状态表示已执行完动态算法的所有元素，输出测试结束信号tst_done以及测试结果Fail_flag信号。如果输出的Fail_flag为1，则表示所测的存储器存在故障，同时诊断器工作，输出故障所在地址Fail_ADR，若Fail_flag为0，则表示未测出故障。图1中其余的状态元素都表示为对存储器的读或写操作。M0:↑↓(w0)表示对存储器进行升序或者降序(仿真中本算法选择升序)写0操作，每进行1次写0操作后，地址加1，当最后一个地址进行写0操作后，执行M1的操作{r0 w1 r1}或{r0 w0 r0nr0 w1 r1}，每当进行到算法元素的最后一个操作时，会进行1次判断，判断当前是否为最后地址，若为最后地址，则跳入下一个状态，若不为最后一个状态则地址加1或者减1，然后跳回该算法元素的第1个操作，以此类推。图1中算法元素M1和M2的R0操作下面的“repeat n-1 times”意味着在w0之后默认会进行1次读操作，之后重复读0的次数会根据设定的R_Times信号值自动减1。

图1 Dynamic-RAWC1算法状态转移图

动态算法执行的关键和独特之处，在于能够自定义选择算法元素，不同的选择结果所执行的测试算法也就不同，对故障的覆盖能力不同，最后的测试时间也就不尽相同。具体来说，从图1可以看出，读写操作由红色背景和绿色背景的两种元素表示，状态跳转的方向由红色箭头和黑色箭头来区分。绿色背景元素为共享的基础算法元素，红色背景元素的操作状态则是可选择的，该元素上的红色箭头表示了另一种算法路径，可以看出，无论是红色箭头所指向的算法路径还是黑色箭头指向的算法路径，都包含了公共的状态元素，这也是本文提出电路的特点，即两种算法共享大部分的电路元素。而传统的MBIST电路若想要实现多种算法的功能，必须设计多个算法状态机才能实现，这样会浪费多余的电路面积，相当于生成多个不同算法的BIST电路内嵌到芯片中。而提出的动态March算法，无需嵌入两个或多个MBIST电路，即可实现多重算法的功能。

以SRAM为测试对象，提出的动态March算法的MBIST电路实现结构如图2所示。整体电路由MBIST生成模块、动态控制器和SRAM Collar构成，MBIST生成模块由数据产生器、地址产生器、控制产生器、比较器和诊断器等模块构成，SRAM Collar由功能/测试信号选择器和SRAM构成。功能/测试信号选择器主要用于切换当前SRAM的工作模式，当Test_Mode为高电平时，SRAM的地址、数据、片选和写使能等信号由MBIST生成模块提供，若Test_Mode拉低，SRAM进入功能模式，MBIST电路将不工作。

图2 动态March算法的MBIST电路实现结构图

MBIST生成模块中的地址产生器和数据产生器模块用于生成SRAM的读写地址和读写数据，控制产生器用于生成SRAM的使能以及读写控制等信号，这3个产生器的数据均受动态March算法状态机控制。动态March算法状态机由20个状态构成，分为初始状态IDLE、结束状态DONE和18个读写状态，而这18个读写状态的跳转规则受动态控制器的控制。动态控制模块的动态控制器配合指令寄存器生成控制算法执行顺序的switch_alg信号和控制Hammer算法的读操作次数的R_times信号，通过用户指令可输出对应的控制信号来调配算法元素状态机，从而形成动态测试算法，用最适合的算法产生读写信号从而检测出当前最容易出现的故障，测试效率更高。比较器用于将从SRAM存储单元里读取的数据和预期的数据进行比对，若读出的数据和预期的数据不一致，则Fail_flag信号拉高，用以提示用户该SRAM存在故障。Fail_flag信号拉高会激活诊断器，诊断器结合地址产生器生成当前SRAM的故障地址，通过Fail_ADR信号输出。

算法状态机中的动态算法由10个算法元素构成(如图2所示)，不同算法元素的序号表示了初步的执行顺序。灰色标记的元素1：↑↓(w0)，元素2：↑(r0, w1, r1)，元素4：↑(r1, w0, r0)，元素6：↓(r0, w1, r1)，元素8：↓(r1,w0,r0)，元素10：↑↓(r0)为不同执行顺序所共享的算法元素；红色和绿色标记的元素3：↑(w0, w0, r0n, r0, r0, 0,r0)，元素5：↑(w1, w1, r1n, r1, r1, w1, r1)，元素7：↓(w0, w0, r0, r0, r0, w0, r0)，元素9：↓(w1,w1, r1, r1, r1, w1, r1)是可选择的算法元素，用于构成复杂度较高的测试算法。

根据电路的结构设计使用Verilog HDL语言编写完可重构MBIST电路的代码部分，然后用VCS和Verdi进行功能仿真，功能确认无误后，基于TSMC40nm的工艺库，使用DC工具进行电路综合，DC工具报出的电路面积见表6。综合后的报告显示，包含March C+和March RAW算法的对比BIST电路面积为543.48 μm2，提出的Dynamic-RAWC面积为228.45 μm2，面积节省了58%，加强了电路资源的利用率。

表6 不同MBIST电路的面积统计(μm2)

4 算法的仿真与FPGA功能验证

算法的数模混合仿真验证环境为VCS和FineSim。以dRDF4故障仿真为例，数模混合仿真的局部波形如图3所示，dRDF4是dRDFn当n=4时的情况，属于动态读干扰故障中的一种，即在同一地址下对某个单元执行写操作后马上执行4次连续的读操作，然后该单元的存储值节点上的值会发生翻转，使得从存储单元中读出错误的逻辑值。在本次仿真中，我们在addr[1]地址的存储单元内注入了该故障，故障注入的方式是在SRAM的spice网表中插入特定的短路或开路电阻来模拟实际物理缺陷，注入的故障导致存储节点“rt”的电压波动。图中标注的Fail_flag信号是算法是检测到故障的标志信号。用提出的动态March算法读出了错误的逻辑值，Fail_flag信号拉高，表示检测出了该故障。

图3 dRDF4故障的数模混合仿真局部波形图

对不同March算法进行功能仿真，就可以从具体的读写操作来解释算法是如何检测到某一类故障的。选择March C+和March RAW分别作为静态故障和动态故障检测算法的代表，图4和图5分别展示了2种算法对dRDF4故障的完整仿真过程。由于March C+和March RAW算法中没有连续4次读操作的敏化序列，因此无法敏化此类故障，从图中Fail_flag信号始终为低电平的仿真结果佐证了此结论。图6为本文提出的Dynamic-RAWC对dRDF4的功能仿真波形图，清晰地展示了算法中M0和M1元素的具体读写过程。动态控制模块中的R_Times的值设置为4，即第1个写操作紧跟在同一地址上执行的4个连续读操作之后。图6中M1元素的第4次读操作后Fail_flag变高，表示已经检测到故障。通过算法的仿真，可以看出动态March算法对动态故障的覆盖能力优于传统算法。

图4 March C+算法对dRDF4故障检测的算法功能仿真波形图

图5 March RAW算法对dRDF4故障检测的算法功能仿真波形图

图6 Dynamic-RAWC1算法对dRDF4故障检测的算法功能仿真波形图

为了验证提出算法的实际测试功能，在Xilinx Spartan 6 FPGA平台上复现了基于动态March算法的MBIST电路和传统测试算法的MBIST电路，并分别对1k×16位(其中，k代表2的10次方，乘号的左边为存储器的地址数，右边为每个地址上存储的数据位数)，32k×8位和256k×16位3种容量规格的SRAM芯片进行测试，测试波形使用逻辑分析仪进行采样捕获。测试时钟采用Spartan 6片上PLL的25M分频时钟，即算法的读写周期为40 ns。经过多组的重复实验，实测的算法功能波形与仿真结果一致，而基于FPGA对提出算法和传统算法的测试时间统计结果见表7。测试时间Talg定义为算法电路使能信号拉高的时间点t1与测试结束信号tst_done拉高的时间点t2的时间间隔：Talg=t2–t1。从表7的统计结果可以看出，时间复杂度越高的算法实际测试时间就越长，本文提出的算法的优势在于时间复杂度是随着调用的不同测试元素而动态调整的，测试时间不会过于冗长，对不同规格芯片的测试时间都在可控的范围内。

表7 基于FPGA不同测试算法对3种规格存储器的测试时间统计

5 结束语

本文提出了一种新型的动态March算法，这是一种结合了March C+，March RAW和Hammer算法的改进算法，该算法不同于传统的March算法，它可以动态选择算法元素来适应不同情况下的故障检测需求。提出的动态March算法具有较高的故障覆盖率，检测静态故障时的故障覆盖率为100%，检测动态故障时的故障覆盖率为80.9%，相较March RAW算法，动态故障覆盖率提升了31.3%。为了验证算法和电路的功能，利用FineSim和VCS进行了数模混合仿真以及利用FPGA对不同规格的SRAM进行了实测，对比了新算法和经典算法对动态故障的检测能力和测试时间开销，仿真和测试结果显示了动态March算法的有效性。