University of Paderborn Computer Science Home AG-Monien Research   Graph   Virtual Topology Library Mapping Workbench

Virtual Topology Library for PARIX PARIX (PARallel extensions to UnIX [12]) is a commercial run-time system for parallel computers distributed by the Parsytec GmbH. To extend the software portability of parallel applications and to improve the handling and efficiency of PARIX a mapping kernel and a distributed mapping workbench have been implemented as library tools at the University of Paderborn and the PC˛ (Paderborn Center for Parallel Computing). The main goal of this project is to make the theoretical results from the areas ``graph embedding'' and ``simulation among networks'' available to non-expert users. Most of the parallel applications possess an ``a priori''-known connection structure of the corresponding communication graph. The simulation of the most important communication graphs should be supported by the run-time system. Since the underlying hardware often differs from the demand communication graph or an application uses different communication graphs at run-time, the concept of virtual topologies was developed. A virtual topology consists of a set of processes and of a set of fixed connections (links) between them. The mapping kernel is composed of a collection of virtual topology library functions. Each of these functions realizes a concrete virtual topology while the single processes are placed on the processors and the links are established with communication primitives of PARIX. Thus, the user is able to implement complex parallel applications without the explicit knowledge of the PARIX communication tasks or of results of theoretical computer science. The graph embedding algorithms which are implemented as functions in the mapping kernel satisfy the following criteria: small dilation (a well-known cost measure for graph embeddings) distributed and fast computation universal applicability easy computation of the inverse embedding Since the underlying hardware of most Transputer systems is realized without a special routing chip, a minimized value for the dilation is of great importance. Thus, the majority of the work done was to adapt well-known embedding techniques and also to develop some new embedding algorithms. For more details, see [6]. In 1993, PARIX 1.2 including the virtual topology library that consists of one-to-one embeddings of the pipe, the ring, the hypercube, the complete k-ary tree [8], the clique, the star, the 2D and 3D grid [5] and torus, and the DeBruijn network on 2D grids has been released (all functions are implemented in C). For a good overview of most of the used embeddings, see [11]. Additionally, the following algorithms have been implemented in a distributed mapping workbench [3] which is integrated in the parallel computing environment of the University of Paderborn: Embedding of specific networks: Simulation of large cube-connected cycles and butterfly networks on smaller ones [9] Simulation of large grids and trees on smaller grids and hypercubes [5], [8], [10] Embedding of arbitrary networks (using heuristics): Mapping with a parallel genetic algorithm [7] (the adaptation of genetic algorithms to the mapping problem is developed within this project [3]) Parallel mapping with the diffusion approach according to [2] Mapping with a parallel Boltzmann Machine [1] (the adaptation of the Boltzmann Machine to the mapping problem is developed within this project [3]) Mapping with Simulated Annealing [4] Some additional functions can be found in a library that simplifies the usage of broadcast and accumulation algorithms. The code of these functions and of the distributed mapping workbench is available as public domain software at the University of Paderborn. Further work was done on an extension to many-to-one embeddings of the mapping kernel that was implemented in C++ [14,15]. For more details, see [6,13,14,15]. If you are interested, please contact Markus Röttger or Ulf-Peter Schroeder. References [1] Aarts, Kost: Simulated Annealing and Boltzmann Machines John Wiley & Sons, 1989. [2] Boillat, Kropf: A fast distributed Mapping Algorithm Proc. of CONPAR '90, Springer LNCS 457, 1990. [3] Diekmann, Monien: MaP -a Distributed Mapping Workbench Draft University of Paderborn, 1994. [4] 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 LNEMS 396, Springer Verlag, pp. 17-44, 1993. see abstract or postscript [5] Ellis, Miller, Sudborough: Compressing Meshes into small Hypercubes Manuscript Computer Science Program M.P.31, University of Texas, Dallas, 1992. [6] M. Röttger, U.-P. Schroeder, J. Simon: Virtual Topology Library for PARIX Technical Report, No. 148, University of Paderborn, 1994. see abstract or postscript [7] Goldberg: Genetic Algorithms in Search, Optimization and Machine Learning Addison Welsey, 1989. [8] R. Heckmann, R. Klasing, B. Monien, W. Unger: Optimal Embedding of Complete Binary Trees into Lines and Grids Proc. of the 17th Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG '91), Springer LNCS 570, pp. 25-35, 1991. see abstract or postscript [9] R. Klasing, R. Lüling, B. Monien: Compressing Cube-Connected Cycles and Butterfly Networks Proc. of the 2nd IEEE Symposium on Parallel and Distributed Processing (SPDP '90), pp. 858-865, 1990, and Technical Report, No. 112, University of Paderborn, 1993. see abstract or postscript [10] Miller, Sudborough: Compressing Grids into Small Hypercubes University of Texas at Dallas, 1992. [11] B. Monien, H. Sudborough: Embedding one Interconnection Network in Another Computing Suppl. 7, 1990, pp. 257-282, 1990. [12]Parsytec Computer GmbH: PARIX 1.2 Documentation and Reference Manual [13] M. Röttger, U.-P. Schroeder, J. Simon: Implementation of a Parallel and Distributed Mapping Kernel for PARIX Proc. of the Intern. Conference and Exhibition on High-Performance Computing and Networking, (HPCN Europe'95), LNCS 919, Springer-Verlag, pp. 781-786, 1995. see abstract or postscript [14] T. Römke, M. Röttger, U.-P. Schroeder, J. Simon: Efficient Mapping Library for Parix Proceedings ZEUS'95, Workshop on Parallel Programming and Computation IOS Press 1995, pp. 275-284, 1995. see abstract or postscript [15] T. Römke, M. Röttger, U.-P. Schroeder, J. Simon: On Efficient Embeddings of Grids into Grids in PARIX Proc. of the first Intern. EURO-PAR Conference LNCS 966, Springer-Verlag, pp. 181-204, 1995. see abstract or postscript   updated by Norbert Sensen Okt/30/1997