\section{Experimental Results}
\label{section: res}

\begin{figure}[p]
{\small
\begin{verbatim}
global
  integer  work  /* the work parameter */
  integer  sum_latency, latencyN, list_place
  diffracting_tree counter
  real avg_latency[], total_latency
 
per processor code {
    local
      integer latency, start, end, i, j, randw
    forever
       start = current_time()
       i = fetch_and_increment(counter)
       end = current_time()
       atomically {
         latency = end - start
         sum_latency = sum_latency + latency
         latencyN = latencyN + 1
         if latencyN  == 1000 then
            avg_latency[list_place] = 
                      sum_latency / latencyN
            list_place = list_place + 1
            sum_latency = 0
            latencyN = 0
         endif
       }
       randw = random(work)
       repeat randw times
         /* nothing */
       endrepeat
       if i > MAXINDEX then quit
    endfor
}

when all processors are done do {
  local 
     integer i
  for i = 2 to list_place-1 do
     total_latency = total_latency + avg_latency[i]
  endfor
  total_latency = total_latency / ( list_place - 2 )
}
\end{verbatim}
}
\caption{Code for Measuring Fetch\&Increment Latency}
\label{figure: benchcode}
\end{figure}

\begin{figure}[tbh]
\begin{center}
\mbox{
\dofigure{d56log.eps}
}
\caption{Latency of diffracting trees, logarithmic scale}
\label{figure: log56}
\end{center}
\end{figure}

\begin{figure}[tbh]
\begin{center}
\mbox{
\dofigure{d5lin.eps}
} \mbox{
\dofigure{d6lin.eps}
}
\caption{Latency of diffracting trees, linear scale}
\label{figure: lin56}
\end{center}
\end{figure}



In order to verify the validity of our theoretical analysis we ran a
set of benchmarks on a simulated distributed-shared-memory
multiprocessor similar to the MIT {\it Alewife}
machine~\cite{Alewife} developed by
Agarwal, et. al. 
Alewife is a large-scale multiprocessor that supports cache-coherent
distributed shared memory and user-level message-passing. The nodes
communicate via messages on a two-dimensional mesh network. 
A Communication and Memory Management Unit on each
node holds the cache tags and implements the memory coherence protocol
by synthesizing messages to other nodes. 
Our experiments make use of the shared memory interface only.
To simulate the Alewife we used
{\it Pro\-teus}\footnote{ Version 3.00, dated February 18, 1993.}, a 
multiprocessor simulator developed by Brewer, Dellarocas, Colbrook and 
Weihl~\cite{Proteus}.  Proteus simulates parallel code by multiplexing 
several parallel threads on a single CPU.  Each thread runs on its own 
virtual CPU with accompanying local memory, cache and communications 
hardware, keeping track of how much time is spent using each component.  In 
order to facilitate fast simulations, Proteus does not do complete hardware 
simulations.  Instead, operations which are local (do not interact with the 
parallel environment) are run 
% fixed Ref A #10
uninterruptedly
on the simulating machine's CPU 
and memory.  The amount of time used for local calculations is added to the 
time spent performing (simulated) globally visible operations to derive 
each thread's notion of the current time.  Proteus makes sure a thread can 
only see global events within the scope of its local time.  




In our benchmarks we
measured the average latency of processors accessing a distributed
Fetch\&Increment counter implemented as a diffracting tree with
hardware Fetch\&Increment counters at its leaves.  The average latency
is the average number of cycles it takes the counter to deliver an index. In 
these experiments {\tt work} was very close to 0.
In each simulation a counter was accessed 
between 10,000 and 20,000 times, and the time to deliver an index was 
measured for each access. The average latency was measured after each 
1000 indices delivered, the average of these times is the latency of 
the counter. In order to take into account start-up times we ignored 
the latency of the first 2,000 indices delivered. The pseudo-code in 
Figure~\ref{figure: benchcode} illustrates how the measurements were 
performed. In the code, {\tt current\_time} gives the number of 
cycles since some agreed global event, {\tt fetch\_and\_increment} is the 
diffracting tree, {\tt MAXINDEX} is the last index to be delivered 
and {\tt total\_latency} is estimate of the counter's latency. 
By monitoring the different values in the {\tt avg\_latency} array for 
different values of {\tt i}, we can make sure that the simulation has 
reached a steady state.
The random number function we used was Proteus' {\tt fast\-\_ran\-dom()} 
which is 
an implementation of the ACM Minimal Standard Random Number 
Generator~\cite{randgen,fastgen}.



We now show how our combinatorial model ties together the choice of
diffracting tree parameters depth, $d$, and prism locations per level,
$L$, to the number of processor, $P$. A diffracting
tree is shown to operate optimally when $P=O(dL)$ and $L=2^d$ (the
number of counters), i.e. the number of processors should be
   approximately equal to the number of prism locations in the tree. 
