A fault-tolerant array processor designed for testability andself-reconfiguration

The design of a fault-tolerant rectangular array of processing elements (PEs) is presented in which the reconfiguration is done by means of on-chip distributed logic, without the help of any external host. Spare PEs are included in every column of the array, and faulty PEs are bypassed within a column to facilitate reconfiguration in the presence of faults. Scan paths are used to enhance the testability of the array. PEs are tested locally using near-neighbor comparisons without the need of an external host. Because the interconnections between logical neighbors are short, the speed penalty for reconfiguration is very small. Any amount of redundancy can be incorporated in the array without changing the topology of the scheme or the design of the reconfiguration switches. The scheme is well suited for very large-area, high-density chips and wafer-scale integration. In order to demonstrate the capabilities of the scheme and evaluate its performance, an experimental chip consisting of a 6×4 array was designed, fabricated, and tested. Details of the design and the implementation of the chip are presented. The scheme is also analyzed for yield and area utilization for a range of array sizes and PE survival probabilities     

Reliable and fast reconfigurable hierarchical interconnectionnetworks for linear WSI arrays

A self-pruning binary tree (SPBT) interconnection network architecture that tolerate faults in a wafer scale integration (WSI) environment is proposed. The goal of the SPBT network is to provide a reliable and a quickly reconfigured interconnection network architecture for linear WSI arrays. The proposed architecture uses a bottom-up approach to reconfigure a linear pipelined array on a potentially defective WSI array using a binary tree interconnection scheme. The binary tree is generated by successive formation of hierarchical modules. For N processing elements (PEs) on the wafer, reconfiguration time is O(log N). The propagation delay is bounded by Θ(log N) and is independent of the number of faulty PEs. Faults in the switching network as well as faulty processing elements are tolerated     

On the optimal reconfiguration of multipipeline arrays in thepresence of faulty processing and switching elements

The reconfiguration of multipipeline arrays in the presence of both faulty processing elements (PEs) and switching elements (SEs) is addressed. Different fault models are used for the PEs and SEs: a PE can be either fault free or faulty; a SE is modeled using a novel functional approach which relates its switching capabilities to its status. This permits a PE to retain a partial functionality in the presence of a fault. An appropriate transformation of the multipipeline array reconfiguration problem to a maximum flow problem is then presented. The conditions under which this transformation is possible, are fully analyzed. A reconfiguration algorithm based on the maximum flow algorithm is presented; the proposed algorithm is optimal as the number of reconfigured pipelines is maximized     

An improved algorithm for accelerating reconfiguration of VLSI array

Reducing the number of visits to failure-free nodes can effectively reduce the reconstruction time of logical columns and improve the reconstruction efficiency. In this paper, we describe a new method to speed up the reconfiguration for the VLSI arrays. An efficient algorithm was proposed based on shortest path first principle for accelerating reconfiguration of VLSI processor subarrays with high power efficiency to meet the requirement of the power consumption of embedded system. The proposed algorithm greatly reduces the number of visits to the fault-free PEs for constructing a local optimal logical column and effectively reduces the construction time. Experimental results show that the proposed algorithm is capable of reducing the consumption time by 32.15% and reducing the numbers of visited PEs by 49.61% for a 128 × 128 host array with 20% falut rate.     

Dynamic load balancing in WDM packet networks with and without wavelength constraints

We develop load balancing algorithms for WDM-based packet networks where the average traffic between nodes is dynamically changing. In WDM-based packet networks, routers are connected to each other using wavelengths (lightpaths) to form a logical network topology. The logical topology may be reconfigured by rearranging the lightpaths connecting the routers. Our algorithms reconfigure the logical topology to minimize the maximum link load. In this paper, we develop iterative reconfiguration algorithms for load balancing that track rapid changes in the traffic pattern. At each reconfiguration step, our algorithms make only a small change to the network topology hence minimizing the disruption to the network. We study the performance of our algorithms under several dynamic traffic scenarios and show that our algorithms perform near optimally. We further show that these large reconfiguration gains are achievable in systems with a limited number of wavelengths.     

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     

Fault-Tolerant Mesh-Based NoC with Router-Level Redundancy

