Sequential diagnosis of processor array systems

We examine the diagnosis of processor array systems formed as two-dimensional arrays, with boundaries, and either four or eight neighbors for each interior processor. We employ a parallel test schedule. Neighboring processors test each other, and report the results. Our diagnostic objective is to find a fault-free processor or set of processors. The system may then be sequentially diagnosed by repairing those processors tested faulty according to the identified fault-free set, or a job may be run on the identified fault-free processors. We establish an upper bound on the maximum number of faults which can be sustained without invalidating the test results under worst case conditions. We give test schedules and diagnostic algorithms which meet the upper bound as far as the highest order term. We compare these near optimal diagnostic algorithms to alternative algorithms, both new and already in the literature, and against an upper bound ideal case algorithm, which is not necessarily practically realizable. For eight-way array systems with N processors, an ideal algorithm has diagnosability 3N/sup 2/3/-2N/sup 1/2/ plus lower-order terms. No algorithm exists which can exceed this. We give an algorithm which starts with tests on diagonally connected processors, and which achieves approximately this diagnosability. So the given algorithm is optimal to within the two most significant terms of the maximum diagnosability. Similarly, for four-way array systems with N processors, no algorithm can have diagnosability exceeding 3N/sup 2/3//2/sup 1/3/-2N/sup 1/2/ plus lower-order terms. And we give an algorithm which begins with tests arranged in a zigzag pattern, one consisting of pairing nodes for tests in two different directions in two consecutive test stages; this algorithm achieves diagnosability (3/2)(5/2)/sup 1/3/N/sup 2/3/-(5/4)N/sup 1/2/ plus lower-order terms, which is about 0.85 of the upper bound due to an ideal algorithm.     

A fault-tolerant protocol for election in chordal-ring networkswith fail-stop processor failures

In a distributed computer system, a group of processors is connected by communication links into a network. Each processor (node) of the network has an identity (a unique integer value) that is not related to its position in the network (its address). A processor's identity is known only to the processor. In the problem of leader election, exactly one processor among a network of processors has to be distinguished as the leader. Previously, many efficient election protocols have been proposed for networks with a sense of direction. In particular, the sequential search is used for election in a reliable complete network, and a multi-token search method is used in a faulty complete network. However, election protocols on a faulty ChRgN (chordal ring network) have not been investigated by other researchers. This paper addresses this issue by: studying the problem of leader election in an asynchronous ChRgN with a sense of direction and with the presence of undetectable fail-stop processor failures; proposing a new election protocol which (a) combines the concept of sequential search and multi-token search techniques, and (b) uses an efficient routing algorithm to reduce the total number of messages used; presenting a protocol for a ChRgN of n processors with I chords/processor and at most f fail-stop faulty processors, with message complexity O(n+(n/l)log(n)+k·f), where k is the number of processors starting the election process spontaneously and at most f相似文献   

Distributed diagnosis for homogeneous systems

This article presents a distributed fault-diagnosis algorithm for identifying faulty and fault-free units (processors, PEs, cells) in homogeneous systems. It is based on local comparison among units in a system and dissemination of the test results. Each unit performs comparison with its neighbors by using its own comparator. Unlike other approaches, the algorithm does not assume that diagnostic circuits are fault free. The algorithm is simple enough to be realized with small circuit overhead. The results are especially useful in locating faulty units in processor arrays implemented on a single chip or wafer. Computer simulation has shown that even for low unit yields, extremely high performance (fault coverage) can be obtained by adjusting algorithm parameters.     

Eventually Byzantine Agreement on CDS-based mobile ad hoc network

