基于MAF模型的串扰时延故障的测试矢量生成

随着深亚微米技术,串扰噪声问题越来越严重。利用MAF模型的基本思想,探讨了一种串扰时延最大化算法,并且利用被修改的FAN算法,生成测试矢量。对于一条敏化通路,利用被修改的FAN算法适当地激活相应的攻击线和受害线,使电路在最恶劣情况下引起最大通路时延,从而实现更有效的时延测试。在标准电路ISCAS’85上进行实验验证,结果表明:该算法对于多攻击线的串扰时延故障的测试矢量产生是有效的。     

面向串扰时延效应的时序分析方法及在集成电路测试中的应用

随着特征尺寸进入纳米尺度,相邻连线之间的电容耦合对电路时序的影响越来越大,并可能使得电路在运行时失效.准确和快速地估计电路中的串扰效应影响,找到电路中潜在的串扰时延故障目标,并针对这些故障进行测试是非常必要的.文中提出了一种基于通路的考虑多串扰引起的时延效应的静态时序分析方法,该方法通过同时考虑临界通路及为其所有相关侵略线传播信号的子通路来分析多串扰耦合效应.该方法引入了新的数据结构"跳变图"来记录所有可能的信号跳变时间,能够精确地找到潜在的串扰噪声源,并在考虑串扰时延的情况下有效找到临界通路及引起其最大串扰减速效应的侵略子通路集.这种方法可以通过控制跳变图中时间槽的大小来平衡计算精度和运行时间.最后,文中介绍了在基于精确源串扰通路时延故障模型的测试技术中,该静态时序分析方法在耦合线对选择和故障敏化中的应用.针对ISCAS89电路的实验结果显示,文中提出的技术能够适应于大电路的串扰效应分析和测试,并且具有可接受的运行时间.     

串扰时延故障的SAT-ATPG算法研究

随着芯片运行速度不断提高,对串扰时延的测试已成为一个迫切需要解决的问题;文中提出一种面向多条攻击线的受害线上最大串扰噪声的测试生成方法;此方法建立了串扰通路时延故障模型、分析了布尔可满足性问题、讨论了七值逻辑,研究了串扰时延故障测试转换为CNF的逻辑表达式,在非鲁棒测试条件下约简CNF范式,并提出了串扰时延故障的SAT-ATPG算法;最后通过实例分析,对本文算法进行验证;结果表明:该算法对串扰时延故障的测试矢量的生成是有效的。     

基于SAT的串扰时延故障测试

随着深亚微米技术的不断发展和芯片运行速率的不断提高,串扰噪声问题越来越严重,对串扰时延测试已成为一个迫切的问题。在组合电路的基础上,将SAT（布尔可满足性）方法引入到串扰引起的时延测试中,通过词法分析和语法分析直接提取Verilog（硬件描述语言）源码的形式模型,组合成CNF（合取范式）形式。并在非鲁棒测试条件下,激活串扰时延故障,约简CNF范式表达式,最终输入SAT求解器得到测试矢量。在标准电路 ISCAS’85上进行实验验证,结果表明：该算法对于串扰时延故障的测试矢量产生是有效的。     

针对线间串扰现象的静态定时分析

超深亚微米工艺下，线间串扰是导致电路故障的主要原因之一。尽管可能导致故障的线间串扰的数量巨大，但真正会引起故障的线间串扰却相对较少。因此，如果能在对电路验证或测试前进行静态定时分析，找出那些导致电路故障的线间串扰，则可以有效提高测试生成效率，并降低测试成本。基于此目的，文章在静态定时分析中引入对线间串扰 扰现象的分析，在线时延模型的基础上使用重叠跳变对故障模型，只需要求出与最长通路的重叠跳变对即可。在对ISCAS89基准电路的实验中，各电路需要测试的串扰数平均减少至10％以下。相对于已发表的实验结果，本文的实验结果具有较高的CPU效率。     

考虑时延偏差的数字电路时延测试综述

