Yield enhancement and manufacturing throughput of redundant memories by repairability/unrepairability detection

In this article, yield enhancement and manufacturing throughput of large repairable memories are analyzed. These objectives are met by repairability/unrepairability detection. Initially two new techniques for detection of memory chips with redundancy are presented. Initially, a heuristic, yet efficient approach is proposed. This first approach is based on finding a very good approximation to the minimum covering set. An algorithm, which executes in quadratic time with respect to the largest dimension of the memory, is presented. This algorithm is executed off-line, that is, when the memory has been fully diagnosed. New conditions for detection are presented and fully analyzed. These are based on a more accurate estimation of the regions of repairability and unrepairability. Hence, this results in a reduction of the uncertainty region, where the status of a memory cannot be established without executing a fully exhaustive search algorithm. The second approach to repairability/unrepairability detection is based on a more complex covering relationship, namely the generalized leading element. A model for manufacturing throughput of large repairable memories is presented.A new repair algorithm which utilizes a ternary tree approach, is also presented. This repair algorithm is perfect in the sense that it finds the optimal repair-solution (whenever one exists) after the memory has not been diagnosed unrepairable.Illustrative examples and simulation results show that considerable improvements for average and the worst-case analysis over existing techniques can be achieved.This research was supported in part by grants from AT&T and NATO.     

A Fast Redundancy Analysis Algorithm in ATE for Repairing Faulty Memories

Testing memory and repairing faults have become increasingly important for improving yield. Redundancy analysis (RA) algorithms have been developed to repair memory faults. However, many RA algorithms have low analysis speeds and occupy memory space within automatic test equipment. A fast RA algorithm using simple calculations is proposed in this letter to minimize both the test and repair time. This analysis uses the grouped addresses in the faulty bitmap. Since the fault groups are independent of each other, the time needed to find solutions can be greatly reduced using these fault groups. Also, the proposed algorithm does not need to store searching trees, thereby minimizing the required memory space. Our experiments show that the proposed RA algorithm is very efficient in terms of speed and memory requirements.     

免疫遗传算法及其应用研究

遗传算法是一种导向随机搜索算法,具有较强的全局搜索能力.为克服遗传算法盲目搜索、收敛速度慢的缺点,文章提出了免疫遗传混合算法.利用求解问题特征对遗传算法的种群进行免疫接种,以提高搜索速度.为检验混合算法的效率,给出了经典TSP问题的混合算法.实验结果表明,混合算法具有收敛速度快、搜索精度高、稳健性强的特点.     

无线传感网络布局的虚拟力导向微粒群优化策略

无线传感网络通常由固定传感节点和少量移动传感节点构成,动态无线传感网络布局优化有利于提高无线传感网络覆盖率和目标检测概率,是无线传感网络研究的关键问题之一.传统的虚拟力算法在优化过程中容易受固定传感节点的影响,无法实现全局优化.本文结合虚拟力算法和微粒群算法,提出一种面向无线传感网络布局的虚拟力导向微粒群优化策略.该策略通过无线传感节点间的虚拟力影响微粒群算法的速度更新过程,指导微粒进化,加快算法收敛.实验表明,虚拟力导向微粒群优化策略能快速有效地实现无线传感节点布局优化.与微粒群算法和虚拟力算法相比,虚拟力导向微粒群优化策略不仅网络覆盖率高,且收敛速度快,耗时少.     

Effect of Ag doping on the electrical properties of thermally deposited CdS–La2O3 TFTs

This paper describes a new approach for repairing memories. Repair is implemented by deletion of either rows and/or columns on which faulty cells lie. These devices are commonly referred to as redundant memories, because redundant columns and rows are added. A new repair technique and an algorithm are proposed. The algorithm is based on a fault-counting technique and on a reduced-covering approach. The innovative feature is that reduced covering permits an heuristic, but efficient, criterion to be included in the selection of the rows and/or columns to be deleted. This retains independence of the repair process on the distribution of faulty cells in memory, while allowing a good repairability/ unrepairability detection. The main benefits that result by using the proposed repair algorithm are a reduction in execution time to determine the repair-solution for the device under test and its suitability for implementation in a defect analysis system. Illustrative examples and theoretical results are provided to substantiate the validity of the proposed repair technique     

