% COMBI COMBI COMBI COMBI COMBI COMBI COMBI COMBI COMBI COMBI
\section{The Combinatorial Model}
\label{section: combi}
We use the following steady-state combinatorial process to model the 
performance of
diffracting trees in the shared memory environment.

The diffracting tree has depth $d$. The root, which is at level $0$,
is a balancer with a prism array of $L$ cells, and one toggle bit.
Level $i<d$ has $2^i$ balancers,
each with a prism of $\lceil L 2^{-i}\rceil$ cells, and one toggle.
Each leaf of the tree has one counter.

The combinatorial process works as follows: There are $P$ processors.
Each processor proceeds from root to leaf via a sequence of balancers
on increasing levels.
%In each {\it step} of the process, each
%processor that is at some balancer of the tree , and possibly 
%performs a
%transition to the next level balancer.
Once a processor reaches a leaf
(which is a counter, on which a fast operation such as a hardware {\it
fetch\&increment} is performed) it proceeds to a `working state'.  It 
returns
to the root of the tree after $r$ steps, where $r$ is distributed
geometrically $G({1\over \mbox{\it work}})$, (i.e., the expected time 
that a
process stays in the `work' state is $\mbox{\it work}$). Our model 
assumes the
empirically verified fact
%(omitted for lack of space)
that, under equal loads, an
operation on a counter is at least as fast as the sequence of 
operations
performed when diffracting on a {\tt prism}. This is true, so long as
contention on the counter is not too great.

Each step has two parts. In the first part each processor currently at
a balancer chooses a random cell of the prism. If two processors
choose the same prism cell, both move to the next level. If only one
chooses that cell, it stays at the same level. If more than two 
choose the
same prism cell simultaneously, two move to the next level, the rest
stay at their current balancer. In the second part of the step, each
processor that it still in that balancer tries to
reach the toggle. If at least one processor reaches the toggle, one
processor moves to the next balancer, and the toggle changes its
state.
Each ``step'' in our model is a simplification of the actual
algorithm, since it represents sequences of operations that in
practice vary in their execution time in different balancers.
%%%%% NEW - AZ
Also, we ignore interference between processors, if three processors pick the
same location in the prism, we assume two will be diffracted, in reality, 
the third might interfere with the diffraction of the other
two. Another simplification is the assumption that a processor appears
in only one place in the prism, this is inaccurate. Since IDs are only
erased from the prism as a result of swapping, it
is possible for some processor's ID to be
written in many places in the prism.
%%%%%
Nevertheless, we will show the model is rich enough to accurately predict
empirically observed behavior.



\subsection{Analysis}

Label the nodes of the tree $1,...,2^{d+1}-1$ in a breadth first
search order, i.e. the $2^i$ nodes at level $i$ have labels $2^i
,...,2^{i+1} -1$.  Let $X_j^t$ denote the number of processors at
node $j$ at time $t$, let $W^t$ denote the number of processors in
the `work' state at time $t$, and let $\tau_j^t$ denote the state of
the toggle of balancer $j$ at time $t$.  Let
$\bar{X^t}=(X_1^t,...,X_{2^{d+1}-1}^t )$, and
$\bar{\tau^t}=(\tau_1^t,...,\tau_{2^{d+1}-1}^t)$.  Clearly
$\{(\bar{X^t},W^t,\bar{\tau^t}),~|~t\ge 1\}$ defines a Markov chain.
This chain is finite, aperiodic, and irreducible, thus it has a
stationary distribution. Our goal is to characterize the performance
of the diffracting tree process in the stationary distribution
as a function of $P$, $L$, $d$, and $\mbox{\it work}$.

%We first formulate a number of relations that characterize the 
%process.
%Let $M(p,b)$ be a random variable counting the number of cells that
%receive at least $2$ balls in a process in which $p$ balls are
%randomly and independently placed in $b$ boxes.
%In the diffracting tree process, at time $t$ balancer $j$ at level 
%$i$
%is sending $M(X_j^t,L2^{-i})+T_j^T$ balls to the next level, where
%$T^t_j$ counts the number of processors sent through the toggle (zero
%or one).

Let $Z^t_i$ denote the number of processors moving from level $i<d$ to
level $i+1$ at step $t$.
Since in the stationary distribution $E[X^t_j]=E[X^{t+1}_j]$,
the expected number of 
% moved Ref B #8
processors moving into a balancer in a given
step equals the expected number of processors moving out of that
balancer.
Thus, in the steady state
$$E[Z^t_i]~=~E[Z^t_{i+1}]~=~E[Z],$$
where $E[Z]$ denote the expected number of processors moving
from any one level of the tree to the next level.

The value we are interested in is $E[T]$, the expected number
of steps, in the steady state, from the time a processor enters the 
root
of the tree until the time it returns to the root.
We first prove a relation between $E[T]$ and $E[Z]$.

\begin{lemma}
$$E[T]={{P}\over{E[Z]}}.$$
\end{lemma}

\begin{proof}
Let $Q_i$ be the
probability that in
the stationary distribution a given processor at level $i$ proceeds to
level $i+1$ of the tree at a given step.  Let $E[Y_i]$ denote the
expected number of processor at level $i$.  Since $E[Y_i] Q_i = E[Z]$,
$Q_i={{E[Z]}\over {E[Y_i]}}$. Let $E[W]$ denote the expected
number of processors at the `work' state in the stationary 
distribution,
then $E[Z]={{E[W]}\over{work}}.$
  Thus,
