Test Scheduling of NoC‐Based SoCs Using Multiple Test Clocks

Network‐on‐chip (NoC) is an emerging design paradigm intended to cope with future systems‐on‐chips (SoCs) containing numerous built‐in cores. Since NoCs have some outstanding features regarding design complexity, timing, scalability, power dissipation and so on, widespread interest in this novel paradigm is likely to grow. The test strategy is a significant factor in the practicality and feasibility of NoC‐based SoCs. Among the existing test issues for NoC‐based SoCs, test access mechanism architecture and test scheduling particularly dominate the overall test performance. In this paper, we propose an efficient NoC‐based SoC test scheduling algorithm based on a rectangle packing approach used for current SoC tests. In order to adopt the rectangle packing solution, we designed specific methods and configurations for testing NoC‐based SoCs, such as test packet routing, test pattern generation, and absorption. Furthermore, we extended and improved the proposed algorithm using multiple test clocks. Experimental results using some ITC’02 benchmark circuits show that the proposed algorithm can reduce the overall test time by up to 55%, and 20% on average compared with previous works. In addition, the computation time of the algorithm is less than one second in most cases. Consequently, we expect the proposed scheduling algorithm to be a promising and competitive method for testing NoC‐based SoCs.     

基于聚类的异步时钟SoC测试

为进一步减少片上系统(System-on-Chip,SoC)测试耗时、降低测试成本,本文结合异步时钟测试机制,提出一种基于聚类的测试调度方法.该方法利用了SoC各测试的特征以及异步时钟测试的特点,对测试数据进行预处理.在ITC'02基准SoC集上,将本文方法与未采用异步时钟机制以及基于混合整型线性规划模型求解的方法进行对比.结果表明,本文的方法分别能平均减少测试耗时20.39％和5.53％,提升了调度算法的优化效率.并且在功耗约束较强时,最终调度结果与耗时下界仅相差0.9％.     

一种峰值功耗约束下的SoC蚁群测试调度算法

基于扫描链技术的SoC芯片测试可产生比正常使用模式下更大的功耗,这将会对器件可靠性产生不利影响,故在测试时需要将芯片测试功耗控制在允许峰值功耗之下.文中采用蚁群优化思路设计SoC测试调度算法,用于在峰值功耗和TAM总线最大宽度约束下降低SoC测试时间.实验结果表明,本方法优于先前已发表的相关方法.     

行为综合功能流水线中的负载平衡蚁群调度算法

在专用集成电路高层次综合中,功能流水线是提高算法描述执行速度的关键技术.针对时间约束和资源约束的两类行为综合功能流水线调度问题,提出了一种基于蚁群优化(ACO)的调度算法.LB-ACO算法将ACO算法与力向算法相结合,使用修改的力向公式定义局部试探因子,用个体调度结果的质量来更新全局试探因子.实验结果表明,LB-ACO算法在保证较低的时间复杂度O(cn2)的前提下,获得接近最优的调度结果.     

A Modified Dynamic Weighted Round Robin Cell Scheduling Algorithm

In this paper, we propose the modified dynamic weighted round robin (MDWRR) cell scheduling algorithm, which guarantees the delay property of real‐time traffic and also efficiently transmits non‐real‐time traffic. The proposed scheduling algorithm is a variation of the dynamic weighted round robin (DWRR) algorithm and guarantees the delay property of real‐time traffic by adding a cell transmission procedure based on delay priority. It also uses a threshold to prevent the cell loss of non‐real‐time traffic that is due to the cell transmission procedure based on delay priority. Though the MDWRR scheduling algorithm may be more complex than the conventional DWRR scheme, considering delay priority minimizes cell delay and decreases the required size of the temporary buffer. The results of our performance study show that the proposed scheduling algorithm has better performance than the conventional DWRR scheme because of the delay guarantee of real‐time traffic.     

基于遗传算法的片上多处理器任务调度策略研究

