%template for producing IEEE-format articles using LaTeX.
%written by Matthew Ward, CS Department, Worcester Polytechnic Institute.
%use at your own risk.  Complaints to /dev/null.
%make two column with no page numbering, default is 10 point
% from wpi.wpi.edu anonymous latex/ieee.tex
 
\documentstyle[twocolumn]{article}
\input{/jj/jamey/tex/laktex}
\input{latex-defs}

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


\pagestyle{empty}

%set dimensions of columns, gap between columns, and space between paragraphs
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}

%I copied stuff out of art10.sty and modified them to conform to IEEE format

\makeatletter
%as Latex considers descenders in its calculation of interline spacing,
%to get 12 point spacing for normalsize text, must set it to 10 points
\def\@normalsize{\@setsize\normalsize{12pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip 6pt plus3pt
minus3pt\let\@listi\@listI} 

%need an 11 pt font size for subsection and abstract headings
\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}

%make section titles bold and 12 point, 2 blank lines before, 1 after
\def\section{\@startsection {section}{1}{\z@}{24pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\large\bf}}

%make subsection titles bold and 11 point, 1 blank line before, 1 after
\def\subsection{\@startsection {subsection}{2}{\z@}{12pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\subsize\bf}}
\makeatother

\begin{document}

%don't want date printed
\date{}

%make title bold and 14 pt font (Latex default is non-bold, 16 pt)
\title{\Large\bf 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

%I don't know why I have to reset thispagesyle, but otherwise get page numbers
\thispagestyle{empty}

\subsection*{\centering Abstract}
%IEEE allows italicized abstract
{\em Synchronizing access to shared data structures is a difficult
problem for simulation programs.  Frequently, synchronizing operations
within and between simulation steps substantially curtails
parallelism.  This paper presents a general technique for performing
this synchronization while sustaining parallelism.  The technique
combines fine-grained, exclusive locks with {\em futures}, a
write-once data structure supporting producer-consumer parallelism.
The combination allows multiple operations within a simulation step
to run in parallel; further, successive
simulation steps can overlap without compromising serializability or
requiring roll-backs.  The cumulative 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{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 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{Atomic Data Structures}

Synchronizing parallel operations on shared data is a well-recognized 
problem.  Traditional synchronization mechanisms, such as semaphores
\cite{Semaphores} and monitors \cite{HoareMonitors}, protect shared data
by ensuring that update operations run under mutual exclusion.
This type of synchronization can be a bottleneck in a parallel
simulation program involving operations on a shared data
structure.  For example, simulating particles in a shared space may
yield little parallelism, because synchronization is required to
properly model particle interactions.

The database community has addressed these issues with a myriad of
locking protocols that ensure atomicity while sustaining parallelism.
In \cite{BarthThesis,MStructures}, the author applies database principles to
shared data structures by introducing a new class of data structures
called {\em M-structures}.  M-structure operations are {\em
implicitly} synchronized for atomicity: reading an M-structure element
locks the element before returning the value; similarly, writing an
element replaces the value and unlocks the element.  This
synchronization is {\em fine-grained}: each M-structure element has
its own lock, so operations on different elements in the same data
structure may operate in parallel.

Reducing the granularity of locks is a well known technique for
improving concurrency.  Each operation on a shared data structure
acquires just the locks it needs; contention arises only when two
operations require the same elements of the data structure.  However,
even this degree of contention can become a bottleneck.  For example,
if a simulation occurs in discrete steps, all updates from one step
must complete before the next step begins.  In this case, any local
contention delays the execution of successive simulation steps.  To
eliminate this bottleneck, this paper describes a way to combine
M-structures with another kind of atomic data structure, {\em
futures}\cite{Multilisp,IStructures}.  

A future is like a promissory note for a value: it represents a value
that will be defined later.   Futures can be passed
and stored as ordinary values, but procedures requiring  a future's value
must wait for the value to be defined.
In the examples below, the function {\cf future} allocates a
future and spawns a process that assigns it a value.
The {\cf touch} function reads the value of a future, suspending until
the future's value has been assigned.  Thus, futures are implicitly
synchronized, like M-structures, thereby eliminating read/write races.
Futures can be implemented by write-once data structures such as
I-structures\cite{IStructures}.

\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\cite{IdBook}, an implicitly parallel programming
language.}

\beginid
\small\tt
def tour n = ~\em atomic M-array of cities from# 1~\em to# n ;
\null
def anneal temp ncities nswaps =
  { templock = ~\em atomic# (tour ncities) ;
   In
    {~\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 = tour![i] ;    % ~\em read and lock#
     old_j = tour![j] ;    
     new_i, new_j =~\em permute# old_i,old_j ;
     tour![i]     = new_i; % ~\em write and unlock#
     tour![j]     = new_j } } ; 
\endid

\illustration{tsp-structure}

This program uses M-structures for synchronization and updates.
The {\cf tour} M-structure has two parts: an M-structure array
(M-array) of cities, and a single M-structure cell for access control.
The {\em atomic} function creates an access control lock for its given
argument.  For example, updates between temperatures is controlled by
{\cf templock}, another M-structure cell that references the
atomic tour.

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}. This region uses the access control lock of the given atomic
object ({\cf templock}) to guarantee the atomicity of the region.
In this case,  this region consists of a parallel {\cf for} loop that
issues the swaps---atomicity means that all swaps from one temperature
complete before the next temperature begins.

The {\cf swap} function also uses an atomic region, in this case to
ensure that each permutation is atomic.  Without atomicity, the same
city could be simultaneously moved to two different positions in the
tour, yielding an invalid tour.  {\cf Swap} also illustrates
Id's implicit parallelism: the statements in a block may execute in
parallel unless constrained by data dependence.   For example, tour
positions {\cf i} and {\cf j} are locked in parallel, then {\em
permute} is called, and finally {\cf i} and {\cf j} are unlocked in
parallel.  Implicit parallelism is a powerful feature of Id, but is
not central to the techniques described here.

\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 futures.  
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):


