\section{Counting Trees and Diffraction}
\label{section: ctrees}
Diffracting trees \cite{SZ} are counting 
trees, a special form of the counting network data structures 
introduced by Aspnes, Herlihy and Shavit \cite{AHS}. 
They are binary trees of nodes called balancers. 
A {\em balancer} is a computing element with one input 
wire and two output wires.
Tokens 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,        
that given a stream of input
tokens, repeatedly sends one token to the left output wire
and one to the right, 
% moved Ref B #2
effectively balancing the output on each wire.
%number of tokens that have been output on its output wires.
We denote by $x$ the number of input tokens ever received 
on the balancer's input wire, and 
by $y_i,\,i \in \{0,1\}$ the number of tokens ever
output on its $i$th output wire. 
Given any finite number of input tokens $x$,
%to the balancer, 
it is guaranteed that within a finite amount of time,
the balancer will reach a {\em quiescent} state, that is,
one in which the sets of input and output tokens are the same.
In any quiescent state,
$y_0=\lceil x/2\rceil$ and $y_1=\lfloor x/2\rfloor$.
We will abuse this notation and use 
$y_i$ both as the name of the $i$th output wire and 
as the  count of the number of tokens output on that wire.

The diffracting tree is defined as follows.
% fixed Ref A #2
Let $k$ be a power of two, and let us 
define the counting tree {\sc Binary$[2k]$} 
inductively.
When $k$ is equal to $1$, the {\sc Binary$[2k]$} network consists of a
single balancer with output wires $y_0$ and $y_1$.  
For $k>1$, we construct the {\sc Binary$[2k]$} 
tree from two {\sc Binary$[k]$} trees and one additional balancer.
We make the input wire $x$ of the single balancer the root of the tree 
and connect each of its output wires to the input wire of a tree of width 
$k$. We then re-designate output wires $y_0, y_1, \ldots, y_{k-1}$ of the tree 
extending from the $0$ output wire as the even output wires 
$y_0, y_2, \ldots, y_{2k-2}$
of {\sc Binary$[2k]$} and the wires $y_0, y_1, \ldots, y_{k-1}$ of the tree 
extending from the balancer's $1$ output 
wire as the odd output wires $y_1, y_3, \ldots, y_{2k-1}$.


One can extend the notion of quiescence to trees in the natural way,
and define a {\em counting tree} of width $w$ as a of tree balancers,
% fixed Ref A #3
{\sc Binary$[w]$},
with outputs $y_0,..,y_{w-1}$ that satisfy the following {\em step
property}:
% in quiescent states
\begin{quote}
In any quiescent state, 
$0 \leq y_i - y_j \leq 1$ for any $i<j$.
\end{quote}

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 {\sc Binary\/}$[4]$ counting tree,
the tree moves
input tokens to output wires in increasing order modulo $w$.
Trees having this property are called counting trees because
they 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+w, \ldots, i+(y_i - 1) w$. 

\begin{figure}[tb]
{\small
\begin{verbatim}
    type balancer is
    begin
      lock:   boolean
      toggle: boolean
      next:   array [0..1] of ptr to balancer
    end
    
    globals
      Width: integer 
      Root : ptr to root of Binary[width] tree
    
 1  function typical_balancer(b: ptr to balancer) : ptr to balancer
 2  begin
 3    lock(b->lock)
 4    i := b->toggle
 5    b->toggle := not(i)
 6    unlock(b->lock)
 7    return b->next[i]
 8  end
    
 1  function fetch&incr(): integer
 2  begin
 3    b:= Root
 4    while not leaf(b)
 5      b := typical_balancer(b)
 6    endwhile
 7    i := increment_counter_at_leaf(b)
 8    return i * Width + number_of_leaf(b)
 9  end
\end{verbatim}
} % end of small
\caption{A Shared-Memory tree-based counter implementation}
\label{figure: treecode}
\end{figure}


On a shared memory multiprocessor, one can implement 
a balancing tree as a shared data structure,
where balancers are records, % each containing a ``toggle bit,'' 
and wires are pointers from one record to another. Each of the 
machine's asynchronous processors can run a program that repeatedly 
traverses the data structure from the root input pointer to some
output pointer, each time shepherding a new token
through the network. Pseudo-code for this implementation appears
in Figure~\ref{figure: treecode}.
% Added Ref A #4
We do not assume an atomic fetch-and-complement operation, instead, we 
use a lock to avoid race conditions on the balancer's toggle bit.

