Publications
129 results found
Louboutin M, Witte P, Lange M, et al., 2017, Full-waveform inversion, Part 1: Forward modeling, Leading Edge, Vol: 36, Pages: 1033-1036, ISSN: 1070-485X
Since its reintroduction by Pratt (1999), full-waveform inversion (FWI) has gained a lot of attention in geophysical exploration because of its ability to build high-resolution velocity models more or less automatically in areas of complex geology. While there is an extensive and growing literature on the topic, publications focus mostly on technical aspects, making this topic inaccessible for a broader audience due to the lack of simple introductory resources for newcomers to computational geophysics. We will accomplish this by providing a hands-on walkthrough of FWI using Devito (Lange et al., 2016), a system based on domain-specific languages that automatically generates code for time-domain finite differences.
Hückelheim JC, Luo Z, Luporini F, et al., 2017, Towards self-verification in finite difference code generation, SC17, Publisher: ACM
Code generation from domain-specific languages is becoming increasingly popular as a method to obtain optimised low-level code that performs well on a given platform and for a given problem instance. Ensuring the correctness of generated codes is crucial. At the same time, testing or manual inspection of the code is problematic, as the generated code can be complex and hard to read. Moreover, the generated code may change depending on the problem type, domain size, or target platform, making conventional code review or testing methods impractical. As a solution, we propose the integration of formal verification tools into the code generation process. We present a case study in which the CIVL verification tool is combined with the Devito finite difference framework that generates optimised stencil code for PDE solvers from symbolic equations. We show a selection of properties of the generated code that can be automatically specified and verified during the code generation process. Our approach allowed us to detect a previously unknown bug in the Devito code generation tool.
Lange M, Kukreja N, Luporini F, et al., 2017, Optimised finite difference computation from symbolic equations, 15th Python in Science Conference (SciPy 2017), Pages: 89-96
Domain-specific high-productivity environments are playing an increasinglyimportant role in scientific computing due to the levels of abstraction andautomation they provide. In this paper we introduce Devito, an open-sourcedomain-specific framework for solving partial differential equations fromsymbolic problem definitions by the finite difference method. We highlight thegeneration and automated execution of highly optimized stencil code from only afew lines of high-level symbolic Python for a set of scientific equations,before exploring the use of Devito operators in seismic inversion problems.
Louboutin M, Lange M, Hermann FJ, et al., 2017, Performance prediction of finite-difference solvers for different computer architectures, Computers & Geosciences, Vol: 105, Pages: 148-157, ISSN: 0098-3004
The life-cycle of a partial differential equation (PDE) solver is often characterized by three development phases: the development of a stable numerical discretization; development of a correct (verified) implementation; and the optimization of the implementation for different computer architectures. Often it is only after significant time and effort has been invested that the performance bottlenecks of a PDE solver are fully understood, and the precise details varies between different computer architectures. One way to mitigate this issue is to establish a reliable performance model that allows a numerical analyst to make reliable predictions of how well a numerical method would perform on a given computer architecture, before embarking upon potentially long and expensive implementation and optimization phases. The availability of a reliable performance model also saves developer effort as it both informs the developer on what kind of optimisations are beneficial, and when the maximum expected performance has been reached and optimisation work should stop. We show how discretization of a wave-equation can be theoretically studied to understand the performance limitations of the method on modern computer architectures. We focus on the roofline model, now broadly used in the high-performance computing community, which considers the achievable performance in terms of the peak memory bandwidth and peak floating point performance of a computer with respect to algorithmic choices. A first principles analysis of operational intensity for key time-stepping finite-difference algorithms is presented. With this information available at the time of algorithm design, the expected performance on target computer systems can be used as a driver for algorithm design.
McManus TM, Percival JR, Yeager BA, et al., 2017, Moving mesh methods in Fluidity and Firedrake, Archer report eCSE06-1
Kukreja N, Louboutin M, Vieira F, et al., 2017, Devito: Automated fast finite difference computation, Pages: 11-19
Domain specific languages have successfully been used in a variety of fields to cleanly express scientific problems as well as to simplify implementation and performance optimization on different computer architectures. Although a large number of stencil languages are available, finite difference domain specific languages have proved challenging to design because most practical use cases require additional features that fall outside the finite difference abstraction. Inspired by the complexity of real-world seismic imaging problems, we introduce Devito, a domain specific language in which high level equations are expressed using symbolic expressions from the SymPy package. Complex equations are automatically manipulated, optimized, and translated into highly optimized C code that aims to perform comparably or better than hand-tuned code. All this is transparent to users, who only see concise symbolic mathematical expressions.
- Abstract
- Open Access Link
- Cite
- Citations: 17
Kukreja N, Louboutin M, Lange M, et al., 2017, Rapid development of seismic imaging applications using symbolic math, Pages: 9-12
In this talk, I will discuss our approach to the formulation and the performance optimization of finite difference methods for PDEs arising in FWI. Our framework consists of a stack of domain specific languages and optimizing compilers. The mathematical specification of a finite difference method is translated by a compiler, Devito, into C code, applying a sophisticated sequence of transformations. These include standard loop transformations, such as blocking and vectorization, as well as symbolic manipulations to reduce the unusually high arithmetic intensity of the stencils arising in forward and adjoint operators. These include common subexpressions elimination, factorization, code motion and approximation of transient functions. I will show the impact of these transformations on standard Intel Xeon architectures as well as on Intel Knights Landing. Compelling evidence points in the direction that our stencil kernels are significantly bound by the L1 cache. I will conclude discussing future challenges and goals of our work.
Lange M, Mitchell L, Knepley M, et al., 2016, Efficient Mesh Management in Firedrake Using PETSc DMPlex, SIAM Journal on Scientific Computing, Vol: 38, Pages: S143-S155, ISSN: 1095-7197
The use of composable abstractions allows the application of new and established algorithms to a wide range of problems, while automatically inheriting the benefits of well-known performance optimizations. This work highlights the composition of the PETSc DMPlex domain topology abstraction with the Firedrake automated finite element system to create a PDE solving environment that combines expressiveness, flexibility, and high performance. We describe how Firedrake utilizes DMPlex to provide the indirection maps required for finite element assembly, while supporting various mesh input formats and runtime domain decomposition. In particular, we describe how DMPlex and its accompanying data structures allow the generic creation of user-defined discretizations, while utilizing data layout optimizations that improve cache coherency and ensure overlapped communication during assembly computation.
Jacobs CT, Gorman GJ, Rees HE, et al., 2016, Experiences with efficient methodologies for teaching computer programming to geoscientists, Journal of Geoscience Education, Vol: 64, Pages: 183-198, ISSN: 1089-9995
Computer programming was once thought of as a skill required only by professional software developers. But today, given the ubiquitous nature of computation and data science it is quickly becoming necessary for all scientists and engineers to have at least a basic knowledge of how to program. Teaching how to program, particularly to those students with little or no computing background, is well-known to be a difficult task. However, there is also a wealth of evidence-based teaching practices for teaching programming skills that can be applied to greatly improve learning outcomes and the student experience. Adopting these practices naturally gives rise to greater learning efficiency-this is critical if programming is to be integrated into an already busy geoscience curriculum. This article considers an undergraduate computer programming course, run during the last five years in the Department of Earth Science and Engineering at Imperial College London. The teaching methodologies that were used each year are discussed, along with the challenges that were encountered and how the methodologies affected student performance. Anonymized student marks and feedback are used to highlight the discussion, and also how the adjustments made to the course eventually resulted in a highly effective learning environment.
Ferrier RJ, Cai L, Lin Q, et al., 2016, Models for apparent reaction kinetics in heap leaching: A new semi-empirical approach and its comparison to shrinking core and other particle-scale models, Hydrometallurgy, Vol: 166, Pages: 22-33, ISSN: 0304-386X
Particle-scale effects are critically important to the performance of heap leaching operations. In a heap-scale simulation, the transport of fluid phases and reactive species external to the ore particles might be modelled with thousands of grid elements by the finite volume or finite element method. The inter- and intra-particle diffusions and reactions are usually parametrised by a deterministic model, such as the shrinking core model (SCM), that translates the external conditions into an effective product extraction rate. However, the rate equation takes the form of an implicit or partial differential equation for all but the simplest models and kinetic regimes, becoming expensive to solve on large grids. We instead propose an economical, easily calibrated semi-empirical approach in which the dependencies on external conditions and the current state of the ore are considered to be mathematically separable. We show that the standard SCM does not suffer greatly from this approximation even when there is a mixed control regime with nonlinear kinetics. The dependency on the state of the ore is derived empirically, inherently capturing heterogeneous features and cluster-scale effects. We demonstrate that this method scales correctly when fitted to data from physical column leaching experiments.
Gorman GJ, Luporini F, Kukreja N, 2016, Devito
Devito is a prototype Domain-specific Language (DSL) and code generation framework for the design of highly optimised finite difference kernels for use in inversion methods. Devito utilises SymPy to allow the definition of operators from high-level symbolic equations and generates optimised and automatically tuned code specific to a given target architecture.
Quattrocchi G, Gorman GJ, Piggott MD, et al., 2016, M2, overtides and compound tides generation in the Strait of Messina: the response of a non-hydrostatic, finite-element ocean model, JOURNAL OF COASTAL RESEARCH, Pages: 657-661, ISSN: 0749-0208
- Author Web Link
- Cite
- Citations: 1
Melnikova Y, Jacquemyn C, Osman H, et al., 2016, Reservoir modelling using parametric surfaces and dynamically adaptive fully unstructured grids
Geologic heterogeneities play a key role in reservoir performance. Surface based geologic modeling (SBGM) offers an alternative approach to conventional grid-based methods and allows multi-scale geologic features to be captured throughout the modeling process. In SBGM, all geologic features that impact the distribution of material properties, such as porosity and permeability, are modeled as a set of volumes bounded by surfaces. Within these volumes, the material properties are constant. The surfaces have parametric, grid-free representation, which, in principle, allows for unlimited complexity, since no resolution is implied at the stage of modeling and features of any scale can be included. Surface based models are discretized only when required for numerical analysis. We report here a new automated and integrated workflow for creating and meshing stochastic, surfacebased models. Surfaces are represented through non-uniform rational B-splines (NURBS). Multiple relations between surfaces are captured through geologic rules that are translated into Boolean operations (intersection, union, subtraction). Finally, models are discretized using fully unstructured tetrahedral meshes coupled with a geometry-Adaptive sizing function that efficiently approximate complex geometries. We demonstrate the new workflow via examples of multiple erosional channelized geobodies, fault models and a fracture network. We also show finite element flow simulations of the resulting geologic models, using the Imperial College Finite Element Reservoir Simulator (IC-FERST) that features dynamic adaptive mesh optimization. Mesh adaptivity allows us to focus computational effort on the areas of interest, such as the location of water saturation front. The new approach has broad application in modeling subsurface flow.
Melnikova Y, Jacquemyn C, Osman H, et al., 2016, Reservoir modelling using parametric surfaces and dynamically adaptive fully unstructured grids
Geologic heterogeneities play a key role in reservoir performance. Surface based geologic modeling (SBGM) offers an alternative approach to conventional grid-based methods and allows multi-scale geologic features to be captured throughout the modeling process. In SBGM, all geologic features that impact the distribution of material properties, such as porosity and permeability, are modeled as a set of volumes bounded by surfaces. Within these volumes, the material properties are constant. The surfaces have parametric, grid-free representation, which, in principle, allows for unlimited complexity, since no resolution is implied at the stage of modeling and features of any scale can be included. Surface based models are discretized only when required for numerical analysis. We report here a new automated and integrated workflow for creating and meshing stochastic, surfacebased models. Surfaces are represented through non-uniform rational B-splines (NURBS). Multiple relations between surfaces are captured through geologic rules that are translated into Boolean operations (intersection, union, subtraction). Finally, models are discretized using fully unstructured tetrahedral meshes coupled with a geometry-Adaptive sizing function that efficiently approximate complex geometries. We demonstrate the new workflow via examples of multiple erosional channelized geobodies, fault models and a fracture network. We also show finite element flow simulations of the resulting geologic models, using the Imperial College Finite Element Reservoir Simulator (IC-FERST) that features dynamic adaptive mesh optimization. Mesh adaptivity allows us to focus computational effort on the areas of interest, such as the location of water saturation front. The new approach has broad application in modeling subsurface flow.
Lange M, Kukreja N, Louboutin M, et al., 2016, Devito: Towards a generic Finite Difference DSL using Symbolic Python, 6th Workshop on Python for High-Performance and Scientific Computing (PyHPC), Publisher: IEEE, Pages: 67-75
- Author Web Link
- Open Access Link
- Cite
- Citations: 20
Robinson D, Wood M, Piggott M, et al., 2016, CFD modelling of marine discharge mixing and dispersion, JOURNAL OF APPLIED WATER ENGINEERING AND RESEARCH, Vol: 4, Pages: 152-162, ISSN: 2324-9676
- Author Web Link
- Cite
- Citations: 13
Jensen KE, Gorman G, 2015, Details of tetrahedral anisotropic mesh adaptation, Computer Physics Communications, Vol: 201, Pages: 135-143, ISSN: 1879-2944
Dargaville S, Goffin MA, Buchan AG, et al., 2015, Solving the Boltzmann transport equation with multigrid and adaptive space/angle discretisations, ANNALS OF NUCLEAR ENERGY, Vol: 86, Pages: 99-107, ISSN: 0306-4549
- Author Web Link
- Cite
- Citations: 9
Rokos G, Gorman G, Kelly PHJ, 2015, A fast and scalable graph coloring algorithm for multi-core and many-core architectures, 21st International Conference on Parallel and Distributed Computing, Publisher: Springer, Pages: 414-425, ISSN: 0302-9743
Irregular computations on unstructured data are an important class of problems for parallel programming. Graph coloring is often an important preprocessing step, e.g. as a way to perform dependency analysis for safe parallel execution. The total run time of a coloring algorithm adds to the overall parallel overhead of the application whereas the number of colors used determines the amount of exposed parallelism. A fast and scalable coloring algorithm using as few colors as possible is vital for the overall parallel performance and scalability of many irregular applications that depend upon runtime dependency analysis. Çatalyürek et al. have proposed a graph coloring algorithm which relies on speculative, local assignment of colors. In this paper we present an improved version which runs even more optimistically with less thread synchronization and reduced number of conflicts compared to Çatalyürek et al.’s algorithm.We show that the new technique scales better on multicore and many-core systems and performs up to 1.5x faster than its predecessor on graphs with high-degree vertices, while keeping the number of colors at the same near-optimal levels.
Avdis A, Jacobs CT, Hill J, et al., 2015, Shoreline and Bathymetry Approximation in Mesh Generation for Tidal Renewable Simulations, European Wave & Tidal Energy
Due to the fractal nature of the domain geometry in geophysical flowsimulations, a completely accurate description of the domain in terms of acomputational mesh is frequently deemed infeasible. Shoreline and bathymetrysimplification methods are used to remove small scale details in the geometry,particularly in areas away from the region of interest. To that end, a novelmethod for shoreline and bathymetry simplification is presented. Existingshoreline simplification methods typically remove points if the resultantgeometry satisfies particular geometric criteria. Bathymetry is usuallysimplified using traditional filtering techniques, that remove unwanted Fouriermodes. Principal Component Analysis (PCA) has been used in other fields toisolate small-scale structures from larger scale coherent features in a robustway, underpinned by a rigorous but simple mathematical framework. Here wepresent a method based on principal component analysis aimed towardssimplification of shorelines and bathymetry. We present the algorithm in detailand show simplified shorelines and bathymetry in the wider region around theNorth Sea. Finally, the methods are used in the context of unstructured meshgeneration aimed at tidal resource assessment simulations in the coastalregions around the UK.
Knepley MG, Lange M, Gorman GJ, 2015, Unstructured Overlapping Mesh Distribution in Parallel
We present a simple mathematical framework and API for parallel mesh and datadistribution, load balancing, and overlap generation. It relies on viewing themesh as a Hasse diagram, abstracting away information such as cell shape,dimension, and coordinates. The high level of abstraction makes our interfaceboth concise and powerful, as the same algorithm applies to any representablemesh, such as hybrid meshes, meshes embedded in higher dimension, andoverlapped meshes in parallel. We present evidence, both theoretical andexperimental, that the algorithms are scalable and efficient. A workingimplementation can be found in the latest release of the PETSc libraries.
Mostaghimi P, Percival JR, Pavlidis D, et al., 2015, Anisotropic Mesh Adaptivity and Control Volume Finite Element Methods for Numerical Simulation of Multiphase Flow in Porous Media, MATHEMATICAL GEOSCIENCES, Vol: 47, Pages: 417-440, ISSN: 1874-8961
- Author Web Link
- Cite
- Citations: 35
Lange M, Knepley MG, Gorman GJ, 2015, Flexible, Scalable Mesh and Data Management using PETSc DMPlex, 3rd International Conference on Exascale Applications and Software, Publisher: ACM, Pages: 71-76
Designing a scientific software stack to meet the needs of thenext-generation of mesh-based simulation demands, not only scalable andefficient mesh and data management on a wide range of platforms, but also anabstraction layer that makes it useful for a wide range of application codes.Common utility tasks, such as file I/O, mesh distribution, and workpartitioning, should be delegated to external libraries in order to promotecode re-use, extensibility and software interoperability. In this paper wedemonstrate the use of PETSc's DMPlex data management API to perform mesh inputand domain partitioning in Fluidity, a large scale CFD application. Wedemonstrate that raising the level of abstraction adds new functionality to theapplication code, such as support for additional mesh file formats and mesh re-ordering, while improving simulation startup cost through more efficient meshdistribution. Moreover, the separation of concerns accomplished through thisinterface shifts critical performance and interoperability issues, such asscalable I/O and file format support, to a widely used and supported opensource community library, improving the sustainability, performance, andfunctionality of Fluidity.
Guo X, Lange M, Gorman G, et al., 2015, Developing a scalable hybrid MPI/OpenMP unstructured finite element model, COMPUTERS & FLUIDS, Vol: 110, Pages: 227-234, ISSN: 0045-7930
- Author Web Link
- Cite
- Citations: 19
Gorman GJ, Rokos G, Southern J, et al., 2015, Thread-parallel anisotropic mesh adaptation, SEMA SIMAI Springer Series, Vol: 5, Pages: 113-137, ISSN: 2199-3041
Mesh adaptation is a powerful way to minimise the computational cost of mesh based computation. It is particularly successful for multi-scale problems where the required mesh resolution can vary by orders of magnitude across the domain. The end result is local control over solution accuracy and reduced time to solution. In the case of large scale simulations, where the time to solution is unacceptable or the memory requirements exceeds available RAM, mesh based computation is typically parallelised using domain decomposition methods using the Message Passing Interface (MPI). This allows a simulation to run in parallel on a distributed memory computer. While this has been a high successful strategy up until now, the drive towards low power multi- and many-core architectures means that an even higher degree of parallelism is required and the memory hierarchy exploited to maximise memory bandwidth. For this reason application codes are increasingly adopting a hybrid parallel approach whereby decomposition methods, implemented using the Message Passing Interface (MPI), are applied for inter-node parallelisation, while a threaded programming model is used for intra-node parallelisation. Mesh adaptivity has been successfully parallelised using MPI by a number of groups, and can be implemented efficiently with few modifications to the serial code. However, thread-level parallelism is significantly more challenging because each thread modifies the mesh data and therefore must be carefully marshalled to avoid data races while still ensuring enough parallelism is exposed to achieve good parallel efficiency. Here we describe a new thread-parallel algorithm for anisotropic mesh adaptation algorithms. For each mesh optimisation phase (refinement, coarsening, swapping and smoothing) we describe how independent sets of tasks are defined. We show how a deferred updates strategy can be used to update the mesh data structures in parallel and without data contention. We show that desp
- Abstract
- Open Access Link
- Cite
- Citations: 8
Jacobs CT, Avdis A, Gorman GJ, et al., 2014, PyRDM: A Python-based Library for Automating the Management and Online Publication of Scientific Software and Data, Journal of Open Research Software, Vol: 2, ISSN: 2049-9647
Candy AS, Avdis A, Hill J, et al., 2014, Integration of Geographic Information System frameworks into domain discretisation and meshing processes for geophysical models
<jats:p>Abstract. Computational simulations of physical phenomena rely on an accurate discretisation of the model domain. Numerical models have increased in sophistication to a level where it is possible to support terrain-following boundaries that conform accurately to real physical interfaces, and resolve a multiscale of spatial resolutions. Whilst simulation codes are maturing in this area, pre-processing tools have not developed significantly enough to competently initialise these problems in a rigorous, efficient and recomputable manner. In the relatively disjoint field of Geographic Information Systems (GIS) however, techniques and tools for mapping and analysis of geographical data have matured significantly. If data provenance and recomputability are to be achieved, the manipulation and agglomeration of data in the pre-processing of numerical simulation initialisation data for geophysical models should be integrated into GIS. A new approach to the discretisation of geophysical domains is presented, and introduced with a verified implementation. This brings together the technologies of geospatial analysis, meshing and numerical simulation models. This platform enables us to combine and build up features, quickly drafting and updating mesh descriptions with the rigour that established GIS tools provide. This, combined with the systematic workflow, supports a strong provenance for model initialisation and encourages the convergence of standards. </jats:p>
Mostaghimi P, Tollit BS, Neethling SJ, et al., 2014, A control volume finite element method for adaptive mesh simulation of flow in heap leaching, JOURNAL OF ENGINEERING MATHEMATICS, Vol: 87, Pages: 111-121, ISSN: 0022-0833
- Author Web Link
- Cite
- Citations: 25
Jacobs CT, Avdis A, Gorman GJ, et al., 2014, PyRDM
PyRDM is a Python-based library for research data management (RDM). It facilitates the automated publication of scientific software and associated input and output data.
Buchan AG, Farrell PE, Gorman GJ, et al., 2014, The immersed body supermeshing method for modelling reactor physics problems with complex internal structures, ANNALS OF NUCLEAR ENERGY, Vol: 63, Pages: 399-408, ISSN: 0306-4549
- Author Web Link
- Cite
- Citations: 5
This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.