Reliability is an important research topic in the study of distributed systems. Under many circumstances, a healthy processor in a distributed system needs to reach a common agreement before performing some special tasks even if the faults exist. In order to achieve fault-tolerance in distributed systems, one must deal with the Byzantine Agreement (BA) problem. Most BA problem require all the healthy processors to obtain an agreement at the same round, this kind of agreement is called an Immediate Byzantine Agreement (IBA). Another kind of agreement, Eventual Byzantine Agreement (EBA), allows its participants to reach a common agreement at different rounds when the f_act < f_p (f_act is the number of actual arbitrary faulty processors; f_p is the number of tolerate arbitrary faulty processors). However, the traditional EBA problem is solved in well-defined networks, but the Mobile Ad hoc NETworks (MANETs) are increasing in popularity. Therefore, EBA problem is revisited under dual failure mode (processors and transmission media) in the MANET. The proposed protocol, Early Dual Agreement Protocol (EDAP), can achieve agreement while tolerating the maximum number of faulty processors and transmission media in a MANET by using the minimum number of message exchanges. Furthermore, our protocol can manage and organize the network efficiently even if the processors move around the network.     

Fault Diagnosis with Imperfect Tests

This paper derives a minimum s-expected cost sequence of built-in-tests (BITs) which will partition modular equipment into mutually exclusive groups of modules. After a fault in the equipment, one of these groups will be identified by a BIT diagnostic subsystem as the group which contains a faulty module. The BITs are imperfect in the sense only that they might not detect all of the possible faults in the equipment; they are perfect in the sense that fault indications are never false. The proportion of faults detectable by each BIT is known. Both the cost of a BIT and the probability that a BIT will pass or fail are functions of which modules are tested. A recursive algorithm is developed which determines a sequence of BITs with a minimum s-expected life-cycle cost. The recursive algorithm is applied to a 4-element numerical example. The algorithm has neither been proved nor implemented for a computer.     

Automation of Test Program Synthesis for Processor Post-silicon Validation

Software-based self-testing (SBST) is introduced for at-speed testing of processors, which is difficult with any of the external testing techniques. Evolutionary approaches are used for the automatic synthesis of SBST programs. However, a number of hard-to-detect faults remain unidentified by these autogenerated test programs. Also, these approaches have considered fault models which have low correlation with the gate-level fault models. This paper presents a greed-based strategy, where the instruction sequences that detect the freshly identified faults are preserved throughout the evolutionary process to identify the hard-to-test faults of the processor. Subsequently, the overall coverage is also improved. A selection probability is estimated from the testability properties of the processor components and assigned to every instruction to accelerate the test synthesis. The range of performance and scalability are comprehensively evaluated on a configurable MIPS processor and a full-fledged 7-stage pipeline SPARC V8 Leon3 soft processor using behavioral fault models. The efficacy of our approach was explained by demonstrating the correlation between behavioral faults and gate-level faults of MIPS processor for the proposed scheme. Experimental results show that improved coverages of 96.32% for the MIPS processor and 95.8% for the Leon3 processor are achieved in comparison with the conventional methods, which have about 90% coverage on the average.     

Applying Petri Nets to Modeling of Many-Core Processor Self-Testing when Tests are Performed Randomly

Today’s many-core processors are manufactured in inherently unreliable technologies. Massively defective technologies used for production of many-core processors are the direct consequence of the feature size shrinkage in today’s CMOS (complementary metal-oxide-semiconductor) technology. Due to these reliability problems, fault-tolerance of many-core processors becomes one of the major challenges. To reduce the probability of failures of many-core processors various fault tolerance techniques can be applied. The most preferable and promising techniques are the ones that can be easily implemented and have minimal cost while providing high level of processor fault tolerance. One of the promising techniques for detection of faulty cores, and consequently, for performing the first step in providing many-core processor fault tolerance is mutual testing among processor cores. Mutual testing can be performed either in a random manner or according to a deterministic scheduling policy. In the paper we deal with random execution of mutual tests. Effectiveness of such testing can be evaluated through its modeling. In the paper, we have shown how Stochastic Petri Nets can be used for this purpose and have obtained some results that can be useful for developing and implementation of testing procedure in many-core processors.     

Failure-Aware Task Scheduling of Synchronous Data Flow Graphs Under Real-Time Constraints

