Quick recovery of two embedded complete binary trees in a hypercube
Ching-Wen Hsu, Y.-W. Liu · IEE Proceedings - Computers and Digital Techniques · 1994
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%.