My. Chan et F. Chin, A PARALLEL ALGORITHM FOR AN EFFICIENT MAPPING OF GRIDS IN HYPERCUBES, IEEE transactions on parallel and distributed systems, 4(8), 1993, pp. 933-946
Citations number
17
Categorie Soggetti
System Science","Computer Applications & Cybernetics","Engineering, Eletrical & Electronic
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.