The aggressively scaled CMOS technology is increasingly threatening the dependability of network-on-chips (NoCs) architecture. In a mesh-based NoC, a faulty router or broken link may isolate a well functional processing element (PE). Also, a set of faulty routers may form isolated regions, which can degrade the design. In this paper, we propose a router-level redundancy (RLR) fault-tolerant scheme that differs from the traditional microarchitecture-level redundancy (MLR) approach to relieve the problem of isolated PE and isolated region. By simply adding one spare router within each router set in a mesh, RLR can be created and connection paths between adjacent routers can be diversified. To exploit this extra resource, two reconfiguration algorithms are demonstrated to detour observed faulty routers/links. The proposed RLR fault-tolerant scheme can tolerate at most one faulty router within a router set. After the reconfiguration, the original mesh topology is maintained. As a result, the proposed architecture does not need any support from the network layer routing algorithms. The scheme has been evaluated based on the three fault-tolerant metrics: reliability, mean time to failure (MTTF), and yield. The experimental results show that the performance RLR increases as the size of NoC grows; however, the relative connection cost decreases at the same time. This characteristic makes our architecture suitable for large-scale NoC designs.

     

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     

Reconfigurable architectures for bio-sequence database scanning on FPGAs

Protein sequences with unknown functionality are often compared to a set of known sequences to detect functional similarities. Efficient dynamic-programming algorithms exist for solving this problem, however current solutions still require significant scan times. These scan time requirements are likely to become even more severe due to the rapid growth in the size of these databases. In this paper, we present a new approach to bio-sequence database scanning using re-configurable field-programmable gate array (FPGA)-based hardware platforms to gain high performance at low cost. Efficient mappings of the Smith-Waterman algorithm using fine-grained parallel processing elements (PEs) that are tailored toward the parameters of a query have been designed. We use customization opportunities available at run time to dynamically reconfigure the PEs to make better use of available resources. Our FPGA implementation achieves a speedup of approximately 170 for linear gap penalties and 125 for affine gap penalties compared to a standard desktop computing platform. We show how run-time reconfiguration can be used to further improve performance.     

Reconfiguration of Logical Topologies with Minimum Traffic Disruptions in Reliable WDM-Based Mesh Networks

A wavelength division multiplexing (WDM) network offers a flexible networking infrastructure by assigning the route and wavelength of lightpaths. We can construct an optimal logical topology, by properly setting up the lightpaths. Furthermore, setting up a backup lightpath for each lightpath improves network reliability. When traffic demand changes, a new optimal (or sub-optimal) topology should be obtained by again applying the formulation. Then, we can reconfigure the running topology to the logical topology obtained. However, during this reconfiguration, traffic loss may occur due to the deletion of older lightpaths. In this paper, we consider reconfiguring the logical topology in reliable WDM-based mesh networks, and we propose five procedures that can be used to reconfigure a running lightpath to a new one. Applying the procedures one by one produces a new logical topology. The procedures mainly focus on utilizing free wavelength resources and the resources of backup lightpaths, which are not used usually for transporting traffic. The results of computer simulations indicate that the traffic loss is remarkably reduced in the 14-node network we used as an example.     

Characterization, testing and reconfiguration of faults in mesh networks

Achieving fault-tolerance through incorporation of redundancy and reconfiguration is quite common. The distribution of faults can have several impacts on the effectiveness of any reconfiguration scheme; in fact, patterns of faults occurring at strategic locations may render an entire VLSI system unusable regardless of its component redundancy and its reconfiguration capabilities. Such fault patterns are called catastrophic fault patterns (CFPs). In this paper, we characterize catastrophic fault patterns in mesh networks when the links are bidirectional or unidirectional. We determine the minimum number of faults required for a fault pattern to be catastrophic. We consider the problem of testing whether a fault pattern is catastrophic. When a fault pattern is not catastrophic we study the problem of finding optimal reconfiguration strategies, where optimality is with respect to either the number of processing elements in the reconfigured network (the reconfiguration is optimal if such a number is maximized) or the number of bypass links to activate in order to reconfigure the array (the reconfiguration is optimal if such a number is minimized). The problem of finding a reconfiguration strategy that is optimal with respect to the size of the reconfigured network is NP-complete, when the links are bidirectional, while it can be solved in polynomial time, when the links are unidirectional. Considering optimality with respect to the number of bypass links to activate, we provide algorithms which efficiently find an optimal reconfiguration.     

Online Fault Tolerance for FPGA Logic Blocks

