A Graph-Theoretic Approach to Minimizing the Number of Dangerous Processors in Fault-Tolerant Mesh-Connected Processor Arrays(Special Issue on Function Integrated Information Systems)
スポンサーリンク
概要
- 論文の詳細を見る
First, we give a graph-theoretic formalization for the spare assigment problems for two cases of reconfiguring N × 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 whice 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.
- 社団法人電子情報通信学会の論文
- 2001-11-01
著者
関連論文
- A Novel Learning Algorithm Which Makes Multilayer Neural Networks Multiple-Weight-Fault Tolerant(Dependable Systems)(Dependable Computing)
- Self-Reconfiguring of 1 1/2-Track-Switch Mesh Arrays with Spares on One Row and One Column by Simple Built-in Circuit(Dependable Computing)
- An implementation of a fault-tolerant 2D systolic array on an FPGA and its evaluation (ディペンダブルコンピューティング)
- An Efficiently Self-Reconstructing Array System Using E-11/2-Track Switches(Fault Tolerance)
- A System for Efficiently Self-Reconstructing 11/2-Track Switch Torus Arrays
- A Graph-Theoretic Approach to Minimizing the Number of Dangerous Processors in Fault-Tolerant Mesh-Connected Processor Arrays(Special Issue on Function Integrated Information Systems)
- An FPGA Implementation of a Self-Reconfigurable System for the 1 1/2 Track-Switch 2-D Mesh Array with PE Faults