法律状态公告日
法律状态信息
法律状态
2018-09-07
未缴年费专利权终止 IPC(主分类):G01R31/3185 授权公告日:20140402 终止日期:20170921 申请日:20100921
专利权的终止
2014-04-02
授权
授权
2011-06-01
实质审查的生效 IPC(主分类):G01R31/3185 申请日:20100921
实质审查的生效
2011-04-13
公开
公开
技术领域
本发明涉及一种片上系统内嵌逻辑芯核测试调度方法,特别是一种多级排序算法运用于片上系统内嵌逻辑芯核测试调度的方法。
背景技术
由于逻辑芯核重用设计方法的使用,集成电路的设计规模和实现功能发生了突变,由原来超大规模集成电路(VLSI,Very Large Scale Integration Circuit)发展到目前的片上系统。但是,随着片上系统设计规模增大、功能复杂度提高,及设计周期缩短,一个严峻的问题日益显现,即片上系统的测试已成为阻碍片上系统发展的瓶颈性问题。有效降低片上系统的测试难度和测试成本,已成为提升片上系统综合竞争力的一个非常重要途径。
由于内嵌于SoC中的众多逻辑芯核在提供来源、电路结构和设计风格等方面存在复杂的多样性,传统的集成电路测试方法已不再胜任SoC的测试工作,必须使用SoC可测性设计(DFT,Design For Testability)方法来完成。目前,对SoC的测试主要是使用不同逻辑芯核提供者提供的测试图形完成相应内嵌逻辑芯核的测试。为此,必须在SoC可测性设计过程中建立起使各内嵌逻辑芯核可独立进行测试的测试环、SoC I/O端与各IP核间进行测试数据传递的测试寻访机制等可测性设计硬件架构。同时,为了进一步有效提高SoC测试资源利用率和减少SoC测试时间,还必须建立完善的测试调度策略。
测试调度实际包含如何确定片上系统内嵌逻辑芯核内测试链路成链和片上系统内嵌逻辑芯核测试调度两部分。当前,最普遍的做法就是对这两部分分别进行排序优化,独立对待。然而,必须注意的是这两部分事实上是紧密相关的,分别排序优化在各自的情况下是最优的,但两者的结合,也就是真正所要的结果并非最理想或最优化。因此,有必要研究一种用统一的多级排序算法一次性解决测试调度问题的方法,来有效解决与完善片上系统内嵌逻辑芯核的测试调度。
发明内容
本发明的目的在于提供一种多级排序算法运用于片上系统内嵌逻辑芯核测试调度的方法,能将片上系统内嵌逻辑芯核测试调度和逻辑芯核内测试链路成链两个以往相对独立的问题有效地统一解决,进而能够有效地降低片上系统的测试时间和测试开销。本发明操作方便,适用于各种以扫描链方式完成逻辑芯核可测性设计的片上系统。
为达上述目的,本发明采用下述技术方案:
一种多级排序算法运用于片上系统内嵌逻辑芯核测试调度的方法,通过SoC文件读入、设置排序深度和优先标准,运用多级排序算法,在逻辑芯核测试调度上获得最优的逻辑芯核测试调度结果,其特征在于操作步骤为:(1)调度矩阵Z建立与初始化、(2)调度矩阵Z行扩展、(3)调度矩阵Z行收缩、(4)调度矩阵Z总测试带宽-总测试时间(W-T)二维调度排序、(5)调度矩阵Z总测试带宽-调节因子(W-α)双重遍历和(6)报告生成;所述步骤(1)调度矩阵Z建立与初始化是:读取SoC文件,该文件符合ITC’02(International Test Conference 2002)制定的SoC文件格式,从中获取SoC中的逻辑芯核总数p,初始化调度矩阵Z,调度矩阵Z中的元素为测试链路成链对象,该对象具有逻辑芯核带宽w和逻辑芯核测试时间t的二维属性;所述步骤(2)调度矩阵Z行扩展是:通过设定测试链路成链排序深度m,对每一个逻辑芯核按特定算式形成m个测试链路成链对象,从而行扩展调度矩阵Z;所述步骤(3)调度矩阵Z行收缩是:通过设置优先标准,在各列上对m个测试链路成链对象按优先标准进行标量化排序,获得优先测试链路成链对象,丢弃其余测试链路成链对象,从而行收缩调度矩阵Z;所述步骤(4)调度矩阵Z总测试带宽-总测试时间(W-T)二维调度排序是:在给定总测试带宽和调节因子α条件下,对已行收缩的调度矩阵Z中的共p个测试链路成链对象进行总测试带宽-总测试时间(W-T)二维排序获得总测试时间T、测试并行数R、空闲率IR以及逻辑芯核测试调度策略等结果;所述步骤(5)调度矩阵Z总测试带宽-调节因子(W-α)双重遍历是:从已行收缩的调度矩阵Z中获取所有有效的总测试带宽W值和调节因子α值,通过对调度矩阵Z总测试带宽-总测试时间(W-T)二维调度排序进行总测试带宽-调节因子(W-α)双重遍历,从而获所有的结果,并按先总测试时间T再空闲率IR最后测试并行数R的优先级对结果进行排序,从而确定最终的唯一测试结果;所述步骤(6)报告生成为以上所有步骤操作过程中的各个细节和结果分别形成文本和图形报告。
上述步骤(1)调度矩阵Z建立与初始化是自动识别由ITC’02规定的SoC文件格式,获取逻辑芯核总数p,在内部建立具有p个表项的数据表,该数据表的各表项与初始为0行p列的调度矩阵Z各列进行关联,各表项都含有从SoC文件中提取的各项重要信息:输入端口数In,输出端口数Out,内部扫描链数n,各条扫描链长度{s1,..,sn},以及测试图形数tp;另外,所述调度矩阵Z建立与初始化(1)还具有对不符合文件格式的信息进行自动剔除、对不完整的重要信息进行自动缺省填补的能力,能够反复输入更新的SoC文件或其它待调度的SoC文件,在已输入SoC文件,且不再重新输入或关闭输入时,任何操作都不会破坏在其内部已建立的数据表和调度矩阵Z。
上述步骤(2)调度矩阵Z行扩展是根据所设定的排序深度m和逻辑芯核总数p对以下算式进行循环求解,
具体过程为:从具有p个表项的数据表中依次获取各个表项中的信息,代入以上算式求解决策变量aij、Ii、Oi,并对同一表项进行m次求解,每次求解时,逻辑芯核带宽w等于次数,结束循环求解后获得m×p个测试链路成链对象,各测试链路成链对象中的逻辑芯核带宽w属性在求解过程中已被确定,而另一属性逻辑芯核测试时间t由以下算式计算而来,
根据这m×p个测试链路成链对象对初始为0行p列的调度矩阵Z行扩展为m行p列,如以下算式所示:
同时,所述调度矩阵Z行扩展(2)能够反复设定排序深度m以获得新的调度矩阵Z。
上述步骤(3)调度矩阵Z行收缩是提供可自行设定的优先标准函数f(w,t),该函数以测试链路成链对象的逻辑芯核带宽w和逻辑芯核测试时间t属性作为参数;根据自行设定的优先标准函数对调度矩阵Z以列为单位进行标量化的升序重排,当未设置优先标准函数时,则根据缺省的优先标准函数f(w,t)=w×(w+t)对调度矩阵Z以列为单位进行标量化的升序重排,对重排后的调度矩阵Z丢弃第2行到第m行,使其退化到1行p列,如以下算式所示:
Z=[A1(w,t)A2(w,t)L Ai(w,t)L Ap(w,t)]。
上述步骤(4)调度矩阵Z总测试带宽-总测试时间(W-T)二维调度排序是对调度矩阵Z中共p个具有逻辑芯核带宽w和逻辑芯核测试时间t属性的测试链路成链对象,以w×t为指标,进行标量化降序排列,更新调度矩阵Z,如以下算式:
Z=[X1(w,t)X2(w,t)L Xi(w,t)L Xp(w,t)];
在给定的总测试带宽W下,根据以下算式求解决策变量bi,式中,α为调节因子,
根据求得的决策变量b,优先选取并行数个第一批测试链路成链对象,在调度矩阵Z上进行标记,将对应的索引号作为节点建立长度为R的总测试带宽(W)-总测试时间(T)二维排序链表,链表中的数据元素按对应的测试链路成链对象的逻辑芯核测试时间t属性降序排列,并为这R个对应的测试链路成链对象增加两对直角坐标信息(x1,y1)和(x2,y2),其关系如以下算式:
其中L(i)表示链表索引i到调度矩阵Z索引号的映射,同时内部建立四个控制变量e、l、u、v,e用于记录在链表中对应最小x2的链表索引、l为链表长度、u用于记录可用空余带宽并用算式计算,v用于记录空余带宽在直角坐标中的横轴位置;初始情况下,e为链表尾,l=R,u=W-y2L(R),v=0,随后将按照以下步骤完成剩余全部总测试带宽W-总测试时间T二维排序:
①在调度矩阵Z上未标记的测试链路成链对象中,按索引号增量寻找逻辑芯核带宽w小于控制变量u的测试链路成链对象Xf,一旦找到立刻停止寻找,在调度矩阵Z上进行标记,
将索引号f追加到二维排序链表的尾部,为该测试链路成链对象增加两对直角坐标信息(0,u-Xf(w))和(Xf(t),W),更新控制变量e、l、u、v;当l>R,将R更新为l;无论是否找到都执行步骤②。
②按①相同的方式寻找下一个Xf并标记,为该测试链路成链对象增加两对直角坐标信息(0,y1f)和(Xf(t),y1f+Xf(w)),如果e不在链表尾,则将索引号f紧插在链表位置e之后,此时,若x2L(e)>x2L(e+1),则y1f=y2L(e),同时用临时方法L-1(f)更新e,否则y1f=y2L(e)+u-Xf(w),且不更新e;如果e在链表尾,则将索引号f紧插在链表位置e之前,y1f=y2L(e-1),同时用临时方法L-1(f)更新e,随后执行步骤②;如果再也无法找到这样的Xf且调度矩阵未被标记满,则更新e(非临时方法)、l、u、v和R,再进入步骤③;如果调度矩阵被标记满,则结束排序过程。
③对u进行修正,如果e在链表头,则修正公式为u=y1L(e+1);如果e在链表中,则修正公式为u=y1L(e+1)-y2L(e-1);如果e在链表尾,则修正公式为u=W-y2L(e-1),继续执行步骤④。④按①相同的方式寻找下一个Xf并标记,将索引号f存入链表位置e,并为该测试链路成链对象增加两对直角坐标信息(v,y1f)和(v+Xf(t),y1f+Xf(w)),如果e在链表头,则y1f=0;如果e在链表尾,则y1f=W-Xf(w);如果e在链表中,此时,若x2L(e-1)>x2L(e+1),则y1f=y2L(e-1),否则,y1f=y1L(e+1)-Xf(w);如果不存在这样的Xf且调度矩阵未被标记满,则删除节点e,无论是否找到,只要调度矩阵未被标记满,则更新e(非临时方法)、l、v和R,再进入步骤③,否则结束排序过程。
上述步骤(5)调度矩阵Z总测试带宽-调节因子(W-α)双重遍历是通过对调度矩阵Z总测试带宽-总测试时间(W-T)二维调度排序进行总测试带宽-调节因子(W-α)双重遍历获得所有测试调度结果;其原因是:在进行总测试带宽-总测试时间(W-T)二维排序时,用于产生第一批测试链路成链对象的特定算式,其调节因子α仅在或(视通过以下算式求解出的αk是否含有0而定)个区间内会使第一批选择结果产生不同,这或个区间的端点可由以下算式求解获得,
另外,总测试带宽(W)的有效范围为从MAX(Xi(w))到SUM(Xi(w))的所有整数。因此,有限的总测试带宽(W)和调节因子(α)构成了总测试带宽-调节因子(W-α)双重遍历,其具体双重遍历方式为:总测试带宽(W)从MAX(Xi(w))开始逐次加1直至SUM(Xi(w))为止,在每一个值上,调节因子α逐次选取各个区间的中值,对于最后一个区间则以作为选取值;在获得所有测试调度结果之后,按先总测试时间(T)再空闲率(IR)最后测试并行数(R)的优先级对结果进行排序,从而确定最终的唯一测试调度结果;该测试调度结果中包含的信息有最终的总测试带宽(W)、最终的总测试时间(T)、最终的空闲率(IR)、最终的测试并行数(R)以及最终的逻辑芯核测试调度策略。
上述步骤(6)报告生成为所有其它步骤在操作过程中的各个细节和结果分别形成文本和图形报告,即为各个步骤的操作过程进行文本记录,记录中标明步骤源、操作名和操作数据;为各个步骤的操作结果进行文本报告生成和图形报告生成。
本发明与现有技术相比较,具有如下显而易见的优点:本发明针对片上系统可测性设计中的测试调度环节,研究了片上系统内嵌逻辑芯核测试调度方法的设计和实现,并运用多级排序算法将片上系统内嵌逻辑芯核测试调度和逻辑芯核内测试链路成链两个以往相对独立的问题有效地统一解决,进而能够有效地降低片上系统的测试时间和测试开销。
附图说明
图1是本发明一个实施例的步骤结构图。
图2是图1示例中调度矩阵Z建立与初始化的流程图。
图3是图1示例中调度矩阵Z进行行扩展的流程图。
图4是图1示例中调度矩阵Z进行行收缩的流程图。
图5是图1示例中调度矩阵Z进行总测试带宽-总测试时间(W-T)二维调度排序的流程图。
图6是图1示例中调度矩阵Z进行总测试带宽-调节因子(W-α)双重遍历的流程图。
具体实施方式
本发明的一个优先实施例是:参见图1,将多级排序算法运用于片上系统内嵌逻辑芯核测试调度的方法,其通过SoC文件读入、设置排序深度和优先标准,运用多级排序算法,在逻辑芯核测试调度上获得最优的逻辑芯核测试调度结果,操作步骤为(1)调度矩阵Z建立与初始化、(2)调度矩阵Z行扩展、(3)调度矩阵Z行收缩、(4)调度矩阵Z总测试带宽-总测试时间(W-T)二维调度排序、(5)调度矩阵Z总测试带宽-调节因子(W-α)双重遍历和(6)报告生成;步骤(1)调度矩阵Z建立与初始化是:读取SoC文件,该文件符合ITC’02(International TestConference 2002)制定的SoC文件格式,从中获取SoC中的逻辑芯核总数p,初始化调度矩阵Z,调度矩阵Z中的元素为测试链路成链对象,该对象具有逻辑芯核带宽w和逻辑芯核测试时间t的二维属性;步骤(2)调度矩阵Z行扩展是:通过设定测试链路成链排序深度m,对每一个逻辑芯核按特定算式形成m个测试链路成链对象,从而行扩展调度矩阵Z;步骤(3)调度矩阵Z行收缩是:通过设置优先标准,在各列上对m个测试链路成链对象按优先标准进行标量化排序,获得优先测试链路成链对象,丢弃其余测试链路成链对象,从而行收缩调度矩阵Z;步骤(4)调度矩阵Z总测试带宽-总测试时间(W-T)二维调度排序是:在给定总测试带宽和调节因子α条件下,对已行收缩的调度矩阵Z中的共p个测试链路成链对象进行总测试带宽-总测试时间(W-T)二维排序获得总测试时间T、测试并行数R、空闲率IR以及逻辑芯核测试调度策略等结果;步骤(5)调度矩阵Z总测试带宽-调节因子(W-α)双重遍历是:从已行收缩的调度矩阵Z中获取所有有效的总测试带宽W值和调节因子α值,通过对调度矩阵Z总测试带宽-总测试时间(W-T)二维调度排序进行总测试带宽-调节因子(W-α)双重遍历,从而获所有的结果,并按先总测试时间T再空闲率IR最后测试并行数R的优先级对结果进行排序,从而确定最终的唯一测试结果;步骤(6)报告生成为以上所有步骤操作过程中的各个细节和结果分别形成文本和图形报告。
参见图2,上述步骤(1)调度矩阵Z建立与初始化是:自动识别由ITC’02规定的SoC文件格式,获取逻辑芯核总数p,在内部建立具有p个表项的数据表,该数据表的各表项与初始为0行p列的调度矩阵Z各列进行关联,各表项都含有从SoC文件中提取的各项重要信息:输入端口数In,输出端口数Out,内部扫描链数n,各条扫描链长度{s1,..,sn},以及测试图形数tp;另外,上述调度矩阵Z建立与初始化(1)还具有对不符合文件格式的信息进行自动剔除、对不完整的重要信息进行自动缺省填补的能力,能够反复输入更新的SoC文件或其它待调度的SoC文件,在已输入SoC文件,且不再重新输入或关闭输入时,任何操作都不会破坏在其内部已建立的数据表和调度矩阵Z。
参见图3,上述步骤(2)调度矩阵Z行扩展是:根据所设定的排序深度m和逻辑芯核总数p对以下算式进行循环求解,
具体过程为:从具有p个表项的数据表中依次获取各个表项中的信息,代入以上算式求解决策变量aij、Ii、Oi,并对同一表项进行m次求解,每次求解时,逻辑芯核带宽w等于次数,结束循环求解后获得m×p个测试链路成链对象,各测试链路成链对象中的逻辑芯核带宽w属性在求解过程中已被确定,而另一属性逻辑芯核测试时间t由以下算式计算而来,
根据这m×p个测试链路成链对象对初始为0行p列的调度矩阵Z行扩展为m行p列,如以下算式所示:
同时,上述调度矩阵Z行扩展(2)能够反复设定排序深度m以获得新的调度矩阵Z。
参见图4,上述步骤(3)调度矩阵Z行收缩是:提供可自行设定的优先标准函数f(w,t),该函数以测试链路成链对象的逻辑芯核带宽w和逻辑芯核测试时间t属性作为参数;根据自行设定的优先标准函数对调度矩阵Z以列为单位进行标量化的升序重排,当未设置优先标准函数时,则根据缺省的优先标准函数f(w,t)=w×t×(w+t)对调度矩阵Z以列为单位进行标量化的升序重排,对重排后的调度矩阵Z丢弃第2行到第m行,使其退化到1行p列,如以下算式所示:
Z=[A1(w,t)A2(w,t)L Ai(w,t)L Ap(w,t)]。
参见图5,上述步骤(4)调度矩阵Z总测试带宽-总测试时间(W-T)二维调度排序是:对调度矩阵Z中共p个具有逻辑芯核带宽w和逻辑芯核测试时间t属性的测试链路成链对象,以w×t为指标,进行标量化降序排列,更新调度矩阵Z,如以下算式:
Z=[X1(w,t) X2(w,t)L Xi(w,t)L Xp(w,t)];
在给定的总测试带宽W下,根据以下算式求解决策变量bi,式中,α为调节因子,
根据求得的决策变量b,优先选取并行数个第一批测试链路成链对象,在调度矩阵Z上进行标记,将对应的索引号作为节点建立长度为R的总测试带宽(W)-总测试时间(T)二维排序链表,链表中的数据元素按对应的测试链路成链对象的逻辑芯核测试时间t属性降序排列,并为这R个对应的测试链路成链对象增加两对直角坐标信息(x1,y1)和(x2,y2),其关系如以下算式:
其中L(i)表示链表索引i到调度矩阵Z索引号的映射,同时内部建立四个控制变量e、l、u、v,e用于记录在链表中对应最小x2的链表索引、l为链表长度、u用于记录可用空余带宽并用算式计算,v用于记录空余带宽在直角坐标中的横轴位置;初始情况下,e为链表尾,l=R,u=W-y2L(R),v=0,随后将按照以下步骤完成剩余全部总测试带宽W-总测试时间T二维排序:
①在调度矩阵Z上未标记的测试链路成链对象中,按索引号增量寻找逻辑芯核带宽w小于控制变量u的测试链路成链对象Xf,一旦找到立刻停止寻找,在调度矩阵Z上进行标记,将索引号f追加到二维排序链表的尾部,为该测试链路成链对象增加两对直角坐标信息(0,u-Xf(w))和(Xf(t),W),更新控制变量e、l、u、v;当l>R,将R更新为l;无论是否找到都执行步骤②。
②按①相同的方式寻找下一个Xf并标记,为该测试链路成链对象增加两对直角坐标信息(0,y1f)和(Xf(t),y1f+Xf(w)),如果e不在链表尾,则将索引号f紧插在链表位置e之后,此时,若x2L(e)>x2L(e+1),则y1f=y2L(e),同时用临时方法L-1(f)更新e,否则y1f=y2L(e)+u-Xf(w),且不更新e;如果e在链表尾,则将索引号f紧插在链表位置e之前,y1f=y2L(e-1),同时用临时方法L-1(f)更新e,随后执行步骤②;如果再也无法找到这样的Xf且调度矩阵未被标记满,则更新e(非临时方法)、l、u、v和R,再进入步骤③;如果调度矩阵被标记满,则结束排序过程。
③对u进行修正,如果e在链表头,则修正公式为u=y1L(e+1);如果e在链表中,则修正公式为u=y1L(e+1)-y2L(e-1);如果e在链表尾,则修正公式为u=W-y2L(e-1),继续执行步骤④。
④按①相同的方式寻找下一个Xf并标记,将索引号f存入链表位置e,并为该测试链路成链对象增加两对直角坐标信息(v,y1f)和(v+Xf(t),y1f+Xf(w)),如果e在链表头,则y1f=0;如果e在链表尾,则y1f=W-Xf(w);如果e在链表中,此时,若x2L(e-1)>x2L(e+1),则y1f=y2L(e-1),否则,y1f=y1L(e+1)-Xf(w);如果不存在这样的Xf且调度矩阵未被标记满,则删除节点e,无论是否找到,只要调度矩阵未被标记满,则更新e(非临时方法)、l、v和R,再进入步骤③,否则结束排序过程。
参见图6,上述步骤(5)调度矩阵Z总测试带宽-调节因子(W-α)双重遍历是:通过对调度矩阵Z总测试带宽-总测试时间(W-T)二维调度排序进行总测试带宽-调节因子(W-α)双重遍历获得所有测试调度结果;其原因是:在进行总测试带宽-总测试时间(W-T)二维排序时,用于产生第一批测试链路成链对象的特定算式,其调节因子α仅在或(视通过以下算式求解出的αk是否含有0而定)个区间内会使第一批选择结果产生不同,这或个区间的端点可由以下算式求解获得,
另外,总测试带宽(W)的有效范围为从MAX(Xi(w))到SUM(Xi(w))的所有整数。因此,有限的总测试带宽(W)和调节因子(α)构成了总测试带宽-调节因子(W-α)双重遍历,其具体双重遍历方式为:总测试带宽(W)从MAX(Xi(w))开始逐次加1直至SUM(Xi(w))为止,在每一个值上,调节因子α逐次选取各个区间的中值,对于最后一个区间则以作为选取值;在获得所有测试调度结果之后,按先总测试时间(T)再空闲率(IR)最后测试并行数(R)的优先级对测试调度结果进行排序,从而确定最终的唯一测试调度结果;该测试调度结果中包含的信息有最终的总测试带宽(W)、最终的总测试时间(T)、最终的空闲率(IR)、最终的测试并行数(R)以及最终的逻辑芯核测试调度策略。
机译: 具有不对称处理器核的系统上的虚拟机和/或多级调度支持
机译: 可编程逻辑控制系统,可编程逻辑控制器,通信测试支持设备,通信测试支持方法以及在通信测试支持设备上可执行的计算机程序
机译: 使用设备上逻辑确定测试结果的用于在半导体设备上存储设备测试信息的方法和系统