QUICK RECOVERY OF 2 EMBEDDED COMPLETE BINARY-TREES IN A HYPERCUBE

被引：4

作者：

HSU, CC

LIU, YW

机构：

[1] Natl Taiwan Inst of Technology, Taipei

来源：

IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES | 1994年 / 141卷 / 04期

关键词：

COMPLETE BINARY TREE; DILATION; EMBEDDING; HYPERCUBE; PROCESSOR UTILIZATION;

D O I：

10.1049/ip-cdt:19941150

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In the paper, the authors propose a novel approach for embedding a (d - 1) level and a (d - 2) level complete binary tree (CBT) into a d-dimensional hypercube (d-cube). Moreover, free processors are used as spare processors to recover a single fault in the two trees. The primary results are that the (d - 1)-CBT can be recovered in at most two steps and the (d - 2)-CBT in one step. The dilation of the recovered embedding is at most two and the processor utilisation is near 75%.

引用

页码：205 / 211

页数：7

共 11 条

[1]

DESPHANDE SR, 1986, P 1986 INT C PAR PRO, P661

[2] COMMUNICATION EFFICIENT BASIC LINEAR ALGEBRA COMPUTATIONS ON HYPERCUBE ARCHITECTURES [J].