基于CortexTM-M3的机器人走迷宫的实现

为了实现机器人走迷宫的最优智能算法,提出了一种基于CortexTM-M3的具有记忆功能的设计方案,并且把传统的＂单步走＂上升为＂连续跑＂,使速度得到了几倍的提高。同时机器人神经自带纠错能力,能够自我调节,使系统鲁棒性得到大大提高。实验结果表明,该设计不仅能够完成一般算法所实现的走迷宫的目的,更在寻址、冲刺,及速度方面有着很大的优势。     

基于量子计算的用户识别算法

本文提出了基于量子算法的快速用户识别算法.当代社会进入互联网时代后,大量的信息充斥在网络上,许多有价值的信息被隐藏在Weblog中,大数据分析的一项任务就是通过对Weblog的分析得到用户行为模式等重要的信息,在这之前必须要做的是对用户进行识别.以往对用户识别算法的研究较为侧重在准确度方面,识别的速度尚不能令人满意.本文基于Grover搜索算法提出了扩展记录模式和非扩展记录模式的两种快速IP地址搜索算法,将搜索的查询复杂度进行了二次加速.     

一种数字系统综合中存储器规划的改进算法

用ＶＨＤＬ语言描述的数字系统中,经常使用大量的数组对应于真实系统中的存储器,减少存储器的操作时间对于提高整个系统的速度是一个非常有意义的问题,而改进存储器的地址生成技术是解决这个问题的途径之一。文章研究了一些与此相关的新技术＾「１」,但这些新技术的使用将增加一些 余的存储单元,特别是对于多数组问题。为此,提出了一种多启发式组合算法,以求同时达到尽量减小冗余量和提高计算速度的目的。     

一种基于禁忌搜索的全局最优化模糊聚类算法

模糊C均值（FCM）算法是一种基于贪心思想的迭代算法,算法沿迭代序列收敛到一个极小值,但存在搜索能力弱、易陷入局部最优的缺点.本文提出了一种基于禁忌搜索的模糊聚类算法,该算法在一个解的邻域内使用禁忌搜索,并采用了基于FCM局部收敛性质的长期表禁忌策略,保证在不断移动搜索起点的同时避免重复搜索;其次使用混沌优化思想与动态步长策略来提升算法的全局搜索能力,以达到获取全局最优解的目的.实验结果表明,改进算法极大地提高了聚类准确率,并具有良好的稳定性,与群智算法和遗传算法的优化相比也具有一定的优势.     

结合问题特征利用SE-Tree反向深度求解冲突集的方法

基于模型诊断是人工智能领域内的一个重要研究方向,求解极小冲突集在基于模型诊断中有着重要应用.在对结合CSISE-Tree求解冲突集方法深入研究的基础上,根据冲突集求解特征重构了结合枚举树的计算冲突集的过程,提出基于深度优先反向搜索求解冲突集的方法.针对CSISE-Tree方法求解时占用内存空间与元件总数指数级相关的缺点,构建反向深度搜索方法减小求解时所占用内存空间;针对CSISE-Tree方法不能对部分非极小的冲突集进行剪枝的问题,给出对非冲突集和更多非极小的冲突集进行剪枝的方法,有效减少了求解时调用SAT(Boolean SATisfiability problem)求解器的次数;实验结果表明,与CSISE-Tree方法相比,本文提出的方法求解效率有明显的提升,并避免了求解时的内存爆炸问题.     

基于禁止搜索的非线性时间匹配优化算法

动态时间规整算法DTW(Dynamic Time Warping)作为一种非线性时间匹配技术已成功地应用于语音识别系统中。DTW算法使用动态规划技术来搜索两个时间序列的最优规整路径,虽然这种算法计算量小,运算时间较短,但只是一种局部优化算法。禁止搜索TS(Tabu Search)算法是一种具有短期记忆的广义启发式全局搜索技术,适用于解决许多非线性优化问题。本文将该技术用于语音识别系统中,提出了基于禁止搜索的非线性时间规整的优化算法TSTW,使得时间规整函数尽可能逼近全局最优。仿真结果表明,TSTW比DTW有更高的识别率,且运行时间比遗传时间规整算法GTW大大减少。     