先进集成电路工艺下,时延测试是数字电路测试的一项重要内容。各种时延偏差来源如小时延缺陷、工艺偏差、 串扰、电源噪声、老化效应等,影响着电路的额定时钟频率,是时延测试中需要考虑的因素。文章在介绍电路时延偏差 问题的各种来源的基础上,给出了针对不同的时延偏差问题所涉及的分析、建模、测试生成与电路设计等关键技术。进 一步介绍了中国科学院计算技术研究所近年来在考虑时延偏差的数字电路时延测试方面所做的研究工作,包括：考虑串 扰/电源噪声的时延测试、基于统计定时分析的测试通路选择、片上时延测量、超速测试、测试优化、在线时序检测等方 面。文章最后对数字电路时延测试技术的发展趋势进行了总结。     

微带线间远端串扰下电路板故障信号检测

在高精度电路板上,电路上的微带信号线路相邻很近.在工作中,由于线路过于接近,形成较强的微带线间远端串扰.这种串扰对电路本身的故障信号的波形造成感染,使得故障信号形成非正常的信号衰减形变.传统的电路故障检测方法在微带线间远端串扰的影响下,对衰减信号提取出现较为明显的失真,为后期的故障信号判断带来难度,降低了故障检测的准确率.提出一种关联信号特征提取的微带线间远端串扰下电路板故障信号检测的优化算法.利用小波变换对微带线感染信号进行滤波,利用卡尔曼算法对故障信号的主成分进行提取,运用主成分的差异特征完成了电路板的故障信号检测.实验结果表明,利用优化算法进行微带线间远端串扰下的电路板故障信号检测,能够极大的提高对故障信号检测的准确性.     

基于串扰影响的混合时序分析

针对产生串扰所需的耦合电容、信号翻转方向及时序信息，提出了包括串扰目标选择、串扰逻辑关系验证的混合时序分析算法。该算法在混合时序分析中引入测试生成，通过考察信号间的时序和逻辑关系来验证耦合电容处是否有串扰发生，并在串扰条件下验证电路的时序是否收敛。实验证明，该算法真实地反映了电路中串扰的分布情况，所得的延时分析结果也更为准确。     

用不同敏化方法提高超速测试的故障覆盖率

面向小时延缺陷(small delay detect,SDDs)的测试产生方法不仅要求测试产生算法复杂度低,还要尽可能地检测到小时延缺陷。超速测试避免了因测试最长敏化通路而带来的测试效率过低的问题,而且它要求测试向量按敏化通路时延进行分组,对每组分配一个合适的超速测试频率,再采用一种可快速、准确选择特定长度的路径选择方法来有效地提高测试质量。同时,文中首次通过优先选用单通路敏化标准对短通路进行检测,对关键通路有选择地进行非强健测试,相对采用单一的敏化方法,能以很小的时间代价提高含有小时延缺陷的结点的跳变时延故障覆盖率(TDF)。在ISCAS’89基准电路中对小时延缺陷的检测结果表明:用不同敏化方法进行测试产生,能在低的cpu时间里取得更高的跳变时延故障覆盖率。     

可逆电路的符号综合方法

描述一种基于矩阵模型和符号代数理论的可逆电路的综合方法,其中考虑到面积、时延、串扰等约束.实验结果已清楚地表明了利用这种启发式算法与现有的综合方法相比,在面积上所得结果近似,而总串扰得到了明显的改善.并且其路径时延要减少5%到20%之多.这种综合方法大大的改善了电路的性能,并且对输入输出较多的可逆电路的综合具有潜在的优势.     

Delay Control and Parallel Admission Algorithms for Real-Time Anycast Flow

An anycast flow is a flow that can be connected to any one of the members in a group of designated (replicated) servers (called anycast group). In this paper, we derive a set of formulas for calculating the end-to-end delay bound for the anycast flows and present novel admission control algorithms for anycast flows with real-time constraints. Given such an anycast group, our algorithms can effectively select the paths for anycast flows' admission and connection based on the least end-to-end delay bounds evaluated. We also present a parallel admission control algorithm that can effectively calculate the available paths with a short delay bound for different destinations in the anycast group so that a best path with the shortest delay bound can be chosen.     

长链树状无线传感器网络中遗传蚁群路由优化算法