针对在片上多处理器上任务调度的特征,提出了一种基于立体编码的遗传算法。采用适合片上多处理器结构的三维立体编码,使计算节点之间的距离得到了描述,结合提出的个体适应度函数计算公式,使通信代价较小的调度策略优先得到选择,从而通过减少因结点间距离产生的通信开销降低了总的任务完成时间。此外,对算法结构、遗传算子进行了改进提出了内部二维交叉算子,加速了算法的收敛。仿真实验结果表明立体编码的遗传算法能够有效地对任务进行分配和调度,较之传统遗传算法具有较好的性能。     

面向异构信号处理平台的负载均衡算法

针对当前异构信号处理平台中信号处理应用的调度算法优化目标单一且调度结果中处理器负载不均衡的问题，提出了一种基于蚁群优化算法的负载均衡算法。该算法结合蚁群优化算法的快速搜索能力和组合优化能力，以信号处理应用的调度长度和处理器负载均衡为优化目标，对初始信息素矩阵和蚂蚁的遍历顺序进行改进，提出调度长度启发因子和负载均衡启发因子对处理器选择公式进行改进，利用轮盘赌策略确定信号处理应用各子任务分配的处理器，完成信号处理应用的调度。仿真结果表明，该算法得到调度结果在调度长度和负载均衡方面均有改进，可以充分发挥各处理器性能，提高异构信号处理平台的整体效率。     

A slot‐based BS scheduling with maximum latency guarantee and capacity first in 802.16e networks

The IEEE 802.16e standard specifies the QoS support at the MAC level for wireless broadband access network. To meet the QoS requirements, an efficient scheduling algorithm at base station (BS), which is not defined in the standard, is necessary for slots allocation. In this paper, a Slot‐based BS scheduling algorithm with Maximum Latency Guarantee and Capacity First (SMLG‐CF) is proposed. With SMLG‐CF, the connection request is satisfied with highest slot capacity first. Together with the use of dynamic sub‐frame adjustment, the overall system transmission can be efficiently improved. Through the finer slots calculation and accurate transmission time scheduling, the maximum latency guarantee can be better achieved for urgent requests. In the simulation, we compare the proposed mechanism with the deficit fair priority queue scheduling algorithm and the Highest Urgency First scheduling algorithm. The simulation results reveal that SMLG‐CF outperforms both algorithms from the aspect of maximum latency violation rate and average transmission rate. Copyright © 2011 John Wiley & Sons, Ltd.     

基于云进化算法的3D NoC测试端口优化选择

针对于三维片上网络测试时,如何选择测试端口以提高测试效率的难题,采用基于云模型的进化算法对三维片上网络测试端口进行位置寻优,并对IP核的测试数据进行合理分配,在测试功耗约束条件下,以重用片上网络作为测试访问机制,基于XYZ路由算法和非抢占式测试调度方式,对三维片上网络IP核实施并行测试,以提高测试效率。研究结果表明,该方法可对测试端口的位置及组合方案进行精确寻优,且有效减少了测试时间。     

Simultaneous Static Testing of A/D and D/A Converters Using a Built‐in Structure

Static testing of analog‐to‐digital (A/D) and digital‐to‐analog (D/A) converters becomes more difficult when they are embedded in a system on chip. Built‐in self‐test (BIST) reduces the need for external support for testing. This paper proposes a new static BIST structure for testing both A/D and D/A converters. By sharing test circuitry, the proposed BIST reduces the hardware overhead. Furthermore, test time can also be reduced using the simultaneous test strategy of the proposed BIST. The proposed method can be applied in various A/D and D/A converter resolutions and analog signal swing ranges. Simulation results are presented to validate the proposed method by showing how linearity errors are detected in different situations.     

基于蚁群算法的多路径覆盖测试数据生成

为了提高多路径覆盖测试数据的生成效率,研究了一种基于蚁群算法的多路径覆盖测试数据生成方法.首先给出蚁群算法的一种改进方法,该算法以蚂蚁对生成测试数据的重要性作为蚂蚁状态转移和蚂蚁路径变异的依据,以引导更多蚂蚁穿越小概率节点,提高测试数据生成效率.其次,根据改进的蚁群算法分别提出了基于单信息素表和多信息素表的多路径覆盖测试数据生成方法.在基于多信息素表的方法中,每条目标路径的信息素表均被用于其它路径测试数据的求解,而且蚁群算法运行一次即可求解多条目标路径的覆盖测试数据.最后对所提出方法的有效性和复杂度进行了理论分析.实验结果表明,与其它方法相比,基于多信息素表的测试数据生成方法能够有效地生成多路径覆盖测试数据.     

