\documentstyle[12pt]{article}

\raggedright
\pagestyle{empty}
\textwidth=5.8in
\textheight=8.5in
\topmargin=-0.5in

\begin{document}

\protect\leftmargini=0pt

% INTRO 

\centerline{\Large \bf Dynamically Triangulated Random Surfaces}

\bigskip

{\large

\begin{itemize}
\item
String theories are candidates for a TOE (Theory of Everything).
They provide a plausible quantum theory of gravity.
\item 
Basic objects are tiny one dimensional ``strings'' (rather than points).
Dynamics described by a two dimensional space-time {\it world-sheet}
(rather than world-line).
\item 
Calculations involve integrating over all possible world-sheets, i.e.
all 2-d surfaces embedded in some higher dimensional space (3-d, 4-d, 26-d, ...)
\item 
Done numerically by a Monte Carlo integration over different triangulations 
of the surface, produced dynamically using the Metropolis algorithm.
\item 
Current research centers on finding good discretizations of the 
continuum theories, and trying to find critical points with divergent
correlation lengths, so the details of the discrete lattice structure 
become irrelevant and we can extract continuum results (c.f. lattice QCD).
\item 
Interesting critical points are phase transitions between a {\it smooth}
phase and a {\it crumpled} phase of the surface. The order and critical
exponents of this {\it crumpling transition} are still uncertain.
\item
We have done the largest simulations so far on 2-d systems, but these are 
only 576 node meshes. Critical slowing down is a major problem -- need
better algorithms.
\item
\bigskip
The same techniques are used to model real fluctuating surfaces, e.g. cell
membranes, lipid bilayers, phase boundaries.
\end{itemize}

% color pictures of strings!

\newpage

\centerline{\Large \bf Computational Issues and Optimization}

\bigskip
{\large

\begin{itemize}
\item
Program for random surfaces is very irregular, with many linked list
and pointer trees to be traversed. Original code
performed very poorly. Completely rewrote and simplified code and
gained a substantial speed-up. \\
Still performed poorly on some RISC processors such as the Intel i860. 
\item
Optimal use of cache memory is vital for processors such as the i860,
which have a small cache memory, and the time to access external 
memory is much greater than the time to perform a floating point 
operation.
\item
Due to the dynamic nature of the code, the neighbors of a site which are
used for the update of that site are constantly changing. This means
we cannot make good use of the cache unless we keep a new array which
constantly readjusts pointers to neighbors, so that data for
neighboring sites is kept in neighboring regions of memory.
\item
Other optimizations on i860 and use of non-IEEE arithmetic gave us a
substantial improvement, but still nowhere near 80 Mflops peak 
performance!
\item
Program performs much better on more recent processors (IBM RS/6000,
Hewlett-Packard).
\end{itemize}
}

\newpage

% PARALLEL ALGORITHMS

\centerline{\Large \bf Parallel Algorithms}

{\large

\bigskip
\noindent
{\bf Independent Parallelism}
\begin{itemize}
\item
Have so far used independent parallelism on MIMD machines and workstation
networks.
\item
Due to strong critical slowing down can only be used for small meshes,
since producing an independent mesh for each processor takes so long.
Need to parallelize over a single simulation.
\end{itemize}

\bigskip
\noindent
{\bf Parallel Random Surfaces}
\begin{itemize}
\item 
{\sl Load Balancing} \\
Poor load balancing on SIMD machines, since the number of links per node
can range from 3 to 20.
\item 
{\sl Dynamic Domain Decomposition} \\
Dynamic mesh means that neighboring points will change during the simulation
and eventually be on distant processors, requiring substantial non-local
communication. 
Need dynamic load balancing to preserve local communications
(c.f. dynamic adjustment of arrays to keep neighboring points in fast cache 
memory on sequential machines).
\item 
{\sl Detailed Balance} \\
The most difficult problem is to preserve {\it detailed balance}. 
A site cannot be updated at the same time as other sites on which its
value depends. 
For a regular 2-d grid, use red/black checkerboard update. 
For a dynamic, irregular grid, identifying
independent sites is a time-consuming problem which must be redone 
before every iteration.
\item 
{\sl Irregular Adaptive Grids for PDEs} \\
This problem has much in common with parallel algorithms for solving
PDEs on irregular, adaptive grids (e.g. CFD).
\item 
{\sl Implementation} \\
Currently developing parallel code for CM-5 and Intel Delta. 
\end{itemize}

}

\end{document}
