Scattering and Gathering Messages in Networks of Processors.
The operations of scattering and gathering in a network of processors involve one processor of the network (P/sub 0/) communicating with all other processors. In scattering, P/sub 0/ sends distinct messages to P/sub 0/. The authors consider networks that are trees of processors. Algorithms for scattering messages from and gathering messages to the processor that resides at the root of the tree are presented. The algorithms are quite general, in that the messages transmitted can differ arbitrarily in length; quite strong, in that they send messages along noncolliding paths, and hence do not require any buffering or queueing mechanisms in the processors; and quite efficient in that algorithms for scattering in general trees are optimal, the algorithm for gathering in a path is optimal and the algorithms for gathering in general trees are nearly optimal. The algorithms can easily be converted using spanning trees to efficient algorithms for scattering and gathering in networks of arbitrary topologies.
Introduction
1.1 Communication in Parallel Computation
Communication is an essential component of parallel computation. A variety of modes of
communication have been studied within the framework of networks of processors - identical
processing elements (PEs) that communicate by means of an interconnection network. The
most commonly studied modes are the following.
ffl (Partial) permutation routing [1, 3, 10, 13, 17] is a form of communication in which
each PE is both the sender and recipient of (at most) one message.
Broadcasting [8, 12] is a form of communication in which one PE sends one specific
message to all other PEs.
Gossiping (or, all-to-all broadcasting) [7, 16] is a form of communication in which each
PE sends one specific message to all other PEs.
Baumslag and Annexstein [1], Johnsson and Ho [8], and Saad and Schultz [14] (among
others) point out that these popular forms of communication do not exhaust the algorithmically
useful possibilities. Specifically, they add to the menu of communication modes the
operations of scattering and gathering. 1
Scattering (or, one-to-all personalized communication) is a form of communication in
which one PE sends (possibly) distinct messages to all other PEs.
ffl Gathering is a form of communication in which all PEs send (possibly) distinct messages
to one specific PE.
Efficient algorithms for a general version of the operations of scattering and gathering form
the subject matter of the current paper. Specifically, we present efficient algorithms for
scattering from and gathering to the root PE of a general tree-structured network. 2 We
present an optimal algorithm for scattering from the root of a general tree, an optimal
algorithm for gathering to the root of a unary tree (i.e., the end-PE of a path), and a nearly
optimal algorithm for gathering to the root of a general tree. Via the use of spanning trees,
Other important modes have also been studied, including multiscattering [11] and exchange [2], but less
frequently.
2 Henceforth, for brevity: we use the term "tree" for "tree-structured network;" also, we use the term
"network" to denote both a network of processors and its underlying interconnection network; context should
always disambiguate each occurrence of the word.
our (nearly) optimal tree-oriented algorithms become efficient algorithms for scattering and
gathering in networks of arbitrary topology. The generality of our study manifests itself in
three ways.
1. We allow messages to differ in length by arbitrary amounts; indeed, some messages may
be null.
This contrasts with the studies in [1, 4, 8, 14], wherein all messages have the same length.
2. We scatter and gather messages in trees of arbitrary shape and, hence, via the use of
spanning trees, in networks of arbitrary topologies.
This contrasts with the studies in [4, 8, 14, 15], which focus on a small repertoire of networks,
such as rings, meshes, and hypercubes.
3. We transmit messages along noncolliding paths in our networks, hence do not require any
buffering or queuing mechanisms in the PEs.
This contrasts with virtually all other studies of message transmission in networks. One
might be able to rationalize our demand for unbuffered communication in terms of resource
conservation: buffering requires both additional memory (each PE must be prepared to store
the longest message in the system) and time (e.g., for the processing of addresses). However,
our overriding motivation in this study was to understand communication in networks better,
by determining the cost of this strict assumption in terms of the complexity of the problems
of scattering and gathering general messages in general networks.
1.2 The Computing Model
A. Networks of Processors
We study the problems of scattering from and gathering to the root-PE of a synchronous
tree of arbitrary shape. Each network A comprises
convention, we always let P 0 denote the root of the tree, i.e., the PE which is the source of
messages in a scattering operation and the target of messages in a gathering operation.
The PEs of the networks we study have neither message buffers nor queues. Messages
within networks must, therefore, be scheduled so as never to "collide" with one another. For
the operation of scattering, the fact that we scatter within a tree guarantees such avoidance;
for the operation of gathering, this scheduling is a major challenge.
The networks we study use the single-port communication regimen: during each communication
step, a PE can send information to at most one of its immediate neighbors and,
simultaneously, receive information from at most one of its immediate neighbors; the sending
and receiving neighbors may be distinct. We do, however, allow a PE to perform (say,
computations while communicating, as well as to access its local memory. This
regimen is to be contrasted with the multiport communication regimen, in which a PE can
send and receive information from each of its immediate neighbors in one step. In Section 4
we indicate briefly how our results extend to a multiport model.
The networks we study communicate in rounds; i.e., while a scattering (resp., a gathering)
operation is in progress, there is no other communication going on in the network. This
means that the only resource contention we must worry about arises from the many messages
that are being scattered (resp., gathered) in the current operation. This regimen is to be
contrasted with the one studied in [2], wherein the present study of bufferless communication
is generalized to allow each PE to be both the source of and the destination for arbitrarily
many messages at once. As an aside, the study in [2] compensates for the generality of its
communication setting - bufferless PEs passing messages in arbitrary ways - by restricting
attention to simple network topologies, specifically, one- and two-dimensional meshes (i.e.,
rings and toroidal meshes).
Porting to General Networks. Our efficient collision-free algorithms can be transported
easily to networks of arbitrary topology via the use of an "efficient" spanning tree of (the
undirected graph underlying) the network in question, rooted at the singular PE for the
scattering or gathering operation. For the operation of scattering, and for the operation of
gathering under a multiport regimen, one would sensibly choose a breadth-first spanning tree,
in order to ensure that every message travels the shortest possible distance to its destination:
the possibility of large node-degrees in breadth-first trees causes no concern, because in a
scattering operation, a PE is receiving or transmitting at most one message at each step, and
in a multiport gathering operation, a PE can service as many ports as it has at each step. For
the operation of gathering under a single-port regimen, the time required to accommodate
large node-degrees in the tree can dominate the time for single-port gathering: broadcasting
is typically part of the synchronization protocol needed for gathering in multi-successor
networks, and high-degree nodes can slow down single-port broadcasts. (As an extreme
example, compare the times for single-port broadcasting in an n-PE network A in which
every pair of nodes is connected by an edge: (a) using a complete binary spanning tree of
A, versus (b) using a single-level degree-(n \Gamma 1) spanning tree.) Consequently, in this case,
one might seek a spanning tree whose structure approximates that of a minimum broadcast
tree [9].
Remark 1. The framework just outlined may represent only the communication subsystem
of a heterogeneous parallel architecture; for instance, the architecture viewed as a whole may
have PEs of differing powers and sizes, which operate asynchronously except during global
communication operations (such as scattering and gathering).
B. Messages and Message Sequences
Each message M i involved in a scattering or gathering operation is a sequence of some
number L i (perhaps zero) of atomic flits: a flit is the largest unit of information that the
network can transmit between adjacent nodes in one communication step (i.e., in one so-called
time).
A message is treated as an indivisible unit during a scattering or gathering operation, in
the sense that the L flits of a message are never interrupted by flits from other messages.
Initially, the L flits of the message are all in the originating PE; after the message has begun
to travel through the network, its flits are always in contiguous PEs; the lack of buffering
ensures that each flit is in a separate PE once it leaves the originating PE. A consequence
of the indivisibility of messages is that addressing information needs appear only in the first
flit of the message, thereby lessening both the setup time for messages and the aggregate
length devoted to addressing information.
be a sequence of messages (to be scattered or gathered).
Let
denote, in increasing order, the subsequence of message indices whose messages are nonnull,
i.e., for which L i j
C. The Scattering and Gathering Problems
In a scattering operation, the root-PE P 0 has a message M i of length L i to send to each
In a gathering operation, each PE P i , where i ? 0, has a message M i of
length L i destined for PE P 0 . (For both operations, some messages M i may be null, so that
We perform these operations in trees of arbitrary shapes, subject to the following
constraints.
ffl Once a message has been dispatched by its originating PE, it encounters no interruption
until it is received by its destination PE. In particular,
- each intermediate PE must relay the message with no queuing or buffering;
- messages are treated as indivisible units (in the sense descibed earlier).
ffl For each i ? 0, message M i will be routed along the unique path ae i that connects PE
in the tree. We let ffi(i) denote the length of path ae i , i.e., the distance
that message M i must travel.
D. Problem Complexity
We measure the complexity of a scattering or gathering operation in terms of the time
for delivering all relevant messages. Focussing on a fixed but arbitrary message sequence
time is formalized as follows.
The Time for Scattering. A schedule for scattering message sequence M is a permutation
oe (for "scattering-schedule") of the index-sequence
function
The intended interpretation is that PE P 0 sends out message M oe(1) , then message M oe(2) ,
then M oe(3) , and so on, in that order, in a steady stream, with no intervening gaps. Thus,
under schedule oe, given index i with L i 6= 0, PE P 0 begins transmitting message M i at
dispatch time
(Note the effect of the single-port regimen.) Message M i arrives at its destination, PE P i ,
at arrival time
ff oe
The time for scattering message sequence M under scattering-schedule oe is the time it takes
for every flit of M to reach its final destination; symbolically,
fff oe (i)g: (3)
Equation (3) implies the following simple result, which delimits the difference between the
best and worst scattering-schedules. The proof is left to the reader.
Proposition 1 Let oe be a scattering-schedule for message sequence M. Assuming that
message M i of M, for 1 - i - n, has length L i , the time for oe satifies the following bounds:
fffi(i)g:
The Time for Gathering. A schedule for gathering message sequence M is a sequence of
integers
(for "gathering-schedule"), where g. The intended interpretation is
that each - fl (i) (where i 2 N(M)) is the dispatch time for message M i , i.e., the time when
. The last flit of message M i is received by PE P 0 at arrival
time
ff
The time for gathering message sequence M under gathering-schedule fl is the time it takes
for every flit of M to reach PE
The Challenges. Note that neither the time for scattering, T scat , nor the time for gathering,
gath , allows for any delay of messages at nodes other than the originating node. This means
that our message-scheduling algorithms cannot rely on - so the network need not provide -
any mechanism for buffering or queuing messages in PEs. This lack of buffering provides an
additional challenge in scheduling the gathering operation, which is lacking in the scattering
operation. Namely, the scheduling algorithm must provide - in a distributed manner - for
the dispatching of messages in the network so that messages never collide on their paths to
Remark 2. Our timing model is somewhat simpler than that of some of the earlier cited
sources. Specifically, we charge L time units to transmit a message containing L flits; some
sources (such as [4]) would charge a message setup time of fi time units, plus a per-flit
transmission time of - time units for this message, for a total cost of fi +L- time units. This
change of model would not affect our analyses in a material way.
Remark 3. As suggested earlier, our algorithms for scattering and gathering in arbitrary
networks employ spanning trees that are fixed, independent of the message sequence M. For
many networks, there exists no single spanning tree that is simultaneously optimal for the
single-port regimen and for all message sequences, especially because messages can be null.
This means that our algorithms for general networks will often be suboptimal.
1.3 Related Work
Saad and Schultz [14] define the operations of scattering and gathering in full generality
but present algorithms only for a specific repertoire of network topologies and for the case
of equal-length messages. Fraigniaud et al. [4] prove the optimality of the Saad-Schultz
algorithm for scattering on a unidirectional ring of processors. Stout and Wagar [15] and
Johnsson and Ho [8] present optimal algorithms for scattering equal-length messages on
a hypercube, using both the single-port and multiport communication regimens. Li [11]
considers performing several scattering operations at once on a reconfigurable network of
processors. Bhatt et al. [2] study the most general type of communication, wherein each PE
has a distinct message for each other PE, in bufferless rings and toroidal networks. All of
these references, save the last, assess time transmitting an L-flit message.
2 Scattering on Networks of Processors
Say that scattering-schedule oe is optimal for message sequence M on a given tree if on that
tree,
for any other scattering-schedule oe 0 for M.
It is shown in [4] that the unique optimal scattering-schedule for equal-length messages on
a unidirectional ring is given by the permutation by sending out messages
according to a farthest-destination-first (FDF) regimen - one in which nonnull messages are
dispatched in decreasing order of the distances to their destinations. We now prove that the
optimality of FDF schedules persists when the lengths of the scattered messages are general
and when the scattering is done from the root-PE of an arbitrary tree. Specifically, we show
that, within this setting, for every message sequence M, every FDF scattering-schedule is
optimal for M (although there may be optimal non-FDF schedules also). It is consistent
with intuition that FDF scattering-schedules need no longer be the unique optimal ones
when one considers messages of arbitrary lengths, because a single enormous message could
so dominate the message transmission time as to mask the order of a collection of small
messages sent out right after it. Since the optimality of all FDF schedules ensures the
optimality of a large family of scattering algorithms, we present the following theorem in
lieu of a specific optimal algorithm.
Theorem 1 Every FDF scattering-schedule for scattering from the root-PE of an arbitrary
tree is optimal.
Proof. Let the tree T with root-PE P 0 be fixed.
The Theorem makes two claims, which we treat in turn. First, we prove that every optimal
scattering-schedule for a given message sequence can be replaced by an FDF scattering-
schedule for the sequence with no increase in scattering time (so the FDF schedule is also
optimal). Second, we prove that every FDF schedule for a message sequence is optimal,
i.e., that messages destined for equidistant PEs can be dispatched in any order. The reader
should note the crucial role of our communicating on a tree in what follows.
1 For every message sequence M and every scattering-schedule oe for M, there is
an FDF scattering-schedule oe 0 for M with
Moral. Every message sequence has an optimal FDF scattering-schedule.
asserts that one can never decrease the scattering time of a schedule by dispatching
a nonnull message that is destined for a nearby PE before a nonnull message that
is destined for a more distant PE. This is not surprising, as one hopes to use pipelining to
make progress in sending the nearby message while the distant message is in transit.
Proof of Claim. Assume, for contradiction, that there is a message sequence
such that no optimal scattering-schedule for M observes the FDF reg-
imen. Let oe 1 be any optimal scattering-schedule for M. Because oe 1 does not observe the
FDF regimen, there must exist PE indices i and j, both in N(M), such that:
oe
Let oe 2 be the scattering-schedule for M obtained from oe 1 by interchanging oe \Gamma1
i.e.,
We claim that
By equation (3), inequality (4) will follow from the inequality
(j)g;
we establish this inequality by analyzing the dispatch and arrival times of messages under
schedules oe 1 and oe 2 . We begin by noting that equation (1) implies the following relations
among the dispatch times under schedules oe 1 and oe 2 . (All indices referred to are associated
with nonnull messages.)
otherwise.
(Note that - oe 1
therefore, we infer the following
relations among the arrival times under schedules oe 1 and oe 2 .
while ff oe 2
(k) for all k 62 fi; jg. (These last equations on ff oe 1
and ff oe 2
hold because
we route messages within a tree.) We can now deduce that
(j)g:
It follows from this chain of reasoning that T scat (oe strict
inequality whenever message M i is the last message to arrive at its destination under schedule
oe 1 . Now, if scattering-schedule oe 2 observes the FDF regimen, then this inequality already
contradicts the assumption that no FDF scattering-schedule is optimal for M. If scattering-
schedule oe 2 does not observe the FDF regimen, then it is "one transposition closer" to
observing the regimen than is schedule oe 1 . In particular, we can iterate the operation of
transposing transmission times that violate the FDF regimen a finite number of times (in
no more than n(n \Gamma 1)=2 times) to arrive at a scattering-schedule oe that does observe
the FDF regimen and that has scattering time no greater than that of schedule oe 1 , thus
contradicting the assumption that no FDF scattering-schedule is optimal for M. 2-ClaimClaim 2 All FDF scattering-schedules take the same time.
Moral. Every scattering-schedule that observes the FDF regimen is optimal.
Proof of Claim. Say that the scattering-schedule oe observes the FDF regimen. The
only way to alter oe without violating the regimen is to rearrange the transmission order of
messages destined for equidistant PEs. We claim that such rearrangement does not alter the
time for the schedule and, hence, must preserve optimality. To wit, equations (1) and (2)
imply the following. If messages M j 1
are all destined for PEs at distance \Delta
from PE P 0 , and if the earliest dispatch time of any of these messages is - , then the latest
arrival time of any of these messages is
independent of the specific order of dispatching the messages. 2-Claim 2
Note that Claim 2 verifies that optimal scattering-schedules for a message sequence M
do not depend on the lengths of the messages in M.
The Theorem follows. 2
Let us focus momentarily on the simplest possible tree, namely, a path having PE P 0
as its root. For notational convenience, say that in this tree: P i+1 is the child of P i , for
is the parent of P i , for is the (sole) leaf. When one is
scattering messages from P 0 in such a tree, the proof of Theorem 1 can be visualized easily.
As one can see in Figure 1, for instance, in this case, each message dispatched by PE P 0
sweeps out a parallelogram in the space-time domain. (The parallelogram associated with
the length-L i message M i destined for PE P i has length-L i sides parallel to the time axis,
corresponding to the path traversed by the L i flits of message M i , and length-i sides at a
45-degree angle to the time axis, corresponding to the progress of the flits along the line of
PEs.) Constructing examples of scattering operations on paths, visualized via space-time
parallelograms, will convince the reader that often a portion of the upper slanted side of the
space-time parallelogram of one message can be "hidden in the shadow" of the space-time
parallelogram of an earlier dispatched message; this corresponds to pipelining the use of the
intermediate PEs to decrease the overall time of the scatter operation. Constructing analogs
of the competing dispatch orders of Figures 1(a) and 1(b) will illustrate what Theorem 1
verifies, namely, that more hiding occurs when the parallelogram of a message destined for
a more distant PE "provides shadow for" the parallelogram of a message destined for a
nearby PE than when the dispatch times of the two messages are reversed. In Figure 1, we
make message M 4 longer than message M 5 to emphasize the independence of the "hiding"
phenomenon from the lengths of messages.
3 Gathering on Networks of Processors
Say that gathering-schedule fl is optimal for message sequence M on a given tree if, on that
tree,
for any other gathering-schedule fl 0 for M.
In an ideal world, we would implement the gathering operation by running an FDF scattering
algorithm "backwards;" by reasoning analogous to that in the proof of Theorem 1, an
algorithm that accomplished this would be optimal. Of course, one can not literally run an
FDF scattering algorithm "backwards," because in the scattering operation, PEs other than
are passive, while in the gathering operation, they are active - they must initiate their
message transmissions. To compensate for this fact, any algorithm for a bufferless gathering
operation must precede the transmission of messages by a distributed protocol that schedules
the dispatch times of the messages so that no two collide in transit. A straightforward
synchronization-like protocol suffices to accomplish this scheduling. We begin this section
with a simple version of this protocol, called shoulder tapping (Section 3.1), that implements
the operation of gathering messages to one end of a path by interlacing the synchronization
and scheduling activities. Although shoulder tapping yields an optimal algorithm for gathering
on a path, it is too simple to work on general tree structures. Since altering shoulder
tapping to operate on general trees leads to a cumbersome algorithm, we opt instead for a
version of the protocol which decouples the synchronization and scheduling activities. The
resulting protocol, called transmission certification (Section 3.2), is readily adapted to general
tree structures, but only at the cost of added time for separate synchronization and
scheduling activities.
It is worth stressing here that gathering must in general be more time consuming than
scattering, because of the need for a scheduling protocol that precedes message transmission.
In particular, in a gathering operation, a PE cannot safely begin transmitting its message
until "told to," for fear of interfering with the transit of another PE's message.
3.1 Shoulder Tapping: a Solution for Paths of Processors
The shoulder-tapping protocol we present now exploits the single-child structure of a path
in an essential way; it is this feature that precludes its graceful extension to trees of more
complicated structure. The algorithm that implements shoulder tapping seeks, for a message
sequence
which minimizes each dispatch time - fl (i j ) subject to the requirement
that messages never collide, and subject to the inequalities
Inequalities (5) must hold for any distributed gathering algorithm on a path; they reflect the
following facts, which hold for all PE indices, not just those in N(M).
ffl Each PE P i (save, of course, must receive a wakeup call telling it when to begin
transmitting its message M i (assuming that the message is nonnull).
ffl The sequence of wakeup calls must be initiated by P 0 (since, in general, it is the best
arbiter of when it is ready to receive the message sequence), hence must take at least
i steps to reach P i .
ffl The single-port communication regimen does not allow P i to overlap dispatching its
message (toward P 0 ) and transmitting a wakeup call to P i+1 .
The algorithm operates as follows. Each PE remains dormant until its
shoulder is tapped by PE P i\Gamma1 with a wakeup call: the call is a (one-flit) message consisting
of the order
where s i is a positive integer. Assume that P i receives its wakeup call at time t i . It responds
by serially entering the following operational phases, which embody Algorithm Shoulder-
Tap.
Algorithm Shoulder-Tap:
Phase 0: P 0 transmits to P 1 the wakeup call
Phase 1: If phase is ignored; else,
receiving its wakeup call), P i transmits
to P i+1 a wakeup call of the form
where the positive integer s i+1 is computed using the following time-line. (Note the
effect of the single-port communication regimen.)
time receives its wakeup call (from P
time receives its wakeup call from P i .
time receives the first flit of M i from P i (when
time receives the last (i.e., the L i th) flit of M i from
hence, at this time, P i is ready to relay (passively) any messages it receives from
Since P i+1 receives its wakeup call at time t must be positive, P i
sets the value of s i+1 as follows:
Phase 2: If L this phase is ignored; else,
to
one flit at a time.
Phase 3: From time begins to relay (passively) any messages
it receives from PEs P j for j ? i.Two small instances of Algorithm Shoulder-Tap appear in Figures 2 and 3. Figure 2
attempts to depict a "typical" message sequence; Figure 3 depicts a somewhat pathological
sequence which illustrates that the dispatch times of messages under the algorithm may not
be monotonic in the indices of the dispatching PEs.
We show now that Algorithm Shoulder-Tap produces an optimal gathering-schedule
for paths.
Theorem 2 Algorithm Shoulder-Tap is an optimal algorithm for gathering on a path.
Proof. Let us consider the behavior of Algorithm Shoulder-Tap on an arbitrary message
sequence
Note first that when all of the messages in sequence M are nonnull, Algorithm Shoulder-
Tap delivers the messages to P 0 in a gap-free fashion. When takes
place from time-step 2 to time-step 1 takes place
from time-step 3 to time-step 2
. In this case, the Algorithm can clearly not be
improved, since the small additive constant in excess of the message-stream length is needed
for synchronization, as in inequality 5.
In order to establish the optimality of Algorithm Shoulder-Tap when some of the
messages in sequence M are null, we introduce the following analogue of FDF scattering-
schedules.
We have already remarked that the ideal gathering-schedule would be one that ran an
FDF scattering-schedule "backwards." From the perspective of PE P 0 , as recipient of the
messages, such a schedule would have messages that originate at nearby PEs arrive before
messages that originate at more distant PEs, i.e., would observe a nearest-received-first
(NRF) regimen. The formal verification that there is an optimal NRF gathering-schedule
satisfying inequality (5) for every message sequence follows the lines of the analogous result
for FDF scattering-schedules (Theorem 1), hence is left to the reader. In common with
Theorem 1, this verification can be visualized geometrically when the underlying tree is a
messages in gathering operations sweep out the same type of parallelograms in the
space-time domain as they do in scattering operations; the main difference is that gathering-
parallelograms slant from the northeast to the southwest, whereas scattering-parallelograms
slant from the northwest to the southeast; cf. Figure 2.
With no loss of generality, we henceforth compare Algorithm Shoulder-Tap only with
gathering-schedules that honor the NRF regimen.
Consider, therefore, an arbitrary NRF gathering-schedule for M,
N(M). For any 2 - j - k, we must have
or else messages M i j
and M i
would either collide or violate the NRF regimen. By
combining inequalities (5) and (6), we obtain:
A straightforward induction establishes that the gathering-schedule produced by Algorithm
Shoulder-Tap satisfies inequality (7) as an equality. It follows that the gathering
time for Algorithm Shoulder-Tap is minimal among algorithms for gathering on a path,
that schedule message deliveries in a distributed fashion, hence obey inequality 5. 2
Generalizing the interlaced synchronization-plus-message passing strategy of Algorithm
Shoulder-Tap to trees whose PEs have multiple children seems to require a rather complicated
protocol: messages must have end-of-message delimiters so that each PE P i can
coordinate the message streams of its children and their descendants. We turn now to an
alternative strategy which accomplishes this coordination in a simpler way, hence extends
gracefully to trees of arbitrary structure.
3.2 Transmission Certification: a Solution for General Trees
We now modify the protocol of Algorithm Shoulder-Tap by decoupling the synchronization
and message passing activities. The resulting Algorithm Transmission-Certification
operates in four phases.
Algorithm Transmission-Certification:
fThe first two phases represent the decoupled synchronization part of the protocol.g
Phase 1: PE P 0 "awakens" all other PEs in the tree by broadcasting a synchronization to-
ken. (This wakeup call lets the PEs know that P 0 is ready to "gather" their messages.)
Phase 2: Each PE P i responds to the synchronization token by sending a (one-flit) transmission
certificate to its parent PE. The certificate indicates how soon P i can initiate
a gap-free transmission of all the messages in the subtree whose root it occupies. The
PEs at the leaves of the tree are the first to send certificates; a nonleaf PE's certificate
is computed using the length of its message, together with the certificates of its
children.
fThe second two phases are reminiscent of Algorithm Shoulder-Tap.g
Phase 3: When P 0 receives its children's certificates, it initiates a wave of transmit-
message orders. Inductively, the orders transmitted by a PE P i to its children schedule
the children's gap-free transmissions: the scheduled dispatch time for each child is
calculated from P i 's own dispatch time, its own message length L i , and the certificates
it received (during Phase 2) from its children.
Phase 4: Finally, the PEs follow the schedule of phase 3, transmitting messages in a gap-free
stream toward P 0 , via their parents.Since P 0 eventually receives the entire set of messages in a gap-free stream (of length
Transmission-Certification is optimal, up to the time required for
the synchronization-and-scheduling protocol. This protocol comprises three phases: two of
the phases (Phases 1 and are essentially broadcasts in the tree; the other (Phase 2) is
essentially a leaf-to-root reverse broadcast, with children's messages being combined into a
single message by each parent. We now describe these phases in detail.
Assume henceforth that each PE P i which is not a leaf in the tree has d i children, denoted
in some arbitrary but fixed order.
Broadcasting and Receiving Messages. Because the single-port communication regimen
allows a PE to communicate with at most two neighbors in a single step (one by sending a
message and one by receiving a message), communications in the various phases of Algorithm
Transmission-Certification must be orchestrated as illustrated in the following scenario.
When PE P i receives a synchronization token "send-certificate" from its parent, it relays
the token in turn to its children, P
. After sending the token to a child, P i
waits to receive that child's transmission certificate before sending the token to the next
child. continues in this fashion, until it has collected transmission certificates from all
children. The reader should note that the Algorithm requires P i to "remember" which
certificate came from which child.
An Overview of Transmission Certificates. During Phase 2 of the Algorithm, each
sends its parent a transmission certificate; this message consists of a pair
of integers is the certified lag time, and n i - 0 is the certified stream
length. The intended interpretation of P i 's transmission certificate is:
c i steps after receiving a transmit-message order, PE P i can start transmitting
toward P 0 a gap-free stream of n i flits, comprising all the messages originating
at PEs in the subtree rooted at P i .
Each PE that is a leaf of the tree can compute its certificate directly from the length of its
message; each nonleaf PE P i computes its certificate from the length of its message, together
with the certificates of its children. (P i needs both the certified lag times and the certified
stream lengths from its children for scheduling purpose, in order to coalesce the children's d i
message streams into a single stream.) When P 0 receives the certificates from its children,
it can proceed to schedule all the transmissions, using transmit-message orders that are
essentially identical to the shoulder taps that characterize Algorithm Shoulder-Tap. The
transmission schedule produced by Algorithm Transmission-Certification differs from
that produced by Algorithm Shoulder-Tap mainly in its avoidance of gaps in message
transmission (such as that observed at Step 8 in Figure 2). We now describe how the
transmission certificates are computed.
Computing Transmission Certificates. Say that PE P i has received the certificates
from its d i children. It uses these certificates, plus the length L i of its message, to compute
its certificate
Length. The computation of P i 's certified stream length n i is straightforward,
since the message stream that P i will transmit is just the concatenation of its message, M i ,
with the message streams of its children; hence,
Lag Time. A PE P i that resides at a leaf of the tree does not have to wait for any
other PE before starting to transmit its message stream - which is just its message M i ;
therefore, it can start transmitting its message stream with no gaps one step after receiving
a transmit-message order, so its certified lag time is just c In contrast, a PE P i
that is not at a leaf of the tree must consider how its message interacts with the message
streams that will come from its children PEs. Specifically, PE P i computes its certified lag
time c i from the certificates c i;1 ; c
of its d i children, via the following reasoning,
which is presented most easily by means of a time-line similar to that used to compute the
wakeup calls in Algorithm Shoulder-Tap. Say that (at some time in the future) P i will
receive the order
transmit in s i steps
at time t. The following actions will ensue.
relay the order to its child P i;j , with an appropriately
modified value s i;j of s i .
as the first stage of transmitting
the message stream from the PEs in the subtree rooted at P i . Note that the
integer s i can be no smaller than d because of the single-port communication
regimen. 3
will begin to relay, without gaps, the message streams sent to it by
its d i children. Note that the integer s i can be no smaller than minfc
because some child of P i must begin its gap-free transmission one step before P i begins
its gap-free relaying. s i may be larger than this lower bound because of the requirement
that message transmission be gap free.
With this time-line in mind, P i computes its certified lag time in four steps, as follows.
1. adopts the preliminary certified lag time c 0
acknowledges the fact that
transmitting its message, M i , until it has dispatched a transmit-message
order to each of its children.
2. P i "adjusts" each of its children's certified lag times, amending the lag time of P i;j , where
acknowledges the fact that P i cannot begin relaying its
children's message streams until it has dispatched a transmit-message order to each of
its children.
3. P i sorts the certified lag times fc i;j of its children, thereby obtaining a
permutation - of the set f1; which orders the children of P i in increasing order of
their certified lag times. (P i will use the permutation - now, in computing its certified lag
time, and later, in computing the transmit-message times for its children.)
4. Finally, P i computes its certified lag time, using a geometrical model. Visualize the
nonnegative x-axis, with the following
ffl X i;0 is a length-L i segment whose left endpoint can be placed anywhere at or to the
right of point c 0
ffl For is a length-n i;j segment whose left endpoint can be placed anywhere
at or to the right of point c 0
3 There is an implicit inductive assumption here that s i
has been assigned a feasible value by P i
's parent.
The intended interpretation is that the x-axis is the time axis, and each line segment represents
the time interval during which the corresponding message stream is being transmitted
by PE P i . Specifically, line segment X i;0 represents the length-L i time interval during which
each other line segment X i;j , for represents the
length-n i;j time interval during which P i relays the message stream it receives from its jth
child P i;j . The restrictions on the placements of the line segments are compatible with this
interpretation: any line segment can be moved to the right, representing a delay in the transmission
time of the corresponding message stream; no line segment can be moved to the left
of its indicated limit (the points c 0
i;k ), for such a move would represent transmitting the
corresponding message stream before the stream is available to it.
now computes its certified lag time by shifting the line segments X i;k along the x-axis
moving segments rightward at will, but never moving any segment X i;k so that its left
endpoint goes to the left of point c 0
i;k - with the goal of combining all d i segments (by
concatenation) into a single line segment of length n i , whose left endpoint is as small, i.e.,
as far to the left, as possible; call this combined line segment X ?
. The left endpoint of
certified lag time c i . Straightforward reasoning allows us to compute c i
explicitly:
Remark 4. (a) Combining the d i +1 line segments into a single line segment X ?
represents
scheduling a gap-free transmission by P i of all messages originating in its subtree.
(b) Placing the line segment X ?
i as far to the left as possible (subject to the constraints of
the points c 0
represents an attempt to schedule P i 's transmission as early as possible.
(c) If we denote by c ?
i;k the left endpoint of line segment X i;k within line segment X ?
the increasing sequence of values of the endpoints c ?
i;k represents a schedule for the gap-free
transmission of the (combined) message streams of P i 's children.
To clarify the connection between moving line segments and scheduling messages, let us
focus on just two segments: for say that line segment X i has length n i and left
constraint c 0
. Say, moreover, that c 0- c 0
. Three cases arise.
1. If c 0
can be positioned in their leftmost legal
positions (namely, c 0
just juxtaposed to form segment X ? .
In this situation, the PEs associated with X 1 and X 2 can both honor their certified lag
times.
2. If c 0
can be positioned in its leftmost possible position (namely,
must be shifted right
positions before being juxtaposed
with segment X 1 in order to form segment X ? . This corresponds to having the PE
associated with time interval X 2 delay its message transmission for
so as not to interfere with the transmission by the PE associated with interval X 1 .
3. If c 0
can be positioned in its leftmost possible position (namely,
must be shifted right c 0\Gamma n 1 positions before being juxtaposed
with segment X 2 in order to form segment X ? . This corresponds to having the PE
associated with time interval X 1 delay its message transmission for c 0\Gamma n 1 time units
so that the final transmission of messages will be free of gaps.
Remark 5. Because line segments start out in their leftmost feasible positions, one can
combine them by moving line segments to the right but never to the left, i.e., by delaying
message streams but never advancing one. This ensures that a single pass over the line
segments, in decreasing order of their indices under the permutation -, suffices to produce
line segment X ?
hence to compute c i .
The Message Scheduling Protocol. After PE P 0 receives a transmission certificate from
its last (i.e., d 0 th) child, it spends the next d 0 steps sending transmit-message orders to
its children. Each order is a one-flit message of the form
after s steps
where the transmission time s is a positive integer; the intended interpretation is that, if a PE
P receives the indicated order at time t, then it begins transmitting its (gap-free) message
stream at time t + s; if P is a nonleaf PE, then it will begin this message transmission
only after it has relayed to its children versions of the order with appropriately modified
times. 4 The issue we must focus on is how a PE (P 0 or any other nonleaf
PE) computes its children's transmission times. This computation can be described more
uniformly if we imagine that P 0 has received the (imaginary) order transmit after 0
steps. Now we can say, uniformly, that nonleaf PE P i receives the order transmit after
steps at time t i , and we can ask, uniformly, how P i computes the transmission times
for its children fP i;j g.
Computing Transmission Times. Say that P i receives its transmission time s i from its
parent at time t i . Earlier, when P i computed its certified lag time c i , it created a tentative
transmission schedule for its children (and itself), which is embodied in the d i +1 start times
g. (Recall that these were computed while constructing the line segment
.) Indeed, c i is just the minimum of these values. The transmission time s i can be viewed
as just an adjustment to this tentative schedule, i.e., as a mandate to adjust the schedule by
When P computed its certified lag time, it included time for relaying orders to its children; hence, we
can safely assume that s has been chosen large enough to allow time for this relaying.
delaying it uniformly by s (equivalently, by shifting X ?
i to the right s
units). Therefore, P i assigns to each of its children P i;j , where 1 - j - d i , the transmission
time s
sends it the order
after s i;j steps .
After dispatching all these orders, P i proceeds to transmit, according to the schedule implicit
in the set fs containing all the messages in its
subtree.
Timing Analysis. The time required by Algorithm Transmission-Certification is divided
into four packets.
1. Broadcasting the synchronization token (Phase 1) and distributing the transmit-
message orders (Phase 3) each takes time essentially equal to the time B for a root-
to-leaf broadcast in the tree.
2. The time C for collecting transmission certificates (Phase 2) is dominated by the
accumulated time for sorting certified lag times at each PE along the leaf-to-root paths
of the tree. This time is estimated as follows. Assign each leaf-PE the weight 0 and
each nonleaf-PE having d children the weight d log 2 d. Assign each root-to-leaf path a
weight that is the sum of the weights of its nodes. Then C is a small multiple of the
maximum weight of a root-to-leaf path.
3. Since message transmission (Phase 4) is gap-free, it requires time
Easily, any gathering algorithm must take time at least max(B;M ); in the worst case, this
bound increases to B+M . To wit, synchronization must take at least B steps, and message
transmission must take at least M steps, yielding the universal lower bound; if there is only
one message in the sequence, and that message resides at a PE at maximum distance from
these activities do not overlap. Summarizing this cost assessment, we arrive at the
following reckoning.
Theorem 3 The time for gathering on a tree using Algorithm Transmission-Certification
is at most 2B . The time for gathering on a tree using any algorithm is at least
max(B;M); in the worst case, this lower bound increases to time B +M .

Figure

4 illustrates the gathering operation of Figure 2 performed using transmission
certificates, rather than shoulder tapping.
As

Figures

2 and 4 indicate, gathering on an n-node ring via transmission certificates is
materially slower (by roughly 2n steps) than gathering on the path via shoulder-tapping, the
extra time being accounted for by the explicit synchronization protocol. Although a portion
of the synchronization time is recovered by the elimination of gaps in the transmission of the
message stream, one would normally choose to use shoulder-taps rather than transmission
certificates when gathering on a path.
4 Algorithms for a Multiport Model
We discuss only briefly how one can extend the gathering algorithms of Section 3.2 to a
multiport communication regimen. Roughly speaking, one can proceed at two levels.
Parallelizing Synchronization. Most simply, in a network with a multiport communication
capability, one can parallelize the three tasks in our algorithm that are dedicated to
synchronization.
Parallelizing the broadcast of the synchronization token requires no modification of the
algorithm.
In contrast, parallelizing the distribution of the transmit-message orders may be
tricky. Specifically, each such order has a transmission time associated with it, and each
child of a given PE must receive a unique such time in order to insure collision-free message
transmission in the absence of message buffers. It is not clear that one can save much time
by parallelizing the transmission of the transmit-message orders if the computation of
the associated transmission times must be sequential.
Finally, parallelizing the computation of certificates is straightforward and, in fact, simplifies
the algorithm by obviating the protocol whereby a PE orchestrates the receipt of
certificates from its children.
Parallelizing Message Transmission. We discuss this topic in the context of scattering
and gathering in arbitrary networks, via the use of spanning trees. There are two compelling
techniques for parallelizing the transmission of messages in a network with a multiport
communication capability. Both techniques involve "covering" the network with trees which
then cooperate in transmitting the messages, using versions of the algorithms presented in
previous sections.
The first technique advocates "covering" the network with mutually edge-disjoint trees
rooted at PE P 0 , which collectively, though not necessarily individually, span the host net-work

Figure

5 depicts two such "coverings:" in Figure 5(a) two trees jointly span the
4 \Theta 4 mesh; in Figure 5(b) two trees each span the 4 \Theta 4 toroidal mesh (i.e., the mesh with
"wraparound" edges). These disjoint trees are then used just as described in previous sec-
tions. The only substantive change in the framework we have been discussing is the role
that PEs play relative to each tree, if they belong to more than one. Most simply, each PE
will be preallocated to one tree in which it will participate actively; the PE will act solely
as a conduit in all other trees. Details can readily be filled in. One attractive feature of
this technique is the availability of research in "covering" certain networks with edge-disjoint
trees (though the requirement that P 0 be the root of all the trees seems to complicate the
problem materially); for instance, one readily shows that the mesh and de Bruijn networks
can be so "covered," as can the hypercube [5, 6].
The second technique modifies the first by dropping the requirement that the "covering"
trees be mutually edge-disjoint. Adapting our algorithms to such a setting may be quite
challenging, as one must schedule the traffic on the shared edges.



--R

A unified approach to global permutation routing on parallel networks.


Complexity of scattering on a ring of processors.
Full Utilization of Communication Resources.
Routing multiple paths in hypercubes.
Optimal algorithms for dissemination of information in some interconnection networks.
Optimal broadcasting and personalized communication in hypercubes.
Approximation algorithms for minimum time broad- cast

Multiscattering on a reconfigurable network of processors.
Data broadcasting in SIMD computers.

Data communication in parallel architectures.
Intensive hypercube communication

"typical"
--TR
Deadlock-free message routing in multiprocessor interconnection networks
Multi-packet-routing on mesh connected arrays
Optimum Broadcasting and Personalized Communication in Hypercubes
All-to-All Broadcast by Flooding in Communications Networks
Intensive hypercube communication. Prearranged communication in link-bound machines
Optimum algorithms for dissemination of information in some interconnection networks
Fully-adaptive minimal deadlock-free packet routing in hypercubes, meshes, and other networks
Full utilization of communication resources
Approximation Algorithms for Minimum Time Broadcast
On Bufferless Routing of Variable-length Message in Leveled Networks (Extended Abstract)
Universal schemes for parallel communication

--CTR
Kevin H. Liu, Performance evaluation of processor allocation algorithms for parallel query execution, Proceedings of the 1997 ACM symposium on Applied computing, p.393-402, April 1997, San Jose, California, United States
Leandros Tassiulas , Jinoo Joung, Performance measures and scheduling policies in ring networks, IEEE/ACM Transactions on Networking (TON), v.3 n.5, p.576-584, Oct. 1995
Sandeep N. Bhatt , Gianfranco Bilardi , Geppino Pucci , Abhiram Ranade , Arnold L. Rosenberg , Eric J. Schwabe, On Bufferless Routing of Variable Length Messages in Leveled Networks, IEEE Transactions on Computers, v.45 n.6, p.714-729, June 1996
Weizhen Mao , Jie Chen , William III Watson, One-to-all personalized communication in torus networks, Proceedings of the 25th conference on Proceedings of the 25th IASTED International Multi-Conference: parallel and distributed computing and networks, p.291-296, February 13-15, 2007, Innsbruck, Austria
multiprocessor interconnection networks;queueing mechanisms;trees of processors;message scattering;distributed processing;networks of processors;buffering;messages gathering;noncolliding paths;scheduling;spanning trees