Effective fault-tolerant techniques are essential for improving the reliability of multiprocessor systems. This paper investigates the fault-tolerance of torus-connected VLSI array using pre-integrated spare processin...
详细信息
ISBN:
(纸本)9783319111971;9783319111964
Effective fault-tolerant techniques are essential for improving the reliability of multiprocessor systems. This paper investigates the fault-tolerance of torus-connected VLSI array using pre-integrated spare processing elements (PEs), by reconfiguring the interconnection network among all PEs. We model the problem of whether all faulty PEs can be replaced by spare ones as the problem of finding maximum independent set for a contradiction graph, which is constructed from the original physical arrays with faulty PEs. Each node of the graph represents an alternative of a faulty PE, while an edge denotes that different alternatives cannot coexist. We propose efficient algorithms to construct contradiction graphs from physical arrays with faulty PEs and redundant PEs. We then customize an ant-colony algorithm to find independent set as large as possible. We develop an efficient algorithm to generate logic arrays based on the produced independent set. Three different distributions of redundant PEs are discussed in this paper, and satisfactory results have been achieved in simulation.
Recontigurable Machine Tool (RMT) has integrated the advantages of the special machine tools, machine tools and CNC machine tools. During the design process of the RMT, the rationality of the module encoding scheme is...
详细信息
ISBN:
(纸本)9781424426928
Recontigurable Machine Tool (RMT) has integrated the advantages of the special machine tools, machine tools and CNC machine tools. During the design process of the RMT, the rationality of the module encoding scheme is of great significance for the establishment and operation of the entire design systems which include the choice of modules, modules integration, enterprise production and management, etc. Started with the modules analysis of the RMT, this paper studies the composing modules features in detail. Then the module encoding system for the RMT is divided into three parts which consisted of the main module codes, module interface feature codes and module drawing management codes. All of the three parts establish the modular encoding schemes for the RMT. The general process of the modules selection and the selection strategy for the analysis of the module choice problem is studied in this paper, and the corresponding mathematical description is also made out. Based on the linear memory structure, the rapid retrieval for the qualitative attributes is achieved. As to the quantitative attributes, the similar factor in the fuzzy math is introduced. Then the fuzzy question of finding the nearest module to the destination module can be solved in the quantitative method which considered all the various attributes. The module selection algorithm processes and examples for the RMT are presented in this paper.
We study dynamic self-reconfiguration of modular metamorphic systems. We guarantee the feasibility of motion planning in a rectangular model consisting of square modules that are allowed to slide along or rotate about...
详细信息
We study dynamic self-reconfiguration of modular metamorphic systems. We guarantee the feasibility of motion planning in a rectangular model consisting of square modules that are allowed to slide along or rotate about one another. That is, we show that any two connected configurations of the same number of modules can be transformed into each other by a sequence of moves so that all intermediate configurations are connected. This settles a conjecture formulated in [6].
First, we give a graph-theoretic formalization for the spare assignment problems for two cases of reconfiguring N x N mesh-connected processor arrays with spares on a diagonal line in the array or two orthogonal lines...
详细信息
First, we give a graph-theoretic formalization for the spare assignment problems for two cases of reconfiguring N x N mesh-connected processor arrays with spares on a diagonal line in the array or two orthogonal lines at the edges of the array. Second, we discuss the problems for minimizing the numbers of "dangerous processors" for the cases. Here, a dangerous processor is a nonfaulty one for which there remains no spare processor to be assigned if it becomes faulty, without modifying the spare assignments to other faulty processors. The problem for the latter case, originally presented by Melhem [1], [2], has already been discussed and solved by the O(N-2) algorithm in [3], but it's procedure is very complicated. Using the above graph-theoretic formalization, we give efficient plain algorithms for minimizing the numbers of dangerous processors by which the problems for both the cases can be solved in O(N) time.
A typical fault-tolerance technique of systolic arrays is to include redundant processors and links so that the array is reconfigurable when some processors fail. Another typical technique is to implement each process...
详细信息
A typical fault-tolerance technique of systolic arrays is to include redundant processors and links so that the array is reconfigurable when some processors fail. Another typical technique is to implement each processor by a majority voter and N (N greater-than-or-equal-to 3) copies of processors so that the faults of up to N-2 copies of processors can be masked without reconfiguration. This paper proposes a systolic linear array called reconfigurable modular redundant linear array (RMA) that combines these techniques with N=4. When up to 2 copies of each processor fail in RMA, the faults can be masked without reconfiguration. When some voters or more than 2 copies of a processor fail, RMA can be reconfigured by specifying a new switch pattern. In order to perform reconfiguration efficiently, we present a reconfiguration algorithm with time complexity 0(n), where n is the number of processors in RMA.
A reconfigurable multiprocessor architecture embedding a shared-bus connected system and an SIMD dedicated-bus system is proposed in this paper. The shared-bus system uses a reduced number of buses. The reconfiguratio...
详细信息
A reconfigurable multiprocessor architecture embedding a shared-bus connected system and an SIMD dedicated-bus system is proposed in this paper. The shared-bus system uses a reduced number of buses. The reconfiguration is achieved through programmable internal switches and crosspoint switches. The aim in developing this reconfigurable architecture is to provide flexibility in choosing various architectures based on the structure of parallel algorithms and parallel computation. We analyze the bandwidth of the shared-bus system and compare the results with a general multiple-bus architecture.
暂无评论