Defect-oriented testability for asynchronous ICs

For a CMOS manufacturing process, asynchronous ICs are similar to synchronous ICs. The defect density distributions are similar, and hence, so are the fault models and fault-detection methods. So, what makes us think that asynchronous circuits are much harder to test than synchronous circuits? Because the effectiveness of best known test methods for synchronous circuits drops when applied to asynchronous circuits? They may very well be a temporal hurdle. Many test methods have already been reevaluated and successfully adapted from the synchronous to the asynchronous test domain. The paper addresses one of the final hurdles: I_DDQ testing. This type of test method, based on measuring the quiescent power supply current, is very effective for detecting (resistive) bridging faults in CMOS circuits. Detection of bridging faults is crucial, because they model the majority of today's manufacturing defects. I_DDQ fault effects are sensitized in a particular state or set of states and can only be detected if we stop the circuit operation right there. This is a problem for asynchronous circuits, because their operation is self-timed. In the paper, we quantify the impact of self timing on the effectiveness of I_DDQ -based test methods for bridging faults, and propose a Design-for-Test (DfT) approach to develop a low-cost DfT solution. For comparison, we do the same for logic voltage testing and stuck-at faults. The approach is illustrated on circuits from Tangram, the asynchronous design-style employed at Philips Research, but it is applicable to asynchronous circuits in general     

Integrity-based self-validation test scheduling

Intelligent sensors use functional self-testing to confirm measurement validity; this introduces the potential for false diagnosis and unnecessary corrective intervention. For a sensor in an integrity-monitoring context, it is desirable to select a test-interval to minimize the probability of faulty operation between discrete tests. The scheduling of discrete test intervals is examined as an optimization problem under a reliability-based cost-function. A convenient test-interval guideline, accounting for the operating context of the sensor, is derived for a simple case under limiting assumptions.     

System-on-chip test scheduling with reconfigurable core wrappers

The problem with increasing test application time for testing core-based system-on-chip (SOC) designs is addressed with test architecture design and test scheduling. The scan-chains at each core are configured into a set of wrapper-chains, which by a core wrapper are connected to the test access mechanism (TAM), and the tests are scheduled in such a way that the test time is minimized. In this paper, we make use of reconfigurable core wrappers that, in contrast to standard wrappers, can dynamically change (reconfigure) the number of wrapper-chains during test application. We show that by using reconfigurable wrappers the test scheduling problem is equivalent to independent job scheduling on identical machines, and we make use of an existing preemptive scheduling algorithm that produces an optimal solution in linear time (O(n); n is the number of tests). We also show that the problem can be solved without preemption, and we extend the algorithm to handle: 1) test conflicts due to interconnection tests and 2) cases when the test time of a core limits an optimal usage of the TAM. The overhead in logic is given by the number of configurations, and we show that the upper-bound is three configurations per core. We compare the proposed approach with the existing technique and show, in comparison, that our technique is 2% less from lower bound.     

Test response reuse-based SoC core test compression and test scheduling for test application time minimization

This paper presents a novel approach to system-on-a-chip (SoC) core test compression and test scheduling. Every test set is compressed through the test responses of its preceding core in preprocessing step by simulation. Consequently, under our method the test sets contain two parts: (1) the test sets that are compatible with the test responses of their individual preceding cores. This part can be removed from their original test sets, and (2) the test sets that none of the test vectors from them are compatible with the test responses of their individual preceding cores. On hardware implementation, only a couple of 2-1 MUXs are needed. The algorithms for reordering the sequences of core-under-tests and those of the test vectors for each corresponding core are outlined for optimal test compression results. It needs neither coder nor decoder, thus saving hardware overhead. Power-constrained SoC core test pipelining consumes less test application time. Hierarchical clustering-based SoC test scheduling can be implemented easily, and the hardware overhead is negligible. Experimental results on benchmark ISCAS 89 demonstrate that our method achieves significant improvement of test time and less ATE requirement over the previous methods, and it does not discount the fault coverage of each test set, moreover, the fault coverage for some test sets is improved instead.     

Production scheduling algorithms for a semiconductor test facility

