Vortex method of fluid flow simulation

This section follows through the analysis of part of the algorithm from the `Fast Multipole Method' for solving fluid flow problems. The data structure used is a tree, with l and r pointers at each node. We also have additional pointers n and p that link nodes at each level into a linked list, and a s spiral pointer that joins the nodes in a spiral from bottom left of the tree to the root.

The nodes carry four items of data psi, phi, theta and gamma, all of which are multipole expansions of the potential due to various sets of nodes. The code shown in Fig. 5 has been simplified in two important ways.

The summations represent more complex manipulations of these expansions.
The code is a `one-dimensional' version of the algorithm. In the two dimensional version there are four subtrees at each node, and the nodes in each level are linked into a grid, rather than a list.

If we analyse the function PhaseTwo, we get the FSA in Fig. 6, for the potential sources of statements. This shows that the reads that occur in statement B are produced by the write in statement A. Also the read in statement A uses the value produced in the previous function call.

We need a different approach to produce information for the function `PhaseOne' since it recurses in a non-generator direction. We have `unrolled' three of the function calls into the body of the loop, and have looked for dependencies within one call, rather than between all calls of the function. The dependancy FSA produced in given in Fig. 8. The main observation is that there are only dependencies between calls that access the first three levels of the tree. In all other levels the four statements are independant and can therefore be executed simultaneously.

**Figure 5:** Algorithm for fast multipole method
$\begin{figure}\begin{center} \hrule \medskip\end{center}\medskip \hrule \end{figure}$

**Figure 6:** FSA for dependency of the second phase of fluid simulation algorithm
$\includegraphics[scale=0.5]{vortex.ps}$

**Figure 7:** PhaseOne of the algorithm, unrolled
$\begin{figure}\begin{center} \hrule \medskip\end{center}\medskip \hrule \end{figure}$

**Figure 8:** FSA for dependencies within one function call of the unrolled PhaseOne function
$\includegraphics[scale=0.5]{unrolled.ps}$

Timothy Lewis
1998-09-18