Enabling scalable parallel implementations of structured adaptive mesh refinement applications

Parallel implementations of dynamic structured adaptive mesh refinement (SAMR) methods lead to significant runtime management challenges that can limit their scalability on large systems. This paper presents a runtime engine that addresses the scalability of SAMR applications with localized refinements and high SAMR efficiencies on large numbers of processors (upto 1024 processors). The SAMR runtime engine augments hierarchical partitioning with bin-packing based load-balancing to manage the space-time heterogeneity of the SAMR grid hierarchy, and includes a communication substrate that optimizes the use of MPI non-blocking communication primitives. An experimental evaluation on the IBM SP2 supercomputer using the 3-D Richtmyer-Meshkov compressible turbulence kernel demonstrates the effectiveness of the runtime engine in improving SAMR scalability.

A methodology for adaptive mesh refinement in optimum shape design problems

This work presents a methodology based on the use of adaptive mesh refinement (AMR) techniques in the context of shape optimization problems analyzed by the Finite Element Method (FEM). A suitable and very general technique for the parametrization of the optimization problem using B-splines to define the boundary is first presented. Then, mesh generation using the advancing front method, the error estimation and the mesh refinement criteria are dealt with in the context of a shape optimization problems. In particular, the sensitivities of the different ingredients ruling the problem (B-splines, finite element mesh, design behaviour, and error estimator) are studied in detail. The sensitivities of the finite element mesh coordinates and the error estimator allow their projection from one design to the next, giving an “a priori knowledge” of the error distribution on the new design. This allows to build up a finite element mesh for the new design with a specified and controlled level of error. The robustness and reliability of the proposed methodology is checked out with some 2D examples.     

Texture-based volume rendering of adaptive mesh refinement data

Many phenomena in nature and engineering happen simultaneously on rather diverse spatial and temporal scales. In other words, they exhibit a multi-scale character. A special numerical multilevel technique associated with a particular hierarchical data structure is adaptive mesh refinement (AMR). This scheme achieves locally very high spatial and temporal resolutions. Due to its popularity, many scientists are in need of interactive visualization tools for AMR data. In this article, we present a 3D texture-based volume-rendering algorithm for AMR data that directly utilizes the hierarchical structure. Thereby fast rendering performance is achieved even for high-resolution data sets. To avoid multiple rendering of regions that are covered by grids of different levels of resolution, we propose a space partitioning scheme to decompose the volume into axis-aligned regions of equal-sized cells. Furthermore the problems of interpolation artifacts, opacity corrections, and texture memory limitations are addressed. Published online: November 6, 2002 Correspondence to: R. K?hler     

Parallelization of structured,hierarchical adaptive mesh refinement algorithms

We describe an approach to parallelization of structured adaptive mesh refinement algorithms. This type of adaptive methodology is based on the use of local grids superimposed on a coarse grid to achieve sufficient resolution in the solution. The key elements of the approach to parallelization are a dynamic load-balancing technique to distribute work to processors and a software methodology for managing data distribution and communications. The methodology is based on a message-passing model that exploits the coarse-grained parallelism inherent in the algorithms. The approach is illustrated for an adaptive algorithm for hyperbolic systems of conservation laws in three space dimensions. A numerical example computing the interaction of a shock with a helium bubble is presented. We give timings to illustrate the performance of the method. Received: 28 April 1999 / Accepted: 25 November 1999     

Addressing spatiotemporal and computational heterogeneity in structured adaptive mesh refinement

Structured adaptive mesh refinement (SAMR) techniques can provide accurate and cost- effective solutions to realistic scientific and engineering simulations modeling complex physical phenomena. However, the adaptive nature and inherent space–time heterogeneity of SAMR applications result in significant runtime management challenges. Moreover, certain SAMR applications involving reactive flows exhibit pointwise varying workloads and cannot be addressed by traditional parallelization approaches, which assume homogeneous loads. This paper presents hierarchical partitioning, bin-packing based load balancing, and Dispatch structured partitioning strategies to manage the spatiotemporal and computational heterogeneity in SAMR applications. Experimental evaluation of these schemes using 3-D Richtmyer–Meshkov compressible turbulence and 2-D reactive-diffusion kernels demonstrates the improvement in overall performance.     

