1 Introduction

The Finite Element Method (FEM) approach is used in many engineering applications with irregular domains, from elastic deformation problems to crack propagation to fluid flow. CHARM++ is a free message-passing parallel runtime system for machines from clusters of workstations to tightly-coupled SMPs. The CHARM++ FEM framework allows you to write a parallel FEM program, in C or Fortran 90, that closely resembles a serial version but includes a few framework calls.

Using the FEM framework also allows you to take advantage of all the features of CHARM++, including run-time load balancing, performance monitoring and visualization, and checkpoint/restart, with no additional effort. The FEM framework also combines naturally with other CHARM++ frameworks built on TCHARM.

The FEM framework has been undergoing a wave of recent improvements. A choice to rename the new version ParFUM has been adopted.ParFUM is short for Parallel Framework for Unstructured Meshes. Section 10 describes some of the new features included in ParFUM that were not present in FEM.

1.1 Philosophy

The CHARM++ FEM framework is designed to be flexible, in that it provided a few very general operations, such as loading and partitioning a ``mesh.'' In describing these operations, we draw on examples from structural analysis, but in fact the same calls can be used for other applications, including fluid dynamics or partial differential equations solvers, or even general-purpose graph manipulation.

For example, the FEM framework does not specify the number of spatial dimensions. Node locations are treated as just another kind of node data, with no restrictions on the number of data items. This allows the FEM framework to work with problems having any number of spatial dimensions.

1.2 Terminology

A FEM program manipulates elements and nodes. An element is a portion of the problem domain, also known as a cell, and is typically some simple shape like a triangle, square, or hexagon in 2D; or tetrahedron or rectangular solid in 3D. A node is a point in the domain, and is often the vertex of several elements. Together, the elements and nodes form a mesh, which is the central data structure in the FEM framework.

An element knows which nodes surround it via the element's connectivity table, which lists the nodes adjacent to each element.

Table 1: Connectivity table for mesh in figure 1.

Element	Adjacent Nodes
e1	n1	n3	n4
e2	n1	n2	n4
e3	n2	n4	n5

A typical FEM program performs some element-by-element calculations which update adjacent node values; then some node-by-node calculations. For example, a material dynamics program has the structure:

time loop element loop- Element deformation applies forces to surrounding nodes node loop- Forces and boundary conditions change node positions end time loop

We can parallelize such FEM programs by partitioning the serial mesh elements into several smaller meshes, or chunks. There is normally at least one chunk per processor; and often even more. During partitioning, we give nodes and elements new, local numbers within that chunk. In the figure below, we have partitioned the mesh above into two chunks, A and B.

Table 2: Connectivity table for chunk A in figure 2.

Element	Adjacent Nodes
e1	n1	n3	n4
e2	n1	n2	n4

Table 3: Connectivity table for chunk B in figure 2.

Element	Adjacent Nodes
e1	n1	n2	n3

Note that chunk A's node n2 and B's node n1 were actually the same node in the original mesh- partitioning split this single node into two shared copies (one on each chunk). However, since adding forces is associative, we can handle shared nodes by computing the forces normally (ignoring the existence of the other chunk), then adding both chunks' net force for the shared node together. This ``node update'' will give us the same resulting force on each shared node as we would get without partitioning, thus the same positions, thus the same final result.

For example, under hydrostatic pressure, each chunk might compute a local net force vector for its nodes as shown in Figure 3 (a). After adding forces across chunks, we have the consistent global forces shown in Figure 3 (b).

**Figure 3:** A force calculation decomposed across chunks: (a) before update (b) after updating forces across nodes.

chunk time loop element loop- Element deformation applies forces to surrounding nodes <update forces on shared nodes> node loop- Forces and boundary conditions change node positions end time loop

This is exactly the form of the time loop for a CHARM++ FEM framework program. The framework will accept a serial mesh, partition it, distribute the chunks to each processor, then you run your time loop to perform analysis and communication.

1.3 Structure of a Classic FEM Framework Program

A classic FEM framework program consists of two subroutines: init() and driver(). init() is called by the FEM framework only on the first processor - this routine typically does specialized I/O, startup and shutdown tasks. driver() is called for every chunk on every processor, and does the main work of the program. In the language of the TCHARM manual, init() runs in the serial context, and driver() runs in the parallel context.

subroutine init read the serial mesh and configuration data end subroutine /* after init, the FEM framework partitions the mesh */ subroutine driver get local mesh chunk time loop FEM computations communicate boundary conditions more FEM computations end time loop end subroutine

In this mode, the FEM framework sets up a default writing mesh during init(), partitions the mesh after init(), and sets up the partitioned mesh as the default reading mesh during driver().

1.4 Structure of an AMPI FEM Framework Program

In addition to the classic init/driver structure above, you can write an FEM framework program using the MPI style. This is a more general, more flexible method of running the program, but it is more complicated than the classic mode. All FEM framework calls are available in either mode.

main program MPI_Init FEM_Init(MPI_COMM_WORLD) if (I am master processor) read mesh partition mesh time loop FEM computations communicate boundary conditions more FEM computations end time loop end main program

In this mode, the FEM framework does not set a default reading or writing mesh, and does no partitioning; so you must use the FEM_Mesh routines to create and partition your mesh. See the AMPI manual for details on how to declare the main routine.

The driver() portion of a classic FEM program strongly resembles an MPI mode main routine--in fact, a classic FEM program can even make MPI calls from its driver() routine, because the FEM framework is implemented directly on top of MPI.

There is even a special shell script for collecting up the FEM framework source code to build a non-Charm, MPI-only version of the FEM framework. To build FEM in this manner, you first build Charm++ normally, then run a script to collect up the neccessary source files (the FEM framework, a small number of Charm configuration and utility files, and the METIS library), and finally build the library using the usual MPI compiler commands:

> cd charm/ > ./src/libs/ck-libs/fem/make_fem_alone.sh > cd fem_alone/ > mpicc -I. -DFEM_ALONE=1 -c *.c *.C > ar cr libfem_alone.a *.o

> mpif90 -I$HOME/charm/fem_alone -L$HOME/charm/fem_alone foo.f90 -lfem_alone -o foo

1.5 Compilation and Execution

A FEM framework program is a CHARM++ program, so you must begin by downloading the latest source version of CHARM++ from http://charm.cs.uiuc.edu/. Build the source with ./build FEM version or cd into the build directory, version/tmp, and type make FEM. To compile a FEM program, pass the -language fem (for C) or -language femf (for Fortran) option to charmc. You can also build using the ``fem_alone'' mode described at the end of the section above.

In a charm installation, see charm/version/pgms/charm++/fem/ for several example and test programs.

At runtime, a Charm++/FEM framework program accepts the following options, in addition to all the usual Charm++ options described in the Charm++ ``Installation and Usage Manual''.