The authors develop production scheduling algorithms for semiconductor test operations. The operations in the facility under study are characterized by a broad product mix, variable lot sizes and yields, long and variable setup times, and limited test equipment capacity. The approach presented starts by dividing the facility or job shop into a number of work centers. The method then proceeds to sequence one work center at a time. A disjunctive graph representation of the entire facility is used to capture interactions between work centers. The introduction of different management objectives leads to different work center problems and different production scheduling algorithms. The authors present algorithms for two different work center problems. Direction for future research are discussed     

Thermal-aware test scheduling using network-on-chip under multiple clock rates

The increasing trend in the number of cores on a single chip has led to scalability and bandwidth issues in bus-based communication. Network-on-chip (NoC) techniques have emerged as a solution that provides a much needed flexibility and scalability in the era of multi-cores. This article presents an optimal integer linear programming (ILP) formulation and a simulated annealing (SA) solution to thermal and power-aware test scheduling of cores in an NoC-based SoC using multiple clock rates. The methods have been implemented and results on various benchmarks are presented.     

Multiobjective scheduling for IC sort and test with a simulationtestbed

In manufacturing environments such as an integrated circuit (IC) sort and test floor, typically more than one objective, such as cycle time and on-time delivery, needs to be simultaneously considered. With multiple objectives, a good solution is called Pareto optimal if it is not inferior to any other feasible solutions in terms of all objectives. The Pareto boundary is the set of all Pareto optimal solutions, which indicates the tradeoff of all good solutions. In this paper, a multiobjective model for IC sort and test is formulated, based upon the current information at any given instant. An approximate Pareto boundary can then be found using the Lagrangian relaxation method for the model. New algorithms are used to solve the dual problem and obtain feasible solutions from the associated subproblem solutions. The impact of the new scheduling approach on performance is illustrated through numerical examples by comparing it with corresponding single-objective problems and various heuristic dispatching rules. Its performance in dynamic and stochastic environments for real world applications is evaluated by using a simulation testbed. Simulation results definitely indicate a high potential for our approach     

Integrated resource scheduling in a distributed scheduling environment

The Space Station era presents a highly complex multimission planning and scheduling environment exercised over a highly distributed system. In order to automate the scheduling process, customers require a mechanism for communicating their scheduling requirements to NASA. An expressive scheduling notation that captures a wide range of customer requirements and scheduling options is one solution to this problem. This article describes a request language that a remotely located customer can use to specify his scheduling requirements to a NASA scheduler, thus automating the customer-scheduler interface. Additionally, this article describes a scheduler that can accept these requests, process them, generate schedules, and return schedule and resource availability information to the requester.     

The spring scheduling coprocessor: a scheduling accelerator

The spring scheduling coprocessor is a novel very large scale integration (VLSI) accelerator for multiprocessor real-time systems. The coprocessor can be used for static as well as online scheduling. Many different policies and their combinations can be used (e.g., earliest deadline first, highest value first, or resource-oriented policies such as earliest available time first). In this paper, we describe a coprocessor architecture, a CMOS implementation, an implementation of the host/coprocessor interface and a study of the overall performance improvement. We show that the current VLSI chip speeds up the main portion of the scheduling operation by over three orders of magnitude. We also present an overall system improvement analysis by accounting for the operating system overheads and identify the next set of bottlenecks to improve. The scheduling coprocessor includes several novel VLSI features. It is implemented as a parallel architecture for scheduling that is parameterized for different numbers of tasks, numbers of resources, and internal wordlengths. The architecture was implemented using a single-phase clocking style in several novel ways. The 328 000 transistor custom 2-μm VLSI accelerator running with a 100-MHz clock, combined with careful hardware/software co-design results in a considerable performance improvement, thus removing a major bottleneck in real-time systems     

Mission scheduling

We investigate through a mission scheduling problem how a neural network can work compared to a hybrid system based on an operations research and artificial intelligence approach. Then we present a discussion to demonstrate the characteristic features of each.     

Window-based peak power model and Particle Swarm Optimization guided 3-dimensional bin packing for SoC test scheduling

