\section{Introduction}

{\it Diffracting trees} \cite{SZ} are among the most effective and scalable
distributed-parallel techniques for shared counting, with a variety 
of applications to load balancing and concurrent data structure design.
Diffracting trees are a special form of the
counting networks of Aspnes, Herlihy, and Shavit \cite{nets}. They are
constructed from simple one-input two-output computing elements called
{\em balancers} that are connected to one another by wires to form a
balanced binary tree.  Tokens (processes) arrive on the balancer's
input wire at arbitrary times, and are output on its output wires.
Intuitively one may think of a balancer as a toggle mechanism (a bit
that is repeatedly complemented), that given a stream of input tokens,
repeatedly sends one token to the left output wire and one to the
right, effectively balancing the
number of tokens that have been output.
% on its output wires.
To illustrate this property, consider an execution in which tokens
traverse the tree sequentially, one completely after the other.
Figure~\ref{figure: simptree} shows such an
execution on a tree of width $4$. As can be seen, the tree moves
input tokens to output wires in increasing order modulo $4$.
Trees of balancers having this property 
can easily be adapted to count the total number of tokens that have
entered the network.
Counting is done by adding a ``local counter'' to each output wire $i$,
so that tokens coming out of that wire are consecutively assigned numbers
$i, i+4, i+(4 \cdot 2) \ldots$

% moved Ref A #1
\begin{figure}[t]
\begin{center}
\mbox{\dofigure{simptree.eps}}
\end{center}
\caption{A Simple Counting Tree}
\label{figure: simptree}
\end{figure}



However, under high loads, the toggle bits, especially the one at 
the root balancer of the tree, 
will be hot-spots suffering from contention and sequential bottlenecks 
that are as bad as
that of a centralized counter implementation. 
%process as it passes a token through it. 
Diffracting trees overcome the problem by having a ``prism'' mechanism
in front of the toggle bit of every balancer, allowing independent
pairs of tokens to be ``diffracted'' in separate memory locations in a
coordinated manner one to the left and one to the right. A coordinated
pair of processors can leave the balancer without either of them
having to toggle the shared bit, since each pair of toggles leaves the
bit in the same state. The processors need simply
% moved Ref B #1
to agree between
themselves which one would have gotten the "0" bit, and which the
"1". The diffraction mechanism uses randomization to ensure high
collision/diffraction rates on the prism, and the tree structure
guarantees correctness of the output values. Given appropriate
hardware primitives, diffracting trees can be implemented in a 
lock-free manner. In fact, assuming a hardware Fetch\&Complement
operation allows making diffracting trees wait-free~\cite{waitfree},
that is,
for each increment operation termination is guaranteed 
in a bounded number of steps
even if all other processors fail.

When implementing diffracting trees \cite{Simon}, the
following type of questions are of critical importance. Given a
typical system with $P$ processors that cycle repeatedly between
performing an increment on a diffracting tree based counter and
performing some amount of {\it work\/}, what are the optimal choices
of: (a) the tree ``size'' (captured by its depth $d$) relative to the
number of processors $P$. If the tree is too small, it will be
overloaded, bringing contention and less parallelism than possible. If
it is too deep, the counters at its leaves will not be fully utilized,
achieving less than optimal throughput.  (b) The prism widths,
quantified by {\tt L}, the total number of {\tt prism} locations in
the balancers at a given level of the tree. This parameter affects the
chances of a successful pairing-off. If it is too large, then
processors will tend to miss each other, failing to pair-off and
causing contention on the toggle bit. If it is too small, contention
and sequential bottlenecking will occur as too many processors will be
trying to access the same {\tt prism} locations at the same time.

Finally, even with an optimal choice of tree parameters for a certain
maximum number of processors $P$, there is a wide range of
intermediate concurrency levels in which it is unclear what the rate
of diffraction will be and hence performance is hard to
predict. 

In this paper we present the first steady-state combinatorial analysis
for diffracting trees, and use it to explain their behavior patterns
and answer critical design questions such as the ones posed above.
Our model is simple and sufficiently high level to overcome many
implementation specific details, and yet as we will show it is rich
enough to accurately predict empirically observed behaviors. As a
result of our analysis we were able to identify starvation problems in
the algorithm of \cite{SZ} and thus introduce a more stable
diffracting balancer algorithm (see section \ref{section: alg}).


We were also able to identify the range (as a function of $P$, $work$,
$d$ and $L$) in which the diffracting tree performs most efficiently,
and the ranges in which its performance degrades.  
We show that when $ {{P}\over{dL}}=O(1)$ and  $L\leq 2^d$,
the throughput of the system is optimal, and contention is low.
With less processors, diffraction probability decreases causing a 
rise in latency which reaches its peak when $P = d\sqrt{L}$. We 
further derive performance bounds for very large and very small values 
of $P$.


In the final section of this paper we provide a collection of
experimental benchmarks that show how accurately our model fits with
actual diffracting tree performance.

The closest modeling work related to ours is the amortized contention
model of Dwork, Herlihy, and Waarts \cite{DHW} used in the analysis of
counting networks \cite{DHW} and of the randomized counting networks
by Aiello, Venkatesan, Yung \cite{randomload}.  However, unlike our
work, that analysis is directed at modeling and quantifying contention
in the face of a {\it worst\/} {\it case\/} adversary, not the steady
state behaviors of the algorithms in normal (i.e. {\it common case\/})
executions.

This paper is organized as follows: 
Section~\ref{section: ctrees} gives a brief
review of tree based counting-networks and contains both 
the original diffracting tree algorithm, as well as the new code
developed based on the analysis. Section~\ref{section: combi}
introduces the combinatorial model and analyzes the performance
of diffracting trees in the steady-state.
In Section~\ref{section: res} we present empirical evidence collected
through benchmarks on a simulated shared memory 
machine to support the analysis
and Section~\ref{section: conc} concludes this paper and lists areas
of further research.