$$E[T]=\mbox{\it work} +\sum_{i=1}^d {1\over Q_i} =
{{E[W]}\over{E[Z]}}+{{P-E[W]}\over{E[Z]}}= {P\over{E[Z]}}.$$
\end{proof}

We do not have a full characterization of the stationary distribution,
but we can obtain a sufficiently good estimate for $E[Z]$.
To simplify the presentation we focus on the case in which
$work=1$, which was also studied in the simulations.

\begin{theorem}
Let $\alpha={P\over{dL}}$. In the steady state distribution
$$E[Z]\geq (1-o(1))2L {{\alpha^2}\over{\alpha^2+2\alpha+1}}.$$
\end{theorem}

\begin{proof}
Since we are interested in a lower bound for $E[Z]$ we can ignore
the contribution of the toggles.
To approximate the performance of the discrete time Markov
chain we study a related continuous time, density dependent
jump Markov chain (see \cite[Chapers 7-8]{Ku1} or
\cite[Chapter 11]{Ku2} for detailed
discussion of density dependent jump Markov processes and
the convergence theorem we use here).

Processors in the continuous Markov process execute the same
steps as in the discrete process. The only difference is
that in the continuous process the time interval between any two
actions of a processor is a random variable exponentially
% moved Ref B #9
distributed
with expectation 1 (instead of deterministically 1
in the discrete process).

Without loss of generality we can assume
that no two events occur simultaneously in the continuous process.
We need however to carefully define the diffraction process so that
the continuous process accurately models the discrete one.
When processor $p_i$ is active, it chooses a prism cell and stays 
there
for a random interval of time, till the next time it is active.
If the prism cell has no diffraction pair in it at time $t$ we say
that the cell is `free'. If $p_i$ chose a free cell that already has
another processor that chose that cell after it became free the
two processors are matched, and the cell becomes `occupied'.
After
another random time interval the two matched processors are 
diffracted to the
next level of the tree, and the cell becomes free again.
Note that processors that chose a cell when it was occupied are not
diffracted even if they stay there after it becomes free.

Let $\ell=2^{d+1}-1$.
The state of the continuous process at time $t$ is defined by three
vectors
$\bar{s}(t)=(s_1(t),...,s_{\ell}(t))$,
$\bar{m}(t)=(m_1(t),...,m_{\ell}(t))$, and
$\bar{x}(t)=(x_1(t),...,x_{\ell}(t))$. Where $s_i(t)$ is the
fraction of prism cells at node $i$ which are free and have one new
processor (a processor that arrived after it became free)
at time $t$, $m_i(t)$ is the fraction of occupied cells at node $i$
at time $t$, and $x_i$ is the number of processors
at node $i$ at time $t$ divided by the number of prism cells at that
node.


\begin{figure}[t]
\begin{center}
\mbox{\dofigure{diffeq.eps}}
\end{center}
\caption{A model of processor advancement in a diffracting tree}
\label{figure: diffeq}
\end{figure}

We formulate a system of differential equations that measures the
expected change in the system's state in a short interval of time.
We denote the parent of node $j$ by $p(j)$.

