\documentstyle[12pt]{article}

\textwidth=5.9in
\textheight=8.5in
\topmargin=-0.5in
\raggedright

\pagestyle{empty}

\begin{document}
{\large

%
\centerline{\bf \Large STATISTICAL MECHANICS}
%                      =====================
\vspace*{0.8cm} 
Many problems in computational physics and chemistry deal with 
systems with extremely large numbers (of order $10^{23}$) of variables
(or {\it degrees of freedom}). 
\vspace*{0.2cm} \\
These systems cannot be solved using standard classical mechanics.
Instead we use {\it statistical mechanics}, where every {\it configuration}
(state) of the system has a certain probability of occurring, subject to a 
particular {\it probability distribution}.
\vspace*{0.2cm} \\
Some physical processes, especially quantum processes, are {\it inherently}
probabilistic, and can only be described statistically, 
\vspace*{0.5cm} \\
%
Statistical mechanics is applicable to many problems, including:
\begin{itemize}
\item
Thermal properties of matter, phase transitions \\
(solid $\Leftrightarrow$ liquid $\Leftrightarrow$ gas).
\item
Magnetic and electronic properties of matter.
\item
Semiconductors and superconductors.
\item
Structure and properties of metallic alloys.
\item
Diffusion, heat conduction, percolation.
\item
Nuclear reactions in a nuclear power station.
\item
Interactions of high energy particles in colliders (``atom smashers''
such as the CERN and Fermilab machines).
\item
Quantum field theories of electromagnetism and the strong and weak
nuclear forces.
\item
String theories and quantum gravity.
\item
Computational chemistry and biology (the structure and interaction
of molecules).
\item
Hard optimization problems (simulated annealing).
\end{itemize}




\newpage
%
\centerline{\bf \Large CALCULATIONS IN STATISTICAL MECHANICS}
%                      =====================================
\vspace*{0.8cm} 
Any configuration $C$ of the system occurs with a Boltzmann (or Gibbs) 
distribution, i.e. a probability 
\begin{displaymath}
P(C) = {1 \over Z} \, e^{-E(C)/kT}
\end{displaymath}
\vspace*{-0.2cm} \\ 
$T$ is temperature, $k$ is Boltzmann's constant, and 
the {\it partition function} is
\begin{displaymath}
Z = \sum_{C} e^{-E(C)/kT} 
\end{displaymath}
\vspace*{0.1cm} \\
{\it Thermal averages} of a measurable quantity $M$ are given by
\begin{displaymath}
<M> \, = \, \sum_{C} M(C) \, P(C) \, 
       = \, {1 \over Z} \sum_{C} M(C) \, e^{-E(C)/kT}
\end{displaymath}
\vspace*{0.1cm} \\
Solving problems in statistical mechanics thus requires numerical calculation
of a sum (or integral if the configuration space is continuous) over the
number of degrees of freedom of the problem, which is usually extremely large
(millions of dimensions in some cases). 
\vspace*{0.1cm} \\
The only reasonable method is Monte Carlo simulation, which is a 
stochastic technique -- the points to be evaluated are chosen randomly. 


\newpage
%
\centerline{\bf \Large MONTE CARLO SIMULATION}
%                      ======================
\vspace*{0.8cm} 
Configurations not chosen completely at random,
since the contribution of most configurations is exponentially suppressed
due to the Boltzmann factor $e^{-E(C)/kT}$. 
\vspace*{0.3cm} \\
Instead use {\it importance sampling}, i.e. try to choose configurations
with a probability roughly proportional to their contribution to the sum,
e.g. $P(C) = e^{-E(C)/kT} / Z$. 
\vspace*{0.3cm} \\
Now the thermal average can be approximated by
\begin{displaymath}
<M> \, = \, \sum_{C} M(C) \, P(C) 
\approx \overline{M} \, = \, {1 \over N} \sum_{t=1}^{N} M(C_{t})
\end{displaymath}
\vspace*{-0.1cm} \\
where the $C_{t}$ are the configurations generated in the Monte Carlo
simulation.
\vspace*{0.5cm} \\
{\bf The Metropolis algorithm}
\vspace*{0.2cm} \\ 
\begin{itemize}
\item Propose a change from configuration $A$ to $B$.
\item Calculate the change in energy $\Delta E = E(B) - E(A)$.
\item If $\Delta E \leq 0$ accept the change. 
\item If $\Delta E > 0$ accept the change with probability $e^{-\Delta E /kT}$. 
\end{itemize}
\vspace*{0.3cm} 
This algorithm can be applied to any system which can be described by 
statistical mechanics. 
\vspace*{0.5cm} \\
For the Ising model the change is taken as trying to ``flip''
one of the spins from up to down or vice versa.
Trying this for each spin in the lattice constitutes one {\it Metropolis
sweep} of the lattice, i.e. one Monte Carlo iteration.
\vspace*{0.5cm} \\
Calculating $\Delta E$ for a single spin flip is easy since the energy
for this model is local (i.e. only depends on neighboring spins).



\newpage
%
\centerline{\bf \Large CLUSTER ALGORITHMS}
%                      ==================
\vspace*{0.8cm} 
Local Monte Carlo updates result in {\it critical slowing down} since many 
local changes are required to make a global change, i.e. create a new 
uncorrelated configuration.
\vspace*{0.1cm} \\
Critical slowing down is the main problem preventing simulations
of large systems near interesting regions such as phase transitions. 
\vspace*{0.5cm} \\ 
New Monte Carlo algorithms have been introduced which make large,
non-local changes to the spin configurations and can dramatically
reduce critical slowing down for many spin models.
\vspace*{0.5cm} \\ 
{\bf The Swendsen-Wang Algorithm}
\begin{itemize}
\item Place bonds between neighboring sites of the same spin with
      probability $p=e^{-2\beta}$, $\beta = J/kT$.
\item Identify clusters of connected sites (connected component labeling).
\item For each cluster, choose a new spin value at random.
\end{itemize}
\vspace*{0.5cm}  
{\bf The Wolff Algorithm}
\begin{itemize}
\item Pick a site at random.
\item Grow a single cluster by recursively placing bonds (with 
      probability $p$) between sites in the cluster and neighboring
      sites of the same spin.
\item Flip all the spins in the cluster.
\end{itemize}
\vspace*{0.3cm} 
These are typical of new non-local, multi-scale and/or irregular algorithms 
in computational physics (e.g. multigrid and adaptive mesh for PDEs, 
hierarchical multipole methods for N-body simulation), 
which perform much better than traditional regular methods but are
much harder to parallelize.


\newpage
%
\centerline{\bf \Large PARALLEL ALGORITHMS}
%                      ===================
\vspace*{0.8cm} 
There are 2 main methods for parallel numerical simulations:
\begin{enumerate}
\item {\bf Independent (job-level) parallelism} -- use different 
      parameter values (e.g. temperatures) on every processor.
      \begin{itemize}
      \item Processes are independent so $100\%$ efficiency.
      \item Only for small problem sizes (memory, CSD).
      \item Only on MIMD machines.
      \item Ideal for networks of workstations.
      \end{itemize}
\item {\bf Domain decomposition} -- split the problem domain (e.g. lattice)
      over the processors.
      \begin{itemize}
      \item Needed for many problems. 
      \item Efficient if the problem and algorithm are both
	    {\it regular} and {\it local}, giving good load balance 
	    and minimal communication. 
      \item May be efficient otherwise, but generally only for MIMD machines.
      \end{itemize}
\end{enumerate}
A hybrid of these 2 methods may be effective on a massively parallel machine.
\vspace*{0.5cm} \\
Errors in Monte Carlo simulations are primarily statistical 
($1/\sqrt N$ for $N$ iterations).
They can be reduced by running independent simulations using different
{\it random numbers} on each processors. 
\vspace*{0.5cm} \\
Parallel Metropolis algorithm for the Ising model is regular and local
and very efficient.
\vspace*{0.2cm} \\
Parallel cluster algorithms for the Ising model are irregular and non-local
and difficult to parallelize efficiently, especially on SIMD machines.


\newpage
%
\centerline{\bf \Large PARALLEL METROPOLIS ALGORITHM}
%                      =============================
\vspace*{0.8cm} 
{\bf Domain decomposition}
\vspace*{0.2cm} \\
Use standard domain decomposition to distribute the lattice over
processors, with a sub-lattice on each processor. 
\vspace*{0.5cm} \\
{\bf Algorithm}
\vspace*{0.2cm} \\
A Monte Carlo algorithm requires that no sites which are connected by
the energy function can be updated at the same time. 
\vspace*{0.15cm} \\
Since the energy for the Ising model is local, this requirement
can be satisfied by a red/black (checkerboard) partitioning of the lattice.
All red sites can be updated in parallel, since their energy depends
only on the values of spins on the neighboring black sites.
All black sites can subsequently be updated in parallel. 
\vspace*{0.15cm} \\
The same technique is often used for iterative solution of partial
differential equations.
\vspace*{0.5cm} \\
{\bf Load Balancing and Communication}
\vspace*{0.2cm} \\
This gives perfect load balance as long as there are more than $2^d$
sites per processor for a $d$-dimensional lattice. 
\vspace*{0.15cm} \\
Since the energy is local, only edge data are communicated. 
\vspace*{0.15cm} \\
Simplest method (fine-grained, non-blocked) is to pass each element of
data (spin value) from neighboring processors when it is needed.
\vspace*{0.15cm} \\
More efficient method (coarse-grained, blocked) is to pass all edge data
in one message before each red/black update.
Same amount of data passed, but greatly reduced latency.
\vspace*{0.5cm} \\
{\bf Efficiency and Scalability}
\vspace*{0.2cm} \\
Blocked algorithm is very efficient and scalable as long as the number of
sites per processor is large and remains constant as the number of 
processors is increased.


\newpage
%
\centerline{\bf \Large PARALLEL CLUSTER ALGORITHMS}
%                      ===========================
\vspace*{0.8cm} 
The main computational cost here is identifying the clusters, i.e.
parallel {\it connected component labeling}. All sites in a cluster
should have the same label, which is unique to that cluster.
\vspace*{0.1cm} \\
Not easy to parallelize efficiently since spin model clusters are
highly irregular in both shape and size.
\vspace*{0.5cm} \\
{\bf Domain decomposition}
\vspace*{0.2cm} \\
Use standard domain decomposition to distribute the lattice over
processors, with a sub-lattice on each processor. 
\vspace*{0.5cm} \\
{\bf Simple SIMD algorithm}
\begin{itemize}
\item Assign each site a unique label.
\item Each site compares its label with those of its connected neighbors,
      and takes the smallest. 
\item Iterate until no labels change.
\item The final cluster label will be the smallest original label of
      all the sites in the cluster.
\end{itemize}
\vspace*{0.4cm} 
{\bf Simple MIMD algorithm}
\begin{itemize}
\item Use a fast sequential component labeling algorithm on the 
      sub-clusters on each processor.
\item Each sub-cluster containing sites on the edge of the sub-lattice
      compares its label with those of its connected neighbors on other
      processors, and takes the smallest.
\item Iterate until no labels change.
\item The final cluster label will be the smallest original label of
      all the sites in the cluster.
\end{itemize}
% \vspace*{0.4cm} 
\newpage
\centerline{\bf \Large PARALLEL CLUSTER ALGORITHMS}
\vspace*{0.8cm} 
{\bf Load balancing and Communication}
\vspace*{0.2cm} \\
Perfect load balancing in the MIMD step, poor load balancing in
the SIMD step. Only processors containing part of the largest cluster
will always be working.
\vspace*{0.15cm} \\
This simple algorithm uses only local communications. Other algorithms
use non-local communications in the SIMD step.
Trade-off between fewer iterations but heavier communications cost.
Non-local algorithms scale better to larger numbers of processors.
\vspace*{0.5cm} \\
{\bf Efficiency and Scalability}
\vspace*{0.2cm} \\
SIMD part is not scalable, so good efficiency only for modest numbers
of processors.


\newpage
%
\centerline{\bf \Large PARALLEL COMPUTING ON WORKSTATION NETWORKS}
%                      ==========================================
\vspace*{0.8cm} 
\underline{\Large\bf Hardware}
\vspace*{0.4cm} \\
\quad {\sl Current:}
\begin{itemize}
\item 4 IBM RS/6000-340 workstations connected by:
      \begin{itemize}
      \item Ethernet.
      \item IBM ALLNODE (V7) switch.
      \end{itemize}
\item nCUBE/2 (for comparison with tightly coupled parallel computer).
\end{itemize}
\vspace*{0.2cm} 
\quad {\sl Future:}
\begin{itemize}
\item IBM SP-1.
\item IBM RS/6000 workstations with FDDI and/or switch.
\item DEC Alpha workstations with FDDI and/or Gigaswitch.
\end{itemize}
\vspace*{0.5cm} 
Ethernet only works for job-level parallelism or very coarse-grain 
applications. 
\vspace*{0.4cm} \\
Workstation networks connected by fast low-latency switches can be
as effective as tightly coupled parallel computers, with smaller cost,
easily scalable, utilization of existing resources, gradual path to
parallelism (compute farm $\rightarrow$ distributed parallelism $\rightarrow$ 
parallel computer).


\newpage
%
\centerline{\bf \Large PARALLEL COMPUTING ON WORKSTATION NETWORKS}
%                      ==========================================
\vspace*{0.8cm} 
\underline{\Large\bf Parallel Languages}
\vspace*{0.4cm} \\
\quad {\sl Current:}
\begin{itemize}
\item Express C and Fortran with message passing.
\end{itemize}
\vspace*{0.2cm} 
\quad {\sl Future:}
\begin{itemize}
\item Fortran 90D, High Performance Fortran.
\item Message Passing Interface.
\end{itemize}
\vspace*{0.5cm} 
Proprietary languages (Intel, nCUBE, Meiko, TMC, etc.) do not allow
easy porting of code to other parallel machines or workstation networks.
Computational scientists would rather work on science than porting code.
\vspace*{0.4cm} \\
Portable(ish) languages (Express, PVM, P4, PICL, Linda, Strand, etc.)
generally allow simple migration of code, but not always well supported
by vendors or computer facilities.
\vspace*{0.4cm} \\
Industry standards offer portable, maintainable, well-supported (and
hopefully efficient) languages.
More computational scientists will be willing to port
large dusty-deck sequential codes.


\newpage
%
\centerline{\bf \Large PARALLEL COMPUTING ON WORKSTATION NETWORKS}
%                      ==========================================
\vspace*{0.8cm} 
\underline{\Large\bf Systems software}
\vspace*{0.4cm} \\
Software for using job-level or data parallel distributed computing
on workstation networks:
\begin{enumerate}
%
\item The Brute Force Approach \vspace*{0.1cm} \\
\begin{itemize}
\item
Log on to each machine, check if it is being used (background or
interactive processes), run the right executable for that architecture.
Run overnight, check periodically.
\item
Can write scripts for much of this work (e.g. {\it shy}), but that should 
be the job of computer scientists and vendors, not computational scientists. 
\item
Very few easily usable tools for cycle stealing or network computing.
\end{itemize}
%
\item Portable Parallel Computing \vspace*{0.1cm} \\
\begin{itemize}
\item
Easy to write parallel code (e.g. in Express) to do job-level parallelism.
\item
Portable parallel code for data parallel algorithms.
\item
Load balancing and process migration very important (and lacking).
\end{itemize}
%
\item A Transparent Network\vspace*{0.1cm} \\
\begin{itemize}
\item
Multiple sequential jobs submitted transparently to the {\it network} 
(e.g. NQS). Handles parallel jobs also.
\item
Systems software handles choice of target machine, load balancing, 
cycle stealing, process migration (e.g. when machine starts being used 
interactively). Software only just starting to becoming available.
\end{itemize}
\end{enumerate}

}
\end{document}