基于FSA ACO混合改进算法的蜗轮蜗杆故障识别

针对蜗轮蜗杆故障诊断问题,提出基于FSA ACO混合改进算法的蜗轮蜗杆故障识别的研究方法。该方法提出了FSA ACO混合改进策略,在谋求一个优势互补的基础上,对算法相关参数优化。同时针对该算法与蜗轮蜗杆故障识别结合构建算法模型问题,提出利用近邻函数准则作理论桥梁策略,寻找一种新的基于FSA ACO混合算法的蜗轮蜗杆故障诊断技术研究方法。以WPA40型号的蜗轮蜗杆为测试对象,验证了该研究方法的可行性和有效性。     

流量管理中队列调度算法研究

介绍了包交换芯片流量管理中队列调度的算法,分析DWRR(Deficit Weighted Round-Robin)算法的优缺点,并提出了一种基于DWRR改进的调度算法.该算法能够根据网络中实时的数据包帧长,来调节每次轮询中向各个队列添加的信用度,能够减少各个队列的时延,同时又增强带宽分配的相对公平性,改善了DWRR算法不能很好满足业务的时延特性.使用NS-2仿真器来对改进的算法进行网络仿真,最终的仿真结果表明改进后的DWRR算法能够有效地降低时延,可以在一定程度上提高QoS.     

基于云进化算法的NoC测试端口优化选择方法

针对片上网络(NoC)中大量节点的测试难题,提出了一种结合二维云进化算法优化选取NoC中测试端口位置,提高测试效率的方法。该方法结合NoC网格结构特点,采用重用测试访问机制和XY路由方式,由测试功耗限制确定端口对数,通过二维云模型对端口坐标进行统一建模,云进化算法自适应控制遗传变异的程度和搜索空间的范围,在测试功耗约束条件下,优化选取最佳测试端口的位置,达到总测试时间最少的目的。以SoCIN结构电路为仿真平台,分别对4×4网格和8×8网格结构NoC进行了实验仿真,结果表明,在NoC节点测试问题上,云进化算法能快速收敛到最优解,有效提高整体测试效率。     

A novel ant colony optimization algorithm for PAPR reduction of OFDM signals

The high peak‐to‐average power ratio (PAPR) is the main challenge of orthogonal frequency division multiplexing (OFDM) systems. Partial transmit sequence (PTS) is a useful approach to diminish the PAPR. Although the PTS approach significantly decreases the PAPR, it requires to explore all possible sequences of phase weighting factors. Hence, the computational cost exponentially increases with the number of divided subblocks. This paper proposes a novel PTS technique based on ant colony optimization (ACO) to diminish the high PAPR and computational cost of OFDM systems. By the new representation of phase factors as a graph, the improved ACO algorithm is combined with the PTS method to explore the optimal compound of the phase rotation factors. Simulation results represent that the proposed ACO‐based PTS approach significantly reduces the PAPR and improves the computational cost at the same time. A comparative analysis of the other meta‐heuristics shows that the ACO‐PTS approach outperforms the genetic algorithm, particle swarm optimization, and gray wolf optimization in terms of reducing PAPR.     

Invasive weed optimization based scheduling for digital microfluidic biochip operations

Digital Microfluidic Biochips (DMFBs) based on electro-wetting-on-dielectric (EWOD) technology are a class of lab-on-a-chip (LOC) devices. DMFBs can efficiently carry out biochemical analysis and have many advantages over the traditional laboratory system. DMFBs offer miniaturization, automation, and programmability. Resource-constrained scheduling is the first and vital step of fluidic-level synthesis of DMFBs while the other two are placement and routing of droplets. Scheduling DMFB operations is a constrained optimization problem which is NP-Complete. We propose an invasive weed optimization (IWO) algorithm based scheduling for the synthesis of DMFBs. The IWO algorithm is a nature-inspired meta-heuristic algorithm. Proposed algorithm can be used for the offline synthesis of DMFBs, where solution quality is more important than execution time. Each weed in the proposed algorithm represents a potential candidate solution for the scheduling problem. To calculate the fitness of individual weeds, we proposed an algorithm based on Heterogeneous Earliest Finish Time (HEFT), which incorporates resource binding, scheduling, and greedy module selection mechanism for bio-assay operations. Weeds (solutions) update their positions (priorities) by colonization behavior of weeds. Simulation results show that proposed IWO outperforms iterative improvement based algorithms and optimal ILP based algorithms which are existing for the offline synthesis of DMFBs.     

