Skip to main content
Top

2006 | Book

Parallel Algorithms and Cluster Computing

Implementations, Algorithms and Applications

insite
SEARCH

About this book

Highperformancecomputinghaschangedthewayinwhichscienceprogresses. During the last 20 years the increase in computing power, the development of e?ective algorithms, and the application of these tools in the area of physics and engineering has been decisive in the advancement of our technological world. These abilities have allowed to treat problems with a complexity which had been out of reach for analytical approaches. While the increase in perf- mance of single processes has been immense the increase of massive parallel computing as well as the advent of clustercomputershas opened up the pos- bilities to study realistic systems. This book presents major advances in high performance computing as well as major advances due to high performance computing. The progress made during the last decade rests on the achie- ments in three distinct science areas. Openandpressingproblemsinphysicsandmechanicalengineeringarethe drivingforcebehindthedevelopmentofnewtoolsandnewapproachesinthese science areas. The treatment of complex physical systems with frustration and disorder, the analysis of the elastic and non-elastic movement of solids as well as the analysis of coupled ?uid systems, pose problems which are open to a numerical analysis only with state of the art computing power and algorithms. The desire of scienti?c accuracy and quantitative precision leads to an enormous demand in computing power. Asking the right questions in these areas lead to new insights which have not been available due to other means like experimental measurements. Thesecondareawhichisdecisivefore?ectivehighperformancecomputing is a realm of e?ective algorithms.

Table of Contents

Frontmatter

Implementions

Frontmatter
Parallel Programming Models for Irregular Algorithms
Abstract
Applications from science and engineering disciplines make extensive use of computer simulations and the steady increase in size and detail leads to growing computational costs. Computational resources can be provided by modern parallel hardware platforms which nowadays are usually cluster systems. Effective exploitation of cluster systems requires load balancing and locality of reference in order to avoid extensive communication. But new sophisticated modeling techniques lead to application algorithms with varying computational effort in space and time, which may be input dependent or may evolve with the computation itself. Such applications are called irregular. Because of the characteristics of irregular algorithms, efficient parallel implementations are difficult to achieve since the distribution of work and data cannot be determined a priori. However, suitable parallel programming models and libraries for structuring, scheduling, load balancing, coordination, and communication can support the design of efficient and scalable parallel implementations.
Gudula Rünger
Basic Approach to Parallel Finite Element Computations: The DD Data Splitting
Abstract
From Amdahl’s Law we know: the efficient use of parallel computers can not mean a parallelization of some single steps of a larger calculation, if in the same time a relatively large amount of sequential work remains or if special convenient data structures for such a step have to be produced with the help of expensive communications between the processors. From this reason, our basic work on parallel solving partial differential equations was directed to investigating and developing a natural fully parallel run of a finite element computation – from parallel distribution and generating the mesh – over parallel generating and assembling step – to parallel solution of the resulting large linear systems of equation and post–processing.
Arnd Meyer
A Performance Analysis of ABINIT on a Cluster System
Abstract
In solid state physics, bonding and electronic structure of a material can be investigated by solving the quantum mechanical (time-independent) Schrödinger equation
Torsten Hoefler, Rebecca Janisch, Wolfgang Rehm
Some Aspects of Parallel Postprocessing for Numerical Simulation
Abstract
The topics discussed in this paper are closely connected to the development of parallel finite element algorithms and software based on domain decomposition [1, 2]. Numerical simulation on parallel computers generally produces data in large quantities being kept in the distributed memory. Traditional methods of postprocessing by storing all data and processing the files with other special software in order to obtain nice pictures may easily fail due to the amount of memory and time required.
Matthias Pester

Algorithms

Frontmatter
Efficient Preconditioners for Special Situations in Finite Element Computations
Abstract
From the very efficient use of hierarchical techniques for the quick solution of finite element equations in case of linear elements, we discuss the generalization of these preconditioners to higher order elements and to the problem of crack growth, where the introduction to of the crack opening would destroy existing mesh hierarchies. In the first part of this paper, we deal with the higher order elements. Here, especially elements based on cubic polynomials require more complicate tasks such as the definition of ficticious spaces and the Ficticious Space Lemma. A numerical example demonstrates that iteration numbers similar to the linear case are obtained.
Arnd Meyer
Nitsche Finite Element Method for Elliptic Problems with Complicated Data
Abstract
For the efficient numerical treatment of boundary value problems (BVPs), domain decomposition methods are widely used in science and engineering. They allow to work in parallel: generating the mesh in subdomains, calculating the corresponding parts of the stiffness matrix and of the right-hand side, and solving the system of finite element equations.
Bernd Heinrich, Kornelia Pönitz
Hierarchical Adaptive FEM at Finite Elastoplastic Deformations
Abstract
The simulation of non-linear problems of continuum mechanics was a crucial point within the framework of the subproject “Efficient parallel algorithms for the simulation of the deformation behaviour of components of inelastic materials”. Nonlinearity appears with the occurence of finite deformations as well as with special material behaviour as e.g. elastoplasticity.
Reiner Kreißig, Anke Bucher, Uwe-Jens Görke
Wavelet Matrix Compression for Boundary Integral Equations
Abstract
Many mathematical models concerning for example field calculations, flow simulation, elasticity or visualization are based on operator equations with global operators, especially boundary integral operators. Discretizing such problems will then lead in general to possibly very large linear systems with densely populated matrices. Moreover, the involved operator may have an order different from zero which means that it acts on different length scales in a different way. This is well known to entail the linear systems to become more and more ill-conditioned when the level of resolution increases. Both features pose serious obstructions to the efficient numerical treatment of such problems to an extent that desirable realistic simulations are still beyond current computing capacities.
Helmut Harbrecht, Ulf Kähler, Reinhold Schneider
Numerical Solution of Optimal Control Problems for Parabolic Systems
Abstract
We consider nonlinear parabolic diffusion-convection and diffusion-reaction systems of the form
Peter Benner, Sabine Görner, Jens Saak

