\documentstyle[12pt]{article}

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

\begin{document}

\protect\leftmargini=0pt

% INTRO 

\centerline{\Large \bf Simulation of Spin Models of Magnets}

\bigskip

{\large
\begin{itemize}
\item
Simple models reproduce quantitative behavior of real magnetic materials
with complex interactions.
\item
\medskip
Fundamental to the development of the theory of phase transitions 
and critical phenomena, which has very wide applicability.
\item
\medskip
Computational algorithms and techniques can be applied to other fields, e.g.
   \begin{itemize}
   \item
   Monte Carlo simulation of lattice models of quantum field theory
   and quantum gravity 
   \item
   simulation of polymers, proteins, cell membranes
   \item
   simulated annealing and other ``physical'' methods for global optimization
   \item
   neural networks
   \item
   condensed matter problems, e.g. superconductors
   \end{itemize}
\item
\medskip
Since the models are simple and exact results are known in some cases 
(e.g. 2-d Ising model), these are used as a testing ground for new 
computational techniques, e.g.
   \begin{itemize}
   \item
   Monte Carlo algorithms 
   \item
   measurements and data analysis
   \item
   random number generators
   \end{itemize}

\end{itemize}

}

% Color pictures of spin models

\newpage

% RESEARCH

\centerline{\Large \bf New Monte Carlo Algorithms}

{\large
\bigskip
\noindent
Research on spin models at NPAC and S.U. Physics Department
has centered on the study and application of new algorithms.

\bigskip
\medskip
\noindent
{\bf The Metropolis Algorithm} \\
\begin{itemize}
\item 
Major problem in Monte Carlo simulation is {\it critical slowing down}.
Standard algorithms (e.g. Metropolis) do single site, local updates. 
Number of iterations needed to change the large-scale structure and 
produce a new uncorrelated configuration \underline{diverges} as a power 
of the lattice size at a critical point. 
\end{itemize}

\bigskip
\noindent
{\bf Cluster Algorithms} \\
\begin{itemize}
\item 
New multi-spin, non-local algorithms (Swendsen-Wang, Wolff) rapidly change
large-scale structure by identifying clusters of sites to be updated at
once, greatly reducing critical slowing down.
\item 
Currently only applicable to a limited class of models. 
\item 
Ongoing research includes:
   \begin{itemize}
   \item 
   Extensions to frustrated spin models (e.g. spin glasses) where critical
   slowing down is extreme
   \item
   Precise measurements of autocorrelations and dynamic critical
   exponents to help understand dynamics of new algorithms
   \item
   Application of new algorithms to simulation of spin models, 
   e.g. O(3) model, fully frustrated Ising model
   \item
   Parallel cluster algorithms
   \end{itemize}
\end{itemize}

\bigskip
\noindent
{\bf Simulated Tempering} \\
\begin{itemize}
\item 
New method for making small changes in temperature while keeping system in
equilibrium. Applications include:
   \begin{itemize}
   \item 
   Allowing tunneling between states at first order phase transitions
   (e.g. random field Ising model)
   \item 
   Global optimization (a la simulated annealing)
   \end{itemize}
\end{itemize}

}

% SLIDES ON: 
% Cluster vs Metropolis
% Autocorrelations
% Color pictures
% Tempering for RFIM

\newpage

% PARALLEL ALGORITHMS

\centerline{\Large \bf Parallel Algorithms}

{\large

\medskip
\bigskip
\noindent
{\bf Metropolis Algorithm}  \\
\begin{itemize}
\item
Regular, local algorithm
\item
Local communication, perfect load balance using standard domain decomposition
\item
Efficiently parallelizable on SIMD and MIMD machines 
\end{itemize}

\bigskip
\noindent
{\bf Swendsen-Wang Algorithm} \\
\begin{itemize}
\item
Irregular, non-local, multiple cluster algorithm
\item
Main computational task is to identify clusters ---
{\it connected component labeling}, also used in image processing 
\item
Clusters are highly irregular (fractal) in shape, and of all sizes 
(usually including one large cluster covering much of the lattice)  
\item
Efficient parallel component labeling is a very difficult problem ---
poor load balancing, lots of non-local communication
\end{itemize}

\bigskip
\noindent
{\bf Wolff Algorithm} \\
\begin{itemize}
\item
Irregular, non-local, single cluster algorithm
\item
Standard domain decomposition gives very poor load balance and
very limited parallelism 
\end{itemize}

\bigskip
\bigskip
General problem in many areas of computational physics:
\begin{itemize}
\begin{itemize}
\item
Traditional simple, regular, local algorithms parallelize efficiently 
\item
Newer irregular, adaptive, non-local algorithms are better sequentially 
but often more difficult to parallelize
\end{itemize}
\end{itemize}
}

\newpage

% PARALLEL ALGORITHMS

\centerline{\Large \bf Parallel Cluster Algorithms}

\medskip

{\large
\bigskip
\noindent
{\bf Parallel Component Labeling}

\begin{itemize}
\item
Simple SIMD component labeling algorithms are very inefficient, 
taking order $L$ iterations to label an $L^2$ lattice.
\item
These algorithms can be used effectively on MIMD machines, however.
Use fast sequential algorithms to label sub-lattices, and simple
SIMD algorithm to match clusters across processors. Takes order $\sqrt P$
iterations for an array of $P$ processors. \\
Good efficiencies if $L \gg P$.
\item
On SIMD machines (CM-2, Maspar) multi-grid algorithms using
regular (hypercube) communication, and multi-scale algorithms using general
non-local communication, do labeling in order $\log(L)$ iterations. \\
Inefficient due to poor load balancing and irregular clusters.
\end{itemize}

\bigskip
\noindent
{\bf Independent Parallelism}

\begin{itemize}
\item
On coarse grain MIMD machines or workstation networks can parallelize over 
independent simulations with different random number streams. \\
This is the only way to parallelize the Wolff algorithm efficiently.
\item
On massively parallel machines, can use a combination of domain decomposition
and independent parallelism for Swendsen-Wang algorithm, e.g. run 8 
independent simulations of 64 nodes each on 512 node nCUBE.
\end{itemize}

}

\end{document}