Most adaptive computing systems use reconfigurable hardware in the form of field programmable gate arrays (FPGAs). For these systems to be fielded in harsh environments where high reliability and availability are a must, the applications running on the FPGAs must tolerate hardware faults that may occur during the lifetime of the system. In this paper, we present new fault-tolerant techniques for FPGA logic blocks, developed as part of the roving self-test areas (STARs) approach to online testing, diagnosis, and reconfiguration . Our techniques can handle large numbers of faults (we show tolerance of over 100 logic faults via actual implementation on an FPGA consisting of a 20 times 20 array of logic blocks). A key novel feature is the reuse of defective logic blocks to increase the number of effective spares and extend the mission life. To increase fault tolerance, we not only use nonfaulty parts of defective or partially faulty logic blocks, but we also use faulty parts of defective logic blocks in nonfaulty modes. By using and reusing faulty resources, our multilevel approach extends the number of tolerable faults beyond the number of currently available spare logic resources. Unlike many column, row, or tile-based methods, our multilevel approach can tolerate not only faults that are evenly distributed over the logic area, but also clusters of faults in the same local area. Furthermore, system operation is not interrupted for fault diagnosis or for computing fault-bypassing configurations. Our fault tolerance techniques have been implemented using ORCA 2C series FPGAs which feature incremental dynamic runtime reconfiguration     

Reconfiguration of hexagonal arrays by diagonal deletion

This paper describes various algorithms for dynamic reconfiguration of VLSI hexagonal arrays. These algorithms are applicable to arrays in which reconfiguration requires logical deletion of the diagonal front of computation. Initially it is proven that the intuitive, but rather naive approach of diagonal deletion is not correct, because it does guarantee the generation of the correct dimensions in the target array.A new approach based on geometrical considerations is proposed. Theorems that preserve the dimensions of the desired target array, are presented. Two reconfiguration algorithms are presented. These algorithms have linear time-complexity with respect to the dimensions of the array. The innovative features of this approach are the dependence of reconfiguration on the dimensions of the array to be reconfigured and a better exploitation of redundancy for run-time reconfiguration. Simple switching circuits are described. It is proved that silicon overhead consists of four two-by-two Banyan switches per cell. Illustrative examples are presented.     

A mathematical programming method for constructing the shortest interconnection VLSI arrays

Mesh-connected processor array is an extensively investigated architecture in parallel processing. Massive studies have addressed the problem of using reconfiguration algorithms to solve the fault tolerance of faulty mesh-connected processor arrays. However, the subarrays generated by the previous studies still contain large interconnection length, which will lead to the increase of capacitance, power dissipation and dynamic communication cost. First, a mathematical model is established for the array reconfiguration. Then, the proposed method treats the interconnections between each PEs as a function with different integer variables, which can be solved by using effective integer programming techniques. Finally, an effective solver is called to find the optimal solution. Simulation results show that the proposed method can reduce the interconnection length of the array in the row and column directions simultaneously, thereby generating a subarray with the shortest interconnection length. On a 32 × 32 host array with fault density of 30%, the total interconnection length of the subarray can be reduced by 8.36% compared with state-of-the-art, and the average interconnection length can be reduced by 39.30%, which is more closer to the lower bound.     

Reconfigurable architectures for VLSI processing arrays

The paper presents the problem of fault tolerance in VLSI array structures: its aim is to discuss architectures capable of surviving a number of random faults while keeping costs (in terms of added silicon area and of increased processing time) as low as possible. Two different approaches are presented, both based upon introduction of simple patterns of faults and by global reconfiguration techniques (rather than one-to-one substitution of faulty elements by spare ones). Various solutions are compared, and relative performances are discussed in order to determine criteria for selecting the one most suitable to particular applications.     

Locally reconfigurable p-cycle networks for dual-failure restoration