Applications

Frontmatter
Parallel Simulations of Phase Transitions in Disordered Many-Particle Systems
Abstract
Phase transitions in classical and quantum many-particle systems are one of the most fascinating topics in contemporary condensed matter physics. The strong fluctuations associated with a phase transition or critical point can lead to unusual behavior and to novel, exotic phases in its vicinity, with consequences for problems such as quantum magnetism, unconventional superconductivity, non-Fermi liquid physics, and glassy behavior in doped semiconductors. In many realistic systems, impurities, dislocations, and other forms of quenched disorder play an important role. They often modify or even enhance the effects of the critical fluctuations. An interesting, if intricate, aspect of phase transitions with quenched disorder are the rare regions. These are large spatial regions that, due to a strong disorder fluctuation, are either devoid of impurities or have stronger interactions than the bulk system. They can be locally in one of the phases even though the bulk system may be in another phase. The slow fluctuations of these rare regions can dominate the behavior of the entire system.
Thomas Vojta
Localization of Electronic States in Amorphous Materials: Recursive Green’s Function Method and the Metal-Insulator Transition at E ≠ 0
Abstract
Traditionally, condensed matter physics has focused on the investigation of perfect crystals. However, real materials usually contain impurities, dislocations or other defects, which distort the crystal. If the deviations from the perfect crystalline structure are large enough, one speaks of disordered systems. The Anderson model [1] is widely used to investigate the phenomenon of localisation of electronic states in disordered materials and electronic transport properties in mesoscopic devices in general. Especially the occurrence of a quantum phase transition driven by disorder from an insulating phase, where all states are localised, to a metallic phase with extended states, has led to extensive analytical and numerical investigations of the critical properties of this metal-insulator transition (MIT) [2–4]. The investigation of the behaviour close to the MIT is supported by the one-parameter scaling hypothesis [5, 6]. This scaling theory originally formulated for the conductance plays a crucial role in understanding the MIT [7]. It is based on an ansatz interpolating between metallic and insulating regimes [8]. So far, scaling has been demonstrated to an astonishing degree of accuracy by numerical studies of the Anderson model [9–13]. However, most studies focused on scaling of the localisation length and the conductivity at the disorder-driven MIT in the vicinity of the band centre [9, 14, 15]. Assuming a power-law form for the d.c. conductivity, as it is expected from the one-parameter scaling theory, Villagonzalo et al. [6] have used the Chester-Thellung-Kubo-Greenwood formalism to calculate the temperature dependence of the thermoelectric properties numerically and showed that all thermoelectric quantities follow single-parameter scaling laws [16, 17].
Alexander Croy, Rudolf A. Römer, Michael Schreiber
Optimizing Simulated Annealing Schedules for Amorphous Carbons
Abstract
Annealing, carried out in simulation, has taken on an existence of its own as a tool to solve optimization problems of many kinds [1–3]. One of many important applications is to find local minima for the potential energy of atomic structures, as in this paper, in particular structures of amorphous carbon at room temperature. Carbon is one of the most promising chemical elements for molecular structure design in nature. An infinite richness of different structures with an incredibly wide variety of physical properties can be produced. Apart from the huge variety of organic substances, even the two crystalline inorganic modifications, graphite and diamond, show diametrically opposite physical properties. Amorphous carbon continues to attract researchers for both the fundamental understanding of the microstructure and stability of the material and the increasing interest in various applications as a high performance coating material as well as in electronic devices.
Peter Blaudeck, Karl Heinz Hoffmann
Amorphisation at Heterophase Interfaces
Abstract
Heterophase interfaces are boundaries, which join two material types with different physical and chemical nature. Therefore, heterophase interfaces can exhibit a large variety of geometric morphologies ranging from atomically sharp boundaries to gradient materials, in which an interface-specific phase is formed, which provides a continuous change of the structural parameters and thus reduces elastic strains and deformations. In addition, also the electronic properties of the two materials may be different, e.g. at boundaries between an electronically conducting metal and a semiconductor or an insulating material. Due to the deviations in the electronic structure, various bonding mechanisms are observed, which span the range from weakly interacting systems to boundaries with strong, directed bonding and further to reactively bonding systems which exhibit a new phase at the interface. Thus, both elastic and electronic factors may contribute to the formation of a new, often amorphous phase at the interface. Numerical simulations based on electronic structure theory are an efficient tool to distinguish and quantify these different influence factors, and massively parallel computers nowadays provide the required numerical power to tackle structurally more demanding systems. Here, this power has been exploited by the parallelisation over an optimised set of integration points, which split the solution of the Kohn-Sham equations into a set of matrix equations with equal matrix sizes. In this way, the analysis and prediction of material properties at the nanoscale has become feasible.
Sibylle Gemming, Andrey Enyashin, Michael Schreiber
Energy-Level and Wave-Function Statistics in the Anderson Model of Localization
Abstract
Universal aspects of correlations in the spectra and wave functions of closed, complex quantum systems can be described by random-matrix theory (RMT) [1]. On small energy scales, for example, the eigenvalues, eigenfunctions and matrix elements of disordered quantum systems in the metallic regime [2] or those of classically chaotic quantum systems [3] exhibit universal statistical properties very well described by RMT. It is now also well established that deviations from RMT behaviour are often significant at larger energy scales.
Bernhard Mehlig, Michael Schreiber
Fine Structure of the Integrated Density of States for Bernoulli–Anderson Models
Abstract
Disorder is one of the fundamental topics in science today. A very prominent example is Anderson’s model [1] for the transition from metal to insulator under the presence of disorder.
Peter Karmann, Rudolf A. Römer, Michael Schreiber, Peter Stollmann
Modelling Aging Experiments in Spin Glasses
Abstract
Spin glasses are a paradigm for complex systems. They show a wealth of different phenomena including metastability and aging. Especially in the low temperature regime they reveal a very complex dynamical behaviour. For temperatures below the spin glass transition temperature one finds a variety of features connected to the inability of the systems to attain thermodynamic equilibrium with the ambient conditions on the observation time scale: aging and memory effects have been observed in many experiments [1–11]. Spin glasses are good model systems as their magnetism provides an easy and very accurate experimental probe into their dynamic behavior. In order to investigate such features different experimental techniques have been applied. Complicated setups including temperature and field changes with subsequent relaxation phases lead to more interesting effects such as age reinitialization and freezing [12, 13].
Karl Heinz Hoffmann, Andreas Fischer, Sven Schubert, Thomas Streibert
Random Walks on Fractals
Abstract
Porous materials such as aerogel, porous rocks or cements exhibit a fractal structure for a range of length scales [1]. Diffusion processes in such disordered media are widely studied in the physical literature [2, 3]. They exhibit an anomalous behavior in terms of the asymptotic time scaling of the mean square displacement of the diffusive particles
Astrid Franz, Christian Schulzky, Do Hoang Ngoc Anh3, Steffen Seeger, Janett Balg, Karl Heinz Hoffmann
Lyapunov Instabilities of Extended Systems
Abstract
One of the most successful theories in modern science is statistical mechanics, which allows us to understand the macroscopic (thermodynamic) properties of matter from a statistical analysis of the microscopic (mechanical) behavior of the constituent particles. In spite of this, using certain probabilistic assumptions such as Boltzmann’s Stosszahlansatz causes the lack of a firm foundation of this theory, especially for non-equilibrium statistical mechanics. Fortunately, the concept of chaotic dynamics developed in the 20th century [1] is a good candidate for accounting for these difficulties. Instead of the probabilistic assumptions, the dynamical instability of trajectories can make available the necessary fast loss of time correlations, ergodicity, mixing and other dynamical randomness [2]. It is generally expected that dynamical instability is at the basis of macroscopic transport phenomena and that one can find certain connections between them. Some beautiful theories in this direction were already developed in the past decade. Examples are the escape-rate formalism by Gaspard and Nicolis [3, 4] and the Gaussian thermostat method by Nosé, Hoover, Evans, Morriss and others [5, 6], where the Lyapunov exponents were related to certain transport coefficients.
Hong-liu Yang, Günter Radons
The Cumulant Method for Gas Dynamics
Abstract
Characterizing fluid flow by the ratio of mean free path and a characteristic flow length (the Knudsen number Kn) we have two extremes: dense gases (Kn ≪ 1) where modeling by Euler or Navier-Stokes equations is valid and rarefied gases (Kn ≫ 1) for which modeling by the Boltzmann equation is necessary. Developing models for the intermediate transition regime is subject to active current research because despite the tremendously growing increase in computational and algorithmic computing performance, numerical simulation of flows in the transition regime remains a challenging problem. Thus there is a considerable gap in the ability to model flows where mean free path and characteristic flow lengths are comparable. However, efficient methods for simulating transition regime flows will be an important design tool for micro-scale machinery, where dense gas models become invalid.
Steffen Seeger, Karl Heinz Hoffmann, Arnd Meyer
Backmatter
Metadata
Title
Parallel Algorithms and Cluster Computing
Editors
Karl Heinz Hoffmann
Arnd Meyer
Copyright Year
2006
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-33541-2
Print ISBN
978-3-540-33539-9
DOI
https://doi.org/10.1007/3-540-33541-2

Premium Partner