引脚约束的数字微流控生物芯片在线并行测试

随着数字微流控生物芯片在生化领域中的广泛应用,对芯片可靠性和制造成本的要求也越来越高,在线测试对于确保微流控生物芯片正常工作异常重要。该文针对引脚约束的数字微流控生物芯片,提出一种基于改进最大最小蚁群算法的在线并行测试方案,在满足各种约束条件的情况下,采用伪随机比例原则,建立禁忌判断策略,自适应地改变信息素的残留系数,实现引脚约束数字微流控生物芯片的在线并行测试。实验结果表明,该方法可以同时用于离线和在线测试,相对于单液滴离线和在线测试,可有效减少芯片的测试时间,提高了测试工作效率。     

An Ant Colony Optimization Approach to a Grid Workflow Scheduling Problem With Various QoS Requirements

Grid computing is increasingly considered as a promising next-generation computational platform that supports wide-area parallel and distributed computing. In grid environments, applications are always regarded as workflows. The problem of scheduling workflows in terms of certain quality of service (QoS) requirements is challenging and it significantly influences the performance of grids. By now, there have been some algorithms for grid workflow scheduling, but most of them can only tackle the problems with a single QoS parameter or with small-scale workflows. In this frame, this paper aims at proposing an ant colony optimization (ACO) algorithm to schedule large-scale workflows with various QoS parameters. This algorithm enables users to specify their QoS preferences as well as define the minimum QoS thresholds for a certain application. The objective of this algorithm is to find a solution that meets all QoS constraints and optimizes the user-preferred QoS parameter. Based on the characteristics of workflow scheduling, we design seven new heuristics for the ACO approach and propose an adaptive scheme that allows artificial ants to select heuristics based on pheromone values. Experiments are done in ten workflow applications with at most 120 tasks, and the results demonstrate the effectiveness of the proposed algorithm.     

The study of spacecraft parallel testing

For the purpose of avoiding interference between each parallel testing tasks in a spacecraft, this paper analyzes the testing process by dividing it into testing atoms, and makes the parameter set as the basic unit for each testing atom resource allocation so as to avoid interference. By means of modeling the parallel testing and with the object of minimizing the total testing time, it puts forward the parallel spacecraft testing task scheduling algorithm on basis of improved particle swarm optimization. The experimental results verify that this method can be efficiently applied in spacecraft parallel testing optimal scheduling.     

Ant-Colony-Optimization-Based Scheduling Algorithm for Uplink CDMA Nonreal-Time Data

Scheduling plays an important role in determining the overall performance of code-division multiple-access (CDMA) systems. This paper is focused on the uplink scheduling of CDMA nonreal-time data. In practical CDMA systems, data can only be transmitted with a few fixed transmission rates. Moreover, to guarantee receiving accuracy, the actual received signal-power-to-interference-plus-noise-power ratio (SINR) is expected to be no less than the target SINR value. Using Heaviside unit step functions, the relationship between the actual SINR value and the actual available maximum transmission rate is described in the proposed system model. Based on the proposed system model, an integer optimization problem is formulated to simultaneously maximize the throughput and the scheduling efficiency. Particularly, an ant-colony-optimization (ACO)-based scheduling algorithm is proposed to solve the proposed optimization problem. The computational complexity analysis indicates that the proposed ACO-based scheduling algorithm is computationally efficient in terms of both running time and storage space. In addition, the numerical results show that the proposed optimization problem is more efficient at guiding the development of scheduling algorithms for uplink CDMA nonreal-time data. Moreover, the proposed ACO-based scheduling algorithm performs quite well in terms of quality, running time, and stability.