\newbox\leftpage
\newdimen\fullhsize 
\newdimen\hstitle
\newdimen\hsbody
\tolerance=1000\hfuzz=2pt
\magnification=\magstep2
\baselineskip=14pt

\font\bfbigger=cmbx10 scaled\magstep2
\font\small=cmr8
\font\itsmall=cmti8

\nopagenumbers

\noindent
\centerline{\bfbigger COMPUTATIONAL ALGORITHMS}
\bigskip

\bigskip
\noindent
{$\bullet$} {\bf Parallel Algorithms }
\medskip

The Metropolis algorithm for spin models is a good example of
a physics problem which parallelizes easily and efficiently
using simple domain decomposition, since it is regular
and local. However these are precisely the properties which make it
a relatively poor physics algorithm.
% \smallskip

Cluster algorithms are good examples of irregular, multi-scale 
methods which are becoming more prominent in physics. 
Unfortunately they are much more difficult to parallelize.

\bigskip
\noindent
{$\bullet$} {\bf Component Labeling}
\medskip

The main computational task for cluster algorithms is identifying the
clusters, which is an example of {\it connected component labeling},
a standard graph problem which is also used in many other areas,
such as image analysis.
% \smallskip

Sequential algorithms for this problem are very efficient, but
this is not the case in parallel.
Cluster algorithms provide a stringent test of parallel
component labeling algorithms, since the clusters are irregular,
and can be very large.

\bigskip
\noindent
{$\bullet$} {\bf Benchmarking Parallel Languages and Compilers}
\medskip

Spin model algorithms provide a good benchmark of parallel
languages and compilers. The Metropolis algorithm
should be able to be parallelized very efficiently, and should
be a simple task for a parallelizing compiler. 
% \smallskip

In contrast, the multi-scale cluster algorithms provide a difficult
challenge for any parallel language and architecture, and in
particular for any parallelizing compiler. A big problem is
that the component labeling algorithm used will probably need to
be different for sequential and parallel machines.

\bigskip
\bigskip
\noindent
{$\bullet$} {\bf Current Research}
\medskip

We are currently investigating a number of different parallel
algorithms for component labeling, for both SIMD and MIMD machines.
One such algorithm, for the Connection Machine (CM), 
is illustrated in the figures below, in
which each cluster is assigned a label, represented by the
different colors. Initially all sites have a unique label
(or color), and gradually these are merged together (Figs. 4 and 5)
until the clusters end up being correctly labeled (Fig. 6).
% \smallskip

This algorithm is currently written in C*, and is being ported to CM
Fortran. As well as using general routing software, it makes use of 
the CM primitive {\it scan}, which passes data very quickly down a row
or column of processors (this is shown by the vertical strips in Fig. 5). 
Access to such functions from a high level parallel language is 
something we have found very useful for this application.

Another area of our research is the implementation of both the 
cluster and Metropolis algorithms in a number of different parallel 
languages, and using them as benchmarks for parallel languages and 
compilers.

\bigskip
\noindent
{$\bullet$} {\bf References}
\medskip

{\small
\noindent
\item{[1]} P.D. Coddington and C.F. Baillie,
{\itsmall Cluster Algorithms for Spin Models on MIMD Parallel Computers},
Proc. of the 5th Annual Distributed Memory Computing Conference,
Charleston (April 1990), eds. D.W. Walker and Q.F. Stout
(IEEE Computer Society Press, Los Alamitos, California, 1990).

\noindent
\item{[2]} C.F. Baillie and P.D. Coddington,
{\itsmall Cluster Identification Algorithms for Spin Models -- 
Sequential and Parallel},
Concurrency: Practice and Experience 3, 129 (1991).

\noindent
\item{[3]} P.D. Coddington and C.F. Baillie,
{\itsmall Parallel Cluster Algorithms},
Proc. of the International Conference on Lattice Field Theory,
Tallahasse, (Oct. 1990),
Nucl. Phys. B (Proc. Suppl.) 20, 76 (1991).

\noindent
\item{[4]} J. Apostolakis, P. Coddington and E. Marinari,
{\itsmall A Multi-Grid Cluster Labeling Scheme},
to be published in Europhys. Lett.

}

\vfill
\end