\Fullname\ trees are counting trees whose balancers are of a novel
type called {\it \fullname\ balancers}.  One could easily implement a
balancer using a single {\tt toggle} bit.  Each processor would toggle
the bit inside the balancer, and accordingly decide on which wire to
exit. However, if many tokens attempted to pass through the same balancer
concurrently, the toggle bit would quickly become a hot-spot.  Even if one
applied contention reduction techniques such as exponential
back-off, the toggle bit would still form a sequential bottleneck.
One can overcome this sequential bottleneck based on the following
observation:
\begin{quote}
{\it
% moved Ref B #3
If an even number of tokens passes through
a balancer, they are evenly balanced left and right,
yet the value of the toggle bit is unchanged.
} %%%%%%%%%%%%%%%% \it
\end{quote}
Thus, one can allow pairs of colliding tokens to
``pair-off'' and coordinate among
themselves %tokens entering the balancer.
which is diffracted ``right'' and which diffracted ``left''.
% moved Ref B #4
Then they
could both leave the balancer without either of them ever having to
touch the toggle bit.  By performing the
collision/co\-or\-di\-na\-tion decisions in separate locations instead
of a global toggle bit, one can increase parallelism and
lower contention.  However, to guarantee good performance one must make sure that many 
collisions occur, not an obvious
task given the asynchrony in the system.

To achieve this goal, the implementation of the diffracting balancer is based on adding a
special {\tt prism} array ``in front'' of the toggle bit in every
balancer.  When a token (processor) $P$ enters the balancer, it first
selects a location $j$ in {\tt prism}
uniformly at random.
$P$ tries to ``collide'' with the previous processor 
% moved Ref B #5
that selected $j$, 
and if successful they leave the balancer one to the left and the other to the right.
Otherwise, $P$ waits (``spins'') for a fixed time {\tt spin}
to see whether some other processor $R$ will enter and collide with it
by selecting the same location $j$ in {\tt prism}.
If no collision occurs within time {\tt spin}, $P$
toggles the shared bit and leaves the balancer accordingly.



\subsection{The Original Diffracting Tree Implementation}
\label{section: org}


\begin{figure}[bth]
{\small
\begin{verbatim}
type balancer is
  size:   integer
  spin:   integer
  prism:  array [1..size] of integer
  lock:   boolean
  toggle: boolean
  next:   array [0..1] of ptr to balancer
endtype

location: global array[1..NUMPROCS] of ptr to balancer
\end{verbatim}
} % end small
\caption{Diffracting balancer data structure}
\label{figure: types}
\end{figure}

\begin{figure}[bth]
\begin{center}
\mbox{\dofigure{smdt4.eps}}
\end{center}
\caption{A diffracting tree of width 4}
\label{figure: difftree}
\end{figure}


Figure~\ref{figure: types} gives the data structure for 
diffracting balancers due to Shavit and Zemach~\cite{SZ-journal}.
Each balancer record consists of a {\tt toggle} bit (with accompanying {\tt
lock}) and a
{\tt prism} array. The {\tt spin} variable holds the amount of a time a
processor should delay at this node while waiting to be diffracted, and
{\tt next[0..1]} are the two balancers (or counters) 
which are descendants of this node of the tree.
An additional global {\tt location\/$[1..n]$} array has an element
per processor $p \in \{1\ldots n\}$ (per processor, not per token),
holding the address of the balancer which $p$
is currently traversing. The data structures of a diffracting tree of
width 4 are depicted graphically in Figure~\ref{figure: difftree}.



