Embedding the Hypercube into the 3-Dimension Mesh

A constant time and space algorithm for embedding the hypercube architecture into the 3-dimension mesh (3Dmesh) is presented. This enables the cube i operation to be performed on the embedded hypercube machine where the interprocessor communication function cube i is defined on the embedded hypercube's PEs as cube i (b n-1 Lb i Lb 0 ) = b n-1 Lb i Lb 0 and b i is the binary complement of b i . 1. Introduction Little work has been done in the area of embedding the hypercube into the mesh. This lack of interest is certainly not due to the nonexistence of mesh based architectures. The mesh is already accepted and the 3D-mesh of processors (PEs) is quickly becoming accepted as a commercial architecture. This is evident by the number of the mesh based machines including the Wavetracer DTC, Maspar MP-1, MPP, AMT DAP, and Intel Paragon XP/S. The Wavetracer DTC has a 3D-mesh and the Maspar MP1 can be software configured to a 3D-mesh. As the 3Dmesh machines become more widely available in indu..