Embedding complete quad trees into faulty twisted Hypercubes

Abstract EN

The appealing properties of the hypercube topology have made hypercube multiprocessors an important computing structure.

A twisted hypercube interconnection network has a hypercube like structure with additional attractive features.

It preserves many properties of the hypercube and most importantly reduces the diameter by a factor of two.

In this paper, we present a recursive scheme to embed a complete quad tree into a faulty twisted hypercube with dilation two and allow up to 22n-4 faulty processors.