For $j=1,...,\ell$:
\begin{eqnarray}
\left\{ \begin{array}{l}
{{dx_j}\over {dt}}~=~ 2m_{p(i)}-2m_j \\
{{ds_j}\over{dt}}~=~ (x_j-2m_j+2m_{p(j)})(1-2s_j-m_j)-s_j \\
{{dm_j}\over{dt}}~=~ (x_j-2m_j+2m_{p(j)})s_j-m_j
\end{array}
\right .
\end{eqnarray}

To see the relation between the above system and the Markov process
note that in the continuous model the expected number of events in
interval $dt$ among $g$ processors is $gdt$. Let $k(j)$ denote the
number of prism cells at node $j$,
then
the change in $x_j(t)$ in interval $dt$ is given by
% fixed Ref A #9
$$d x_j(t) = {1\over{k(j)}}(k(p(j))m_{p(j)}(t)dt-2m_j(t)k(j)dt).$$
Since $k(p(i))=2k(i)$ we get the first differential equation above
(see illustration in Figure~\ref{figure: diffeq}).
We get the second equation by observing that a total of
$k(j)(x_j(t)-2m_j(t)+2m_{p(j)}(t))$ processors will choose a cell
in node $j$ when they become active.
$k(j)(x_j(t)-2m_j(t)+2m_{p(j)}(t))dt$ processors become active in
time interval $dt$. Each has probability $(1-s_j(t)-m_j(t))$ to
pick a free cell with no new processors, and probability $s_j$ to
transform a free cell with one new processor to an occupied processor.
The last term counts free cells with one new processors that loose
that processor.
Similar derivations give the third relation.

Consider first a deterministic process controlled by the above set
of differential equations. A necessary and sufficient condition for
$(\bar{s},\bar{m},\bar{x})$ to be a fixed point of that process is
that for all $i$
${{dx_i}\over {dt}}=0$, ${{ds_i}\over {dt}}=0$, and ${{dm_i}\over 
{dt}}=0$.
The solution of the above system gives:
$$m_j={{\alpha^2}\over{\alpha^2+2\alpha+1}}.$$
The density dependent jump Markov process satisfies the conditions of
Kurtz's convergence theorem (see Theorem 8.1 in \cite{Ku1}). Thus,
as $L,d\rightarrow\infty$ the behavior of the Markov process converges
to that of the deterministic process.
\end{proof}

We can now use the above analysis to characterize the performance of
the diffracting tree. We need however to add another bound which
we ignored above, namely that there are exactly $2^d$ counters at the
leaves of the tree.

Consider the case in which ${{P}\over{dL}} \rightarrow
\infty$. In that case $E[Z]=MIN[L-o(L), 2^d]$, and
$E[T]=MAX[{P\over L}, P2^{-d}]$. If $L<2^d$ then
congestion in the prism cells degrades the performance,
if $L>2^d$ the main congestion is in the counters. In both cases
the performance is less than optimal.

If $P$ satisfies $ {{P}\over{dL}}=O(1)$,
then $E[Z]=MIN[O(L),2^d]$. If $L\leq 2^d$, then
$E[Z]$ is linear in $L$, and
$E[T]=O(P/L)=O(d)$, which is optimal up to a constant factor.

As $P$ gets smaller,
${{P}\over{dL}}\rightarrow 0$,
the diffracting probability decreases, and the
performance degrades.
If $P=\Omega(d\sqrt{L})$,
$E[Z]=\Omega ({{P^2}\over{d^2 L}})\geq {{P}\over{d\sqrt{L}}}$,
and $E[T]=O(d\sqrt{L})$.
If $P=o(d\sqrt{L})$, most of the contribution is from the
toggles. As long as $P>d$ at least one processor moves forward
in each level, $E[Z]\geq 1$, and $E[T]\leq P$.
If $P<d$, $E[T]\leq d$.

Note that when $P=O(dL)$, which is the interesting range, the expected
number of processors trying to access a prism cell simultaneously
is $O(1)$, and with high probability no more than $\log L$ processors
try to reach the same cell simultaneously. These bounds
justify our definition of a step, and conform with the experimental
results showing that diffracting trees have low memory contention.

The starvation observed in experimenting with the old algorithm can be
easily understood when it is analyzed in our model. We can show that
in each step in each balancer a constant fraction of the processors
reach the toggle, and since in that algorithm processors do not return
to the prism to try and diffract again, and given that the toggle
processes only one processor at a time, there is congestion built up
in the toggle queue.

Finally we comment about adapting the diffracting tree to various
ratios between the speed of accessing a prism cell and the speed of
the counter. If the counter is $\ell$ times faster than a diffracting
process, we can trim the diffracting tree so that a prism of size
$\ell$ feeds one counter. On the other hand if the speed of a
diffraction or a toggle step is $\ell$ times faster than the counter,
each leaf of the full diffracting tree should feed a binary tree of
depth $\lceil\log_2 \ell\rceil$ with $\ell$ counters in the leaves.


