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


Quote

Science Feb. 5, '99, 283 5403, pp. 766:

``Research Council Says US Climate Models Can't Keep Up''

  1. 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''
  2. 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:


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:


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.

plugin.gif


PSE Design

Two approaches for designing PSEs for scientific problems:


PSEs and Computer Algebra Systems

Advantages using computer algebra systems (CAS) for an integrated PSE implementation:


PSEs and Computer Algebra Systems

Implementation problems:


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


CAS Problem: Fixed Semantics

In Maple\sc tm for example, the summation
b

i = a 
f(i)
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.


Ctadel System

system.gif


Ctadel hirlam Parallelization

integ2.gif



Subdomain-splitting



domdecom.gif


Ctadel hirlam Parallelization

Shared-virtual memory parallel:



sharedi.gif



sharedo.gif



Explicit message passing:



distrin.gif


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.

ophier.gif


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

x

b

a 
u dy
\Updownarrow

b

a 

x
u dy

Some rewrite rules can be very application specific, eg:


x
(v u)             v 
x
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:

f(g(u)) = g(f(u))
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)\notsum(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

ui
=
n

j = 1 
f(vi+1,j+vi,j)
wi
=
n

j = 1 
(vi-1,j+vi,j)
If and f commute, CSE results in
wi
=
n

j = 1 
(vi-1,j+vi,j)
ui
=
f(wi+1)
(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.


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
ast.gif


Conclusions


File translated from TEX by TTH, version 2.21.
On 22 Jun 1999, 10:20.