CTADEL:
A Computer Algebra System
for the Generation
of Efficient Numerical Codes for PDEs
Robert A. van Engelen
Florida State University
engelen@cs.fsu.edu
In collaboration with
Lex Wolters
Leiden University
and
Gerard Cats
Royal Netherlands Meteorological Institute
More information:
http://www.wi.leidenuniv.nl/CS/HPC/ctadel.html
Transparencies available from:
http://www.cs.fsu.edu/ engelen/imacs99aca.html
June 18, 1999
Overview
- Introduction
- Large-Scale Scientific Application Development
- Problem-Solving Environments
and Computer Algebra Systems
- Ctadel
- Conclusions
Quote
Science Feb. 5, '99, 283 5403, pp. 766:
``Research Council Says US Climate Models Can't Keep Up''
- Lack of coordinated strategy for building models:
``Delay of integration of model components such as atmosphere, oceans, and chemistry because of the
absence of uniform model development'';
``No mechanism for integrating research results''
- Lack of supercomputer power:
``Fastest machine used in US climate modeling ranks 102 world-wide''
Large-Scale Scientific Applications
Absence of uniform model development paradigm results in extensive development
and maintenance efforts on (large-scale) scientific applications.
As more types of (super)computer systems emerge, problems become more apparent:
- Mismatches between data structures and I/O data formats of applications
- Difficulties of code adaptation to support parallelism:
- Parallelization of numerical algorithms
- Data structure changes for domain decomposition
Scientific Application Development Tools
While I/O problems may be difficult to solve,
the adaptation of algorithms and data structures of codes
to meet requirements of new hardware is possible through:
- Restructuring and parallelizing compilers
- Portable programming languages
eg. HPF or Fortran + OpenMP
- Portable numerical libraries
eg. LAPACK
- Communication libraries for distributed computing
eg. MPI or PVM
- Problem-solving environments
Problem Solving Environments
Definition [Houstis]
``A Problem-Solving Environment (PSE) is a computer system that provides all the computational facilities
necessary to solve a target class
of problems. These features include advanced solution methods, automatic and semi-automatic selection of
solution methods, and ways to easily incorporate novel solution methods.''
> Application area (scope) ?
> Design and implementation (power) ?
> Correctness (reliability) ?
> User extensibility (adjustability) ?
PSE Application Area
For effective use in large-scale scientific applications, a PSE should
generate codes that match the requirements of the application.
PSE plug-in paradigm:
Numerical or visualization routines generated by a PSE are incorporated
in the application.
PSE Design
Two approaches for designing PSEs for scientific problems:
- Simulation environment for computation and visualization:
A collection of connected software tools and libraries;
OR: A framework for connecting tools and libraries
- Code generation software:
Integrated computer algebra/compilation environment for numerical code development;
Uniform model development is possible through controlling data structures and algorithms
PSEs and Computer Algebra Systems
Advantages using computer algebra systems (CAS) for an integrated PSE implementation:
- Fast symbolic computation
- Scripting-like procedural programming language
- Posibilities for symbolic-numeric computation
- Graphical user interface and visualization tools
- User-defined transformations with powerful pattern matching (when supported by CAS)
PSEs and Computer Algebra Systems
Implementation problems:
- Normal forms that interfere with user-defined transformations
- Translation into normal forms may affect numerical properties
- CAS constructs with fixed semantics (fixed evaluation)
- No compiler-like techniques for program transformation and optimization
- No compiler-like type checking such as for polymorphic languages
- No ready-to-use database for storage of knowledge
- Much of analytical functionality of a CAS is will not be used in a PSE
CAS Problem: Canonical Representations
Normal forms and canonical representations
may not match user-defined transformations.
Example reduce\sc tm: LHS of ~X*f(~X*~Y)=>X-Y does not match 2*f(2*a)
Normal forms and canonical representations
possibly change numerical properties.
For example
- Linearized and expanded forms
|
|
¶
¶x
|
|
æ
è
|
u(x)+ |
ó
õ
|
1
0
|
a v(x,y) dy |
ö
ø
|
|
|
is normalized by Maple\sc tm into
|
|
æ
ç
è
|
¶
¶x
|
u(x) |
ö
÷
ø
|
+ |
ó
õ
|
1
0
|
a |
æ
ç
è
|
¶
¶x
|
v(x,y) |
ö
÷
ø
|
dy |
|
- Product forms
7*(a+b) is normalized into 7*a+7*b
CAS Problem: Fixed Semantics
In Maple\sc tm for example, the summation
is represented as
sum(f(i),i=a..b)
Now consider the evaluation
sum(i,i=10..1) = -44
The semantics are different from what we possibly want,
and incorrect when summations are directly translated into loops:
s=0
do i=10,1 ! Note: ub>lb
s=s+i
enddo
In general, semantics of builtin CAS constructs cannot be redefined.
Ctadel Design
We developed Ctadel as a PSE for a specific weather forecast system.
Ctadel has generated efficient parallel codes for the kernel numerical routines of the
hirlam numerical weather forecast system (3D advection, 2nd order explicit FD).
Two errors of the hand-written code were detected and corrected by comparing the codes with the generated codes.
Ctadel is a micro CAS, no analytic capabilities,
but emphasis on transformation, conversion, and code optimization/parallelization.
- Version 1 (1994): limited to simple symbolic manipulation
- Version 2 (1997): powerful pattern matching, program transformations, and optimization
- In progress: solution methods, efficiency of kernel, more flexibility
Ctadel System
Ctadel hirlam Parallelization
Subdomain-splitting
Ctadel hirlam Parallelization
Shared-virtual memory parallel:
Explicit message passing:
Ctadel Algebraic Properties of Operators
In the refinement of a scientific model into code, associativity, commutativity, and commuting
of (linear) operators plays a significant role.
- Mathematical functions such as sum, int, and diff commute with certain constraints
- Program constructs such as loops commute with certain constraints
|
outerloop(innerloop(S)) Û innerloop(outerloop(S)) |
|
do i=1,n do j=1,m
do j=1,m do i=1,n
S <=> S
enddo enddo
enddo enddo
Ctadel Pattern Matching
Suppose we have the transformation
|
|
¶
¶x
|
u+ |
¶
¶x
|
v Þ |
¶
¶x
|
(u+v) |
|
This transformation can be applied to
|
|
æ
ç
è
|
ó
õ
|
b
a
|
|
¶
¶x
|
u dy |
ö
÷
ø
|
+ |
¶
¶x
|
v |
|
if we can somehow commute
Some rewrite rules can be very application specific, eg:
When applied, it translates
|
|
¶
¶x
|
|
ó
õ
|
1
0
|
u v dy into |
ó
õ
|
1
0
|
|
æ
ç
è
|
v |
¶
¶x
|
u |
ö
÷
ø
|
dy |
|
We need a powerful pattern matcher to deal with cases like these!
Ctadel Commuting Operators
The predefined `commuting_op' class implements basic constraints for commuting operators:
if
|
FV(f)ÇBV(g) = ÆÙBV(f)ÇFV(g) = ÆÙBF(f)ÇBF(G) = Æ |
|
where FV(f) are the free variables of operator f and BV(f) are the bound variables of operator f.
For example:
sum(sum(u,i=1..n),j=1..m)Ûsum(sum(u,j=1..m),i=1..n)
But
sum(sum(u,i=1..j),j=1..m)\notÛsum(sum(u,j=1..m),i=1..j)
Ctadel Model Optimization
Common-subexpression elimination (CSE) exploits algebraic properties
of operators to
rewrite subexpressions to check if they are common.
CSE also matches expressions that are indexed differently, but are identical
given an affine transformation, eg.
|
uj+1,i+uj,i = [ui,j+ui-1,j]i = I(i,j),j = J(i,j) |
|
where I(i,j) = j+1 and J(i,j) = i
For example
If å and f commute, CSE results in
(Note the indexing of w in the last equation)
Ctadel Hardware Model
Common-subexpression elimination should be applied with care if operations are cheap like in RISC architectures.
Therefore, the additional storage and loads associated with a variable holding
a common subexpression should be weighted against the arithmetic costs saved.
A common-subexpression elimination algorithm iteratively refines the model
codes by using heuristic hardware cost information.
Ctadel Type Checking/Conversion
PDE problem specification language is polymorphic:
variables and operators can have more than one type.
The inference engine takes a type specification and converts expressions symbolically.
- Type checking ensures correct PDE problem specification.
- Type conversion and operator overloading is part of problem-solving process by selection of most appropriate operators.
- Dimensional analysis and unit conversion
- Discretization by overloading and conversion of continuous operators
Ctadel Annotated Syntax Trees
Annotated syntax trees (ASTs) record important information for the optimization of codes, such as interval analysis.
An attribute synthesizer takes an attribute specification and annotates codes symbolically.
The annotated information is propagated through the tree.
Transformations on the AST can use the AST properties.
do i=1..n
v(i):=sum(u(i+1,j), j=1..m)
enddo
Conclusions
- Software synthesis allows uniform model development
- A software synthesis environment imposes specific requirements on a computer algebra system
- Ctadel has been successfully used to generate efficient parallel codes for a weather forecast system
File translated from TEX by TTH, version 2.21.
On 22 Jun 1999, 10:20.