% M-structures abstract
\documentstyle[11pt]{article}

% Standard Latex definitions.


\input{/jj/jamey/tex/laktex}
\input{latex-defs}

\def\illustrationfileprefix{/jj/barth/thesis/}
% ----------------------------------------------------------------

% HERE BEGINS THE DOCUMENT

\begin{document}

\title{Using Atomic Data Structures for Parallel Simulation}

\author{%
Paul S. Barth\thanks{This paper describes research performed at the
Laboratory for Computer Science of the Massachusetts Institute of
Technology.  Funding for the Laboratory is provided in part by the
Advanced Research Projects Agency of the Department of Defense under
the Office of Naval Research contract N00014-89-J-1988.
The author is supported by a fellowship from Schlumberger
Technology Corporation.}\\ 
\small M.I.T Laboratory for Computer Science\\
\small 545 Technology Square \\
\small Cambridge, MA 02139\\
{\cf barth@au-bon-pain.lcs.mit.edu}
}

\maketitle

\section*{Introduction}
Simulation programs present a difficult challenge for parallel
computing.  Although many simulations have a large parallel component,
controlling the interaction between simulation steps 
can become a significant bottleneck.  For example, the behavior of
particles in a PIC simulation[Chakra91] are largely independent, 
so many particles may be simulated in parallel.  However,
correctly modeling particle interactions requires synchronizing
particles at each time step.  When the density of particles is low,
this synchronization limits achievable parallelism.

This paper presents a general technique for increasing the parallelism
of simulation programs.  The technique combines locking techniques
developed by the database community with {\em futures}, a
write-once data structure supporting producer-consumer parallelism.
This uncovers two important sources of parallelism.  First, multiple
operations within a simulation step can run in parallel.  Second, and
more important, futures allow simulation steps to overlap without
compromising serializability or requiring roll-backs.
The combined effect of these two sources of parallelism is dramatic:
the example presented in this paper shows almost 20-fold increase in
parallelism over traditional synchronization mechanisms.

\section*{TSP and Simulated Annealing}

To illustrate this technique, consider using simulated annealing to
solve the traveling salesman problem (TSP).  The objective of TSP is
to find the shortest tour of $n$ cities in which each city is visited
exactly once, returning to starting city at the end of the tour.  TSP
is typically implemented as a graph algorithm, where nodes represent
cities and weighted edges represent the distance between cities.

Since TSP is NP-complete, approximate techniques such as simulated
annealing are used.  In this approach, an initial tour of the cities
is generated and then permuted to converge to a locally
optimal solution.  To avoid convergence on a poor local minimum, the
simulation admits some permutations that increase the tour length, in
hopes of entering a region containing better solutions.  The frequency
of such non-improving permutations is governed by the ``temperature''
of the simulation.  Initially, the system is at a very high
temperature and almost all permutations are accepted.  As the simulation
progresses the temperature ``cools,'' allowing only permutations that
reduce the cost of the tour.
 
In this version of the simulated annealing algorithm, each temperature
tries several permutations of the tour in parallel.  Each permutation
exchanges the position of two cities in the tour.
These permutations may execute in any order, as long as each
updates the tour atomically.  However, permutations from different
temperatures must be serialized to ensure that the system stabilizes.
The following program implements this
algorithm:\footnote{The pseudo-language used here is based on Id[Nikhil91], an
implicitly parallel programming language.}

