Fault Tolerant Processor Allocation in Hypercube Multiprocessors

Dusan JOKANOVIC; Norio SHIRATORI; Shoichi NOGUCHI

Fault Tolerant Processor Allocation in Hypercube Multiprocessors

Dusan JOKANOVIC, Norio SHIRATORI, Shoichi NOGUCHI

Full Text Views

0

Cite this

Summary :

In hypercube multiprocessors it is important for the resource manager to be able to recognize and allocate subcubes of adequate sizes. Known allocation schemes, such as Gray code allocation strategy, do not consider hypercube in which there are faulty processors. However, faulty processors destroy some of the subcubes which resource manager can recognize searching on the current allocation list. This decreases the allocation performance. We propose a fault tolerant allocation algorithm which reconstucts allocaton list in order to remedy damege caused by faults. First, one measure of goodness of allocation list is introsuced referred to as a subcube recogizability. Then, general rules for allocation list restructuring are formulated. Accordingly, a two-step algorithm is developed which builds a new allocation list with improved subcube recognizability. Namely, the number and/or size of fault-free recognizable subcubes on the new list are maximal, for the given distribution of faults. Such a graceful degradation of allocation performance in injured hypercube is achieved just by means of prosessor readdressing. At last, the correctness and optimality of the algorithm are proved.

Publication: IEICE TRANSACTIONS on Information Vol.E74-D No.10 pp.3492-3505

Publication Date: 1991/10/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Fault Tolerant Computing

Authors

Dusan JOKANOVIC
Norio SHIRATORI
Shoichi NOGUCHI

Keyword

Cite this

Copy

Dusan JOKANOVIC, Norio SHIRATORI, Shoichi NOGUCHI, "Fault Tolerant Processor Allocation in Hypercube Multiprocessors" in IEICE TRANSACTIONS on Information, vol. E74-D, no. 10, pp. 3492-3505, October 1991, doi: .
Abstract: In hypercube multiprocessors it is important for the resource manager to be able to recognize and allocate subcubes of adequate sizes. Known allocation schemes, such as Gray code allocation strategy, do not consider hypercube in which there are faulty processors. However, faulty processors destroy some of the subcubes which resource manager can recognize searching on the current allocation list. This decreases the allocation performance. We propose a fault tolerant allocation algorithm which reconstucts allocaton list in order to remedy damege caused by faults. First, one measure of goodness of allocation list is introsuced referred to as a subcube recogizability. Then, general rules for allocation list restructuring are formulated. Accordingly, a two-step algorithm is developed which builds a new allocation list with improved subcube recognizability. Namely, the number and/or size of fault-free recognizable subcubes on the new list are maximal, for the given distribution of faults. Such a graceful degradation of allocation performance in injured hypercube is achieved just by means of prosessor readdressing. At last, the correctness and optimality of the algorithm are proved.
URL: https://global.ieice.org/en_transactions/information/10.1587/e74-d_10_3492/_p

Copy

@ARTICLE{e74-d_10_3492,
author={Dusan JOKANOVIC, Norio SHIRATORI, Shoichi NOGUCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Fault Tolerant Processor Allocation in Hypercube Multiprocessors},
year={1991},
volume={E74-D},
number={10},
pages={3492-3505},
abstract={In hypercube multiprocessors it is important for the resource manager to be able to recognize and allocate subcubes of adequate sizes. Known allocation schemes, such as Gray code allocation strategy, do not consider hypercube in which there are faulty processors. However, faulty processors destroy some of the subcubes which resource manager can recognize searching on the current allocation list. This decreases the allocation performance. We propose a fault tolerant allocation algorithm which reconstucts allocaton list in order to remedy damege caused by faults. First, one measure of goodness of allocation list is introsuced referred to as a subcube recogizability. Then, general rules for allocation list restructuring are formulated. Accordingly, a two-step algorithm is developed which builds a new allocation list with improved subcube recognizability. Namely, the number and/or size of fault-free recognizable subcubes on the new list are maximal, for the given distribution of faults. Such a graceful degradation of allocation performance in injured hypercube is achieved just by means of prosessor readdressing. At last, the correctness and optimality of the algorithm are proved.},
keywords={},
doi={},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - Fault Tolerant Processor Allocation in Hypercube Multiprocessors
T2 - IEICE TRANSACTIONS on Information
SP - 3492
EP - 3505
AU - Dusan JOKANOVIC
AU - Norio SHIRATORI
AU - Shoichi NOGUCHI
PY - 1991
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E74-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 1991
AB - In hypercube multiprocessors it is important for the resource manager to be able to recognize and allocate subcubes of adequate sizes. Known allocation schemes, such as Gray code allocation strategy, do not consider hypercube in which there are faulty processors. However, faulty processors destroy some of the subcubes which resource manager can recognize searching on the current allocation list. This decreases the allocation performance. We propose a fault tolerant allocation algorithm which reconstucts allocaton list in order to remedy damege caused by faults. First, one measure of goodness of allocation list is introsuced referred to as a subcube recogizability. Then, general rules for allocation list restructuring are formulated. Accordingly, a two-step algorithm is developed which builds a new allocation list with improved subcube recognizability. Namely, the number and/or size of fault-free recognizable subcubes on the new list are maximal, for the given distribution of faults. Such a graceful degradation of allocation performance in injured hypercube is achieved just by means of prosessor readdressing. At last, the correctness and optimality of the algorithm are proved.
ER -