3D SoC测试结构优化与测试调度的博弈模型

硅通孔技术是实现三维系统芯片的一种新兴的方法.而作为测试基础,测试访问机制和测试外壳则方便了三维系统芯片模块化测试,测试结构优化问题是研究的热点.提出基于博弈论的3D SoC测试结构优化技术,使基于核的三维系统芯片测试时间最少,TAM带宽最大,并且满足TSV数目约束.提出的方法利用二人合作博弈论方法的优点,对测试结构和测试调度问题进行建模,给出了基于博弈实现3D SoC测试结构优化的算法.用ITC02 SoC测试基准电路搭建成堆叠SoC,并在其上对提出的算法进行了模拟.实验结果显示,与之前的2D IC上开发的方法相比较,本文提出的测试结构优化与测试调度方法结果更优越.     

基于量子进化算法的层次型SOC测试结构优化

以减少系统芯片SOC测试时间为目标,研究了层次型SOC的多层次TAM优化问题。根据嵌入式IP核的分类,将层次型SOC测试结构优化转变成了平铺型SOC测试结构优化,并建立了基于量子进化算法的数学模型。通过对群体的观测,决定IP核在测试访问机制上的分配以及当前群体中的最佳个体,实现了包含TAM-ed且wrapped的嵌入式核的层次型SOC测试结构优化。针对国际标准片上系统芯片验证表明,与GA、ILP和启发式算法相比,该算法能够获得更短的测试时间。     

功耗限制下SOC互联总线测试完整性故障的结构的优化

本文提出了一种SOC互联总线测试完整性故障的结构优化方法,本方法是在功耗限制下通过分配TAM使测试时间最小,从而优化了系统测试结构。本文先对测试测试集进行二维压缩分割SI测试集成几个SI组初始化测试结构,为每个核分配一位TAM,通过为每个的TAM进行计算后找出关键TAM,再通过在功耗限制下,反复分配空闲TAM给关键TAM和共享TAM的方法进行测试时间的减少。对ITC‘02的试验结果表明,本方法能在功耗限制下大大减少了SOC测试时间。     

3D SoC并行测试中TAM调度优化设计

提出了一种在功耗及测试并行性约束下三维片上系统（System on Chip,SoC）绑定中测试阶段并行测试的优化策略,通过最大限度地利用测试访问机制（Test Access Mechanism,TAM）资源,大大减少了测试时间,降低了测试成本。在3D SoC的测试过程中系统TAM资源十分有限,通过设计相应的测试外壳结构,对系统当前状态下空闲的TAM资源与待测芯核内部扫描链进行重新分配,使待调度的芯核提前进入测试阶段,减少了并行测试过程中的空闲时间块。在该结构基础上调整各芯核调度顺序,使测试过程满足各项约束条件。在ITC’02电路上的实验结果表明,在同样的功耗约束及测试并行性约束条件下,所提方法与现有方法相比更有效地降低了测试时间。     

基于双核扫描链平衡的SoC测试调度

由于芯核的测试时问与芯核内最长扫描链的长度成正比,通过将ScC中的芯核进行成对匹配,使双芯核内最长的扫描链比两个单芯核内最长的扫描链短,从而缩短测试时间．利用粒子群优化算法和分合策略,高效地匹配芯核、设置芯核的测试顺序并分配测试总线,以获得优化的测试计划．在ITC’02基准SoC集上的实验结果表明,相对于其他基于单核扫描链平衡的测试调度技术而言,文中的测试调度技术能获得具有最短测试时间的测试计划．     

复用NoC测试SoC内嵌IP芯核的测试规划研究

测试规划是SoC芯片测试中需要解决的一个重要问题。一种复用片上网络测试内嵌IP芯核的测试规划方法被用于限制测试模式下SoC芯片功耗不超出最大芯片功耗范围,消除测试资源共享所引起的冲突,达到减小测试时间的目的。提出了支持测试规划的无拥塞路由算法和测试扫描链优化配置方法。使用VHDL硬件描述语言实现了在FPGA芯片中可综合的二维Mesh片上网络测试平台,用于片上网络性能参数、路由算法以及基于片上网络的SoC芯片测试方法的分析评估。     

SoC测试中低成本、低功耗的芯核包装方法

提出一种SoC测试中新颖的并行芯核包装方法（parallel core wrapper design,pCWD）,该包装方法利用扫描切片重叠这一特点,通过缩短包装扫描链长度来减少测试功耗和测试时间．为了进一步减少测试时间,还提出了一种测试向量扫描切片划分和赋值算法．实验结果表明,针对ITC2002基准SoC集中d695芯片,应用并行包装方法和测试向量切片划分及赋值算法,能够减少50％的测试时间及95％的测试功耗．     

SoC测试调度的进程代数模型

