SAGA - Scientific Computing with Algebraic and Generative Abstractions
The SAGA project is an activity at Bergen Language Design Laboratory (BLDL).
This project demonstrates the benefits of using
algebraic software methodologies
as a breakthrough technology in the area of computational modelling.
Available positions related to this project are announced on the BLDL web pages.
Contents
- This WWW page
- Sub-WWW-pages
Computational modelling on high performance computers (HPC) is becoming a
valuable aid for industry. For the
potential benefit consider such areas as oil exploration where the cost of
drilling a well may be 25 million ECU. Here seismic modelling
provides background evidence needed to decide where to drill. More
modest examples, but still important to European industry, are the
processes of injection moulding, e.g. of plastics or foods, and coating,
e.g.,
of wires and surfaces. The former problems are characterised by the need for expensive
and time consuming testing where many injection schemes must be tried
before an effective one may be chosen. The latter problems are
characterised by the need for fine tuning of the production process
itself. In both these cases computational
modelling can be used, either to find the optimal mould design before they
are built, or to find the optimal setting of the production parameters for
coating, thereby reducing waste and improving product quality.
At the heart of computational modelling lies the development of
mathematical equations, typically partial differential equations (PDEs)
for the actual models that describe the problem and
its solution. These must be turned into efficient computer programs
that will solve the specific problem at hand. Many of these equations,
such as the Navier-Stokes equation defining the flow of fluids
for Computational Fluid Dynamics (CFD) problems, are so complex and general
that they must be simplified and adapted to the specific problem
to be solved. The development of a computational model in the form of
a program typically proceeds through the following stages:
- mathematical modelling: an iterative process that
requires the development of prototype implementations of the model
to test the assumptions made,
- programming of the final model as an efficient HPC
program,
- mesh generation: an iterative process that, via a
sequence of trial executions, finds an optimal representation of the
data for the computation, and
- execution of program on data sets to solve the actual industrial
problem.
Going from a mathematical model to an algorithm is an open-ended process
with many options and possibilities. Currently only a few of these options
are investigated, and even then only with great effort, requiring time and
highly skilled researchers.
Working
with such code adds to the development time and cost, especially in the
prototype development phase and when rewriting the prototype program for
an HPC environment. It is virtually impossible to test an algorithm on one
computer architecture and then easily move to an HPC platform where
actual production runs are to be performed. Worse yet, as new
architectures emerge, higher execution speeds can be achieved at a
fraction of the previous computer costs, but moving from one HPC
architecture to another is very costly. The effect is that
computational modelling currently is worthwhile in high profile
cases, but not for run of the mill problems. This also precludes
small and medium sized enterprises (SMEs) from benefitting from computer modelling
using HPC.
What is needed are breakthrough technologies that shorten the
mathematical modelling cycle times, and dramatically reduce the
cost of porting the prototype implementation onto the appropriate HPC
architectures.
The aim of the SAGA project is to demonstrate and quantify the benefits of using
algebraic programming techniques as a breakthrough technology in the area
of computational modelling.
Algebraic Software Methodologies for PDEs
Algebraic software methodologies are a result of the last 20-30 years
investigation into abstract data types and algebraic development
techniques. They include concepts like algebra, many-sorted universal
algebra and category theory - concepts which originally were developed from the
abstract characterisation of rings, fields and free vector spaces, the
fundamental concepts in the theory of PDEs.
The algebraic concepts also abstract modern program structuring
mechanisms like classes and generic (or template) modules of object-oriented
programming languages such as C++, Generic Java and Fortran-2000.
Using the abstract theory of PDEs to structure PDE solving software
seems a natural way of utilising this correspondence (see Hans
Munthe-Kaas and Magne Haveraaen: "Closing the gap between pure and
applied mathematics?", ZAMM vol. 76, supplement 1, 1996, pp.
487-488). Experience from the SAGA-oriented projects indicate that
- using algebraic techniques for software structuring purposes gives
more mature software structures which are less prone to redesigns
than conventionally developed systems,
providing a general framework for solvers
of most kinds of PDEs, with
- a high degree of reuse even within the library itself, so that
advanced concepts are defined by combinations of basic modules,
which provides the ability that
- a numerical solution strategy may be replaced with another just by
substituting a few modules and without changing the system structure,
- prototype code development times are reduced since central
numerical modules are reused rather than readapted, and
- only a few minor modules need to be replaced when porting to and
between HPC architectures.
This shows that the effort needed to move from mathematical models to
prototype software, and from prototype software to efficient HPC code can
be significantly reduced. These are critical parts of the development
cycles, and parts where conventional techniques have obvious shortfalls.
Industrial Case Studies
Two industrial areas have been chosen for the practical tests of the
SAGA methodologies: seismic modelling and computational fluid dynamics.
These represent a varied challenge for numerical software.
Seismic exploration is based on recording and analysing seismic waves
that have passed through a geological medium, e.g., a hydrocarbon
reservoir.
Seismic modelling is the simulation of such waves.
The scales of such models range from several kilometer long profiles to a few decimeters
around a borehole.
The governing equation for this is the elastic wave equation,
which is relevant for most major problems related to seismics.
This is a hyperbolic PDE, normally solved using a finite
difference scheme. The seismic case study has been developed into a full
industrial product, SeisMod.
Computational fluid dynamics (CFD) is the study of fluid flow using
computers and computational models. This encompasses both high-speed flows
of gases (Reynolds numbers larger than 100), such as those around
aeroplanes, and slow flows of highly viscous liquids (Reynolds numbers less
than 1), such as that of syrup and glass. CFD problems occur in everything
from the mixing of dough for breads and biscuits (where the quality of the
mixing of the initial ingredients can have a significant effect on the
quality of the final product), to co-injection of multiple components of
foods or polymers and coating of wires and optical fibres. CFD problems
are governed by the Navier-Stokes PDE, which has both elliptic and
hyperbolic properties. Typically they may be solved using finite element methods.
As a case study the coating of wires with polymers was chosen. This is an
example of viscous incompressible non-isothermal and non-Newtonian flows of
specific relevance to a wide range of the processing industry. A parallel
version of a reference code developed using traditional means was adapted,
and the detailed design of a code using the SAGA methodologies was
developed.
This allowed a direct comparison of the different approaches to computational
modelling, see Experience using SAGA
methodologies.
SAGA Technologies
The study of algebraic software methodologies for PDEs is a vast area.
Through the SAGA initiative we have so far developed prototypes
of a selected set of tools.
- Sapphire: For the quick prototyping of
mathematical models
we have developed an algebraic programming language and a compiler
that translates recursive functions into non-recursive, imperative code.
This allows us to code the recursive equations of the mathematical
formulation of a solver directly as recursive functions and compile this
for both sequential and parallel HPC computers. The compiled code has the
same execution time complexity as conventional imperative code:
- a recursively written solver for the heat equation using
finite difference has linear complexity in the number of grid nodes and
the number of time steps,
- a recursively written fast Fourier transform (FFT) has
n logn complexity for input data size
n, and
- a recursive formulation of a dynamic programming problem, such as
the stagecoach problem, has linear complexity in the number of
connecting arcs of the corresponding graph.
This is achieved by letting the data dependencies of the problem be an
explicit structure in the code, thus giving the programmer full control
over how recursive calls are reused within the computation.
- Sophus: This is a software library written in C++ and
carefully designed to mimic the abstract structure of the PDE
mathematics. By requiring strict adherence to specified interfaces, we
have been able to achieve that different implementations of the same mathematical
concepts are basically interchangeable. Sophus library components can be
presented as different layers of abstractions.
- Application layer: solvers for PDEs such as the seismic simulator
and the coating problem.
- Tensor layer: handles coordinate systems, matrices and vectors and
general differentiation operators.
- Scalar field layer: numerical discretisations such as finite
differences and finite elements with partial derivatives.
- Mesh layer: implements grids for sequential and parallel HPC
machines.
The interchangeability of modules within a layer allows software
developers to experiment with different solution strategies and HPC
architectures without the need for extensive reprogramming. For
example, the change from a sequential to a parallel version of a seismic
simulator does not involve any reprogramming of the rest of the solver
application.
- CodeBoost: This is a software transformation system being
developed to address the gap between well formed code (from a software
engineering point of view) and efficient code (from a run-time point of view).
For example, code written using expressions and functions seems to be easier to
understand and maintain than code written as long sequence of statements. However, the
latter often seems to generate better code with current compilers. CodeBoost provides a
transformation, mutification, that transforms code from the expression
form to sequence form. Thus it becomes possible to write well formed code
without sacrificing efficiency.
A first version of CodeBoost was written in ASF+SDF at CWI. This version only
supported simple transformations like mutification, but showed the viability
of the concept. The current version of CodeBoost is developed in Stratego at the
University of Bergen. Stratego is a strategic rewrite language being
developed at Utrecht University. The second version of CodeBoost is more and
more becoming a generative programming support tool, sponsoring things such as
user-defined rules. User-defined rules allows a programmer to embed domain-specific
transformation rules in the program code they apply to.
More information on CodeBoost, and a full distribution of the system, is
available at http://www.codeboost.org/.
Current project: SAGA-GEO
The current activity is focused on solving geophysical problems
and comparing the SAGA solvers with traditional software for the same problems.
This means we need to
- reformulate the chosen problems into coordinate-free form,
including newer methods for handling difficult boundary conditions,
- adapt and build solvers for these problems in the Sophus library,
- provide means for checking that the traditional and the SAGA solvers
deliver similar answers, and
- improve the efficincy of the SAGA solvers to meet those of the traditional solvers,
a software transformation task utilising domain specific optimisation possibilities
and parallelisation.
The software will be developed in cooperation with geophysical experts.
- Vytautas Čyras and Magne Haveraaen:
Modular programming of recurrencies: a Comparison of
Two Approaches.
Informatica, 6(4)397-444, 1995.
An
earlier version
appeared on pages 112-126 in
Uffe H. Engberg and Kim G. Larsen and Peter D. Mosses (editors):
Proceedings
of the 6th Nordic Workshop on Programming Theory - NWPT6,
BRICS notes series, BRICS-NS-94-6, v+483pp, 1994.
- Magne Haveraaen and Steinar Søreide:
Solving recursive
problems in linear time using Constructive Recursion.
Proceedings of Norsk Informatikk
Konferanse NIK'98, Tapir, Norway, 1998, pp. 310-321.
- Magne Haveraaen and Helmer André Friis and Tor Arne Johansen:
Formal Software Engineering for Computational Modeling.
Nordic Journal of Computing, 1999, 3(6):241-270.
An earlier version is available as
University of Bergen, Reports
in Informatics no. 173, June 1999, pp. 27.
- Magne Haveraaen:
Efficient
Parallelisation of Recursive Problems Using Constructive
Recursion. In Arndt Bode and Thomas Ludwig and Roland
Wismüller (editors): Euro-Par 2000, Lecture Notes in
Computer Science, volume 1900, pp. 758--761, Springer Verlag,
2000.
- Special issue of Scientific
Programming,
vol. 8 no. 4,
pp. 209-273, 2000, on coordinate-free numerics.
- Petter Bjørstad: Coordinate Free Numerics.
Scientific Programming, vol. 8 no. 4 2000, pp. 209.
- Phil Grant, Magne Haveraaen and Mike Webster:
Coordinate Free Programming of
Computational Fluid Dynamics Problems.
Scientific Programming, vol. 8 no. 4, 2000, pp. 211-230.
- Magne Haveraaen:
Machine and Collection Abstractions
for User-Implemented Data-Parallel Programming.
Scientific Programming, vol. 8 no. 4, 2000, pp. 231-246.
- T.B. Dinesh and Magne Haveraaen and Jan Heering:
An Algebraic Programming Style
for Numerical Software and its Optimization.
Scientific Programming, vol. 8 no. 4, 2000, pp. 247-259.
- Magne Haveraaen:
Case Study on Algebraic Software
Methodologies for Scientific Computing.
Scientific Programming, vol. 8 no. 4, 2000, pp. 261-273.
- Krister Åhlander and Magne Haveraaen and Hans Munthe-Kaas:
On the Role of Mathematical Abstractions for Scientific Computing.
In Ronald F. Boisvert and Ping Tak Peter Tang (editors):
The Architecture of Scientific Software,
pp. 145-158, Kluwer Academic Publishers, 2001.
- Magne Haveraaen and Hogne Hundvebakke:
Some Statistical Performance
Estimation Techniques for Dynamic Machines.
In Weihai Yu (editor): Norsk informatikkonferanse NIK'2001,
Tapir, Trondheim, 2001, pp. 176-185.
- Helmer André Friis and Tor Arne Johansen and Magne Haveraaen and
Hans Munthe-Kaas and Åsmund Drottning:
Use of coordinate free numerics in elastic wave simulation.
Applied Numerical Mathematics, vol. 39 no. 2, 2001, pp.
151-171.
- Krister Åhlander and Magne Haveraaen and Hans Munthe-Kaas:
On Object-Oriented Frameworks and
Coordinate Free Formulations of PDEs.
Engineering with Computers, vol. 18, 2002, pp. 286-294.
- Otto Skrove Bagge and Magne Haveraaen:
Domain-Specific
Optimisation with User-Defined Rules in CodeBoost.
Electronic Notes in Theoretical Computer Science, vol. 86 no.
2, 2003, pp. 15.
- Otto Skrove Bagge and Karl Trygve Kalleberg and Magne Haveraaen and Eelco Visser:
Design of the CodeBoost Transformation System for
Domain-Specific Optimisation of C++ Programs.
In Dave Binkley and Paolo Tonella (editors):
Third IEEE International Workshop on Source Code Analysis and
Manipulation, IEEE Computer Society, 2003, pp. 65-74.
- Alexa Anderlik and Magne Haveraaen:
On the category of data dependency algebras and embeddings.
Proceedings of the Estonian Academy of Sciences, Physics,
Mathematics, vol. 52 no. 4, 2003, pp. 337-355.
- Magne Haveraaen and Jim Cordy and Jan Heering and Ganesh Sittampalam (editors):
Position papers from Software Transformation Systems Workshop 2004.
October, 2004,
http://www.program-transformation.org/Sts/STS04.
This contains
- Magne Haveraaen:
Software transformations supporting software engineering,
(position paper), pages 17-18.
- Magne Haveraaen and Helmer André Friis and Hans Munthe-Kaas:
Computable
Scalar Fields: a basis for PDE software.
Journal of logic and algebraic programming,
2005.
- Magne Haveraaen and Enida Brkic:
Structured testing in Sophus.
In Eivind Coward (ed.): Norsk Informatikkonferanse NIK 2005, Tapir, Trondheim, 2005, pp. 43-54.
- Anya Helene Bagge, Valentin David, Magne Haveraaen, and Karl Trygve Kalleberg.
Stayin’ alert: moulding failure and exceptions to your needs. In Stan Jarzabek, Douglas C. Schmidt, and Todd L. Veldhuizen (editors), GPCE '06: Proceedings of the fifth international conference on Generative programming and component engineering, pages 265–274, 2006.
- Magne Haveraaen:
Institutions, Property-Aware Programming and Testing.
In Jeremy Siek and Frank Tip (editors), LCSD '07: Proceedings of the 2007 Symposium on Library-Centric Software Design, pages 21-30, 2007.
- Anya Helene Bagge and Valentin David and Magne Haveraaen:
Axiom-based testing for C++ (Demonstration).
In OOPSLA Companion '08: Companion to the 23rd ACM SIGPLAN conference on Object oriented programming systems languages and applications, 721-722, 2008.
- Anya Helene Bagge and Valentin David and Magne Haveraaen:
Testing with concepts and axioms in C++ (Poster).
In OOPSLA Companion '08: Companion to the 23rd ACM SIGPLAN conference on Object oriented programming systems languages and applications, 773-774, 2008.
- Magne Haveraaen and Helmer André Friis:
Coordinate-free numerics: all your variation points for free?.
International Journal of Computational Science and Engineering, 4(4):223–230, 2009.
- Anya Helene Bagge and Valentin David and Magne Haveraaen:
The axioms strike back: testing with concepts and axioms in C++.
GPCE '09: Proceedings of the eighth international conference on Generative programming and component engineering, pages 15-24, 2009.
- Anya Helene Bagge and Magne Haveraaen:
Axiom-Based Transformations: Optimisation and Testing.
Electronic Notes in Theoretical Computer Science, 238:17–33, 2009.
- Valentin David and Magne Haveraaen:
Concepts as Syntactic Sugar.
In SCAM '09: Proceedings of the 2009 Ninth IEEE International Working Conference on Source Code Analysis and Manipulation, pages 147-156, 2009.
- Eva Burrows and Magne Haveraaen:
A Hardware Independent Parallel Programming Model.
Journal of Logic and Algebraic Programming, 78:519–538, 2009.
- Eva Burrows and Magne Haveraaen:
Dependency-driven Parallel Programming.
In Proceedings of Norsk Informatikk Konferanse NIK'09, Tapir, Norway, 2009.
- Adis Hodzic and Magne Haveraaen:
Software Institutions.
In Magne Haveraaen and Marina Lenisa and John Power and Monika Seisenberger (editors),
CALCO Young Researchers Workshop 2009 - CALCO-jnr, pages 47-62, 2010.
- Joseph Young:
The Automatic Construction and Solution of a Partial Differential Equation from the Strong Form.
In Ivan Lirkov and
Svetozar Margenov and
Jerzy Wasniewski (eds):
Large-Scale Scientific Computing, 7th International Conference,
LSSC 2009, Sozopol, Bulgaria, June 4-8, 2009. Revised Papers.
Lecture Notes in Computer Science, 5910, pages 679-686, 2010.
Contact address
The SAGA project
Magne Haveraaen
Department of Informatics
University of Bergen
Høyteknologisenteret
N-5020 BERGEN
Norway
E-mail saga-inquire@ii.uib.no.
Contact person: Magne Haveraaen, phone +47 55 58 41 54
Phone front office: +47 55 58 42 00
Fax: +47 55 58 41 99
There is also a SAGA interest group e-mail distribution list.
Partners on the SAGA project
- University of Bergen, Norway;
Coordinator: Magne Haveraaen
Hans Munthe-Kaas,
Steinar Søreide, Anya Helene Bagge, Otto Skrove Bagge,
Karl Trygve Kalleberg.
- CWI, Amsterdam, Netherlands;
Contact person: Jan Heering
- International Research Institute of Stavanger (IRIS),
Norway; Contact person: Helmer André Friis
- University of Swansea, Wales, UK;
Contact person: P.W. Grant
J.V. Tucker,
M.F. Webster.
- Delft University of Technology,
Netherlands;
Contact person: Eelco Visser
- Uppsala University,
Sweden;
Contact person: Krister Åhlander
The SAGA project and related subprojects have received support from
These pages last updated 2011-02-20
© 1999-2010 Magne Haveraaen, University of Bergen, Norway.
SAGA contact address.
Up to top of main SAGA WWW page.