为提高长链树状无线传感器网络的服务质量(QoS),本文用云遗传蚁群网络算法对无线传感器网络路由进行优化.算法中将正向蚂蚁根据节点负载情况发现的可行路径作为遗传算法的初始种群进行染色体编码,用路径时延、跳数及链路质量定义的适应度函数对染色体进行评价;利用正态云发生器实现路径的交叉和变异操作,逆向蚂蚁对优化后的路径进行信息素更新.仿真结果表明该路由算法能够满足无线传感器网络的实时性、可靠性等方面的要求,实现了网络的负载平衡及拥塞控制机制.     

A route pre-computation algorithm for integrated services networks

We provide an algorithm for computing best paths on a graph where edges have a multidimensional cost, one dimension representing delay, the others representing available capacity. Best paths are those which guarantee maximum capacity with least possible delay. The complexity of the algorithm is of the order ofO(V ³) in the bidimensional case, for a graph withV vertices. The results can be used for routing connections with guaranteed capacity in a communication network.     

一个有效的延迟费用受限的多路径算法

在集成网络中,服务质量(QoS)的一个重要方面是寻找满足端到端约束的可行路径,从而有效利用网络资源。考虑端到端的延迟约束和传输费用,对宽度优先算法(BFS)进行扩展,提出了满足延迟约束多路径算法K_DCP,并对其进行改进,得到多路径算法K_EDCP。仿真结果显示,两种算法性能良好。     

A tool for computing computer network reliability

The computation of the reliability of a computer network is one of the important tasks of evaluating its performance. The idea of minimal paths can be used to determine the network reliability. This paper presents an algorithm for finding the minimal paths of a given network in terms of its links. Then, it presents an algorithm for calculating the reliability of the network in terms of the probabilities of success of the links of its minimal paths. The algorithm is based on a relation that uses the probabilities of the unions of the minimal paths of the network to obtain the network reliability. Also, the paper describes a tool that has been built for calculating the reliability of a given network. The tool has two main phases: the minimal paths generation phase, and the reliability computation phase. The first phase accepts the links of the network and their probabilities, then implements the first proposed algorithm to determine its minimal paths. The second phase implements the second proposed algorithm to calculate the network reliability. The results of using the tool to calculate the reliability of an example network are given.     

Selected Crosstalk Avoidance Code for Reliable Network-on-Chip

With the shrink of the technology into nanometer scale, network-on-chip (NOC) has become a reasonable solution for connecting plenty of IP blocks on a single chip. But it suffers from both crosstalk effects and single event upset (SEU), especially crosstalk-induced delay, which may constrain the overall performance of NOC. In this paper, we introduce a reliable NOC design using a code with the capability of both crosstalk avoidance and single error correction. Such a code, named selected crosstalk avoidance code (SCAC) in our previous work, joins crosstalk avoidance code (CAC) and error correction code (ECC) together through codeword selection from an original CAC codeword set. It can handle possible error caused by either crosstalk effects or SEU. When designing a reliable NOC, data are encoded to SCAC codewords and can be transmitted rapidly and reliably across NOC. Experimental results show that the NOC design with SCAC achieves higher performance and is reliable to tolerate single errors. Compared with previous crosstalk avoidance methods, SCAC reduces wire overhead, power dissipation and the total delay. When SCAC is used in NOC, it can save 20% area overhead and reduce 49% power dissipation.     

A tree-based particle swarm optimization for multicast routing

QoS multicast routing is a non-linear combinatorial optimization problem. It tries to find a multicast routing tree with minimal cost that can satisfy constraints such as bandwidth, delay, and delay jitter. This problem is NP-complete. The solution to such problems is often to search first for paths from the source node to each destination node and then integrate these paths into a multicast tree. Such a method, however, is slow and complex. To overcome these shortcomings, we propose a new method for tree-based optimization. Our algorithm optimizes the multicast tree directly, unlike the conventional solutions to finding paths and integrating them to generate a multicast tree. Our algorithm also applies particle swarm optimization to the solution to control the optimization orientation of the tree shape. Simulation results show that our algorithm performs well in searching, converging speed and adaptability scale.