A new MHD code with adaptive mesh refinement and parallelization for astrophysics

A new code, named MAP, is written in FORTRAN language for magnetohydrodynamics (MHD) simulations with the adaptive mesh refinement (AMR) and Message Passing Interface (MPI) parallelization. There are several optional numerical schemes for computing the MHD part, namely, modified Mac Cormack Scheme (MMC), Lax–Friedrichs scheme (LF), and weighted essentially non-oscillatory (WENO) scheme. All of them are second-order, two-step, component-wise schemes for hyperbolic conservative equations. The total variation diminishing (TVD) limiters and approximate Riemann solvers are also equipped. A high resolution can be achieved by the hierarchical block-structured AMR mesh. We use the extended generalized Lagrange multiplier (EGLM) MHD equations to reduce the non-divergence free error produced by the scheme in the magnetic induction equation. The numerical algorithms for the non-ideal terms, e.g., the resistivity and the thermal conduction, are also equipped in the code. The details of the AMR and MPI algorithms are described in the paper.     

Radiative cooling in numerical astrophysics: The need for adaptive mesh refinement

Energy loss through optically thin radiative cooling plays an important part in the evolution of astrophysical gas dynamics and should therefore be considered a necessary element in any numerical simulation. Although the addition of this physical process to the equations of hydrodynamics is straightforward, it does create numerical challenges that have to be overcome in order to ensure the physical correctness of the simulation. First, the cooling has to be treated (semi-)implicitly, owing to the discrepancies between the cooling timescale and the typical timesteps of the simulation. Secondly, because of its dependence on a tabulated cooling curve, the introduction of radiative cooling creates the necessity for an interpolation scheme. In particular, we will argue that the addition of radiative cooling to a numerical simulation creates the need for extremely high resolution, which can only be fully met through the use of adaptive mesh refinement.     

The NIRVANA code: Parallel computational MHD with adaptive mesh refinement

I report on a new version of the magnetohydrodynamics code NIRVANA¹ which is targeted at the study of astrophysical problems. The new version allows for distributed-memory simulations supporting adaptive mesh refinement. Numerical algorithms include dissipative terms (viscosity, Ohmic diffusion, thermal heat conduction) in a conservative form. Domain decomposition is preferably block-wise in case of unigrid applications but adopts space-filling curve techniques for adaptive mesh applications with a hierarchical block-structured mesh. The code architecture facilitates workload balancing among processors for arbitrary mesh refinement depths maintaining intra-level data locality via space-filling curve mappings and, at the same time, ensuring inter-level data locality by applying a novel technique called block sharing. This way, it is demonstrated that comparable performance can be achieved for problems with locally highly refined grid. The data transfer between processors extensively utilizes the coarse-granularity concept of parallel computing and makes use of the MPI library. Conservation properties of the numerical method carry over to the parallel framework. In particular, the solenoidality condition for the magnetic field is preserved to roundoff precision applying the constrained transport machinery. This paper has its focus of discussion on implementation details related to the parallelization and on a code performance analysis.     

Controlled cost of adaptive mesh refinement in practical 3D finite element analysis

In this paper, attention is restricted to mesh adaptivity. Traditionally, the most common mesh adaptive strategies for linear problems are used to reach a prescribed accuracy. This goal is best met with an h-adaptive scheme in combination with an error estimator. In an industrial context, the aim of the mechanical simulations in engineering design is not only to obtain greatest quality but more often a compromise between the desired quality and the computation cost (CPU time, storage, software, competence, human cost, computer used). In this paper we propose the use of alternative mesh refinement with an h-adaptive procedure for 3D elastic problems. The alternative mesh refinement criteria allow to obtain the maximum of accuracy for a prescribed cost. These adaptive strategies are based on a technique of error in constitutive relation (the process could be used with other error estimators) and an efficient adaptive technique which automatically takes into account the steep gradient areas. This work proposes a 3D method of adaptivity with the latest version of the INRIA automatic mesh generator GAMHIC3D.     

