1-1hit |
M. A. Amaral HENRIQUES Hideo ITO
The problem of embedding two-dimensional grids into hypercube parallel computers is the main subject of this work. Two methods (called dilation 1 and dilation 2 embedding) are used to embed a grid and their performances are evaluated. In dilation 1 (d1) embedding a grid edge connecting 2 points is mapped into one hypercube link, and in dilation 2 (d2) embedding there are cases in which one grid edge is mapped into two hypercube links. Generally, this makes the performance of d2 embedding poorer than that of d1 embedding, as communication between some adjacent grid points have to be forwarded through an intermediate link. However, there are cases where d2 embedding allows a more efficient use of the hypercube, as more processors can be used in the embedding. Thus, it is necessary to find out what kind of embedding achieves the best performance. We assume that the number of grid points is larger than the number of processors, and then propose a method to divide the grid in rectangular parts of arbitrary size called fragments, which are actually embedded into a processor. Using the parameters of a commercial hypercube, the performances of several grids embedded under different conditions are evaluated. As a result, the relation between hypercube size and grid size is found to have a strong influence on the choice of the embedding method.