The search functionality is under construction.

The search functionality is under construction.

First, we give a graph-theoretic formalization for the spare assignment 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 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, 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.

- Publication
- IEICE TRANSACTIONS on Information Vol.E84-D No.11 pp.1462-1470

- Publication Date
- 2001/11/01

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section PAPER (Special Issue on Function Integrated Information Systems)

- Category

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Itsuo TAKANAMI, "A Graph-Theoretic Approach to Minimizing the Number of Dangerous Processors in Fault-Tolerant Mesh-Connected Processor Arrays" in IEICE TRANSACTIONS on Information,
vol. E84-D, no. 11, pp. 1462-1470, November 2001, doi: .

Abstract: First, we give a graph-theoretic formalization for the spare assignment 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 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, 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.

URL: https://global.ieice.org/en_transactions/information/10.1587/e84-d_11_1462/_p

Copy

@ARTICLE{e84-d_11_1462,

author={Itsuo TAKANAMI, },

journal={IEICE TRANSACTIONS on Information},

title={A Graph-Theoretic Approach to Minimizing the Number of Dangerous Processors in Fault-Tolerant Mesh-Connected Processor Arrays},

year={2001},

volume={E84-D},

number={11},

pages={1462-1470},

abstract={First, we give a graph-theoretic formalization for the spare assignment 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 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, 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.

keywords={},

doi={},

ISSN={},

month={November},}

Copy

TY - JOUR

TI - A Graph-Theoretic Approach to Minimizing the Number of Dangerous Processors in Fault-Tolerant Mesh-Connected Processor Arrays

T2 - IEICE TRANSACTIONS on Information

SP - 1462

EP - 1470

AU - Itsuo TAKANAMI

PY - 2001

DO -

JO - IEICE TRANSACTIONS on Information

SN -

VL - E84-D

IS - 11

JA - IEICE TRANSACTIONS on Information

Y1 - November 2001

AB - First, we give a graph-theoretic formalization for the spare assignment 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 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, 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.

ER -