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
 LargeScale Scientific Application Development
 ProblemSolving 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 worldwide''
LargeScale Scientific Applications
Absence of uniform model development paradigm results in extensive development
and maintenance efforts on (largescale) 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
 Problemsolving environments
Problem Solving Environments
Definition [Houstis]
``A ProblemSolving 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 semiautomatic 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 largescale scientific applications, a PSE should
generate codes that match the requirements of the application.
PSE plugin 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
 Scriptinglike procedural programming language
 Posibilities for symbolicnumeric computation
 Graphical user interface and visualization tools
 Userdefined transformations with powerful pattern matching (when supported by CAS)
PSEs and Computer Algebra Systems
Implementation problems:
 Normal forms that interfere with userdefined transformations
 Translation into normal forms may affect numerical properties
 CAS constructs with fixed semantics (fixed evaluation)
 No compilerlike techniques for program transformation and optimization
 No compilerlike type checking such as for polymorphic languages
 No readytouse 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 userdefined transformations.
Example reduce^{\sc tm}: LHS of ~X*f(~X*~Y)=>XY 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 handwritten 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
Subdomainsplitting
Ctadel hirlam Parallelization
Sharedvirtual 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
Commonsubexpression 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.
u_{j+1,i}+u_{j,i} = [u_{i,j}+u_{i1,j}]_{i = I(i,j),j = J(i,j)} 

where I(i,j) = j+1 and J(i,j) = i
For example




n å
j = 1

f(v_{i+1,j}+v_{i,j}) 
 


n å
j = 1

(v_{i1,j}+v_{i,j}) 

 

If å and f commute, CSE results in




n å
j = 1

(v_{i1,j}+v_{i,j}) 
 


 

(Note the indexing of w in the last equation)
Ctadel Hardware Model
Commonsubexpression 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 commonsubexpression 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 problemsolving 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 T_{E}X by T_{T}H, version 2.21.
On 22 Jun 1999, 10:20.