As more processors are integrated into Multiprocessor System-on-Chips (MPSoCs) via relentless technology scaling, the mean-time-to-failure (MTTF) is reduced to the extent that unexpected processor failures are considered during design time. A popular approach to tolerate processor failures is to migrate tasks on the faulty processor to live processors. This approach, however, is not suitable for real-time digital signal processing (DSP) applications since it may not guarantee real-time constraints. In this paper, we propose the re-scheduling of the entire application to minimize throughput degradation under a latency constraint, given that the application is specified by a Synchronous Data Flow (SDF) graph. We obtain sub-optimal re-scheduling results using a genetic algorithm for each scenario of processor failures at compile-time. If a failure is detected at run-time, the live processors obtain the saved schedule, perform task transfer, and execute the remaining tasks of the current iteration. We compare preemptive and non-preemptive migration policies and propose a hybrid policy to obtain better performance. We demonstrate the viability of the proposed technique through experiments with real-life DSP applications as well as randomly generated graphs under timing constraints and random fault scenarios.     

Computation in faulty stars [hypercube networks]

The question of simulating a completely healthy hypercube with a degraded one (one with some faulty processors) has been considered by several authors. We consider the question for the star-graph interconnection network. With suitable assumptions on the fault probability, there is, with high probability, a bounded distance embedding of K_n×S_n-1 in a degraded S_n , of congestion O(n). By a different method, a congestion O(log(n)) embedding of S, can be obtained. For the hypercube O(1) congestion has been obtained, but this is open for the star graph. Other results presented include a guaranteed O(n) slowdown simulation if there are sufficiently few faults, and upper and lower bounds for the minimal size of a system of faults rendering faulty every m-substar     

Fault tolerance in Clos–Knockout multicast ATM switch

In this paper, we propose a new architecture for multicast ATM switches with fault tolerant capability based on the Clos–Knockout switch. In the new architecture, each stage has one more redundant switch module. If one switch module is faulty, the redundant module would replace the faulty one. On the other hand, under the fault‐free condition, the redundant modules in the second and third stages will provide additional alternative internal paths, and hence improve the performance. The performance analysis shows that the cell loss probability is lower than the original architecture when all modules are fault free, and the reliability of the original architecture is improved. Copyright © 2002 John Wiley & Sons, Ltd.     

Design of a self-reconfiguring interconnection network forfault-tolerant VLSI processor arrays

An interconnection network capable of spontaneously reconfiguring a VLSI processor array on detection of faulty processors is presented. Although the reconfiguration process is global, the network control circuitry is localized around each processor and is therefore completely modular. The structure of the control circuitry is fixed and thus independent of the array size or the number of spare processors. The network performance in yield enhancement is analyzed through Monte Carlo simulation. The network effectiveness in using surviving processors is close to that of an ideal network (one capable of tolerating as many faulty processors per row as there are spare processors per row). Strategies involved in testing the fault-tolerant array are also presented. Test circuitry is placed around each of the processors to enable testing of all the processors in parallel. The same circuitry is used to test the interconnection network efficiently. The additional silicon area requirements due to the network and the test circuitries are examined through the design of a prototype fault-tolerant array     

On gracefully degrading multiprocessors with multistageinterconnection networks

The behavior of a multiprocessing system with a multistage interconnection network is studied in the presence of faulty components. Measures for the connectivity and performance of these systems are proposed, including the average number of operational paths, the average number of accessible processors and memories, the average number of fault-free processors (memories) that are connected to an accessible memory (processor), the bandwidth, and the processing power of the system. Based on these measures, a tight upper bound for the maximal fully connected system is suggested. The gracefully degrading system is then compared, through some numerical examples, to a system whose faulty components are repaired upon failure. Based on these comparisons, the anticipated reduction in system performance can be estimated and consequently, appropriate maintenance policies can be determined     

A dynamically reconfigurable interconnect for array processors