Polyclonal clustering algorithm and its convergence

Being characteristic of non-teacher learning, self-organization, memory, and noise resistance, the artificial immune system is a research focus in the field of intelligent information processing. Based on the basic principles of organism immune and clonal selection, this article presents a polyclonal clustering algorithm characteristic of self-adaptation. According to the core idea of the algorithm, various immune operators in the artificial immune system are employed in the clustering process; moreover, clustering numbers are adjusted in accordance with the affinity function. Introduction of the recombination operator can effectively enhance the diversity of the individual antibody in a generation population, so that the searching scope for solutions is enlarged and the premature phenomenon of the algorithm is avoided. Besides, introduction of the inconsistent mutation operator enhances the adaptability and optimizes the performance of local solution seeking. Meanwhile, the convergence of the algorithm is accelerated. In addition, the article also proves the convergence of the algorithm by employing the Markov chain. Results of the data simulation experiment show that the algorithm is capable of obtaining reasonable and effective cluster.     

Fair-efficient call admission control policies for broadbandnetworks-a game theoretic framework

A fundamental problem in connection oriented multiservice networks (ATM and STM) is finding the optimal policy for call acceptance. One seeks an admission control policy that efficiently utilizes network resources while at the same time being fair to the various call classes being supported. The theory of cooperative games provides a natural and precise framework for formulating such multicriterion problems as well as solution concepts. The authors describe how this framework can be used for analysis and synthesis of call admission strategies in broadband networks. In particular they investigate the Nash (1950), Raiffa-Kalai-Smorodinsky (Raiffa, 1953; Kalai and Smorodinsky, 1975), and modified Thomson (Cao, 1982) arbitration solutions from game theory. The performance of all solutions is evaluated by applying the value iteration algorithm from Markov decision theory. The approach is illustrated on a one-link network example for which the exact solutions can be achieved. The results indicate that the arbitration schemes from game theory provide some attractive features especially when compared to traditional control objectives: blocking equalization and traffic maximization. The authors also compare the optimal solutions with some simplified policies belonging to four different classes: complete sharing, coordinate convex, trunk reservation, and dynamic trunk reservation. The comparison indicates that in many cases, the trunk reservation and dynamic trunk reservation policies can provide fair, efficient solutions, close to the optimal ones     

Design and Experimental Evaluation of a Database-Assisted V2V Communications System Over TV White Space

In the past years, many works have demonstrated the applicability of Coarse-Grained Reconfigurable Array (CGRA) accelerators to optimize loops by using software pipelining approaches. They are proven to be effective in reducing the total execution time of multimedia and signal processing applications. However, the run-time reconfigurability of CGRAs is hampered overheads introduced by the needed translation and mapping steps. In this work, we present a novel run-time translation technique for the modulo scheduling approach that can convert binary code on-the-fly to run on a CGRA. We propose a greedy approach, since the modulo scheduling for CGRA is an NP-complete problem. In addition to read-after-write dependencies, the dynamic modulo scheduling faces new challenges, such as register insertion to solve recurrence dependences and to balance the pipelining paths. Our results demonstrate that the greedy run-time algorithm can reach a near-optimal ILP rate, better than an off-line compiler approach for a 16-issue VLIW processor. The proposed mechanism ensures software compatibility as it supports different source ISAs. As proof of concept of scaling, a change in the memory bandwidth has been evaluated. In this analysis it is demonstrated that when changing from one memory access per cycle to two memory accesses per cycle, the modulo scheduling algorithm is able to exploit this increase in memory bandwidth and enhance performance accordingly. Additionally, to measure area and performance, the proposed CGRA was prototyped on an FPGA. The area comparisons show that a crossbar CGRA (with 16 processing elements and including an 4-issue VLIW host processor) is only 1.11 × bigger than a standalone 8-issue VLIW softcore processor.     

