|
At the origin of this thesis stood the own painful experience with the difficulties of developing and reusing scientific software, even if the underlying mathematical problems solved by the individual software in our working group were closely related.
Indeed, software development is a serious problem in almost all computational fields, and it is certainly not easier in the branch of scientific computing dealing with the numerical solution of partial differential equations. This is the context this thesis grew out of, and it runs through the whole work as a leitmotiv. Yet, both the methods applied as well as the results obtained reach beyond it.
The increasing number of publications and conferences
devoted to scientific computing software is a clear indication
of the problem's significance.
Where do these difficulties come from,
and is there anything special about scientific computing?
One leading goal of software development
in scientific computing is efficiency:
The problems solved are large,
often as large as current technology allows.
This pressure for efficiency has had a deep impact on the methods of software development. Typically, many decisions are `hard-wired' into the code and thus not localized any more. Data structures and algorithms are closely interlocked. If aspects of a working software, grown over some period of time, are to be adapted to new requirements, major difficulties arise.
Obviously, starting from scratch is not an option, due to the size of complete applications -- systematic software reuse is on the agenda of computer science at least since MCILROYS vision [2], but traceable to the earliest day of computing [1]. Yet, success is mixed at best in general, and scientific computing makes no exception. What makes reuse so hard?
Scientific computing is an algorithm-dominated field, as are Computational Geometry, Computational Graph Theory, or what is more generally grouped under the term `Computational Science and Engineering' (CSE). The natural unit of reuse in these fields often is an algorithm, or small sets of algorithms, in combination with associated data structures. Different applications combine different selections of algorithms in a unique way to achieve their specific aims. Yet, it is very common that a given algorithm is used by a whole class of applications.
But reuse of single algorithms is admittedly hard. It is true, there are a number of successful software packages, specifically for the different types of PDE solution. Yet, conventional packages are not organized in a way that would allow single-algorithm reuse out-of-context: Implementations of algorithms must make certain assumptions on the way the data they `live on' are represented. The more complex the data structures are, the less stable are these assumptions, and the lower the probability that they hold across the boundaries of the current context.
Thus, problems occur whenever algorithms are to be reused outside the narrow context they were developed for, or if this context changes: So substituting new, better data structures may be impossible; in the limit, evolution of the application may face unsurmountable difficulties and come to an end.
The first major contribution of this thesis is
an in-depth analysis of the problem,
and the development of a solution strategy.
This solution is worked out in detail for the case
of algorithms operating on computational grids.
Such grids are central to numerical PDE solution,
and are important in other fields,
like Computer Graphics or Computational Geometry.
Furthermore, the corresponding data structures
are sufficiently complex and variable
to virtually exclude out-of-context reuse of algorithm,
unless special measures are taken.
The solution we present attacks the central problem, namely the commitment to specific data representations.
The main task here lies in identifying and describing the relationship between data and algorithms. Towards this aim, we move a step back from the specifics of concrete data structures and algorithms, to gain a broader perspective. The mathematical branches of topology and combinatorics are chosen to provide the conceptual framework. Their precise language allows to express the essential mathematical structures of the problem domain in a general, abstract way, independent of any representational issues.
Guided by a review of representative grid algorithms, we then arrive at an abstract description of the capabilities of data structures: A small set of kernel concepts, on which a large portion of relevant algorithms can be based.
In order to transfer the abstract notions found into working software, the paradigm of generic programming is employed. It has already proven its usefulness and power for data structures representing a comparatively simple mathematical structure, such as linear sequences and matrices. The kernel concepts give rise to a small brokerage layer separating data from algorithms. We show that the approach leads to efficient implementations, with performance coming near to that of direct, low-level implementation.
Thus, a effective decoupling of grid algorithms from data structures is achieved. This decoupling raises the reusability of these algorithms to a new level.
The second major contribution of this thesis tackles the
problem of parallel grid computations.
A key problem in high performance scientific computing
is the parallelization of applications.
The driving force here is the need to calculate ever larger problems,
or, to minor extent, the same problems in less time.
Many computational tasks are beyond reach without the use of parallel computers.
Efficient parallelization of algorithmic code is a non-trivial task. It cross-cuts both data structures and algorithms. Automatic methods are of restricted use in this area, because a satisfying efficiency is generally not obtained this way.
A promising alternative are domain-specific approaches, which have been the topic of many research efforts in recent years. We derive a new, general concept, founded on an abstraction for distributed overlapping grids, for parallelizing algorithms working on arbitrary grid types. In particular, a novel characterization of the data dependencies for algorithms on unstructured grids is developed. Based on this characterization, we present a new algorithm for automatic generation of grid overlaps. This method is of optimal complexity, namely linear in the size of the overlap, and constitutes a progress of significant practical value.
Using the generic approach, the algorithms and data structures are implemented in a way that is independent of both dimension and the underlying sequential grid representation. These components add very low overhead in terms of memory consumption and runtime (linear in the size of overlap). They drastically reduce the effort for developing new parallel applications, or parallelizing existing ones.
A vast set of components
-- among them those described in this thesis --
have been implemented using the C++ language.
The code can be obtained on request from the author.
The body of this work is organized as follows.
In chapter ![[*]](http://www.math.tu-cottbus.de/icons/LatexHtml//crossref.gif){kind=icon}
,
we investigate in detail the problems and conditions of
software development and reuse in scientific computing,
and point out the fundamental role of grid data structures
for numerical PDE solution.
Subsequently, the generic programming approach
is introduced
as a possible solution
to the problems identified.
Chapter is devoted to a domain analysis
for grids and grid algorithms.
First, a detailed analysis of topological and combinatorial properties of
grids is undertaken,
followed by a study of several representative algorithms.
The resulting list of algorithm requirements is used as guiding principle
for an investigation of grid data structure
variabilities and commonalities.
The next chapter contains a development of the abstract layer mentioned above, leading to a micro-kernel capturing the essential properties. We then show how a number of grid components can be implemented on top of this kernel, leading to a repository of generic, highly reusable components.
Chapter tackles the parallelization problem.
First, a set of abstract concepts for data-parallel grid computations is
introduced, including a formalization of the notion of a stencil
for algorithms on unstructured grids.
This notion encapsulates essential aspects of algorithms,
and allows to formulate distribution methods independently of concrete algorithms.
Then, the generic approach is used to implement a family of
algorithmic and data-oriented components,
representing the abstract concepts in a faithful way, that is,
without sacrificing generality.
These components more or less completely
encapsulate any technical detail related to data distribution,
and are a convincing example for the power of the generic approach.
An investigation of the practical usability of the approach is
done in chapter .
We show how the generic paradigm
can be used to construct complex applications
(in this case a finite volume solver for hyperbolic equations of gas dynamics),
leading to a sort of program families,
and general implementations of finite-element and multigrid algorithms.
By discussing the parallelization of an existing application
for solving the incompressible Navier-Stokes equations,
we demonstrate the seamless integration
of the generic approach
with more traditional ways of software design.
Furthermore, by assessing the performance of generic programs with a set of small kernels, we show that our methods lead to efficient code that can compete with low-level implementations in C or FORTRAN.
Finally, the results obtained are discussed, and promising further research directions are indicated. There is reason to expect that along the lines of the concepts developed in this thesis, substantial progress can be made in algorithm reuse, and therefore in scientific computing software development in general.
Additional material, such as source code for the components,
is available online at
http://www.math.tu-cottbus.de/~berti/gral.
This document was generated using the LaTeX2HTML translator Version 99.2beta6 (1.42)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 wrap-intro.tex
The translation was initiated by Guntram Berti on 2000-09-21