Scalable parallel regridding algorithms for block‐structured adaptive mesh refinement

Block‐structured adaptive mesh refinement (BSAMR) is widely used within simulation software because it improves the utilization of computing resources by refining the mesh only where necessary. For BSAMR to scale onto existing petascale and eventually exascale computers all portions of the simulation need to weak scale ideally. Any portions of the simulation that do not will become a bottleneck at larger numbers of cores. The challenge is to design algorithms that will make it possible to avoid these bottlenecks on exascale computers. One step of existing BSAMR algorithms involves determining where to create new patches of refinement. The Berger–Rigoutsos algorithm is commonly used to perform this task. This paper provides a detailed analysis of the performance of two existing parallel implementations of the Berger–Rigoutsos algorithm and develops a new parallel implementation of the Berger–Rigoutsos algorithm and a tiled algorithm that exhibits ideal scalability. The analysis and computational results up to 98 304 cores are used to design performance models which are then used to predict how these algorithms will perform on 100 M cores. Copyright © 2011 John Wiley & Sons, Ltd.     

Development of a parallel Poisson's equation solver with adaptive mesh refinement and its application in field emission prediction

A parallel electrostatic Poisson's equation solver coupled with parallel adaptive mesh refinement (PAMR) is developed in this paper. The three-dimensional Poisson's equation is discretized using the Galerkin finite element method using a tetrahedral mesh. The resulting matrix equation is then solved through the parallel conjugate gradient method using the non-overlapping subdomain-by-subdomain scheme. A PAMR module is coupled with this parallel Poisson's equation solver to adaptively refine the mesh where the variation of potentials is large. The parallel performance of the parallel Poisson's equation is studied by simulating the potential distribution of a CNT-based triode-type field emitter. Results with ∼100 000 nodes show that a parallel efficiency of 84.2% is achieved in 32 processors of a PC-cluster system. The field emission properties of a single CNT triode- and tetrode-type field emitter in a periodic cell are computed to demonstrate their potential application in field emission prediction.     

A survey of self‐healing systems frameworks

Rising complexity within multi‐tier computing architectures remains an open problem. As complexity increases, so do the costs associated with operating and maintaining systems within these environments. One approach for addressing these problems is to build self‐healing systems (i.e. frameworks) that can autonomously detect and recover from faulty states. Self‐healing systems often combine machine learning techniques with closed control loops to reduce the number of situations requiring human intervention. This is particularly useful in situations where human involvement is both costly to develop, and a source of potential faults. Therefore, a survey of self‐healing frameworks and methodologies in multi‐tier architectures is provided to the reader. Uniquely, this study combines an overview of the state of the art with a comparative analysis of the computing environment, degree of behavioural autonomy, and organisational requirements of these approaches. Highlighting these aspects provides for an understanding of the different situational benefits of these self‐healing systems. We conclude with a discussion of potential and current research directions within this field. Copyright © 2014 John Wiley & Sons, Ltd.     

A survey of routing algorithm for mesh Network-on-Chip

With the rapid development of semiconductor industry, the number of cores integrated on chip increases quickly, which brings tough challenges such as bandwidth, scalability and power into on-chip interconnection. Under such background, Network-on-Chip (NoC) is proposed and gradually replacing the traditional on-chip interconnections such as sharing bus and crossbar. For the convenience of physical layout, mesh is the most used topology in NoC design. Routing algorithm, which decides the paths of packets, has significant impact on the latency and throughput of network. Thus routing algorithm plays a vital role in a wellperformed network. This study mainly focuses on the routing algorithms of mesh NoC. By whether taking network information into consideration in routing decision, routing algorithms of NoC can be roughly classified into oblivious routing and adaptive routing. Oblivious routing costs less without adaptiveness while adaptive routing is on the contrary. To combine the advantages of oblivious and adaptive routing algorithm, half-adaptive algorithms were proposed. In this paper, the concepts, taxonomy and features of routing algorithms of NoC are introduced. Then the importance of routing algorithms in mesh NoC is highlighted, and representative routing algorithms with respective features are reviewed and summarized. Finally, we try to shed light upon the future work of NoC routing algorithms.     