\begin{minipage}[t]{3.5in}
\beginid
\small\tt
def tour n = ~\em atomic array of cities from# 1~\em to# n ;
\null
def templock = ~\em atomic# (tour ncities) ;
\null
def anneal temp ncities nswaps =
  {~\em parallel# while (~\em~not\_frozen## temp) do 
     {atomically a_tour = templock update
       {~\em parallel# for j from 1 to nswaps do
          swap ~\em two random cities# } } ;
     next temp = ~\em cool# temp } ; 
\null
def swap i j a_tour temp =
 {atomically tour = a_tour update 
   { old_i_city = tour[i] ;    
     old_j_city = tour[j] ;    
     new_i_city, new_j_city = ~\em permute# i,j ;
     tour[i]    = new_i_city;   
     tour[j]    = new_j_city } } ; 
\endid
\end{minipage} \ \begin{minipage}[t]{3in}

\vspace{.3in}

\illustration{tsp-structure}

\vspace{.3in}

\end{minipage} 


This program uses {\em atomic} data structures[Barth91], which
associates an exclusive lock with shared data.  The {\cf tour} is an
atomic array of cities, and is included in another atomic object
associated with the temperature ({\cf templock}).



The {\cf anneal} function takes three arguments: the initial
temperature ({\cf temp}), the number of cities in the tour ({\cf
ncities}), and the number of permutations to perform at each
temperature ({\cf nswaps}). The parallel {\cf while} loop spawns
multiple, parallel iterations until the system freezes.  The {\cf
atomically} expression inside the loop is called an {\em atomic
region}.   The body of this
region is a parallel {\cf for} loop that issues the swaps.
The side-effects of the atomic region 
execute indivisibly, \eg\ the effect of a swap performed at one
temperature is visible only at later temperatures.

Each swap atomically updates the tour, reading the cities in the 
two positions, computing their new values, and putting them back.
This step must be atomic so that parallel {\cf swap} operations
do not interfere.  If this was not atomic, the same city could be
simultaneously moved to two different positions in the tour,
yielding an invalid tour.

\section*{Synchronizing Atomic Regions}

The nested atomic regions in this example highlight an important
problem in parallel simulation.  Although each permutation only
affects a small fraction of the shared data structure,
ensuring the atomicity of each permutation requires careful
synchronization.   The rest of this section
describes three different synchronization strategies for ensuring
atomicity, and compares their performance.

{\bf Barrier Synchronization:}
The traditional method of synchronizing atomic regions involves
barriers.  In this case, the body of an atomic region is surrounded by
synchronization operations.  These operations (typically semaphores)
lock the atomic object before the atomic region begins and release the
lock when the region completes. In this strategy, all parallel
processes spawned inside the atomic region must complete before the
lock is released.

{\bf Lock-Coupling:} 
A technique developed by the database community, called {\em lock-coupling},
ensures atomicity but unleashes more parallelism than barrier
synchronization.  In lock-coupling, the shared data is structured as a
tree of locks.  Every operation on the data acquires the locks in tree
order, releasing the parent lock after the child is acquired.

To implement lock-coupling in this example, a lock is associated with
every position in the tour array.  Under lock-coupling, {\cf swap}
locks the {\cf tour}, acquires the locks of the two cities to be
updated, then releases the lock on {\cf tour}. This allows other
swaps to begin while the two cities are being updated.  Similarly, {\cf
anneal} releases the temperature lock as soon as the last {\cf swap} process
has locked the {\cf tour}.

{\bf Futures:}
Parallelism can be further increased by using {\em futures}[Halstead86].  
A future is a ``placeholder'' for a value that is being computed by 
some process.  If a process tries to read the value of a future before it is
defined, that process is suspended; when the value is written,
any suspended processes are resumed.   

In the TSP example, each element of the tour is a future containing
a city.  The {\cf swap} function calls {\em touch} and {\em future} to
read the cities and update the positions with new futures, as follows
(lock-coupling operations are excluded for brevity):

\begin{minipage}[t]{3.5in}
%\small\tt
\beginid
def swap i j a_tour temp =
 {atomically tour = a_tour update 
   { old_i_city =~\em touch# tour[i] ;    
     old_j_city =~\em touch# tour[j] ;    
     tour[i]    =~\em future# new_i_city ;   
     tour[j]    =~\em future# new_j_city ; 
     new_i_city, new_j_city = ~\em permute# i,j } } ;
\endid
\end{minipage} \ \begin{minipage}[t]{3in}

\vspace{.1in}

\illustration{tsp-f-structure}

\vspace{.1in}

\end{minipage} 

In this version of {\cf swap}, new futures are placed in
positions {\cf i} and {\cf j} 
well before the new values for the cities are computed.
In turn, the {\cf tour} is locked only long enough for 
new futures to be allocated---even when {\cf swap} operations
contend for the same position!  If some position becomes a  ``hot-spot,''
swaps involving other positions can run in parallel.  Thus, futures
allow  significant parallelism between swaps, even between swaps in 
different temperatures.

\section*{Experimental Results}

The behavior of the TSP program was tested on a parallel simulator
called GITA[Nikhil90].  This simulator measures potential parallelism
under many conditions.  Using a graph of 100 cities, the following
data reflect the performance of annealing for five temperatures, where
each temperature spawns 40 swaps:

\begin{center}
\begin{tabular}{|l|r|r|r|}
\hline
Synchronization                           &
\multicolumn{1}{l|}{Total}        &
\multicolumn{1}{l|}{Critical}     &
\multicolumn{1}{l|}{Average}      \\
method                                  &
\multicolumn{1}{l|}{instructions} &
\multicolumn{1}{l|}{path}         &
\multicolumn{1}{l|}{parallelism}  \\
                                  &
\multicolumn{1}{l|}{executed}     &
                                  &
                                  \\
\hline
Barrier  &       237,119 &  105,973  &     2.2  \\
Lock-Coupling &       239,424  & 19,240   &  12.4  \\
Futures       &    241,424  &   6,417 &   37.6  \\
\hline
\end{tabular}
\end{center}

The excess parallelism in the futures version comes from overlapping
{\cf swap} operations, as depicted in the  diagram below.
The $y$ access represents tour positions, while the $x$
access is time (in machine instructions).  Each line corresponds to an
interval that a tour position is being updated.  
The three different shades correspond to the three annealing temperatures.  

\boxedillustration{tsp-future-10}

The three temperatures complete updating the tour with new futures in the
first 500 instructions.  After this, there is significant overlap
between temperatures. For example, position 25 is updated by
temperature 2 before all updates have completed in temperature 1.
Note that the updates still respect the serial order of the
temperatures; each position is updated by temperature 1 before
temperature 2, etc.

Futures have proved especially effective in low-density simulations,
where the overlap between time steps allows a high degree of
parallelism.  These simulations have been empirically measured to be
within 20\% of the maximum attainable parallelism.

%\bibliographystyle{abbrv}
%\bibliography{thesis}

\end{document}