%The second
%part, $L$, tells us how to take into account the fact that,
%when {\it work} is not negligible, some processors will be busy and
%will not participate in the diffraction process.  
The constant hidden by the $O$ notation is small and depends on a
particular machine's ability to handle multiple accesses to the same
memory location.  This is an expected result and fits well with the
saturation model of Aspnes, Herlihy, and Shavit for counting
networks~\cite{nets}.


The following figures show how our model accurately predicts the
experimental results.  Figure~\ref{figure: log56} shows the latency of
diffracting trees five and six levels deep. In these experiments
we use binary trees with $d$ levels (meaning $2^d$ counters)
and $L=2^d$.
The graphs have a distinctive shape. The left hand part corresponding
to a small number of processors shows a low latency, that increases as
more processors are added. When the number of processors is very
small, the slope of the graph is low, indicating a nearly constant
latency, this fits the term $E[T]= d$.  As more processors
are added, the slope increases due to the sequential bottleneck at the
toggle bits, this fits the term $E[T] = O(P)$ for the range
$d \leq P \leq d\sqrt{L}$.
There is a local maxima of bad performance reached when
$P= O(d\sqrt{L})$, here, as our model predicts, there
are too few processors to achieve diffractions, but too many to be
processed by the toggle bit. At this point, we approach the bound
$E[T] \leq O(d\sqrt{L})$ which is the algorithm's worst case 
performance.
In fact, these results imply that one
should avoid using the trees in this range of concurrency. As more
processors are added latency decreases linearly, in accordance with
the formula $E[T] = O(P/L)$. The close-up graphs in Figure~\ref{figure:
lin56}, especially the depth 6 tree, show this linear decrease 
well. The depth 5 tree also shows how latency increases again as concurrency
increases. Note that the calibration of our graphs, and hence the
phenomena we are modeling, are very fine relative to the changes in
latency for other types of data structures. For example, in \cite{SZ},
{\it combining trees} \cite{Goodman} are shown to have a latency
increase by $2500$ units over the tested concurrency range, and so the
$300$ unit change in latency of diffracting trees would be considered
almost constant. See~\cite{SZ} for details.

\begin{figure}[tbh]
\begin{center}
\mbox{
\dofigure{width.eps}
}
\caption{Latency of diffracting trees with different width prisms}
\label{figure: width}
\end{center}
\end{figure}


Figure~\ref{figure: width} shows the effects of changing $L$, the
total number of prism locations in a level of the diffracting tree
while keeping the other parameters constant. Here we used a tree of
depth 3 and 64 processors, with almost no {\it work}. The number of
counters in the tree does not change, it remains $2^d=8$. We vary
the number of locations in a prism array of a balancer at level $i$ so
that there are $\lceil\mbox{\it L} / 2^i\rceil$ per prism.  The left
hand side of the graph corresponds to a small $L$ and a large $P$,
this approximates the case where ${{P-L}\over{dL}} \rightarrow
\infty$.  We expect the latency to behave as $E[T]={P\over L}$, and
this is indeed the case. When $L$ is this small diffractions are
constantly occurring on the prisms which can't keep up with the flow of
new processors.  This situation continues up to an optimum point,
after which increasing $L$ lowers the chance that two processors
will pick the same location in the prism, and thus latency begins to
rise. Since the number of diffractions in the tree is
$O({{P^2}\over{dL}})$ we get a linear increase in latency.
%
%  Maybe We should add a closeup graph to show this linear part
%  its hard to see it on the exp graph
%
%\comment{asaph, send linear graph if you have time..}
We can expect the rise in latency to taper off when 
$L$ is large such that no diffractions are occurring, this can be 
observed in the right hand side of the graph.

%
% NEW NEW NEW
%
\begin{figure}[tbh]
\begin{center}
\mbox{
\dofigure{oldvsnew.eps}
}
\caption{Comparison of old and new diffracting tree algorithms in terms of
average and maximal latency.}
\label{figure: oldvsnew}
\end{center}
\end{figure}

%
% NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW
%
Finally, we present empirical evidence which indicates that the 
new algorithm solves the
starvation problem discussed in Section~\ref{section: alg}.
Figure~\ref{figure: oldvsnew} shows a comparison between
the average and maximal latencies of the old and new 
algorithms. In these experiments we ran a diffracting tree based
counter for several thousand increment requests. After every
thousand requests we measured the average time for an index to be
delivered and the maximum time any single processor waited for an
index. As can be seen, maximal times increase rapidly in the old
version -- an indication of starvation, but remain stable for the new
version implying that the starvation problem has indeed been remedied.