Reconfigurability of processor arrays is important due to two reasons (1) to efficiently execute different algorithms and (2) to isolate faulty processors. An array processor that is reconfigurable by the user any number of times to yield a different topology or to isolate faults is envisaged in this paper. The system has a host or controller that broadcasts a command to the interconnect to configure itself into a particular fashion. The interconnect uses static-RAM programming technology and can be programmed to different configurations by sending a different set of bits to the configuration random access memory (RAM) in the interconnect. We present three designs reconfigurable into array, ring, mesh, or Illiac mesh topologies. The first design provides no redundancy or fault tolerance. The second design is capable of graceful degradation by bypassing faulty elements. The third design is capable of graceful degradation by rerouting. The details of the interconnect and the configuration RAM contents for typical configurations are illustrated. It is seen that reconfigurable interconnect results in a highly reconfigurable or polymorphic computer     

Parallel video signal processor configuration based on overlap-save technique and its LSI processor element: VISP

A parallel signal processor architecture has been developed for real time motion picture encoding. The architecture is based on spatial parallelism utilization in a picture signal. Plural element processors handle subregional pictures simultaneously without communicating with other element processors. However, due to an overlapsave technique where every sub-picture input area is chosen to be wider than the output area, element processors can carry out continuous processing over an entire picture. In order to increase motion picture processing efficiency as well as system implementation simplicity, a specific element processor LSI chip, composed of a pipeline arithmetic unit, two dimensional address generators, a raster scan signal handler, and a sequence controller, has been developed by using more than 220,000 transistors. The developed parallel processor is shown to be applicable to a software programmable low bit rate TV codec.     

Self-reconfiguring interconnection network for a fault-tolerantmesh-connected array of processors

An interconnection network capable of spontaneously reconfiguring a mesh-connected processor array on detection of faulty processors is presented. Although the reconfiguration process is global in nature, the network control circuitry is localised around each processor and is therefore completely modular. In addition, the structure of the control circuitry is fixed and thus independent of the array size or the number of spare processors     

基于Modbus协议的机房监控系统设计

介绍了一种基于ARM嵌入式处理器的机房环境监测系统,系统采用WinCE6.0嵌入式操作系统.各数据采集模块按照Modbus协议与ARM嵌入式处理器进行通讯,采集数据经预处理后,通过以太网发送到远程控制平台.从而实现对机房环境的远程监控.     

NODIFS-simulating faults fast

This article introduces, perhaps for the first time, an asynchronous, distributed, circuit partitioned algorithm that is capable of fault simulating both combinational and sequential digital designs on parallel processors. In this approach, called NODIFS (NOvel asynchronous DIstributed algorithm for Fault Simulation), every circuit component is modeled as an asynchronous and concurrent entity that is checked for faults as soon as appropriate signal transitions and fault lists are asserted at its input ports. The circuit is partitioned such that components of every partition are allocated to a unique processor of the parallel processor system     

空时二维雷达信号处理机的系统设计

针对雷达信号处理算法复杂、数据量大、数据传输速度高的特点,本文介绍一种基于ADSP-TS101通用信号处理板的设计,并以此处理板构成了空时二维雷达信号处理信号机.此处理板具有可重构性和可扩展性,简单的扩展或适当增加此模块的数目即可满足不同的雷达信号处理要求.     

A 110-K transistor 25-MPixels/s configurable image transformprocessor unit

A configurable architecture for performing image transform algorithms is presented that provides a better tradeoff between low complexity and algorithm flexibility than either software-programmable processors or dedicated ASIC's. The configurable processor unit requires only 110 K transistors and can execute several image transform algorithms. By emulating the signal flow of the algorithms in hardware, rather than software, complexity is reduced by an order of magnitude compared with current software programmable video signal processors, while providing more flexibility than single function ASIC's. The processor has been fabricated in 1.2-μm CMOS and has been successfully used to execute the discrete cosine transform/inverse discrete cosine transform (DCT/IDCT), subband coding, vector quantization, and two-dimensional filtering algorithms at pixel rates up to 25 MPixels/s