SUBCUBE EMBEDDABILITY OF FOLDED HYPERCUBES
Shahram Latifi · Parallel Processing Letters · 1991
The Folded Hypercube (FHC) has been proven to be an attractive hypercube-based network. This paper closely compares the FHC to its standard hypercube counterpart from the subcube allocation viewpoint. It is shown that the FHC(n) outperforms the n-dimensional hypercube (n-cube for short) in offering subcubes of size k by a factor of [Formula: see text]. In an environment where subcubes of the original network must be allocated to incoming tasks, the FHC achieves an excellent processor utilization by assigning subcubes in an efficient and compact manner. Using the concept of virtual hypercubes, an efficient way is suggested to recognize the available subcubes in the FHC by adapting the already developed subcube recognition algorithms. An alternative approach to the subcube recognition problem is also given.