p-Cycle reconfiguration methods (for instance complete, incremental, or dynamic-repair) based on the first event adaptive restoration model provide a promising approach for improving the dual-failure restorability characteristics of static p-cycle methods based on the static preplanned restoration model. However, if the reconfiguration process triggered by the first failure is not completed before a second failure occurs, p-cycle reconfiguration methods fail to achieve 100% dual-failure restorability and reduce to the static p-cycle methods which do not take advantage of the spare capacity to be reconfigured. In this study, we propose to use a new restoration model designated as first event locally adaptive restoration model with a coordinated re-restoration effort. This model is aimed to limit the reconfiguration scope to a local p-cycle where the spare capacity is only reconfigured on its straddling links for reducing the reconfiguration overhead (i.e., the average number of reconfigured links during the reconfiguration time.) According to this model, a two-phase locally reconfigurable p-cycle method is proposed. Only the straddling links of the local p-cycle affected by the first failure are reconfigured in the first phase. The second phase is not initialized until the second failure really occurs in the affected local p-cycle. The second phase is to enable the dual-failure restorations with a coordinated re-restoration effort for the first failed link from its original end nodes for any damage that the second failure causes to previously deployed restoration paths. The objective of the proposed method is to maximize the dual-failure restorability within a limited reconfiguration scope. We evaluate the correlation between the normalized spare capacity cost and the dual-failure restorability. The results show that the proposed local reconfiguration heuristic method improves the average dual-failure restorability of the 9n17s and Cost 230 networks by 45.1% and 20.1%, respectively, relative to the static p-cycles method and achieves closely the optimal value obtained using integer linear programming (ILP). Additionally, the spare capacity cost of the proposed local reconfiguration method is smaller than that of previous p-cycle reconfiguration methods in the two test networks.

A systolic architecture for optimal filter design support

A prototype filter design is reviewed to underscore the computational problems arising in such designs. A purely systolic-array architecture is presented. This array provides the computational support necessary for filter design. Due to a simple and novel data steering technique the array is capable of carrying out a number of important matrix operations such as factorization, inversion of factors, and matrix-matrix multiplication. Another interesting attribute is the array's ability to maximally overlap computations of multiphase algorithms. In this study we demonstrate the execution of a dense matrix factorization phase and a factor inversion phase on the array with no need for intraphase or interphase I/O. We show that these phases (which are the backbone of an optimal filtering algorithm) are completed in the optimal count of aboutn time units. The array employs 2n ⁿ–n simple processing elements (PEs) that are active every other time unit. It is shown that the functions of two adjacent PEs can be merged and assigned to a single PE thus maximizing PE utilization. A possible design of a merged PE is given.     

Parallelization of motion compensation algorithm based on reconfigurable video array processor

The new encoding tools of high efficiency video coding (HEVC) make the interpolation operation more complex in motion compensation (MC) for better video compression, but impose higher requirements on the computational efficiency and control logic of the hardware architecture. The reconfigurable array processor can take into consideration both the computational efficiency and flexible switching of algorithms very well. Through mining the data dependency and parallelism among interpolation operation, this paper presents a parallelization method based on the dynamic reconfigurable array processor proposed by the project team. The number of pixels loaded from the external memory is reduced significantly, by multiplexing the common data in the previous reference block and the current reference block. Flexible switching of variable block operation is realized by using dynamic reconfiguration mechanism. A 16 x 16 processor element (PE)'s array is used to dynamically process a 4 x 4 - 64 x 64 block size. The experimental results show that, the reference block update speed is increased by 39.9%. In the case of an array size of 16 PEs, the number of pixels processed in parallel reaches 16.     

Optimal Placement of Spare Modules in a Cascaded Chain

A class of redundant cascaded chains with i.i.d. modules is considered in which recovery from a failure takes place by replacing the faulty module by a spare module. The complexity of the reconfiguration process depends upon the location of spare modules in the cascade. This paper deals with the question of optimally placing the spare modules in order to minimize the s-expected recovery time (down time) of the system. Exact analysis is carried out for cascades with one and two spare modules and an approximate analysis is given for three or more spares. Even though exact analysis does not seem to be practical in the general case, the symmetry of spare module positions in the special cases discussed here and linearity of the system suggest that one might expect the optimal positions to be symmetric in general. Because of this symmetry, one can reduce the number of variables to be considered in the general case, however, some inaccuracies might be introduced.     

Two dynamic reconfiguration approaches for optimizing the restoration path length in p-cycle protection network

p-cycle is one of the most promising technique of span protection in optical transport networks with mesh-like efficiency and ring-like speed. Longer p-cycle provides better efficiency in term of spare capacity, but longer restored path increases end-to-end propagation delay, which reduces the reliability of the restored network. Hence, minimization of restoration path is a critical issue in p-cycle based protection network. In this paper, two new dynamic reconfiguration approaches namely inter-cycles switching (ICS) and local restoration paths (LRP) are discussed to reduce the length of restored paths in existing optimal spare capacity design of p-cycle. Both proposed approaches are meant to utilize the idle p-cycles thus significantly reducing the path length. This reduction in restored path length also releases the redundant spare capacity.