\beginid
\small\tt
def swap i j a_tour temp =
 {atomically tour = a_tour update 
   { old_i =~\em touch# tour![i] ;    
     old_j =~\em touch# tour![j] ;    
     new_i, new_j =~\em permute# old_i,old_j ;
     tour![i] =~\em future# new_i ;   
     tour![j] =~\em future# new_j } } ;
\endid

\illustration{tsp-f-structure}

In this version of {\cf swap}, the current cities in positions {\cf i}
and {\cf j} are read by locking these positions and touching the
futures; {\em permute} is called and, {\em in parallel}, new futures
are placed in positions {\cf i} and {\cf j}.  (Recall that Id
statements execute in parallel, and the {\em future} function returns
future before its value has been assigned.)  Thus, all locks are
released 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.  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\cite{IdWorld}.  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}\small
\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 first column gives the total number of instructions executed,
which is comparable for all three methods.  Note that GITA measures
{\em idealized} performance to demonstrate the maximum achievable
parallelism.  One important idealization is that memory allocation
(including allocating futures) takes a single instruction.  Although
very low overhead allocation schemes have been
developed\cite{SteeleThesis}, real systems will not realize this 
assumption.  However, increasing the cost of future allocation does
not significantly curtail parallelism; rather, the additional overhead
is masked by parallel computation.


Clearly, traditional barrier synchronization yields the least parallelism
of the three.  Lock-coupling improves on this, allowing permutations
on different elements to proceed in parallel; however, when there is
contention, the access lock of the tour remains locked until the
contention is resolved.  Futures eliminate this bottleneck,
unleashing the most parallelism.

\subsection{The Critical Path of Shared Data Structures}
The examples above demonstrate that atomicity barriers and
futures enable a program to tolerate contention.  But how
close is this to optimal?  Can more concurrency be wrung from
this program?

To address these questions, consider the {\em critical path} of
the tour M-array.  The annealing process posts $t\times n$ swaps against
the tour, where $t$ is the number of temperatures and $n$ is the 
number of swaps per temperature.  The critical path of the tour
is the time it takes for all swaps to complete.
For the TSP program, the tour position involved in the most number of
swaps gives a lower bound on the critical path of the tour.

For example, consider annealing a tour of 25 cities in three steps,
where each temperature attempts 10 swaps.  Thus, a total of
30 swaps are performed against the tour.  The histogram below
shows the distribution of swaps against the
tour positions.  Position 7 is swapped 6 times, the most of any
position in the tour.  Since each swap takes 500 cycles to update
the positions, the minimum critical path for the tour is 3000 cycles
(500 cycles $\times$ 6 swaps).  
 
\boxedillustration{tsp-hist-small}

Figures~\ref{tsp-barrier-10} through \ref{tsp-future-10} depict
the history of swaps for each of the three algorithms.
In these diagrams, the $x$ axis represents time (cycles), while 
the $y$ axis represents each of the 25 tour positions.  For each position,
horizontal lines indicate update intervals.  The start of an interval
indicates when a swap has acquired the position's old value, \eg\ when
a position has been locked.  The interval ends when a new value put back
into the position.  The three different line patterns associate
the intervals with the three annealing temperatures.
 
Figure~\ref{tsp-barrier-10} shows the swap history when barriers
are used.  Note that there is no overlap between swaps: each locks and
updates a pair of positions before the next swap begins.  Given
this serialization, the critical path of the tour cannot be less than
30$\times$500 cycles = 15,000 cycles.  The actual critical path is
slightly longer, due to synchronization overhead between swaps.

\begin{figure*}[htbp]
\boxedillustration{tsp-barrier-10-shpcc}
     \caption{
        \label{tsp-barrier-10}
       {Swap history of the tour using barriers.}
            }
\end{figure*}

Figure~\ref{tsp-atomic-10} shows the swap history when lock-coupling
is used to synchronize atomic regions.
Here, many swaps within a temperature execute in parallel.  Note that
unlike Figure~\ref{tsp-barrier-10}, these intervals are of different
lengths.  Long intervals indicate contention: for example, consider
positions 20, 18, and 4.  The first positions swapped are 20 and 4, from
interval 0 to 500.  At time step 10, the program attempts to swap
positions 18 and 4.   Position 18 is successfully locked, 
but position 4 is deferred until the first swap updates its value.
Note that while position 4 is deferred, the tour remains locked and
no other swaps begin.   The first swap unlocks position 4 at time 500;
after this, the swap on positions 18 and 4 begins computing their new values, 
and other swaps on the tour begin.



\begin{figure*}[htbp]
\boxedillustration{tsp-lock-10-shpcc}
     \caption{
        \label{tsp-atomic-10}
        {Swap history of the tour using lock coupling.}
            }
\end{figure*}

Parallelism between temperatures is quite minor.  This is because
the next temperature cannot begin until the last {\em take} in the previous
temperature completes.  Thus, the maximum overlap between temperatures
is 500 cycles, as occurs between cycles 3800 to 4300.

The critical path of the tour when atomicity barriers are used
is 5400 cycles.  This is a dramatic improvement over completion barriers,
but still 80\% longer than the lower bound of 3000 cycles.
Note that all positions have ``gaps'' between update intervals; in particular,
position 7 has 3 gaps totalling more than 1500 cycles, and
one contention delay (as described above) from cycle 1100 to 1700.

Figure~\ref{tsp-future-10} illustrates how futures allow these
gaps to be filled and delays to be masked.  By cycle 200, all
swaps for the first temperature have replaced their tour positions with
futures.  Similarly, the second temperature inserts all its futures by
cycle 400, and the third temperature by cycle 600.  In this figure,
intervals indicate the time between touching an old future and
filling a new one.  Note that there are no gaps in the intervals,
because all the swaps are initiated by time step 600.
In particular, position 7 has no gaps or delays, and is finished
with all 6 updates by cycle 3000.

\begin{figure*}[htbp]
\boxedillustration{tsp-future-10}
     \caption{
        \label{tsp-future-10}
        {Swap history of the tour using futures.}
            }
\end{figure*}

However, delays are not eliminated; rather, they are masked.
For example, the conflict between positions 20, 18, and 4 cited above
is still present.  Position 18 is again delayed until position 4 is
updated by its swap with 20.  However, no other swap is affected by
this delay (unless it involves positions 18 and 4).    In fact,
while position 18 is delayed, swaps in temperatures 2 and 3
are proceeding!

The critical path when futures are used is 3400 cycles, just
13\% above the lower bound.  It is interesting that the
critical path does not involve position 7.  Rather, position 15 incurs
enough delay to make it the critical path.  This points out that
futures do not guarantee that updates occur in the optimal order;
rather, futures opportunistically fill gaps in the swap history.  If
parallel swaps fill these gaps in a different order, a shorter
critical path may be achieved.  Scheduling updates to achieve an
optimal critical path is analogous to bin-packing, and is not
considered further.
%
%The excess parallelism in the futures version comes from overlapping
%{\cf swap} operations, as depicted in Figure~\ref{contention}.
%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.  
%
%\begin{figure*}[htbp]
%
%\illustration{tsp-barrier-10}
%
%\illustration{tsp-lock-10}
%
%\illustration{tsp-future-10}
%\caption{Contention in {\cf tour} data structure.\label{contention}}
%\end{figure*}
%
%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.
%
\subsection{Implicit Futures}

Using futures in M-structures can be viewed as another form of queuing.
In this view, the return of the future is an acknowledgment that an
update has been enqueued, while touching a future indicates that an
update has completed.  Since the updates are seen in the order
received, futures implement a FIFO queue.

Given this perspective, it is natural to ask whether M-structures
should provide the functionality of futures implicitly.  That is, each
M-structure read can implicitly touch a future for the value, and
every write can replace the old future with a new one.  Although
technically possible, this strategy places important limitations on
how M-structures are implemented.

Consider the changes required to incorporate futures into M-structure
operations.  First, each M-structure read must return a signal
indicating that it has been enqueued on a list of processes waiting
for an element.  Second, reads and writes must respect a FIFO queuing
protocol.  With these two changes, atomic regions could synchronize on
the {\em enqueuing} of M-structure reads, rather than their
completion, thus yielding the behavior of futures.  FIFO ordering
ensures that reads from different atomic regions occur in order to
avoid deadlock.  Thus, availability is increased without rewriting a
program with futures.

Unfortunately, this design places some important restrictions on the
implementation of M-structure operations.  First, requiring a FIFO
order on reads and writes precludes simple implementations such as
spin-locks and stacks.  Also, the additional acknowledgment returned
by M-structure reads induces additional memory traffic, or requires
special capabilities of the network.  These restrictions make an
efficient implementation more difficult and costly, and so futures are
coded explicitly.

\section{Conclusions}

Atomic data structures provide a clean model for synchronizing
processes that share data.  By coupling two types of atomic data
structures---M-structures and futures---simulation programs can
exploit substantial amount of parallelism.  This technique is widely
applicable, enabling updates to a shared data structure to be posted
in constant time (the time allocate the futures), even in the presence
of conflicts.  The strategy maintains serializability, so algorithms
requiring this property can also benefit.

The examples in this paper demonstrate the benefit of futures in the
presence of cheap, fine-grained locking.  Generalizing this mechanism
for coarse-grained locking over large data structures is a topic of
further research.  

\bibliographystyle{abbrv}
\bibliography{/jj/barth/thesis/thesis}

\end{document}
