\def\picture #1 by #2 (#3){
  \vbox to #2{
    \hrule  width #1 height 0pt depth 0pt
     \vfill
     \special{picture #3}}}

\def\scaledpicture #1 by #2 (#3 scaled #4) {{
  \dimen0=#1 \dimen1=#2
  \divide\dimen0 by 1000 \multiply\dimen0 by #4
  \divide\dimen1 by 1000 \multiply\dimen1 by #4
  \picture \dimen0 by \dimen1 (#3 scaled #4)}}

\makeatletter
\long\def\unmarkedfootnote#1{{\long\def\@makefntext##1{##1}\footnotetext{#1}}}
\makeatother


\documentstyle[times,11pt]{article}

\textheight = 10.25in % was 9.5
%\textwidth = 7.5in		% assume output has this much centered
\textwidth = 8.25in		% assume output has this much centered
\voffset = -.5in
\hoffset = -.5in
%
%
\topmargin = 10pt
\headheight = 16pt
\headsep = 24pt
\footheight = 12pt
\footskip = \footheight \advance\footskip by 30pt
\advance\textheight by -\topmargin
\advance\textheight by -\headheight
\advance\textheight by -\headsep
\advance\textheight by -\footskip
%
\newdimen{\outermargin}
\oddsidemargin = 30pt  %was 60
\evensidemargin = \oddsidemargin
\outermargin = 60pt  
\marginparwidth = 00pt
\marginparsep = \outermargin \advance\marginparsep by -\marginparwidth
\divide\marginparsep by 2
\advance\textwidth by -\oddsidemargin	% left side
\advance\textwidth by -\outermargin	% right side
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%

\newtheorem{defi}{Definition}[section]
\newtheorem{theo}[defi]{Theorem}
\newtheorem{algo}[defi]{Algorithm}
\newtheorem{lemm}[defi]{Lemma}
\newtheorem{assumption}[defi]{Assumption}
\newtheorem{coro}[defi]{Corollary}
\newtheorem{conj}[defi]{Conjecture}
\newtheorem{clai}[defi]{Claim}
\newtheorem{rema}[defi]{Remark}
\newtheorem{prop}[defi]{Proposition}
\newtheorem{ques}[defi]{Question}
\def\vec#1#2{#1_{1},\ldots,#1_{#2}}    % Defin. of vector 
\def\QED{\hfill$\Box$}

\newcommand{\lln}{\log\log n}
\newcommand{\slln}{\sqrt{\lln}}
\newcommand{\eff}{\mbox{\rm eff}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceiling}[1]{\lceil #1 \rceil}
\newcommand{\fln}{\lfloor \log n \rfloor}
\newcommand{\tim}{\!\!\times\!\!}
\newcommand{\interval}{\, .. \,}
\def\proof{\noindent{\bf Proof}:\ } 
\def\lar{\leftarrow}                  % leftarrow
\def\lra{\Leftrightarrow}             % leftarrow
\def\rar{\rightarrow}                 % rightarrow
\def\nl{\newline}

\begin{document}




\title{Subset Barrier Synchronization on a Private Memory Parallel System
}
\author{Anja Feldmann, Thomas Gross, Dave O'Hallaron, and Thomas M.\ Stricker \\
\\
School of Computer Science \\
Carnegie Mellon University \\
Pittsburgh, PA 15213 \\
}

\date{}
\maketitle
\thispagestyle{empty}




%\begin{abstract} 

%\end{abstract}
\section{Introduction}
Barrier synchronization is a useful technique for organizing the
execution of a parallel program into a sequence of loosely coordinated
phases.  For example, a phase of a data--parallel program running on a
private memory system might consist of a communication step,
where processors exchange messages among themselves, followed by a
computation step, where the processors operate independently on their
local data. In this example, a barrier synchronization between
data--parallel phases  keeps messages from different
phases from being intermixed.

We call a barrier that involves a group of processors a {\em subset
barrier}, and we say a processor {\em participates} in a barrier
synchronization, if it has to wait until all other processors in the
subset for this barrier have reached the given barrier.  To provide a
basis for parallel program generators, we require that an arbitrary
subset of processors can participate in a barrier.  Further, disjoint
subsets of processors can participate in different barriers in
parallel.  This property allows us, for example, to allocate disjoint
subsets of processors to different data--parallel tasks, and then
synchronize each each of these data--parallel tasks independently and
in parallel.

Since the mapping of processes to processors may not be known at compile
time, we cannot rely on the identifiers of each processor to identify
different subset barriers.  That is, if two processes $P_{a}$ and $P_{b}$
participate in one barrier $B_1$ and three other processes $P_{x}$, $P_{y}$,
and $P_{z}$ participate in another barrier $B_2$, then we cannot use the
unique id's of the processors that executed $P_{a}$, $P_{b}$, $P_{x}$,
$P_{y}$, and $P_{z}$ to determine if a barrier is reached (even if we map
a single process onto each processor), since the barrier is placed in
the programs before the mapping of processes to processors is known.
Similarly, barriers based on bit masks do not do justice to the range of
programs that can be executed on a MIMD computer.  Therefore, we introduce
{\em named barriers}.  Names do not have be unique; the only restriction is
that no two barriers with the same name can be active at the same time. 

It is desirable to limit the amount of information that must be
exchanged by messages.  A processor participating in a named barrier
need only know the barrier name and the number of participating
processors.  (If any of these are omitted, the problem of determining
if all processors reached the barrier becomes undecidable.) The
identity of the participating processors is determined by the barrier
synchronization algorithm in a distributed fashion. Thus, both the
identity and the number of processors participating in a named barrier
can change over time, without having to maintain any global run--time
mapping information.

Furthermore, we require that all processors participating in a named
barrier use a {\em symmetric} protocol, that is, they execute the same
code for synchronization.  If one processor is to perform extra work
(e.g., it determines that all processors have reached the barrier),
then the barrier algorithm must dynamically identify one processor out
of the subset of processors.

Previous work on barrier synchronization has focused on specific
synchronization hardware
\cite{lundstrom,beckmann-polychronopoulos,okeefe-dietz1,ghose-cheng,gupta}
and on algorithms for synchronizing common memory systems
\cite{arenstorf-jordan,lubachevsky,brooks,hensgen-finkel-manber}.
In this paper we investigate subset barrier synchronization in the
context of private memory systems without specific synchronization
hardware.  We introduce two general models for communication systems:
the {\em bounded buffer broadcast model} and the {\em anonymous
destination message passing model}. We describe subset barrier
synchronization algorithms for the general models, and then show how
the algorithms for the general models can be adapted to the
communication structures of a specific private memory system, in our
case, the iWarp computer\cite{iwarp,iwarp:arch}. For a ring network,
we show the somewhat counterintuitive result that the execution time of
the algorithm is $O(\sqrt{N})$, where $N$ is the total number of
processors. The analysis is supported by measured execution times on
iWarp.  In addition to providing a convenient package that is used
both by iWarp user programs as well as the iWarp runtime system, these
algorithms give us an opportunity to evaluate how some of the unique
features of the iWarp communication system effect barrier
synchronization.


\section{Algorithms and communication models} 

\label{algo-over} Barrier synchronization algorithms consist of
two phases:  

\begin{description} 
\item[Phase 1:] Determine that every participating processor has reached 
the barrier.

\item[Phase 2:] Inform  every participating processor of the successful 
completion of Phase 1.
\end{description} 
We say Phase 1 ends if one processor has reached Phase 2.  Phase 2 can be
empty if every processor can determine that every processor has reached the
barrier. For any symmetric barrier synchronization protocol on a private memory
MIMD system, each processor reaching a barrier must somehow signal
this fact by sending some data to another processor.  In general, a
processor must send a message to at least {\em one} other
participating processor, and at least one participating processor must
be able to receive information about {\em all} of the others. The
information contained in receiving a message is that one additional
processor has reached the barrier.  The algorithms described in this
paper have the key property that only {\em one} processor (determined at
runtime needs to receive information from {\em all} other participating
processors. 

We introduce two communication models and develop symmetric subset 
barrier synchronization algorithms for these models. The algorithms
share the following advantages:
\begin{itemize}
\item Each processor uses a constant number of message buffers.
\item Non--participating processors incur minimal overhead.
\end{itemize}

\subsection{Bounded buffer broadcast}

If we guarantee that the processor that reaches the barrier first
receives messages from all other participating processors, then all
other processors currently not at a barrier can safely ignore
(discard) any messages that arrive.  After one of the processors has
received messages from all participating processors, it enters Phase 2
and broadcasts a successful completion message.  This message is then
received by all participating processors that are waiting for
messages, and can be ignored (discarded) by all other processors.
Receiving such a message allows a processor to continue its
computation.

The {\em bounded buffer broadcast} model, which provides for fast
broadcasting and for fast and easy discarding of messages, is
characterized by the following:
\begin{enumerate} 
\item Each processor can broadcast a message to all other processors, and
this message is guaranteed to arrive at its destination within some
fixed time interval.

\item Messages are stored at every processor in FIFO (first in first out) 
order in a bounded number of buffers.  If a message arrives but no
buffer is free, the oldest message is retired to make space for the
newly received message.

\item Only messages currently buffered at a processor can be read by this 
processor.
\end{enumerate}

This model includes two communication primitives, {\em broadcast} and
{\em receive}, with their usual meaning.  Discarding of messages is
implicit because messages are thrown out whenever there is
no space available.  This model allows us even to discard messages
without interrupting the computation on the processor that accumulated
the messages.  Algorithm \ref{algo-broad} is a barrier synchronization
algorithm for the bounded buffer broadcast communication model.

\begin{algo}
{%\scriptsize
%\noindent{\bf Bounded Buffer Broadcast Barrier}
{\bf Generic Bounded Buffer Broadcast Barrier}

{\bf barrier}({\em barrier\_name}, {\em count})

{\small
{\em barrier\_name.reached} and {\em barrier\_name.complete} are
identifiers generated uniquely from {\em barrier\_name}. 
}

\vspace*{-.5cm}
\begin{verse}
 i = 0;\hfill/$*$ Phase 1 $*$/\\
 /$*$ discard old messages $*$/\\ 
 {\bf broadcast} ({\em barrier\_name.reached});\\ 
 {\bf do} \\ 
 \hspace*{1cm}	{\bf receive}(name\_rec);\\ 
 \hspace*{1cm}	{\bf if}\ \ (name\_rec {\bf ==} {\em barrier\_name.reached})\\ 
 \hspace*{2cm}		 i{\bf $++$};\\ 
 {\bf until}  ((i {\bf ==} {\em count}) {\bf or} (name\_rec {\bf ==} {\em barrier\_name.complete}));\\ 
 {\bf if}\ \ (i {\bf ==} {\em count})\hfill /$*$ Phase 2 $*$/\\ 
 \hspace*{1cm}	{\bf broadcast} ({\em barrier\_name.complete});\\ 
 \hspace*{1cm}	{\bf receive}();\\ 
 {\bf wait}(till broadcast completed);
\end{verse}
\vspace*{-.5cm}
}
\label{algo-broad}
\end{algo}

This model is fairly realistic (its reliance on a bounded number of
resources (buffers) will be appreciated by any implementor). Section
\ref{sec-structures} will provide an example of how this model can be 
implemented on a specific parallel system.  Note that the bounded
buffer broadcast model makes no assumptions on the number of buffer
elements; a single buffer element is sufficient for Algorithm
\ref{algo-broad}.

\subsection{Anonymous destination message passing}

In the bounded buffer broadcast model, messages are discarded at the
destination after being broadcast to all the processors in the system.
In some communication systems, broadcasting a message and then
removing it at the destination is a costly operation, so we also
investigate a model that does not rely on broadcasting and discarding.
In this model, a processor receives messages only after it has reached
a barrier.

In the generic message passing model, each processor has a unique
identifier, and this identifier is used to address the processor.  A
processor $P_s$ sends a message to a destination processor $P_d$ by
providing $P_d$'s identifier (as well as the data of the message) to the
communication system.  The message then consists of a header $H$ and
data $D$, and the destination identifier (plus maybe some routing
information, depending on the router used) is encoded in the header.
This message is then transported to the destination processor; it can
be received only by this processor.  Note that we expect that the
destination identifier is encoded in the header of the message,
systems that do not meet this requirement may encounter difficulties
implementing algorithms based on this model or models derived from it.

We now consider a modification of the generic message passing model:
{\em anonymous destination message passing}.  This model differs from
generic message passing in the following way: the destination of a
message is determined not only by the sending processor but also
influenced by the receiving processors.  There is
exactly one receiver processor, but the sender does not know the exact
identifier of the receiver processor at the time the message is sent.
Thus this model is characterized by three features:
\begin{enumerate}
\item Each message consists of a message header and some data. 

\item Every processor can  specify the destination header of 
messages that it wants to receive.

\item If the header of a message does not match the destination header as
specified by a processor, the message is automatically forwarded to a
default processor. (The default processor could be for example the
next processor based on the physical topology.)

\end{enumerate}
A sender processor does not know which processor receives the message,
but it decides what ``identifier'' the receiver must assume to receive
the message.  The third feature allows a processor to assume
different identifiers. The model has two communication primitives:
\begin{enumerate}

\item {\em selective\_send} (h, d): send data $d$ with a header $h$ to 
unspecified receiver.

\item {\em selective\_receive} (\{h\}, ha, a): receive a message with a
header $h'$ in the  set \{h\} and store the header at local address $ha$ and the data at $a$.

\end{enumerate}
Note that a bounded buffer broadcast model can be easily emulated by
the anonymous destination message passing model, so Algorithm
\ref{algo-broad} can still be used.  However, barrier synchronization
can exploit the fact that in this model a processor can actually send
messages only to participating processors.  A processor that reaches
barrier $B$ sends a message with header $H_b$ to an anonymous processor
with id $H_b$.  ($H_b$ is related to the barrier name.)  This message
then travels around until another processor decides to receive a
message with header $H_b$.  If a processor does this only if it is
participating in the related barrier, we have a way to send a message
to some processor that is participating in the same barrier and has
already reached it.

A barrier synchronization algorithm for the anonymous destination
message passing model is given in \ref{algo-message}.  Note that
correctness and some details of Algorithm \ref{algo-message} are
highly dependent on some properties of the communication system (e.g.,
what is the ``default'' processor?). For a more detailed discussion
see Section \ref{chapter-algo}.

\begin{algo}
{%\tiny

{\bf Generic Anonymous Destination Message Passing Barrier}

{\bf barrier}{\em (barrier\_name, count)} 

{\small
{\em barrier\_name.reached} and {\em barrier\_name.complete} are
identifiers generated uniquely from {\em barrier\_name}. 
}
\vspace*{-.3cm}
\begin{verse}
 i = 0;\hfill /$*$ Phase 1 $*$/\\ 
 {\bf selective\_send} ({\em barrier\_name.reached}, dummy\_data);\\ 
 {\bf do} \\ 
 \hspace*{1cm}	{\bf selective\_receive}({\em \{barrier\_name.reached, barrier\_name.complete\}}, name\_rec, dummy\_adr);\\ 
 \hspace*{1cm}	{\bf if}\ \ (name\_rec {\bf ==} {\em barrier\_name.reached})\\ 
 \hspace*{2cm}		 i{\bf $++$};\\ 
 {\bf until}  ((i {\bf ==} {\em count}) {\bf or} (name\_rec {\bf ==} 
			{\em barrier\_name.complete}));\hfill /$*$ Phase 2 $*$/\\
 {\bf if}\ \ (i {\bf ==} {\em count})\\ 
 \hspace*{1cm} {\bf selective\_broadcast} ({\em barrier\_name.complete}, {\em
						dummy\_data} ); \\\hfill /$*$ Implemented by selective\_send() $*$/\\ 
 \hspace*{1cm} {\bf selective\_receive}(\{{\em barrier\_name.complete}\}, name\_rec, dummy\_adr );
\vspace*{-.3cm}
\end{verse}
}
\label{algo-message}
\end{algo}

\section{iWarp communication structures}
\label{sec-structures}
iWarp \cite{iwarp,iwarp:arch} is a single chip VLSI processor
developed jointly by Carnegie Mellon and Intel Corp.  It contains a
{\em computation agent} (20 MFLOPS, 20 MIPS) and a high throughput
(320 MBytes/s), low latency (200 ns/32--bit word/hop) {\em
communication agent} for transferring data between other iWarp
processors.  An iWarp system is a 2D torus of iWarp processors,
ranging in size from 4 processors to 1024 processors. Carnegie
Mellon currently has three 64--processor iWarp systems.

We exploited three features of the iWarp architecture to implement the
communications primitives in the bounded buffer broadcast and
anonymous destination message passing models: a {\em broadcast unit},
{\em logical channels/pathways}, and a {\em user--configurable address
match CAM}.  Here we briefly describe these structures and how they
are used to implement the primitives; the full paper will have more
details.

\subsection{iWarp structures for bounded buffer broadcast primitives} 
\label{sec-sru-model}
Each iWarp processor is connected to a {\em broadcast unit} (the
System Reporting Unit [SRU]), which is a global ``wired or'' network
that transmits, receives, and detects collisions using 3 shift
registers on each iWarp processor.  The iWarp broadcast unit directly
supports discarding of messages and the {\em broadcast}, and {\em
receive} primitives of the bounded buffer broadcast model, with a
buffer size of 1.  Costs for iWarp implementations of the bounded
buffer broadcast primitives are summarized below. A clock is 50 ns.

\begin{description}
\label{sec-ring-model}
\item[{\em broadcast:}] One bit of data is broadcast with every 16
clocks. Including start and stop information, a message contains around 36
bits. Thus message broadcast can be achieved in 576 clocks.

\item[{\em receive:}] Receiving takes the same amount time as sending, 
576 clocks.
\end{description}

\subsection{iWarp structures for anonymous destination message passing primitives}

iWarp processors communicate with neighboring processors over structures
called {\em logical channels}, which can be chained together to form {\em
pathways}\cite{iwarp:arch}.  Although the physical connection pattern of the
iWarp is a 2D torus, logical channels and pathways allow for logical
connection patterns such as rings, trees, and hypercubes. Logical channels
can be created and destroyed dynamically, and each iWarp processor can
support at most 20 logical channels at any point in time.

We implement the primitives of the anonymous destination message
passing model on iWarp using a unidirectional ring, constructed from
logical channels, that passes through all processors.  The reason for
choosing such a simple network was to have the barrier algorithm
consume as few communications resources as possible.

Each iWarp processor contains an {\em address match CAM} (content
addressable memory) with four entries that can be set by the
programmer. When a special word called a {\em message header} arrives
over a pathway to a processor, the match CAM hardware automatically
compares the message header to its four entries.  If any of the
entries matches the message header, the message header is held in the
pathway (this is called {\em splitting a pathway}), and the
computation agent is signaled. The computation can consume an
arbitrary number of words from the pathway, and then allow the
remainder of the unconsumed words to proceed over the pathway to the
next processor (this is called {\em joining a pathway}).

To implement the {\em selective\_send} primitive on iWarp, the
computation agent simply places a message header and data on the ring.
The message circulates around the ring until one of the match CAMs in
the ring matches the message header. Note that no message circulates
forever because the match CAM of a sender is configured to receive any
message it has placed on the ring, since it must be prepared to
receive messages with the same header from other processors
participating in this barrier.

To implement the {\em selective\_receive} primitive on iWarp, the
computation agent writes the desired header to one of the match CAM
entries, waits for a matching header to arrive (thus splitting the
pathway), consumes the message header and data, and then joins the
pathway so that any trailing messages can proceed to the next
processor in the ring.

Costs for iWarp implementations of the anonymous destination message
passing primitives are summarized below.  The latency of a message
traveling through intermediate processors is roughly 4 clocks/processor.
\begin{description}
\item[{\em selective\_send:}] The cost of a {\em selective\_send} is the 
cost of composing a message header (20 clocks), the cost of splitting
the pathway (250 clocks), the cost of sending a header and data out (2
clocks/word), and the cost of joining the connection (250 clocks,
provided there is no backlog of messages). The total cost is roughly
500 clocks.

\item[{\em selective\_receive:}] The cost of a {\em selective\_receive} is 
the cost of loading a match CAM (12 clocks) and after the message
arrives an overhead of a split (250 clocks), the cost of receiving the
header and data (2 clocks/word) and the cost of joining the connection
(250 clocks). Again, the total cost is roughly 500 clocks.
\end{description}

\section{Algorithms for barrier synchronization on iWarp} 

In this section, we adapt the generic algorithms to the iWarp
communication structures and analyze their performance.

\subsection{Broadcast--based barrier synchronization algorithm}
To adapt Algorithm \ref{algo-broad} to the broadcast unit of iWarp, we
must only incorporate collision detection and rebroadcasting.  The
performance analysis is also straightforward; this algorithm takes
$O(n)$ steps for one subset barrier with subset size $n$, and $O(k*n)$
algorithm for $k$ such barriers (not accounting for rebroadcasting).

\subsection{Ring--based barrier synchronization algorithms}
\label{chapter-algo}
Algorithm \ref{algo-message} assumes nothing about the structure of
the underlying communication network.  Here we will develop methods
which exploit the topology of the ring network.

Consider the implementation of the {\em selective\_receive} primitive
on a ring. The example execution of the barrier algorithm in Figure
\ref{lower-bound} shows a simple case where the same processor ($P1$)
performs a {\em selective\_receive} of all messages.  In general
however any processor of the subset can receive such messages after
reaching the barrier (e.g., if steps (c) and (b) are interchanged in
Figure \ref{lower-bound}, P3 receives the "reached A" message of
$P2$).  So any such message must be passed on, unless the receiving
process originally sent the message.  This guarantees that the
processor that reaches a barrier first can {\em selective\_receive}
a message from {\em each} participating processor.
\begin{figure}[hp]
\scaledpicture 11.38in by 13.76in (barrier1 scaled 500)
\begin{quotation} 
3--processor barrier $A$ involving processors $P_1, P_2, P_3$.
(a) When $P_1$ reaches barrier $A$, it sets its match CAM to $A$ and
sends a message that is subsequently received by itself. 
(b) When  $P_2$ reaches barrier $A$ ,it sets its match CAM and sends
a message that is received by $P_1$.  
(c) When  $P_3$ reaches barrier $A$, it sets its match CAM and sends a
message which is also received by $P_1$. 
(d)  $P_1$ has now received $3$ messages and therefore
completes Phase 1.  A {\em selective\_broadcast} 
informs the other processors;  $P_1$ resets its match
CAM and continues its computation. $P_2$ and $P_3$ receive the
``complete'' message, reset their match CAMs, and then continue their
computations.  \end{quotation}

\caption{Example of a barrier synchronization in the anonymous destination message passing ring}
\label{lower-bound}
\end{figure}

Implementing the {\em selective\_broadcast} on a ring is easy because
we already know that every participating processor is waiting for a
message. The processor that ends Phase 1 sends a ``barrier complete''
message, and all processors receiving the message forward it (unless
they are the original sender) and then continue their computations.

The running time of this algorithm is proportional to the number of
sequential receiving and sending steps. If $n$ is the number of
participating processors, then the number of sequential receiving
steps for Phase 1 is $n$ (one processor has to receive $n$ messages).
In Phase 2 one message has to be forwarded sequentially around the
entire ring, which costs $n$ steps.  The drawback of this method is
that it unnecessarily forwards messages in Phase 1 and does not
overlap the receiving of messages on the different processors in
Phases 1 and 2. We will now discuss three ring--based algorithms
that improve on this naive approach.

\subsubsection*{RING1}
This algorithm eliminates the forwarding of messages in Phase 1 by
using a tournament or combining approach.  The processor that wins the
tournament is the processor that ends Phase 1.  Note that standard
tree contraction algorithms are inappropriate here because they
require bidirectional communication, which is not allowed in our model
and is hard to provide for the barrier synchronization, given the
limited number of logical channels available.  In our tournament
approach, there are two possibilities after a processor receives a
message: (1) it continues to receive messages (wins the round) or (2)
it forwards a message and waits for notification from the winning
processor (loses the round).  We choose the processor with the highest
id (each processor has a unique integer id) among those processors
participating in the barrier as the processor that ends Phase 1.  This
means that a processor is only allowed to continue receiving messages
as long as it does not know about another participating processors
with a higher valued id.  Also, we must preserve the information about
how many messages have been received by a processor. So in each
message we include a counter that accumulates the number of messages
the losing processors have received.

\subsubsection*{RING2}
This algorithm improves Phase 2 of algorithm RING1 by distributing the
completion notification efficiently (in some tree--like fashion).  The
tree from Phase 1 cannot be reused because of the uni-directional
communication network and the highly imbalanced nature of the tree (see
e.\,g.\ Figure \ref{lower-bound}).
Rather, the processor that finishes Phase 1, denoted $P_1$, determines
the set of participating processors over the course of Phase 1.
During Phase 2, it sends one message to the nearest participating
processor, and one message to the participating processor halfway
around the ring.  To apply this approach recursively, the messages
sent by $P_1$ must include the set of participating processors.  This
causes extra work and means that the message length will be linear in
the number of processors instead of logarithmic. In reality this works
fine for small systems but may create problems for large systems.

\subsubsection*{RING3}
This algorithm gives an alternative approach to Phase 2 with a
logarithmic message length, but with potentially decreased
performance. During Phase 2, processors are divided into classes.
Each processor with id $k$ belongs to class $\log k$, except for
processor $P_1$, which always belongs to the highest class.  First,
processor $k$ (except $P_1$) selectively receives any message sent to
class $l \leq k$.  Next, processor $k$ selectively sends a message to
all classes $l \leq k$.  Finally processor $k$ selectively receives
messages sent to classes $l \leq k$ until it receives a message sent
to class 0. A detailed outline of algorithm RING3 is shown in Appendix A.
%\Alph{\ref{appendix-rbalg}}.

\subsection{Performance analysis}

Let $N$ be the total number of processors and $n$ be the number of
processors participating in one barrier.  We analyze two different
costs: (1) the length of the timespan from the moment the last
processor reaches the barrier to the moment all processors left the
barrier, and (2) the message complexity (number of messages * number
of wires traveled during the entire barrier synchronization
algorithm).

In summary the time complexity of Phase 1 is $O(N)$, which is provably
the best we can expect for the tournament approach, and it shows a
$O(\log N)$ for all common cases, which in general is
the best we can hope for.

The time complexity of Phase 2 of algorithm RING2 is $O(\log
n)$. The time complexity of Phase 2 of algorithm RING3 is
$O(n)$, but for all common cases, it is $O(\log N)$. By choosing a
random distribution of the classes, the expected 
performance can be reduced to $O(\log^2 n)$. 

The message complexity of Phase 1 is close to optimal and for Phase 2
we incorporate a tradeoff between time complexity (algorithm RING1)
versus message complexity (algorithms RING2 and RING3).


\subsubsection{Time complexity}
\label{sec-time}
The cost of transmitting a message along the ring is small compared to
the cost of a {\em selective\_receive} or a {\em selective\_send}.
So we are concerned only with the number of {\em selective\_receive}
and {\em selective\_send} operations.

A clear lower bound on the time complexity for this problem is $\log
n$ (for otherwise we could compute the ``or'' of $n$ numbers in time
$o(\log n)$).

If, during Phase 1, the last $l$ of the $n$ participating processors
reach the barrier at time $t$ when $k - l$ processors of the other $n
- l$ processor have already been eliminated, then the time complexity
of this barrier is the same as if those $l + k - l = k$ processors had
reached the barrier at time $t$.  This implies that an $n$--processor
barrier where only one processor reaches the barrier late will finish
Phase 1 in time proportional to a $2$--processor barrier, which is a
very desirable property.

The time complexity is equivalent to the number of rounds in our
tournament.  The minimal number of rounds that may be necessary is
bounded by the length of the longest increasing subsequence\footnote{A
subsequence of a list of numbers is an arbitrary subset of the numbers
kept in the same order as the original list of numbers.} $inc$ and the
longest decreasing subsequence $dec$ of id's along the ring: A
processor may have to receive a message from $inc$ other processors,
or a message may get received by $dec$ many processors.  With an
appropriate processor numbering scheme (see Appendix B
%\Alph{\ref{appendix-analysis}} 
for a sketch and \cite{feldmann:tr} for
details), we can show that:

\begin{lemm}
\label{lemm-phase1}
For any subset barrier with $n$ participating processors there exist a
numbering scheme such that the number of rounds of Phase 1 is at most 
\[\max\{4 * \sqrt{N}, n\}.\]
If the subset of processors includes every $(2^k)^{th}$ processor, and $inc_{sub}$
($dec_{sub}$) is the longest increasing (decreasing) subsequence between those
processors, then the number of rounds is at most
\[\log N - k + 1 + inc_{sub} + dec_{sub}.\]
\end{lemm}
\proof See Appendix B.
%\Alph{\ref{appendix-analysis}}. 
\QED

Note that this result is the best we can hope for considering the
worst case sequences and that any sequence of $N$ distinct numbers
contains either an $\sqrt{N}$ increasing or decreasing subsequence of
length $\sqrt{N}$ (See Appendix B Lemma \ref{lemm-sqrt}).

The time complexity of Phase 2 of Version 2 is $O(\log n)$, since in
every round the number of processors that must be notified by a
processor is halved.  The analysis of the time complexity of Phase 2
of Version 3 is similar to the analysis of Phase 1 (see
\cite{feldmann:tr}).  The problem here is that we cannot bound the
length of the longest increasing (decreasing) subsequence as we did
before because the class id's are no longer distinct. But if every
$(2^k)^{th}$ processor is participating we still get a logarithmic
bound.  If every processor chooses its class randomly according to a
distribution we can improve this result to an expected number of
rounds of $O(\log^2 n)$.

So the total time complexity is given by the following result:
\begin{theo}
Let $inc$ ($dec$) be the length of the longest increasing (decreasing)
subsequence of the list of id's.  Using algorithm RING2 the time
complexity for a $n$ processor barrier is at most
\[ O(\max\{inc + dec, n + 1\})\;\;\;\leq\;\;\;\; O(\sqrt{N}).\]
Using algorithm RING3 with a random distribution of classes the time
complexity for a $k$ processor barrier is at most
\[ O(\max\{inc + dec, n + 1, \log^2 n\})\;\;\;\leq\;\;\;\; O(\sqrt{N}).\]
Using algorithm RING3 with a fixed distribution of classes the time
complexity for a $n$ processor barrier including every $2^{k}$'s
processor with $inc_{sub}$ ($dec_{sub}$) being the length of the
longest increasing (decreasing) subsequence of the classes between
those processors is
\[ O(\log N - k + 1 + inc + dec).\]
\end{theo}

To determine the {\bf time complexity} of {\em $h$ simultaneous}
barriers, we have to refine the proof methods we used to prove the
results for the single barrier cases, see \cite{feldmann:tr} for the
details.  Obviously the number of rounds is bounded by the sum of the
rounds of the separate barriers. Note that if the barriers work on
separate pieces of the ring the barriers do not interfere at all (or
only minimally) with each other.  This is a nice feature of practical
importance.

\subsubsection{Message complexity}
\label{sec-message}
To find a lower bound on the message complexity of Phase 1 we assume
that every processor sends at least one message and this message can
only be received by processors which have already reached the barrier.
\begin{lemm}
\label{lemm-lower}
A lower bound for the message complexity of an $n$ processor barrier for Phase
1 is $\Omega(n * N)$.
\end{lemm}
\proof See Appendix B.
%\Alph{\ref{appendix-analysis}}.
\QED

To bound the message complexity of Phase 1 of our algorithm we observe
that every processor is sending 1 message initially, every other
message which is send is only forwarded and all but one message
travels at most one time around the ring. Also the number of messages
send and the way messages are send only depends on how many processors
participate in a certain barrier and is independent of the number of
simultaneous barriers.

So the message complexity of Phase 1 of our algorithm, which is
independent on the number of simultaneous barriers, is at most $n * N$ plus an
additive term which is necessary to reduce the time complexity. The
additive term depends on the length of timespan between which the
first processor reaches the barrier and the last processor reaches the
barrier e.\,g.\ how often the processor with the current highest $id$
has to do some polling. If the timespan is sufficiently small Step 16
of the algorithm of Figure \ref{algo-ring} will never by executed and
our message complexity is $n * N$.

The message complexity of Phase 2 for Version 1 is $n$ (we just send
one single message once around the ring) which is optimal. For Version
2 we get a message complexity of up to $N * \log n$ messages and for
Version 3 we get a message complexity of up to $N * \log N$ messages
which is the price we pay for an improved time complexity.
\begin{theo}
Let the timespan between which the first processor and the last
processor reached the barrier be $t$ and the time for a message to
travel once around the ring be $t_r$ and the time to receive and send
be $t_s$ then the message complexity of RING1 for $h$ $k$ processor
barriers is at most:
\[n * N + \frac{t}{t_r + t_s} * N + h * N\]
and of algorithms RING2 and RING3 it is at most: 
\[n * N + \frac{t}{t_r + t_s} * N + h * N * \log N\]
\end{theo}
Note that this is close to optimal. 

\section{Performance measurements and evaluation}

% 1-barrier
% ring based barriers
%	version1
%	version2
%	version3
% bounded buffer based barrier
% graph_1

We measured the execution times of different implementations of
barrier synchronization on iWarp\footnote{We used a prototype 64--processor
system at Carnegie Mellon that runs at half-speed.}.  All
coding was done in C, and the programs were compiled with release
2.4.1 of the C compiler (this is a pre-release without the optimizer.)
All data are in clock cycles (50 ns in a production system).


\begin{figure}[htb] \centering
\hspace{.5cm}\scaledpicture 6.46in by 7.0in (times scaled 750 )
\caption{Execution times for different barrier synchronization methods}
\label{graph}
\end{figure}

Figure \ref{graph} shows the time for a {\em single} barrier, as a
function of the number of participating processors, if all processors
reach the barrier at the same time.  The times for Version 2 have been
obtained by adding the times of the individual phases.  Notice that
the times for Version 2 grow logarithmically, while the times for
Version 1 and for the bounded buffer version grow linearly.  This is
desirable and allows graceful scaling up of this form of barrier
synchronization.  It also confirms that the analysis in Section
\ref{sec-time} and \ref{sec-message} 
is correct since the observed execution times match the predictions.

Notice that subset barriers incur a cost. For comparison, we coded a
fast total barrier using logical channels.  Such a total barrier can
be implemented on a 64--processor iWarp system in about 1200 clocks
using a ring, and in about 200 clocks if more logical channels are
used (to build a higher order network). On the other hand, determining the
processor that sends the ``barrier complete'' message can be done at no
additional cost. 

%, it is
%surprising to notice that we do not incur additional costs by
%disallowing precomputed bitmasks in our synchronization algorithms.
% N-barrier
% discussion
% depends a little on which processors are involved

Of course the real value of subset barriers is that multiple barriers
can be active in parallel.  We measured the cost of performing $k =
64/2^{i}$ barriers in parallel, each with $2^{i}$ processors, for $i =
0, 1, \ldots, 5$.  On the ring, performing multiple barriers in
parallel added (for the considered subsets) at most 25\% to the total
execution time, whereas the 
time for the bounded buffer version grows linearly with the number of
barriers.  In general the ring--based synchronizations are about 2---3
times as fast as the broadcast--based synchronizations.  There is some
variation depending on how processors are grouped into subsets; if
each subset occupies a segment of the ring, there is less interference
between the different groups.

% One processor late
If all but one processor has reached the barrier when the last
processor arrives, our measurements verify that the only cost we
incur is the cost to end Phase 1 and to perform Phase 2, which in
broadcast--based methods are two broadcasts (2500 clocks) and, in the
ring--based methods one message plus the cost for Phase 2 (6100 clocks).

% other features
% sru releases everyone within 400 ns (clock resolution)
The above comparison between broadcast--based and ring-based
synchronization fails to draw attention to one major advantage of the
broadcast--based schemes: All participating processors leave Phase 2
at the same time, and this feature can be used to synchronize the
local timers on all processors to within 800 ns (the timer resolution is
400 ns).  This is an extremely valuable feature which has simplified our
measurement tasks significantly.

%summary figure

\section{Concluding remarks}
% logical channels a big win
%    can do subset barriers
%    clear win over SRU-based approach
%    a really big win 
%    can support a-d message passing
%      good use of message routing capabilites of the hardware
We have developed communication models for flexible barrier synchronization
which capture important features of the underlying hardware. These
allowed us to develop algorithms which, using only a ring, have an
$O(\log N)$ running time for all common partitions and an $O(\sqrt{N})$,
rather then the expected $O(N)$, worst case performance.

The ring--based subset barrier synchronization algorithms presented in
this paper present another innovative use of the iWarp's logical
channels and address match CAM. They provide the foundation for our
algorithms by efficiently implementing anonymous destination message
passing.  A simplistic router that requires specification of
the path by the sender cannot provide this service and would have
restricted our algorithm design resulting in an algorithm worse than the
broadcast--based algorithm. 
However, the large difference between the time for a total barrier and
a subset barrier for all processors points to some inefficiencies in
the design of the communication system; joining and splitting pathways
takes longer than desired.  Part of this is due to the design of the
(software) runtime kernel, and a future release will address this
issue.

% improve split/join performance
% 

% the model is good
%   based on micro-measurements, we can predict fairly accurately the
%		execution time
%   a-d message passing quite powerful

The iWarp system is a high--performance, commercial parallel system that
includes a number of novel concepts.  Obtaining performance estimates for an
algorithm is difficult for most real systems especially so for
high--performance systems due to the number of performance--enhancing
features included in the architecture.  The simple models presented in this
paper, based on micro--measurements of a few communication operations,
provide  an accurate cost model for barrier synchronization algorithms.

%This encourages us, because it confirms our view that real
%parallel systems can not only be programmed, but can also be understood and
%analysed.
% but can also provide a fertile playing ground (training ground, 
% proving ground?) for theoreticians. 

%\section*{Acknowledgments}

\newpage
\bibliography{paper}

\newpage
\appendix 

\section{Ring--based barrier algorithm}
\label{appendix-rbalg}
\begin{algo}

{%\tiny
%\noindent{\bf ALGORITHM RB\_SYNCH}
{\bf Anonymous Destination Message Passing Ring Barrier}

{\em barrier(barrier\_name, count)}

{\small
{\em barrier\_name.reached} and {\em barrier\_name.class\_i} ($i = 0, \ldots,
\log$({\em count})) are identifiers generated uniquely from {\em barrier\_name}. 
}
\begin{verse}
 $i = 0$; class $= \log_2 id$;\hfill /$*$ Phase 1 $*$/\\
 mask\_set $=$ {\em \{barrier\_name.reached}, {\em barrier\_name.class\_i} ($i
= 0, \ldots, \log$ (count))\} \\
 {\bf selective\_send} ({\em barrier\_name.reached}, id, $0$); \\
 {\bf do} \\
 \hspace*{1cm}	{\bf selective\_receive}(mask\_set, name\_rec, id\_rec, count\_rec);\\
 \hspace*{1cm}	{\bf if}\ \ (name\_rec {\bf $==$} barrier\_name.class\_i)\\
 \hspace*{2cm}		{\bf break};\\
 \hspace*{1cm}	$i$ {\bf $+=$} count\_rec;\\
 \hspace*{1cm}	{\bf if}\ \ (id\_rec {\bf $<=$} id)\\
 \hspace*{2cm}		{\bf if}\ \ (id\_rec {\bf $<$} id)\\
 \hspace*{3cm}		 	i {\bf $++$};\\
 \hspace*{2cm}	 	{\bf else} \\
 \hspace*{3cm}			{\bf if}\ \ ((i {\bf $==$} {\em count}
						$-$ $1$) {\bf and} (id\_rec {\bf ==}
								id))\\
 \hspace*{4cm}		 		{\bf break}; \\
 \hspace*{3cm}			{\bf else} \\
 \hspace*{4cm}			 	{\bf selective\_send} 
						({\em barrier\_name.reached}, 
							rec\_id, 0);\\
 \hspace*{1cm}	{\bf if}\ \ (id\_rec {\bf $>$} id)\\
 \hspace*{2cm}	 	{\bf selective\_send} ({\em barrier\_name.reached}, 
							rec\_id, $i$);\\
 {\bf until}  ($0$);\\
 mask\_set = mask\_set / {\em \{barrier\_name.reached\}};\hfill /$*$ Phase 2 $*$/\\
 {\bf if}\ \ (i {\bf ==} count $-$ $1$)\hfill /$*$ barrier complete $*$/\\
 \hspace*{1cm}	{\bf for} ($i = \log N, i > 0, i--$)\\
 \hspace*{2cm}		{\bf selective\_send} ({\em barrier\_name.class\_i},
					id, $0$);\\
 \hspace*{1cm}	{\bf while} (name\_rec != {\em barrier\_name.class\_0})\\
 \hspace*{2cm}		{\bf selective\_receive}(mask\_set, header\_rec, id\_rec, count\_rec);\\
 {\bf else}\\
 \hspace*{1cm}	{\bf for} ($i = class, i > 0, i--$)\\
 \hspace*{2cm}		{\bf selective\_send} ({\em barrier\_name.class\_i},
					id, $0$);\\
 \hspace*{1cm}	{\bf while} (name\_rec != {\em barrier\_name.class\_0})\\
 \hspace*{2cm}	{\bf selective\_receive} ({\em barrier\_name.class\_i},
					id\_rec, count\_rec);\\
\end{verse}
}
\label{algo-ring}
\end{algo}

\section{Performance analysis proofs}
\label{appendix-analysis}
\subsection*{Numbering scheme and proof of Lemma \ref{lemm-phase1}}
Before actually giving the proof to Lemma \ref{lemm-phase1} we first show how
to analyze the number of rounds exactly (see Lemma \ref{lemm-rounds}) by
using the notion of an interval graph G\_INT (see Definition
\ref{def-inter}). Then we use this information to define the numbering
scheme NUM before we proof Lemma \ref{lemm-phase1}. 

\bigskip
We introduce the following interval graph G\_INT which captures
all conflicting operations.
\begin{defi}[G\_INT]
\label{def-inter}
Define an interval graph G\_INT of a sequence of $k$ numbers $n_1,
\ldots, n_k$ to be the graph with the following nodes and edges: 
\begin{description}
\item [nodes:] (type (a) \{$[i,j]$\} if $n_i < n_j$ and $\not\exists k$:$ i < k <
j \wedge n_i < n_k$
 and (type (b)) \{$[i,j]$\} if $n_i > n_j$ and $\not\exists k$:$ i < k <
j \wedge n_k > n_j$.
\item [edges:] $([i,j], [k, l])$ if the two intervals $[i,j]$ and $[k,
		l]$ intersect.
\end{description}
\end{defi}
This definition can easily extended to circular sequences by allowing the $<$
and $>$ relations to ``lap around''. Note that G\_INT is actually a tree,
because if two intervals $[i,j]$ and $[k, l]$ intersect then by definition $i
< k$ and $l < j$. 

Looking at the interval graph G\_INT of the circular sequence of the
identifiers (id's) of the processors participating in a barrier along the
ring, we can interpret the graph the following way: 
\begin{description}
\item [] node (a):
a message from processor $i$ can only be received by processor $j$ if the
id of processor $j$ is the first id larger than the id of processor $i$. 

\item [] node (b):
a message from processor $i$ can only eliminate processor $j$ if the
id of processor $i$ is the first id larger than the id of processor $j$. 

\item [] edge:
before a processor $l$ can be eliminated by the message sent by $k$, or can
destroy the message sent by $k$, it first must finish all operations that 
involve the processors between $l$ and $k$. So if the intervals $[l,k]$ and $[i,k]$
overlap, we cannot execute the associated operations in parallel.
\end{description}

\bigskip

\begin{lemm}
The number of rounds for Phase 1 of a $n$ processor barrier involving
processors $p_1, \ldots, p_n$ in their order in the ring with id's $id_{p_1},
\ldots, id_{p_k}$ is the length of the longest path in the circular interval
graph $G\_INT$. 
\end{lemm}
\vspace{5pt}
\proof Every operation corresponding to a leaf of the interval graph can be done in
one round. All leaf nodes can be handled in parallel in one round, because per definition
the intervals are distinct, and then implies that there will by no conflicts.

By induction we can show that we need $k$ rounds if the length of the longest
path in $G\_INT$ is bounded by $k$.

\QED
\bigskip

Let $[i_1, j_1], \ldots, [i_k, j_k]$ be a path in $G\_INT$.
These intervals have to follow certain rules.
\begin{enumerate}
\item For all intervals $i_l \geq i_{l+1}$ and $j_l \leq j_{l+1}$ at least
	one of the inequalities is strict. 
\item For all intervals of type (a) along the path $[i_{a_1},j_{a_1}],
\ldots [i_{a_k}, j_{a_k}]$ the id of processor $i_{a_k}$ must 
be larger than or equal to the id of processor $i_{a_{k - 1}}$.
\item For all intervals of type (b) along the path $[i_{b_1},j_{b_1}]$,
\ldots $[i_{b_k}, j_{b_k}]$ the id of processor $k_{b_k}$ must 
be larger than or equal to the id of processor $j_{b_{k - 1}}$.
\end{enumerate}

\bigskip

Therefore we can bound the number of rounds in terms of the
longest increasing and decreasing subsequences.
\begin{lemm}\label{lemm-rounds}
Let $id_1, id_2, \ldots, id_N$ be the distinct id's of the $N$ processors. 
Let $inc$ be the length of the longest decreasing subsequence and $dec$ be the
length of the longest decreasing subsequence of the list of id's.
Then the number of rounds of Phase 1 for a $n$ processor barrier $p_1, \ldots p_n$ is
bounded by
\[ \max\{inc + dec, n + 1\}.\]
\end{lemm}
\vspace{5pt}
\proof Because the intervals along a path in $G\_INT$ have to follow the
above rules, the processor id's along each path in $G\_INT$ build an intermixed
increasing and decreasing subsequence. So the longest path in $G\_INT$
cannot be longer than the sum of the longest increasing and decreasing
subsequence of the total list of id's or the number of processors
participating in the barrier (one of the inequalities of condition 1 has to be
strict). 
\QED

\bigskip

Unfortunately the longest decreasing or the longest increasing subsequence of
a list of $N$ numbers is at least $\sqrt{N}$. 

\begin{lemm}
\label{lemm-sqrt}
Every sequence $n^2 + 1$ distinct integers contains either an increasing
subsequence of length $n + 1$ or a decreasing subsequence of length $n + 1$.
\end{lemm}
\vspace{5pt}
\proof Let $a_1, a_2, \ldots, a_{n^2 + 1}$ denote the sequence of integers. Suppose
there is no increasing subsequence of length $n + 1$. Then we can show that there is
a decreasing subsequence of that length. For each $a_k$ let $i_k$ be the
length of the longest increasing subsequence beginning at $a_k$. Since all
$n^2 + 1$ of the $i_k$'s are between $1$ and $n$, some label, say $m$, must be
used at least $n + 1$ times. The $n + 1$ integers $a_k$ for which $i_k = m$
must form a decreasing subsequence as required.
\ \QED

So the best we can hope for is to find a numbering scheme where the longest
subsequences is $O(\sqrt{N})$. But we also like to find a numbering scheme
that for commonly used subset barriers gives us a logarithmic number of
rounds. Choosing the following recursively defined numbering scheme NUM
along the ring allows us to proof Lemma \ref{lemm-phase1}.
Let $j$ be the $j$-th processor along the ring then $\mbox{snake}_i(j)$
is the id of the $j$-th element in a ring with $i$ elements:

\[\mbox{snake}_1(0) = 0\]
\[\mbox{snake}_{n}(i) = \left\{\begin{array}{ll}
	\mbox{snake}_{\frac{n}{2}}(i - \frac{n}{2}) * 2 + 1  & 
					\mbox{\ \ if\ \ } n > \frac{n}{2} \\
	\mbox{snake}_{\frac{n}{2}}(i) * 2  &
					\mbox{\ \ otherwise\ \ }
				\end{array}
			\right. \] 

For an example for this numbering scheme see Figure \ref{num-example}.
\begin{figure}
\[0\;\;8\;\;4\;\;12\;\;2\;\;10\;\;6\;\;14\;\;1\;\;9\;\;5\;\;13\;\;3\;\;11\;\;7\;\;15\]
\caption{An example for the numbering scheme used for the tournament approach.}
\label{num-example}
\end{figure}

\begin{lemm}
\label{lemm-num}
Using the above numbering scheme we need at most $\max\{4 * \sqrt{N}, n\}$
rounds for Phase 1 of a $n$ processor barrier.
\end{lemm}
\vspace{5pt}
\proof Using Lemma \ref{lemm-rounds} we only have to bound the length of the
longest increasing and longest decreasing subsequence in the numbering scheme
NUM. We will now show that 
\[	inc(length(NUM) = 2) = 2 \]
\[	inc(length(NUM) = 4) = 3 \]
\[	inc(length(NUM) \leq 2 * inc(length(NUM)/4)\]
To verify this result for length(NUM) = 2 and 4 is easy. 
For length(NUM) = $k$ let $l_i$ ($r_i$) be the length of the longest
increasing subsequences with elements smaller (greater) than or equal to $i$
in NUM($k/2$). Then the length of the longest increasing sequence in NUM($k$) is 
\[ \max_{i}\;\{\; l_i + r_i\}.\]
Due to the symmetric nature of the sequence this maximum is obtained for $i =
k/2$. 

It is then easy to see that: 
\[inc(length(NUM) = k) \leq 2 * \sqrt{k}\]
\QED

\bigskip

\begin{lemm}
\label{lemm-complexity}
If the subset of processors includes every $(2^k)^{\mbox{th}}$ processors and $inc_{sub}$
($dec_{sub}$) is the longest increasing (decreasing) subsequence between those
processors then the number of rounds for Phase 1 is bounded by   
\[\log N - l + inc_{sup} + inc_{sup}.\]
\end{lemm}
\vspace{5pt}
\proof see \cite{feldmann:tr}
\QED

Lemma \ref{lemm-phase1} follows immediately from Lemma \ref{lemm-num} and
\ref{lemm-complexity}.

\subsection*{Proof of Lemma \ref{lemm-lower}}
Consider a barrier with $n/2$ participating processors $P_1, \ldots, P_{n/2}$ (numbered
in ring order). Processor $P_1$ reaches the barrier first. No other processor
has reached the barrier, so the message which is sent travels
once around the ring. Processor $P_2$ reaches the barrier and sends its
message. It has to travel at least till it reaches processor $P_1$, $N - 1$
wires, etc.\ . If Processor $P_i$ reaches the barrier, its message has to
travel $N - i$ wires. So the total message complexity must be at least
$\frac{7}{8}n^2 - \frac{1}{4}n$.
(For an example of such a situation see Figure \ref{lower-bound}.) 

\QED
\end{document}