鲁棒自适应控制综述

讨论了鲁棒自适应控制的产生,现有的鲁棒自适应控制方案及发展方向。     

Local heuristic for the refinement of multi-path routing in wireless mesh networks

We consider wireless mesh networks and the problem of routing end-to-end traffic over multiple paths for the same origin–destination pair with minimal interference. We introduce a heuristic for path determination with two distinguishing characteristics. First, it works by refining an extant set of paths, determined previously by a single- or multi-path routing algorithm. Second, it is totally local, in the sense that it can be run by each of the origins on information that is available no farther than the node’s immediate neighborhood. We have conducted extensive computational experiments with the new heuristic, using AODV and OLSR, as well as their multi-path variants, as underlying routing methods. For two different CSMA settings (as implemented by 802.11) and one TDMA setting running a path-oriented link scheduling algorithm, we have demonstrated that the new heuristic is capable of improving the average throughput network-wide. When working from the paths generated by the multi-path routing algorithms, the heuristic is also capable to provide a more evenly distributed traffic pattern.     

An adaptive mesh refinement of quadrilateral finite element meshes based upon an a posteriori error estimation of quantities of interest: modal response

Modal analysis is commonly performed in a vehicle development process to assess dynamic responses of structure designs. This paper presents an adaptive quadrilateral refinement process for modal analysis of elastic shells based upon a posteriori error estimation in natural frequencies. The process provides engineers with an estimation of their modal analysis quality and an effective adaptive refinement tool for quadrilateral meshes. The effectiveness of the process is demonstrated on the eigenvalue analyses of two numerical examples, a shock tower cap and a roof structure. It shows that the solution error in the frequency of interest is effectively reduced through the adaptive refinement process, and the resulting frequency of interest converges to the solution of a very fine model.     

An adaptive mesh refinement of quadrilateral finite element meshes based upon a posteriori error estimation of quantities of interest: linear static response

A posteriori error estimation in finite element analysis serves as an important guide to the meshing tool in an adaptive refinement process. However, the traditional posteriori error estimates, which are often defined in the energy or energy-type norms over the entire domain, provide users insufficient information regarding the accuracy of specific quantities in the solution. This paper describes an adaptive quadrilateral refinement process with a goal-oriented error estimation, in which a posteriori error is estimated with respect to the specified quantity of interest. A highlight of this paper is the demonstration of tools described in the paper used in a practical industrial environment. The performance of this process is demonstrated on several practical problems where the comparison is with the adaptive process based on the traditional error estimation.     

Error analysis and adaptive refinement of boundary elements in elastic problem

The adaptive boundary element mesh generation based on an error analysis scheme called ‘sample point error analysis’ developed previously for the potential problem is extended and applied to the two-dimensional static elastic analysis. The errors on each element are determined as the required modification so aa to enforce the boundary integral equation to hold on the points other than the assumed initial nodes, which are referred to as the sample points. Boundary elements refinement, h-version in this study, is performed with the aid of the extended error indicator defined by the above-mentioned errors multiplied by the corresponding fundamental solutions. Two-dimensional simple problems are analysed to validate the utility of the proposed method.     

Theory and applications of adaptive control—A survey

Progress in theory and applications of adaptive control is reviewed. Different approaches are discussed with particular emphasis on model reference adaptive systems and self-tuning regulators. Techniques for analysing adaptive systems are discussed. This includes stability and convergence analysis. It is shown that adaptive control laws can also be obtained from stochastic control theory. Issues of importance for applications are covered. This includes parameterization, tuning, and tracking, as well as different ways of using adaptive control. An overview of applications is given. This includes feasibility studies as well as products based on adaptive techniques.