This paper addresses the issue of power-aware test scheduling of cores in a System-on-Chip (SoC). While the existing approaches either use a fixed power value for the entire test session of a core or cycle-accurate power values, the proposed work divides the power profiles of cores into fixed-sized windows. This approach reduces the number of power values to be handled by the test scheduling algorithms while reducing the amount of pessimistic over-estimations of instantaneous power consumption. As a result, the power model can be integrated with more exhaustive meta-search techniques for generating power constrained test schedules. In this paper, the proposed power model has been integrated with a Particle Swarm Optimization (PSO) based 3-dimensional (3-D) bin packing technique to generate test schedules. Experimental results prove the quality of the approach to be high compared to the existing scheduling techniques.     

基于变长度调度间隔的雷达资源调度算法

在相控阵雷达完成精密跟踪和目标识别等不同任务时,波形、数据率和积累时间等雷达资源需要自适应改变,基于固定长度调度间隔的自适应调度算法较为复杂且不能充分利用雷达资源。提出了一种基于变长度调度间隔的自适应资源调度算法,根据任务请求的重要性函数安排待执行的雷达事件顺序,并根据雷达资源的动态变化情况,自适应地调整调度间隔的时间长度。利用VC语言建模弹道导弹目标和多功能地基相控阵雷达,进行分布式仿真,通过直观观测资源调度的执行过程,以及通过目标跟踪数量和时间利用率两个指标,评价了资源调度算法性能。改进算法的软件实现较为容易,可以增加目标跟踪数量,节约时间资源。     

Field workforce scheduling

BT employs thousands of field engineers across the UK to maintain networks, repair faults and provide service to customers. To allocate work more efficiently, BT launched Work Manager in the early 1990s — an information system automating work management and field communications, and now marketed as a.p.solve's TASKFORCE. In 1996, BT Exact's Intelligent Systems Lab enhanced Work Manager with a Dynamic Scheduler (DS) combining heuristic search and constraint-based reasoning. Since its national roll-out in 1997, DS has consistently reduced operational costs while preserving high quality of service. This paper gives an overview of BT's workforce scheduling problem, the DS system, and its operational and commercial impact. This revised version was published online in July 2006 with corrections to the Cover Date.     

Group priority scheduling

We present an end-to-end delay guarantee theorem for a class of guaranteed deadline (GD) servers. The theorem can be instantiated to obtain end-to-end delay bounds for a variety of source control mechanisms and GD servers. We then propose the idea of group priority, and specialize the theorem to a subclass of GD servers that use group priority in packet scheduling. With the use of group priority, the work of packet schedulers can be substantially reduced. We work out a detailed example, for the class of burst scheduling networks, to illustrate how group sizes can be designed such that the worst case end-to-end delay of application data units in a real-time flow is unaffected by the use of group priority. Group priority also can be used in packet schedulers that provide integrated services (best effort as well as real-time services) to achieve statistical performance gains, which we illustrate with empirical results from simulation experiments     

提高全局资源调度和本地资源调度的效能的云计算资源调度方案分析

设计分析可以提高当前全局资源调度、本地资源调度效能的云计算资源调度方案。在云计算资源调度中,能够优化分析,提高全局资源调度和本地资源调度的效能的调度方案,分析调度方案设计需求,设计实现提升云计算资源调度效能。结果证实,在云计算资源调度方案设计中,确保提高全局资源调度和本地资源调度的效能,全局资源调度效能提高20%,提高本地资源调度效能达到32%,发挥积极影响。结论表达出在进行云计算资源调度方案设计中,优化设计其全局资源调度、本地资源调度,可以提升资源调度效能,有助于提升云计算资源调度方案质量,发挥实用价值。     

Multi-parameter clock skew scheduling

Clock skew scheduling is a powerful technique for circuit optimization. Conventionally it can be formulated as a minimum cost-to-time ratio cycle (MCR) problem, which can be solved efficiently by a set of specialized network optimization algorithms. However, those algorithms can only handle one single parameter at a time, for example, the clock period, the timing slack or the yield. This inflexibility limits the applicability of the scheduling technique because in a real design one may need to consider multiple parameters simultaneously. In this paper, we introduce a multi-parameter extension to the MCR problem. Furthermore, a convex nonlinear extension is also considered. In particular, we generalize Lawler׳s algorithm, which is based on the bisection strategy. When there is more than one parameter, the bisection strategy is naturally replaced by the ellipsoid method. More importantly, the ellipsoid method does not require the knowledge of all constraints explicitly in prior. Instead, for each iteration, only a constraint that is violated by the current solution is required. This constraint turns out to be a negative cycle in our formulation, which can be detected efficiently. As a result, our proposed method could gain up to 12× run-time speedup for linear problems compared with a general linear programming solver and more than 700× run-time speedup for nonlinear problems compared with a general convex programming solver based on our experimental results.     