功耗约束下的SoC核流水测试可避免过高功耗毁坏待测芯片,对SoC核的流水测试进行调度可合理地分配测试资源、减少测试时间.以进程代数为理论基础,提出了一种SoC核流水测试的测试调度方法.通过建立并发测试进程的时间标记变迁系统模型,形成了将前者转化为共享资源的通信代数(ACSR)描述的几个定理;建立了SoC测试调度模型;将核的流水测试映射为并发执行的进程、把测试资源建模为ACSR资源,用优先级解决测试冲突,使得功耗约束下的测试获得最大并行性,同时使测试应用时间最小.实验结果证明进程代数ACSR在处理SoC测试调度问题方面优于已有的经典算法.     

面向测试优化的片上网络映射算法

针对复杂片上系统(SoC)芯片的片上网络(NoC）映射方案未考虑测试需求的问题,提出了一种面向测试优化的NoC映射算法,兼顾了可测性的提升和映射开销的最小化。该映射方案首先依据特定的测试结构,使用划分算法进行片上系统所有IP核的测试分组,其优化目标为测试时间最短;之后,再基于分组内IP核之间的通信量,应用遗传算法实现NoC映射,其优化目标是在测试优化的基础上实现映射开销最小。通过多个ITC'02测试基准电路进行的实验结果表明:应用该方案后,测试时间平均减少12.67%;与随机任务映射相比,映射代价平均减少24.5%。     

SoC测试中IP核透明路径的构建

大量IP核复用于SoC中,给IP核的测试复用带来困难。该文给出一种基于透明路径的测试访问机制构建方法,对PARWAN处理器构建透明路径。实验结果表明,增加透明路径后的PARWAN处理器只增加少量占用的资源。将构建了透明路径的PARWAN处理器作为测试访问机制应用干SoC中,对其他IP核进行测试,能减少测试向量施加时间。     

High speed ant colony optimization CMOS chip

Ant colony optimization (ACO) is an optimization computation inspired by the study of the ant colonies’ behavior. This paper presents design and CMOS implementation of the ant colony optimization based algorithm for solving the TSP problem. In order to implement ant colony optimization algorithm in CMOS, we will present a new algorithm. This algorithm is based on the original ant colony optimization but it can be implemented in CMOS. Briefly, pheromone matrix is transformed on the chip area and ants move up-down through the pheromone matrix and they make their decisions. Finally ants select a global path. In previous researches only pheromone values is used, but select the next city in this paper is based on heuristics value and pheromone value. In definition of problem, we use heuristics value as a matrix. Previous researches could not be used for wide type of optimization problem but our chip gives heuristics value initially and we can change initial value of heuristics value according to the optimization problem so this capability increases the flexibility of ACO chip. Simple circuit is used in blocks of our chip to increase the speed of convergence of ACO chip. We use Linear Feedback Shift Register (LSFR) circuit for random number generator in ACO chip. ACO chip has capability of solving the big TSP problem. ACO chip is simulated by HSPICE software and simulation results show the good performance of final chip.     

基于文化的连续蚂蚁优化算法的研究*

针对蚂蚁优化算法在求解连续空间问题方面的缺陷,提出一种基于文化的连续蚂蚁优化算法。该算法将蚂蚁优化算法纳入文化算法的框架,组成基于蚂蚁优化算法的主群体和信念的两大空间。在知识和群体层面使用双重进化机制支持问题的求解和知识的提取,从而充分利用精英蚂蚁所携带的特征信息,在很大程度上提高了收敛速度,增强了搜索的多样性。实验结果表明,该算法求解速度快、寻优成功率高,是一种提高蚂蚁优化算法性能的有效算法。     

基于蚁群算法车辆导航系统路由选择问题的研究

利用蚁群运动的遍历性、随机性和规律性特点,分析了车辆导航系统路由选择问题的蚁群优化算法,仿真结果 表明该方法是一种简单有效的算法。     

改进的重叠蚁群优化算法

针对蚁群优化算法在进行全局最优解搜索时容易陷入局部最优解和收敛速度缓慢等缺陷,提出了一种有效求解全局最优解搜索问题的重叠蚁群优化算法。该算法通过设置多个重叠的蚁群系统,并对每一个蚁群初始化不同的参数,之后在蚁群之间进行信息素的动态学习,增强了不同蚁群对最优解的开采能力,避免了算法出现早熟现象。仿真实验结果表明,重叠蚁群优化算法在避免陷入局部最优解方面具有良好的效果,是一种提高蚁群算法性能的有效的改进算法。     

求解多处理机调度问题的蚁群算法

蚁群算法是受自然界中的蚂蚁觅食行为启发而设计的智能优化算法，特别适合处理离散型的组合优化问题。提出一种求解多处理机调度的蚁群算法,利用一个蚂蚁代表一个处理机来选择任务，并通过分析关键路径及每个任务的最早、最迟开始时间来确定每个任务的紧迫程度，让蚂蚁以此来选择任务。实验证明，该算法可比传统算法取得有更好运行效率的调度策略。     

Improved auto control ant colony optimization using lazy ant approach for grid scheduling problem

An auto controlled ant colony optimization algorithm controls the behavior of the ant colony algorithm automatically based on a priori heuristic. During the experimental study of auto controlled ACO algorithm on grid scheduling problem, it was observed that the induction of lazy ants not only reduces the time complexity of the algorithm but also produces better results on the given objectives. Lazy ants are basically a mutated version of active ants that remain alive till the fitter lazy ants are generated in the successive generations. This work presents an improved auto controlled ACO algorithm using the lazy ant concept. Performance study reveals the efficacy and the efficiency achieved by the proposed algorithm. A comparative study of the proposed method with some other recent meta-heuristics such as auto controlled ant colony optimization algorithm, genetic algorithm, quantum genetic algorithm, simulated annealing and particle swarm optimization for grid scheduling problem exhibits so.     

基于粒子群优化的蚁群算法在TSP中的应用

结合粒子群算法的问题,提出用混合蚁群算法来求解著名的旅行商问题.问题的核心是应用粒子群算法对蚁群算法的控制参数:启发式因子、信息素挥发系数、随机性选择阈值进行优化,以及运用蚁群系统算法寻找最短路径.新算法对于蚂蚁算法中的参数调整大大减低,减少了大量盲目的实验,力求在开发最优解和探究搜索空间上找到平衡点.对旅行商问题的仿真实验表明,新算法的优化质量和效率都优于传统蚁群算法和遗传算法,接近理论最佳值.新算法也可推广用于其他NP问题的求解.     

GACO – A HYBRID ANT COLONY OPTIMIZATION METAHEURISTIC FOR THE DYNAMIC LOAD-BALANCED CLUSTERING PROBLEM IN AD HOC NETWORKS

We present the design of a novel hybrid genetic ant colony optimization (GACO) metaheuristic. Genetic ant colony optimization is designed to address the dynamic load-balanced clustering problem formulated from ad hoc networks. The main algorithm in GACO is ACO. Whenever an environment change occurs (i.e., nodes move), it makes use of a genetic algorithm to quickly achieve adaptation by refocusing the search process around promising areas of the search space induced by the new problem structure. Compared to other ACO approaches for dynamic problems, GACO does not depend on any problem-specific heuristics to repair or deconstruct solutions. Genetic ant colony optimization also does not require the knowledge of the specific changes that occurred. We compare GACO with three other adaptation methods, namely, P-ACO, PAdapt, and GreedyAnts. P-ACO is a population-based ACO approach that invokes a repair algorithm on its population of solutions when an environment change occurs. PAdapt works by adapting the values of major ACO parameters, while GreedyAnts employs a group of ants that construct solutions in a greedy manner. Empirical results show that GACO is able to react and recover faster from any performance degradation. Genetic ant colony optimization also produces better solutions within the allowable recovery window. These results are shown to be statistically significant.     

时间依赖型车辆路径问题的一种改进蚁群算法

时间依赖型车辆路径规划问题(TDVRP),是研究路段行程时间随出发时刻变化的路网环境下的车辆路径优化.传统车辆路径问题(VRP)已被证明是NP-hard问题,因此,考虑交通状况时变特征的TDVRP问题求解更为困难.本文设计了一种TDVRP问题的改进蚁群算法,采用基于最小成本的最邻近法(NNC算法)生成蚁群算法的初始可行解,通过局部搜索操作提高可行解的质量,采用最大--最小蚂蚁系统信息素更新策略.测试结果表明,与最邻近算法和遗传算法相比,改进蚁群算法具有更高的效率,能够得到更优的结果;对于大规模TDVRP问题,改进蚁群算法也表现出良好的性能,即使客户节点数量达到1000,算法的优化时间依然在可接受的范围内.     

Search bias in ant colony optimization: on the role of competition-balanced systems

One of the problems encountered when applying ant colony optimization (ACO) to combinatorial optimization problems is that the search process is sometimes biased by algorithm features such as the pheromone model and the solution construction process. Sometimes this bias is harmful and results in a decrease in algorithm performance over time, which is called second-order deception. In this work, we study the reasons for the occurrence of second-order deception. In this context, we introduce the concept of competition-balanced system (CBS), which is a property of the combination of an ACO algorithm with a problem instance. We show by means of an example that combinations of ACO algorithms with problem instances that are not CBSs may suffer from a bias that leads to second-order deception. Finally, we show that the choice of an appropriate pheromone model is crucial for the success of the ACO algorithm, and it can help avoid second-order deception.