Large Scale Rectangular Grids in Hypercubes: An Embedding Scheme and Its Evaluation

M. A. Amaral HENRIQUES; Hideo ITO

Large Scale Rectangular Grids in Hypercubes: An Embedding Scheme and Its Evaluation

M. A. Amaral HENRIQUES, Hideo ITO

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E74-D No.6 pp.1705-1714

Publication Date: 1991/06/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Software Systems

Authors

M. A. Amaral HENRIQUES
Hideo ITO

Keyword

Cite this

Copy

M. A. Amaral HENRIQUES, Hideo ITO, "Large Scale Rectangular Grids in Hypercubes: An Embedding Scheme and Its Evaluation" in IEICE TRANSACTIONS on Information, vol. E74-D, no. 6, pp. 1705-1714, June 1991, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e74-d_6_1705/_p

Copy

@ARTICLE{e74-d_6_1705,
author={M. A. Amaral HENRIQUES, Hideo ITO, },
journal={IEICE TRANSACTIONS on Information},
title={Large Scale Rectangular Grids in Hypercubes: An Embedding Scheme and Its Evaluation},
year={1991},
volume={E74-D},
number={6},
pages={1705-1714},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={June},}

Copy

TY - JOUR
TI - Large Scale Rectangular Grids in Hypercubes: An Embedding Scheme and Its Evaluation
T2 - IEICE TRANSACTIONS on Information
SP - 1705
EP - 1714
AU - M. A. Amaral HENRIQUES
AU - Hideo ITO
PY - 1991
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E74-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 1991
AB - 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.
ER -