数字阵列雷达波束驻留调度间隔分析算法

针对数字阵列雷达波束驻留调度问题,研究了基于调度间隔分析的调度算法。该算法综合分析了1个调度间隔内申请执行的波束驻留任务,且调度过程中进行了脉冲交错。调度准则充分考虑了任务的工作方式优先级和截止期,并以任务丢失率、实现价值率、系统时间利用率作为评估指标。仿真结果表明修正截止期准则主要强调任务的紧迫性,修正工作方式优先级主要强调任务的重要性,而截止期—工作方式优先级和工作方式—截止期调度准则可以在二者间更好地折中,在总体性能上要优于其他调度准则。     

Control-flow versus data-flow-based scheduling: combining bothapproaches in an adaptive scheduling system

As high-level synthesis techniques gain acceptance among designers, it is important to be able to provide a robust system which can handle large designs in short execution times, producing high-quality results. Scheduling is one of the most complex tasks in high-level synthesis, and although many algorithms exist for solving the scheduling problem, it remains a main source of inefficiency by either not producing high-quality results, not taking into account realistic design requirements, or requiring unacceptable execution times. One of the main problems in scheduling is the dichotomy between control and data. Many algorithms to date have been able to provide scheduling solutions by looking only at either the data part or the control part of the design. This has been done in order to simplify the problem; however, it has resulted in many algorithms unable to handle efficiently large designs with complex control and data functionality. This paper presents algorithms for combining dataflow and control-flow techniques into a robust scheduling system. The main characteristics of this system are as follows: 1) it uses path-based techniques for efficient handling of control and mutual exclusiveness (for resource sharing), 2) it allows operation reordering and parallelism extraction within the context of path-based scheduling, 3) it contains a control partitioning algorithm for design space exploration as well as for reducing the number of control paths, and 4) it combines the above algorithms into an adaptive scheduling system which is capable of trading optimality for execution time on-the-fly. Results involving billions of paths are presented and analyzed     

Effective resource scheduling scheme considering scheduling relevancy for downlink joint transmission system

Coordinated multi-point(CoMP) transmission is a promising technique to improve both cell average and cell edge throughput for long term evolution-advanced(LTE-A).For CoMP joint transmission(CoMP-JT) in heterogeneous scenario,if joint transmission(JT) users are firstly scheduled,other non-JT users will not be allocated sufficient resources,i.e.,scheduling relevancy exists in the users under different cells in the same coordination cluster.However,the CoMP system throughput will decline remarkably,if the impact of scheduling relevancy is not considered.To address this issue,this paper proposes a novel scheduling scheme for CoMP in heterogeneous scenario.The principles of the proposed scheme include two aspects.Firstly,this scheme gives priority to user fairness,based on an extended proportional fairness(PF) scheduling algorithm.Secondly,the throughput of the coordination cluster should be maintained at a high level.By taking the non-CoMP system as a baseline,the proposed scheme is evaluated by comparing to random PF(RPF) and orthogonal PF(OPF) scheme.System-level simulation results indicate that,the proposed scheme can achieve considerable performance gain in both cell average and cell edge throughput.     

WFQ流量调度算法研究

高速包交换电路常常需要为各种不同要求的服务公平地分配带宽,在公平分配带宽的同时还需要满足这些服务的服务质量(QoS)参数.不同QoS需求的业务将被复用到同一条输出链路上,要为它们公平地分配带宽就需要用到各种各样的流量调度算法.加权公平队列(WFQ)是一种常用的流量调度算法.它不仅能保证带宽分配的公平性,而且具有较好的时延性能.文章较为详细地讨论了WFQ算法的基本原理.