Efficient variable partitioning and scheduling for DSP processors with multiple memory modules

Multiple on-chip memory modules are attractive to many high-performance digital signal processing (DSP) applications. This architectural feature supports higher memory bandwidth by allowing multiple data memory accesses to be executed in parallel. However, making effective use of multiple memory modules remains difficult. The performance gain in this kind of architecture strongly depends on variable partitioning and scheduling techniques. In this paper, we propose a graph model known as the variable independence graph (VIG) and algorithms to tackle the variable partitioning problem. Our results show that VIG is more effective than interference graph for solving variable partitioning problem. Then, we present a scheduling algorithm known as the rotation scheduling with variable repartition (RSVR) to improve the schedule lengths efficiently on a multiple memory module architecture. This algorithm adjusts the variable partitions during scheduling and generates a compact schedule based on retiming and software pipelining. The experimental results show that the average improvement on schedule lengths is 44.8% by using RSVR with VIG. We also propose a design space exploration algorithm using RSVR to find the minimum number of memory modules and functional units satisfying a schedule length requirement. The algorithm produces more feasible solutions with equal or fewer number of functional units compared with the method using interference graph.     

一种改进的时延受限低代价光组播路由算法

针对光网络时延受限光组播路由计算复杂度高的问题,提出一种基于改进的和声搜索求解时延受限光组播路由的算法。论文通过引入自适应的和声记忆保留率及微调概率提高和声算法搜寻到全局最优光组播树的能力;算法设计了一个能够保持备选光组播树多样性的动态适应度函数以扩大光组播路由的搜索范围;同时,算法在初始化和声库时采用精英保留策略简化和声迭代过程。仿真结果表明,提出的改进算法能够求得代价更低的光组播路由,且算法在较大光网络规模下具有较好的收敛稳定性。     

基于FPGA的空间存储器的纠错系统

国际空间站上AMS存储系统受到高能粒子的轰击,可能对随机存储器(RAM)电路产生影响,改变半导体存储器件的逻辑状态,导致存储单元在逻辑‘0’与‘1’之间发生翻转,产生一些关键存储数据出错和控制程序跑飞等问题。本文提出了基于纠错编码基本原理的BCH(31,16)算法,该算法能够有效解决三位随机错误的纠正问题,其译码算法采用错误图样查找法。利用Verilog DHL编程语言来设计BCH(31,16)码的编码与解码,并下载到FPGA开发板上进行电路验证。     

基于有限前缀扩展和多Hash函数的 动态IP路由查找算法

该算法根据IP路由表的分布特征将前缀有限扩展为三种长度,并用算法所提出的最大熵判定法选取多个Hash函数,将扩展后的前缀映射到三个Hash表的不同级别.在查找过程中算法根据三个Hash表的命中率动态计算查找代价,并据此调整对三个Hash表的搜索顺序.算法支持增量更新,适于软件实现和硬件流水实现.实验表明,对128K前缀的真实转发表算法仅约需3.7M字节,平均每次查找仅需约1.1次访存,而且路由更新时间较小.     

规范化分段线性化电阻网络多解的实用算法

本文采用虚区域的概念和解曲线的基本性质,提出了求规范化分段线性化电阻钢络多解的实用算法。它的特点是整个求解过程没有重复无效的迭代步骤,不论网络有多少个解,求出全部解的总迭代步骤数仅取决于定义域Rn由超平面分割而成的区域总数。它所依据的概念简单,易编程序,在一般微机上能解多个非线性元件的网络,比较实用。     

一种基于加速Dijkstra算法的图像分割技术

利用最短路径搜索算法中的Dijkstra算法进行图像分割。提出一种加速Dijkstra算法减小经典Dijkstra算法的运算量,以加快其运行速度。提出基于加速Dijkstra算法的Live-Wire图像分割方法勾画出一幅图像中感兴趣目标的轮廓并采用边界填充分割该目标。实验结果表明该算法能正确地进行图像分割,抗噪声性能好,与手工分割法相比交互次数较少,与原Live-Wire分割算法相比运行时间较短。