Abstract
A hardware independent method of programming a massively parallel machine (MPP) can best be supported by a well-designed run-time environment. An important problem in this design is the ability of efficiently simulating networks different from the hardware topology. We will describe the mapping kernel of the virtual processors library for the commercial run-time system PARIX3. This kernel contains description classes for several topologies (so-called virtual topologies) and implementations of respective embeddings which map given instances of virtual topologies onto others or onto the hardware. Using these functions, PARIX is able to establish concrete virtual topologies with corresponding communication channels. The implemented functions were selected with respect to the well-known criteria for graph embeddings: equal load and small dilation. Additionally, we focus on fast distributed computation and universal applicability. As an example, we will show new methods for efficiently embedding an arbitrary 2-dimensional grid as a guest graph into any 2-dimensional grid as a host graph.
This work was partly supported by the EU ESPRIT Basic Research Action No. 7141 (ALCOM II) and the EU Human Capital and Mobility project: “Efficient Use of Parallel Computers: Architecture, Mapping and Communication”.
Chapter PDF
References
R. Aleliunas, A. Rosenberg: On Embedding Rectangular Grids in Square Grids, IEEE Transactions on Computers, Vol. C-31, No. 9, September 1982.
F.S. Annexstein: Parallel Implementations of Graph Embeddings, Parallel Architectures and their efficient use, Lecture Notes in Computer Science, Vol. 678, 1992.
M. Baumslag, M.C. Heydemann, J. Opatrny, D. Sotteau: Embeddings of shuffle-like graphs in hypercubes, Parallel Architectures and Languages Europe (PARLE'91), Springer LNCS 505, pp. 179–190, 1991.
J.E. Boillat, P.G. Kropf: A fast distributed Mapping Algorithm, Proc. of CONPAR '90, Springer LNCS 457, 1990.
M.Y. Chan: Embedding of Grids into Optimal Hypercubes, SIAM J. Computing, Vol. 20, No. 5, pp. 834–864, 1991.
M.Y. Chan, F.Y.L. Chin: Parallelized simulation of grids by hypercubes, Technical Report, University of Hong Kong, October 1990.
R. Diekmann, R. Lüling, J. Simon: Problem Independent Distributed Simulated Annealing and its Applications, Applied Simulated Annealing, Lecture Notes in Economics and Mathematical Systems, Springer LNEMS 396, 1993.
R. Heckmann, R. Klasing, B. Monien, W. Unger: Optimal Embedding of Complete Binary Trees into Lines and Grids, Proc. 17th Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG91), Springer LNCS 570, pp. 25–35, 1991.
C.T. Ho, S.L. Johnsson: Embedding Meshes in Boolean Cubes by Graph Decomposition, Journal of Parallel an Distributed Computing, 8, pp. 325–339, 1990.
S.-H. Huang, H.L. Liu, R. Verma: A New Combinatorial Approach to Optimal Embeddings of Rectangles, Intern. Parallel Processing Symposium, 1994.
S.R. Kosaraj, M.J. Atallah: Optimal Simulations Between Mesh-Connected Arrays of Processors, ACM Symposium on Theory of Computing, pp. 264–272, 1986.
E. Ma, D.G. Shea: The Embedding Kernel on the IBM Victor Multiprocessor for Program Mapping and Network Reconfiguration, Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing, 1990.
Z. Miller, I.H. Sudborough: Compressing Grids into Small Hypercubes, Networks, Vol. 24, pp. 327–358, 1994.
B. Monien, I.H. Sudborough: Embedding one Interconnection Network in Another, Computing Suppl. 7, pp. 257–282, 1990.
J. Philbin: Virtual Topologies: A New Concurrency Abstraction for High-Level Parallel Languages, DIMACS Workshop on Interconnection Networks, 1994.
M. Röttger, U.-P. Schroeder, J. Simon: Implementation of a Parallel and Distributed Mapping Kernel for PARIX, Intern. Conference and Exhibition on Highperformance Computing and Networking, (HPCN Europe'95), pp. 781–786, 1995.
M. Röttger, U.-P. Schroeder, W. Unger: Embedding 3-dimensional Grids into optimal Hypercubes, Proc. of the 1st Canada-France Conference on Parallel Computing (CFCP '94), Springer LNCS 805, pp. 81–94, 1994.
F.C. Sang, I.H. Sudborough: Embedding Large Meshes into Small Ones, Proc. of the IEEE Symposium on Circuits and Systems, Vol. 1, pp. 323–326, 1990.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Römke, T., Röttger, M., Schroeder, UP., Simon, J. (1995). On efficient embeddings of grids into grids in PARIX. In: Haridi, S., Ali, K., Magnusson, P. (eds) EURO-PAR '95 Parallel Processing. Euro-Par 1995. Lecture Notes in Computer Science, vol 966. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0020464
Download citation
DOI: https://doi.org/10.1007/BFb0020464
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60247-7
Online ISBN: 978-3-540-44769-6
eBook Packages: Springer Book Archive