A PARALLEL ALGORITHM FOR AN EFFICIENT MAPPING OF GRIDS IN HYPERCUBES

This paper parallelizes the embedding strategy for mapping any two-dim ensional grid into its optimal hypercube with minimal dilation. The pa rallelization allows each hypercube node to independently determine, i n constant time, which grid node it will simulate and the communicatio n paths it will take to reach the hypercube nodes which simulate its g rid-neighbors. The paths between grid-neighbors are chosen in such a w ay as to curb the congestion at each hypercube node and across each hy percube edge. Explicity, the node congestion for our embedding is at m ost 6 (one above optimal), while the edge congestion is at most 5.