\begin{figure}
{\small
\begin{verbatim}
 1 function do-node(node: ptr to balancer) returns ptr to balancer
 2 begin
 3   location[MYID] = node

 4   rand_place = random(node.size)
 5   his_id = SWAP(node.prism[rand_place],MYID)
 6   if C&S(location[MYID],node,EMPTY) then
 7      if C&S(location[his_id],node,EMPTY) then
 8         return node.next[0]
 9      else location[MYID] = node
10   else return node.next[1]
11   repeat forever
12     repeat node.spin times 
13           if location[MYID] != node  
14              return node.next[1]
15     endrepeat

16     if T&T&S(node.lock) then  
17        if C&S(location[MYID],node,EMPTY) then
18           bit_val = node.toggle_bit
19           node.toggle_bit = 1 - bit_val
20           node.lock = OPEN
21           return node.next[bit_val]
22        else 
23           node.lock = OPEN
24           return node.next[1]
25        endif
26     endif
27    endrepeat
28 end
\end{verbatim}
}
\caption{Original version of diffraction node algorithm}
\label{figure: oldalg}
\end{figure}


Figure~\ref{figure: oldalg} gives the implementation of a diffracting tree
balancer that was used in~\cite{SZ}.
\begin{itemize}
\item {\tt MYID} -- The ID of the processor executing the code.
\item {\tt random(n)} -- Returns an integer number in the range 
$[0,n-1]$.
\item {\tt SWAP(a,x)} -- Atomically writes {\tt x} to address {\tt a}, and 
returns the previous value there.
\item {\tt C\&S(a,p,n)} -- Atomically compares the value at address 
{\tt a} to {\tt p}, if they match, writes {\tt n} to {\tt a} and 
returns {\tt TRUE}, otherwise returns {\tt FALSE}.
\item {\tt T\&T\&S(l)} -- Performs a Test\&Test\&Set
operation~\cite{TnTnS} on the 
lock, {\tt l}, returns {\tt TRUE} if the lock was captured.
\end{itemize}

The counters at the tree's leaves are implemented using a hardware
{\tt F\&I} operation. The code
translates into the following sequence of operations performed by a
% fixed Ref A #6
processor, $p$, shepherding a token through a balancer, $b_0$
(see also accompanying illustration in Figure~\ref{figure: difftree}).
First, $p$ announces its arrival at $b_0$, by writing $b_0$
to {\tt location[$p$]} (line 3).  
It then swaps its own PID for the
one written in a randomly chosen location in the {\tt prism} array 
(line 4-5).
Assuming it has read the PID of an existing processor (e.g. $r$), 
$p$ attempts to
collide with it.  The collision itself is accomplished by performing
two compare-and-swap operations. The first removes $p$ from
the set of processors waiting at this balancer (thus assuring no
other processor will collide with it), the second removes the other
processor, completing the diffraction, and allowing $p$ to be
diffracted to the {\tt next[0]} balancer (lines 6-8).  
If the first compare-and-swap fails, 
it means that some other processor has already
managed to collide with $p$, so $p$ is diffracted to the
{\tt next[1]} balancer (line 10).  
If the first succeeds but the second
compare-and-swap fails, it means that the processor with whom $p$ was
trying to collide is no longer available, (e.g. if $p$ were trying to
collide with $q$),
in which case it goes on to
the second part of the algorithm (line 9).

This part starts with $p$ giving some other processor, who may have
read its ID from {\tt prism}, time to diffract it. This is done
by repeatedly reading the value of {\tt location[$p$]}
{\tt spin} times (lines 12-15).
Unless diffracted, $p$ now attempts to acquire the 
lock on the toggle bit (line 16).
If successful, it first removes itself from the set of waiting
processors (line 17)
and then toggles the bit and exits the balancer (lines 18-21).
If it could not remove itself from the set, it follows
that some other processor already collided with $p$,
and it exits the balancer, being diffracted to {\tt next[1]} (lines 23-24).


\subsection{The Critical Parameters}
As a rule of thumb, when a large number of processors concurrently
enter the balancer, the chances for successful collisions in {\tt
prism} are high, and contention on the toggle bit is unlikely.  When
there are few processors, each will spin a short while, reach for the
toggle bit and be off, since all ``spinning'' is done on a locally
cached copy of a memory location, it incurs no overhead.  However,
there is a large range of concurrency levels where there are moderate
numbers of processors, and yet it is far from clear what level of
diffraction is achieved. Furthermore, it was observed by \cite{SZ,ST}
that too many concurrent processors can also cause performance
degradation.

