Loading...
Please wait, while we are loading the content...
Similar Documents
Mapping large parallel simulation programs to multicomputer systems
| Content Provider | Semantic Scholar |
|---|---|
| Author | Heiß, Hans-Ulrich Dormanns, Marcus |
| Copyright Year | 1994 |
| Abstract | We consider the problem of mapping parallel simulation programs to distributed memory parallel machines. Since a large fraction of computer simulations consists of solving partial differential equations, the communication patterns of the resulting parallel programs can be exploited to construct efficient mappings which lead to low communication overhead. We report about the application of Kohonen-networks to find such mappings. Most computer simulations deal with physical processes in space and time modeled by a set of partial differential equations (PDEs). Discretization leads to a large sparse system of linear equations or - in case of nonlinear PDEs or discretization in time - to a sequence of such systems. The simulation can therefore easily be parallelized along the spatial structure of the model resulting in programs that can be considered as grid-like graphs with vertices as computational nodes and edges as communication relations between them. Ideally, the parallel machine (MIMD with distributed memory) executing the simulation program matches the topological structure of the model, i.e. the communication graph of the parallel program. While suitable machines can be found for regular problem structures (complete 2D- or 3D-grids), many communication graphs are irregular to some degree, e.g. if the physical system to be modeled is of irregular shape or if the discretization uses different degrees of refinement in different areas (finite element method, FEM). Irregular communication patterns are also usual in parallel discrete event simulation programs. In these cases there exists the problem, how to map the communication graph of the simulation program to the machine graph that consists of the processor nodes and the interconnection links. The goal is to spread the computational load as evenly as possible across the processor network while keeping communication delays low by placing strongly communicating tasks close together. The problem can be formalized as a graph embedding problem which is notoriously NP-hard. Algorithms to solve this problem are therefore of heuristic nature. After giving a brief overview of heuristic approaches to that problem we propose a new algorithm that is based on the concept of self-organizing maps introduced by Kohonen. We show how our algorithm performs compared to the well known Simulated Annealing (SA) heuristic. This is done based on simulation experiments using real FEM-graphs mapped to processor networks of different sizes. As another example application we report about experiences with modeling the non-stationary heat conduction in a irregularly shaped area by the corresponding PDE which is calculated using a parallel Conjugate-Gradient (CG) solver on a transputer-based multicomputer system. |
| Starting Page | 285 |
| Ending Page | 290 |
| Page Count | 6 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://kbs.cs.tu-berlin.de/publications/paps/HD94a.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
