A good mapping is said to exist when adjacent processors in the guest
network are mapped to reasonably close processors in the host network
(i.e. small dilation) and when the paths between adjacent
processors in the guest network are chosen in such a way
that the congestion at each host node and across each host edge is
moderately small (i.e. small node- and edge-congestion).
In the case of mapping guest networks onto smaller hosts,
the processors of the host
have to be assigned to a similar number of processes from the guest
(i.e. small load-factor).
In [MS], Monien and Sudborough reviewed results on embedding network and program structures into popular parallel computer architectures.
In [M], Monien demonstrated how to embed an arbitrary binary tree
with dilation 11
and optimal expansion into an X-tree. This was the first result proving
that every binary tree can be simulated by a natural
network of bounded degree with constant dilation and constant expansion.
Heckmann, Klasing, Monien, and Unger [HKMU] proved that the complete binary tree can be embedded into the square grid of the same size with almost optimal dilation (up to a very small factor).
Bezrukov, Monien, and Unger [BMUW] examined the embedding of caterpillars - a special type of trees where vertices of degree 3 or greater lie on a single path - into the hypercube. For this purpose they introduced two ``new tools''. One of them is the iterative embedding into the hypercube using its ``dense subsets''. The second tool is the ``ladder'' a subgraph of the hypercube. They examined the problem of minimizing the dilation of embedding a caterpillar into its optimum-size hypercube and presented lower and upper bounds for the dilation.
Feldmann and Unger [FU] proved the cube-connected-cycles network of dimension n to be a subgraph of the butterfly network of dimension n. Additionally, they demonstrate that the shuffle-exchange graph of dimension n is a subgraph of the DeBruijn network of dimension n. Klasing, Lüling and Monien [KLM] show that large cube-connected-cycles and butterfly networks can be simulated very efficiently on smaller ones.
Röttger, Schroeder and Unger [RSU] were the first to prove that every 3-dimensional grid with at most 2^9-18 nodes is embeddable into its optimal hypercube with dilation 2. Additionally, they introduced new easily computable functions which embed many 3-dimensional grids into their optimal hypercubes with dilation 2. Moreover, they demonstrated that one can reduce the open problem to recognize whether it is possible to embed every 3-dimensional grid into its optimal hypercube with dilation at most 2 by constructing embeddings for a particular class of grids.
To extend the software portability of parallel applications of the PARIX run-time system and to improve the handling and efficiency of PARIX a mapping kernel and a distributed mapping workbench have been implemented (see [RSS]). Many-to-one embeddings of the pipe, the ring, the hypercube, the complete k-ary tree, and arbitrary 2D and 3D meshes and tori into 2D meshes were appended to PARIX.
If you are interested, please contact Burkhard Monien, Walter Unger, Markus Röttger or Ulf-Peter Schroeder.