This brings us to the questions most often asked by practitioners
implementing diffracting trees \cite{Simon}. Given a 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:
\begin{enumerate}
\item {\tt d} --- The depth, and hence the ``size'' of the tree (the
width is $2^d$). 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.
\item {\tt L} --- The total number of {\tt prism} locations at a given
level of the tree. At level $i$ there are $2^i$ {\tt
prism}s of size $\mbox{\tt L}/2^i$. 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.
\end{enumerate}
It is these and similar questions that our work attempts to address.

\subsection{The New Algorithm}
\label{section: alg}
We begin by modifying the diffracting tree
algorithm presented in Section~\ref{section: org}.
%\footnote{We 
%made some additional changes, such as adding an exponential backoff 
%mechanism when choosing the {\it spin} delay time}. 

Touitou~\cite{talk dan} reports the following when running a benchmark
on the prototype MIT Alewife machine~\cite{Alewife}. In his benchmark,
processors repeatedly attempt to increment a diffracting tree based
counter until some fixed number of increments has been performed.
During sufficiently long runs, some processors end up performing all
the increments, while all others remain ``starving'' in the tree.
He conjectured that this is caused by processors that were not
diffracted and queue up in front of the lock on a toggle bit. The
solution was to add a second layer prism
between the first layer and the toggle bit, a method which 
empirically exhibits more stability at the price of slightly increased
latency \cite{ST}. 
%Though we added to
%the code a mechanism to allow processes another attempt at being
%diffracted, 
The combinatorial model of the next section shows that this form of
starvation is an inherent 
% moved Ref B #6
phenomenon in the old code due to the fact
that processors that do not diffract can leave the balancer only by 
toggling
the shared bit, that is, by passing through a sequential bottleneck.
Our analysis shows that in sufficiently long runs one will reach a
permanent global state in which processors are piled up at the toggle
bits. This would also be true of the method of \cite{ST} unless 
many levels of prisms a re used, resulting in poor latency. 

\begin{figure}
{\small
\begin{verbatim}
 1  function do-node(node: ptr to balancer) returns ptr to balancer
 2  begin
 3    location[MYID] = node

 4    forever           /* Moved up to encompass entire algorithm */
 5       rand_place = random(node.size)
 6       his_id = SWAP(node.prism[rand_place],MYID)
 7       if C&S(location[MYID],node,EMPTY) then
 8          if C&S(location[his_id],node,EMPTY) then
 9             return node.next[0]
10          else location[MYID] = node
11       else return node.next[1]

12       repeat node.spin times 
13          if location[MYID] != node then
            /* diffracted? probably a high load better to spin longer */
14              if node.spin < MAXSPIN then       
15                 node.spin = node.spin * 2      
16              endif                             
17              return node.next[1]
18          endif
19       endrepeat

20       if T&T&S(node.lock) then  
21          if C&S(location[MYID],node,EMPTY) then
22             bit_val = node.toggle_bit
23             node.toggle_bit = 1 - bit_val
24             node.lock = OPEN
              /* toggled? probably a low load better to spin less */
25             if node.spin > 1 then             
26                node.spin = node.spin / 2      
27             endif                             
28             return node.next[bit_val]
29          else 
30             node.lock = OPEN
31             return node.next[1]
32          endif
33       endif 

34    endfor
35  end
\end{verbatim}
}
\caption{New version of diffraction node algorithm}
\label{figure: newalg}
\end{figure}

The improved algorithm presented in this article solves this problem
by allowing processors to repeatedly return to attempt diffractions on
the prism after failing to acquire the toggle bit. It is a dynamic form
of the method used by~\cite{ST}, but does not suffer from the same
latency increase since it always uses the ``right'' number of prisms.
Figure~\ref{figure: newalg} shows
the new algorithm. The {\tt forever} loop has been moved up to
encompass the entire diffraction attempt (Instead of
being between lines 11 and 12 it is now on line 4). 
Now if a processor could not diffract the processor
whose ID it has read from {\tt prism}, and was not subsequently
diffracted by a processor who read its ID, and could not acquire the
lock on the toggle bit, then it will go on to make a fresh diffraction
attempt, starting the process anew.

The method suggested in~\cite{SZ} to overcome starvation was to 
allow processors waiting for the toggle bit to rewrite their IDs to {\tt
prism}
so that later arriving processors
might diffract them (this is equivalent to adding
the code {\tt node.prism[rand\_place]=MYID} between lines 26 and 27
of Figure~\ref{figure: oldalg}).
This offers only a partial remedy, since if
many processors wait for the toggle bit, no
diffractions occur even if the processors' PIDs are written in the
prism array.  In any sufficiently long run some processors will get
stuck, forever waiting for the toggle bit.  
In the next
section we prove that the new algorithm, when run with the optimal tree
of depth $d$ and the optimal prism width {\tt L/$2^i$}, does not
% moved Ref B #7
suffer from this starvation phenomenon. 

Figure~\ref{figure: newalg} also gives the code for the dynamic
update of the {\tt spin} variable (lines 14-16 and 25-27), 
a performance enhancement technique
that was used both in~\cite{SZ} and here.
The spin variable serves both as a delay in which a 
processor may be diffracted and as a method to exponentially back-off 
from the toggle bit. {\tt Spin} time is doubled when a processor is diffracted
and halved if it captures the lock on the toggle bit. 
The reasoning behind the update policy is that if 
a processor is diffracted, it implies there are many other processors in 
the system, if it has captured the toggle bit, there are probably 
only a few active processors. With many processors, waiting avoids 
overloading the toggle bit and has a good chance of yielding a 
diffraction, with only a few processors, waiting for a diffraction is 
a waste of time -- better to go for the toggle bit directly. {\tt 
MAXSPIN} is a system dependent constant which defines the maximum 
amount of time a processor might spin.



\newcommand{\CnS}{{\mbox {\it C\&S}}}
\newcommand{\FullCnSTrue}[1]{
$\CnS_{#1}(\mbox{\tt location\/}[r],b,\mbox{\tt EMPTY})=\mbox{\tt true}$
}
\newcommand{\FullCnS}[1]{
$\CnS_{#1}(\mbox{\tt location\/}[r],b,\mbox{\tt EMPTY})$
}
\newcommand{\FullWrite}[1]{
${\it write}_{#1}(\mbox{\tt location\/}[r]:=b)$
}

The method used in~\cite{SZ-journal} to prove correctness 
is based on analysis of the different values taken by the 
elements of the {\tt location} array during the execution of
the algorithm. Those methods carry over to the new algorithm
with only slight modifications. We will show this for the most 
important lemma of~\cite{SZ-journal}, the rest of the proof can be 
deduced in a similar manner. The proof is constructed around the 
pairing of {\em canceling tokens}, those that leave the balancer 
through the {\tt return node.next[0]} of line 9, and {\em 
canceled} tokens, those that leave the balancer 
through the {\tt return node.next[1]} of lines 11, 17 or 31. 
Since all other tokens go through the toggle 
bit, showing 
that the number of canceled tokens is equal to the number of 
canceling tokens is enough to prove that a
balance is maintained on the balancer's output wires. 
We denote by \FullCnSTrue{p}, a successful compare-and-swap operation 
performed by processor $p$ on {\tt location[$r$]}, changing its value 
from $b$ to {\tt EMPTY}. Similarly, \FullWrite{q}, denotes the 
operation of writing $b$ to {\tt location[$r$]} by $q$.

\begin{lemma}
Given processors $q \neq r$, if $q$ performs \FullCnSTrue{q}, then the 
token currently shepherded by $r$ through $b$ is a canceled token.
\end{lemma}
\begin{proof}
Lemmas 5.8 and 5.10 of~\cite{SZ-journal} prove that if $q$'s \CnS\ 
operation, on $r$'s element of {\tt location} was 
successful, then $r$ was in fact shepherding a token though $b$ at 
that same time. This token is performing operations in the code somewhere 
between lines 4 and 34. In order for $r$'s token to leave through one 
of the {\tt returns} on lines 9 or 28, it must perform a
\FullCnSTrue{r} operation. This can't happen since the success of 
$q$'s operation changed {\tt location[$r$]} to empty. Since $r$ can only 
shepherd one token at a time, and only $r$ can perform a 
\FullWrite{r}, it follows that all subsequent \FullCnS{r} operations 
must fail. If $r$'s token can't leave through lines 9 or 28, it is a 
canceled token.
\end{proof}

