Gossiping on Meshes and Tori.
AbstractAlgorithms for performing gossiping on one- and higher-dimensional meshes are presented. As a routing model, the practically important wormhole routing is assumed. We especially focus on the trade-off between the start-up time and the transmission time. For one-dimensional arrays and rings, we give a novel lower bound and an asymptotically optimal gossiping algorithm for all choices of the parameters involved. For two-dimensional meshes and tori, a simple algorithm composed of one-dimensional phases is presented. For an important range of packet and mesh sizes, it gives clear improvements upon previously developed algorithms. The algorithm is analyzed theoretically and the achieved improvements are also convincingly demonstrated by simulations, as well as an implementation on the Paragon. On the Paragon, our algorithm even outperforms the gossiping routine provided in the NX message-passing library. For higher-dimensional meshes, we give algorithms which are based on an interesting generalization of the notion of a diagonal. These algorithms are analyzed theoretically, as well as by simulation.
Introduction
Meshes and Tori. One of the most thoroughly investigated interconnection schemes for parallel
computers is the n\Thetan mesh, in which n 2 processing units (PUs) are connected by a two-dimensional grid of
communication links. A torus is a mesh with wrap-around connections. Their immediate generalizations
are d-dimensional n\Theta\Delta \Delta \Delta\Thetan meshes and tori. Although these networks have a large diameter in comparison
to the various hypercubic networks, they are nevertheless of great importance due to their simple structure
and efficient layout. Numerous parallel machines with mesh and torus topologies have been built, and
various algorithmic problems have been analyzed on theoretical models of the mesh.
Wormhole Routing. Traditionally, algorithms for the mesh have been developed using a store-and-
forward routing model in which a packet is treated as an atomic unit that can be transferred between
two adjacent PUs in unit time. However, many modern parallel architectures employ wormhole routing
instead. Briefly, in this model a packet consists of a number of atomic data units called flits which are
routed through the network in a pipelined fashion. As long as there is no congestion in the network, the
time to send a packet consisting of l flits between two arbitrary PUs is well approximated by t s +l \Delta t l , where
t s is the start-up time (the time needed to initiate the message transmission) and t l is the flit-transfer
time (the time required for actually transferring the data). Usually, t s ?? t l , so that it is important to
minimize the number of startups when the packet size is small, whereas it is important to minimize the
time when the packet size is large. These two goals may conflict, and then trade-offs must
be made.
Gossiping. Collective communication operations occur frequently in parallel computing, and their performance
often determines the overall running time of an application. One of the fundamental communication
problems is gossiping (also called total exchange or all-to-all non-personalized communication).
Gossiping is the problem in which every PU wants to send the same packet to every other PU. Said
differently, initially each of the N PUs contains an amount of data of size L, and finally all PUs know
the complete data of size N \Delta L. This is a very communication intensive operation. On a d-dimensional
store-and-forward mesh it can be performed trivially in N=d steps, but for wormhole-routed meshes it is
less obvious how to organize the routing so that the total cost is minimal.
Gossiping appears as a subroutine in many important problems in parallel computation. We just
mention two of them. If M keys need to be sorted on N PUs (M ?? N ), then a good approach is to
select a set of m splitters [14, 13, 7] which must be made available in all PUs. This means that we have to
perform a gossip in which every PU contributes m=N keys. In this case, the cost of gossiping (provided
it is performed efficiently) will not dominate the overall sorting time when the input size is large, because
the splitters constitute only a small fraction of the data. A second application of gossiping appears in
algorithms for solving ordinary differential equations using parallel block predictor-corrector methods
[15]. In each application of the method, block point computations corresponding to the prediction are
carried out by different PUs, and these values are needed by all PUs for the correction phase, requiring
a gossiping of the data.
Previous Work. A substantial amount of research has been performed on finding efficient algorithms
for collective communication operations on wormhole-routed systems (see, e.g., [1, 4, 12, 3, 17]). However,
most papers either deal with very small packets or with very large packets. Both these extreme cases
require algorithms optimizing only one parameter.
If the packets are small, then the number of start-ups should be minimized. Peters and Syska [12]
considered the broadcasting problem on two-dimensional tori and showed that it can be performed in
the optimal 2 \Delta dlog 5 ne steps. Their ideas have been generalized to three-dimensional tori in [3]. The
algorithms described in these papers can be adapted for the gossiping problem by first concentrating all
data into one PU and then performing a broadcast. However, such an approach leads to a prohibitively
large transmission time. Another drawback of both approaches is that it is assumed that the routing
paths may be selected by the algorithm. The algorithms presented in this paper can also be used if the
network only supports dimension-ordered routing.
If the packets are large, a store-and-forward approach yields the best results. As mentioned before,
on a d-dimensional n \Theta mesh it can be performed trivially in n d =d packet steps. Gossiping in a
store-and-forward hypercube model was studied in [8].
There are many other papers on collective communication operations on wormhole-routed meshes and
tori. Although these papers do not deal with the same problem, there are some similarities. For exam-
ple, Sundar et al. [16] propose a hybrid algorithm for performing personalized all-to-all communication
(complete exchange) on wormhole-routed meshes. Briefly, they employ a logarithmic step algorithm until
the packet size becomes large, at which point they switch to a linear step algorithm.
Our Results. In this paper we focus on the trade-off between the start-up time and the transmission
time. This is useful, because there is a large range of mesh sizes, packet sizes and start-up costs, in which
neither of the two contributions is negligible. We would like to emphasize that we are not proposing a
hybrid algorithm that simply uses the fastest of the gather/broadcast approach and the store-and-forward
approach. In an intermediate range of packet sizes, our algorithm is asymptotically better than the best
of the two extreme approaches.
A non-trivial lower bound shows that our algorithms are close to optimal for all possible values of
the parameters involved. For the efficiency of the two-dimensional algorithm, it is essential that data
is concentrated in PUs that lie on diagonals. For higher dimensional meshes we give an interesting
generalization of the notion of a diagonal, which may be of independent interest. We remark that Tseng
et al. [17] also used diagonals in their complete exchange algorithm. However, the generalization of a
diagonal given there for three-dimensional tori is rather straightforward. Hyperspaces are used that when
projected give back a diagonal in two-dimensional space. We generalize the diagonal in a different way,
that gives better performance, and which allows to formulate a generic algorithm that works for arbitrary
dimensions (not only dimension three) without problem.
We also compare the value of several strategies by substituting parameters in the formulas for their
time consumptions. Furthermore, our theoretical results for two-dimensional meshes are completed with
measurements of an implementation on the Intel Paragon. The assumed and the real hardware model
do not completely coincide, but still we believe that these measurements support our claims in most
important points.
described. Thereupon, in Section 3, we present several lower bounds for the gossiping problem. The
in Section 5 and Section 6, we extend the algorithm to two- and higher-dimensional meshes and tori.
Finally, in Section 7, experimental results gathered on the Intel Paragon are presented.
2 Model of Computation
A d-dimensional mesh consists of processing units (PUs) laid out in a d-dimensional grid of side
length n. Every PU is connected to each of its (at immediate neighbors by a bidirectional
communication link. A torus is a mesh with wrap-around connections. We concentrate on the communication
complexity, and assume that a PU can perform an unbounded amount of internal computation in a
step. It is also assumed that a PU can simultaneously send and receive data over all its connections. This
is sometimes called the full-port or all-port model. With minor modifications, the presented algorithms
can also be implemented on one-port architectures.
For the communication we assume the much considered wormhole routing model (see [6, 11, 5] for
some recent surveys). In this model a packet consists of a number of atomic data units called flits.
During routing the header flit governs the route of the packet and the other flits follow it in a pipelined
fashion. Initially all flits reside in the source PU and finally all flits should reside in the destination PU.
At intermediate stages, all flits of a packet reside in adjacent PUs. The packets should be 'expanded'
and 'contracted' only once. That is, two or more flits should reside in the same PU only at the source
and destination PU. Wormhole routing is likely to produce deadlock unless special care is taken.
The reasons to consider wormhole routing instead of the more traditional store-and-forward routing
are of a practical nature. On modern MIMD computers (such as the Intel Paragon and the Cray T3D), the
time to initiate a packet transmission is considerably larger than the time needed to traverse a connection.
Wormhole routing has been developed in response to this fact. The time for sending a packet consisting
of l flits over a distance of d connections is given by
We refer to t s as the start-up time, t d as the hop time, and t l as the flit-transfer time.
Equation (1) is only correct if there is no link contention (in other words, as long as the paths of the
packets do not overlap). If paths of various packets overlap, then the transfer time increases. All our
algorithms are overlap-free.
3 Lower Bounds
We start with a trivial but general lower bound. Thereupon, we give a more detailed analysis, proving a
stronger lower bound for special cases.
Lemma 1 In any network with N PUs, degree \Delta and diameter D, the time T con (N; \Delta; D) needed to
concentrate all information in a single PU satisfies:
Proof: The terms are motivated as follows: N \Delta l flits have to be transferred over at most \Delta connections
to the PU in which the data is concentrated; one packet must travel over a distance of at least (D=2) to
reach the concentration PU; after t steps a PU can hold at most data items by induction.
Of course, a lower bound for T con immediately implies the same lower bound for the gossiping problem.
The degree of a d-dimensional n \Theta \Delta \Delta \Delta \Theta n mesh is 2 \Delta d, and the diameter equals d \Delta (n \Gamma 1).
Usually, t d is comparable to t l while D ! (N=\Delta) \Delta l. Thus we can omit the term (D=2) \Delta t d from the
lower bound without sacrificing too much accuracy. By dividing both remaining terms by l \Delta t l , and by
setting the following simplified lower bound for concentrating
all data in one PU:
con
In Section 4, gossiping algorithms are presented that match this lower bound up to constant factors for all
well as for all n). For the intermediate range there is a considerable deviation
from (2). Therefore, these values of r are considered in more detail. Let T 0
gos (n) denote the number of
time units (of duration l \Delta t l each) required for gossiping on a circular array with n PUs.
Theorem 1 Let
Theorem 1 will be proven by two lemmas. Notice that it establishes a smooth transition from the range
of small r values (r - n 1\Gammaffl , ffl ? 0) to the range of large r values n)), for which (2) already gives
sharp results.
First we show that for proving lower bounds, one can concentrate on the dissemination problem: the
problem of broadcasting the information that is concentrated in one PU to all other PUs. The number
of time units required for this problem is denoted by T 0
dis .
Proof: Starting with all data concentrated in a single PU, the initial situation can be established in time
con by reversing a concentration. On the other hand, gossiping can be performed by concentrating and
subsequently disseminating.
As in our case we will prove a dissemination time that is of larger order than the concentration time (e.g.,
for
con
For the dissemination problem with certain r, it is easy to see that having full freedom of choosing
the size of the packets can be at most a factor two cheaper than when the data are bundled into fixed
messages of size r. That is, we may focus on the problem of disseminating n=r messages, residing in
PU 0, while sending a message takes 2 time. At most another constant factor difference is
introduced if we assume that dissemination has to be performed on a circular array with only rightward
connections. By the above argumentation the proof of Theorem 1 is completed by
Lemma 3 Consider a circular array with only rightward connections and with n PUs. Initially, PU 0
contains n=r messages of size r. In one step the messages may be sent rightwards arbitrarily far, but
the paths of the messages should be disjoint. If r - (n \Gamma 1)=e, then dissemination takes at least n=r \Delta
steps.
Proof: We speak of the original n=r messages as colors, and the task is to make all colors available in
all PUs. We define a cost function F (t) for the distribution of colors after t steps. Consider a PU i and
a color c, and let j be the rightmost PU to the left of i holding color c. The contribution of PU i to F (t)
by color c is does not contain color c and 0 otherwise. The initial cost is given by
We consider how much the cost function can be reduced after a step is performed. It is essential that the
paths must be disjoint. One large 'jump' by a message of some color c gives a strong reduction of the
contribution by color c, but the following claim shows that the total reduction is at most n= ln(n=r).
(n\Gamma1)=e, then after one step the cost function is reduced by at most n= ln(n=r). Moreover,
this occurs if we make a jump over distance r with one message from each color.
From this, the result of the lemma follows, because then the number of steps required for dissemination
is at least
r
In order to prove the claim, let d c be the maximum jump made by a message of color c, 0 - c - n=r \Gamma 1.
Obviously, we must have
c
d c - n, since the paths of the messages must be disjoint. The reduction of
the contribution to F (t) by color c is at most
This can be seen as follows. The initial contribution by color c is at most
After a step
over distance d c , the contribution of the PUs which are within distance d c remains unchanged. This
contribution is
Furthermore, the contribution of the other PUs becomes
The reduction due to the step made by color c is therefore at most
From (3), it follows that the total reduction (due to all steps made by all colors) is bounded by
\DeltaF -
It needs to be shown that this expression is at most n= ln(n=r). 'Powering,' we obtain
dc \Deltaln(n=d c
d
dc
d
The Lagrange multiplicator theorem (see, e.g., [10, Section 4.3]) gives that the product of factors with a
fixed sum is maximal if all factors are equal. Therefore
n=r
dc
It follows that
dc
d
dc
Let a
r \Deltak
We need to show that a k is maximal if k is fixed at its maximum
legal value, which is n. Consider the ratio a k+1 =a k . We have
a k+1
a k
It needs to be shown that a k+1 =a k ? 1. Hence, we must have
r
r
which holds because r - (n \Gamma 1)=e. It follows that the total reduction in cost is at most
4 Linear and Circular Arrays
In this section we analyze gossiping on one-dimensional processor arrays. It is assumed that the time for
routing a packet is given by (1), as long as the paths of the packets do not overlap. As in the previous
section, the distance term, which is of minor importance anyway, is neglected in the rest of this paper.
Furthermore, we write express the time needed for gossiping in units of duration l \Delta t l .
We only present algorithms for circular arrays. Due to their more regular structure, these are slightly
'cleaner', but with minor modifications all results carry on for linear arrays.
4.1 Basic Approaches
For gossiping on a circular array with n PUs, there are two trivial approaches. Each of them is good in
an extreme case.
1. Every PU sends a packet containing its data to the left and right. The packets are sent on for bn=2c
steps.
2. Recursively concentrate the data packets into a selected PU. After that, disseminate the information
to all other PUs by reversing the process.
denote the time taken by Approach 1 and Approach 2, respectively. A simple
analysis gives
Lemma 4
Proof: Approach 1 consists of bn=2c steps, and in each step every packet consists of l flits.
The time taken by Approach 2 is determined as follows. During the concentration phase, the packets
get three times as heavy in every step:
log 3
The expression for the dissemination phase is similar, but in this case the packets consist of n \Delta l flits in
every step:
log 3
Adding the two contributions and neglecting the lower-order term n=2 gives the stated result.
Approach 1 is good when r is small. Comparing it with the lower bound given in (2) shows that
it is exactly optimal when goes to infinity, Approach 2 becomes optimal to within a
constant factor. It will outperform Approach 1 for many practical values of r. Still, in principle, the time
consumption of Approach 2 is not even linear in n.
4.2 Intermixed Approach
For log n, both approaches require \Theta(n \Delta log n) time units. This is a factor of log n more than given
by the lower bound. For this intermediate range of r-values, we present an algorithm that establishes a
better trade-off between the start-up and the transfer time. The algorithm consists of three phases and
works with parameters a and b:
Algorithm circgos(n, a, b)
1. Concentrate n=a packets in a evenly interspaced PUs, called bridgeheads.
2. For ba=2c steps, send the packets of size n=a among the bridgeheads in both directions, such that
afterwards every bridgehead contains the complete data.
3. In dlog a repeatedly increase the number of bridgeheads by a factor of a. This will be
done as follows. Let b - ba=2c denote the number of steps allowed in one round, and let
Every bridgehead partitions the data into k packets of size n=k each. Thereupon, the packets
are broadcast to the new bridgeheads in a pipelined fashion. The packets to the right are sent in order,
whereas the packets to the left are sent in reverse order.
In Phase 2, the packets are circulated around. The description is pleasant because of the circular structure.
In Phase 3, two oppositely directed packet streams are sustained between the bridgeheads. In order to
fully exploit the bidirectional communication links, a bridgehead should not send the same packets to
the left and right. Rightwards the packets should be sent in order, whereas leftwards they should be sent
in reverse order. Figure 1 shows two examples.
The total time consumption of algorithm circgos is given in the following lemma. We do not consider
all rounding details.
cg,f denote the time taken by Phase f of circgos(n; a; b). Then
Proof: Phase 1 corresponds to a concentration step on linear arrays of size n=a instead of n. The time
needed for Phase 2 follows by multiplying the number of steps by the time taken by each of them. In order
to prove the time consumption of Phase 3, it needs to be shown that after b steps every new bridgehead
contains the complete data. Consider a new bridgehead and assume it is at distance d - ba=2c to the
closest old bridgehead. This new bridgehead receives the first packet after d steps. After that, it receives
one more packet in Step d+1 through Step a \Gamma d \Gamma 1. From that point onwards, it receives two packets in
every step. After Step a \Gamma d +x, it contains a+ 2 \Delta packets. By setting
that after b steps the new bridgehead contains a
oe
oe
oe
oe
oe
oe
oe

Figure

1: Behavior of one round of Phase 3 of algorithm circgos. Every arrow is labeled with the time
steps at which the corresponding packet reaches the PUs. The top figure illustrates the case a = 9 and
5. In this case, 3 packets are routed from the bridgeheads. The bottom figure illustrates the case
In this case, the data is partitioned into 4 packets.
At first glance, it is not clear what the result of Lemma 5 means. In particular, it is not immediately
clear which a and b should be chosen. In order to obtain an impression, we have written a small program
which searches for the optimal values. Table 1 lists some typical results. From these results we conclude
that
ffl For realistic values of n and r, circgos may be several times faster than the best of Approach 1
and Approach 2. Furthermore, it never performs worse.
ffl The range of r values for which algorithm circgos is the fastest increases with n.
ffl The best choices for a and b increase with n and decrease with r. In this range of n and r, b is
approximately given by
729 4397 4493 4973 7373

Table

1: Comparison between the time taken by Approach 1 (top), Approach 2 (middle) and circgos
(bottom). The values of the parameters a and b for which the result for circgos was obtained are given
behind its time consumption. The cost unit is l \Delta t l .
Notice that when a identical to Approach 1. Furthermore, circgos(n; 3; 1) behaves
almost identically to Approach 2, but after log 3 n steps the three bridgeheads contain the complete data.
The dissemination phase therefore requires one routing step fewer than in Approach 2. This explains
why circgos(n; 3; 1) is always faster than Approach 2, which does not profit from the wrap-around
connections.
Although the exact choice for the parameters is essential for obtaining the best performance (as shown
in

Table

1), the asymptotic analysis remains unchanged if we take a. The reason for this is that
using different parameters can reduce the amount of transferred data by at most a factor of two. For
proving asymptotic results this is fine, but for practical applications this is highly undesirable. On the
other hand, we might have used more parameters: the factor a by which the number of bridgeheads is
increases in every round of Phase 3 might have been chosen differently, together with its corresponding
optimal choice of b.
Theorem 2 Let r ! n. The number of time units needed by circgos(n; n=r; n=r) is given by
Proof: From Lemma 5 it follows that
When the second term never dominates because
Replacing the factor of ln r in the third term by ln n gives the theorem.
Thus, algorithm circgos gives a continuous transition from gossiping times O(n) (as achieved by Approach
to gossiping times O(n \Delta log n) (as achieved by Approach 2 when n). For
intermediate r values, circgos may be substantially faster:
Corollary 1 Algorithm circgos is asymptotically optimal for all values of r. For all log
\Omega\Gamma/14 n) times faster than Approach 1 and Approach 2.
Proof: The optimality claim follows by comparing the result of Theorem 2 with the lower bound given
in Theorem 1. For r - n, optimality was already established before.
For r - log n, Approach 1 and Approach 2 both take \Omega\Gamma n \Delta log n) time units. On the other hand, when
r - n 1\Gammaffl , circgos has a time consumption of at most O(n \Delta log
4.3 Generalization
In the previous section we presented a gossiping algorithm for linear and circular arrays which is optimal
to within a constant factor for all values of r. In this section we show that this immediately implies an
asymptotically optimal algorithm for 2- and 3-dimensional meshes and tori. In fact, it immediately gives
an asymptotically optimal algorithm for d-dimensional meshes, as long as d is constant. The reason to
develop gossiping algorithms for 2- and higher-dimensional meshes (as will be done in subsequent sections)
is therefore to obtain algorithms with good practical behavior, paying attention to the constants.
The algorithm for gossiping on a d-dimensional mesh consists of d phases. In Phase f ,
the packets participate in a gossip along axis f . For each of these one-dimensional gossips, the most
efficient algorithm is taken. As the size of the packets increases in each phase (in Phase f , the packets
consist of l \Delta n f =d flits each), this is not necessarily the same algorithm in all phases. The described
algorithm will be denoted by high-dim-gos.
Theorem 3 For constant d, high-dim-gos has asymptotically optimal performance.
Proof: Denote the time taken by Phase f of high-dim-gos by T hdg,f , and the time taken by the optimal
gossiping algorithm by T opt . Clearly, T opt exceeds the time required for making all information available
in all PUs, starting with the situation at the beginning of Phase d \Gamma 1. In Phase d \Gamma 1, only a fraction
of 1=d of the connections is used. Using all connections would make the algorithm faster by at most a
factor of d. Thus, T hdg,d
f
Thus, once again, we would like to emphasize that achieving asymptotically optimal performance is
not the real issue, but constructing algorithms with good practical behavior.
Algorithm high-dim-gos does not take advantage of the all port communication capability. To do
better, the l flits in each PU are colored with d colors: Flit bc \Delta l=dc to Flit b(c+1) \Delta l=d \Gamma 1c are given Color c,
d. After that we perform d independent gossiping operations with parameter r
where l In Phase f , the packets with Color c participate in an operation along
c) mod d. This algorithm will be denoted by high-dim-gos 0 . It has the same start-up time as
high-dim-gos, but the transfer time is reduced by a factor of d.
5 Two-Dimensional Arrays
In this section we analyze the gossiping problem on two-dimensional n \Theta n tori. First we investigate what
can be obtained by overlapping two one-dimensional gossiping algorithms, one along the rows and one
along the columns, as sketched in Section 4.3. After that, a truly two-dimensional algorithm is presented,
which for some values of n and r performs significantly better.
5.1 Basic Approaches
The simplest idea is to apply high-dim-gos 0 with a choice from the presented one-dimensional gossiping
algorithms in each phase. Let Approach i-j denote the algorithm in which first Approach i is applied,
and then Approach j. Approach 1-2 can be excluded, since it will never outperform the best of the other
approaches. Let T 0
i;j denote the number of time steps taken by Approach i-j. Using the results from
Section 4, we find
Lemma 6
The time consumption for applying the best version of circgos in both phases cannot be fitted in a
simple formula, but it is better then the best of the above algorithms by almost the same factors as those
found before. In Table 2 some numerical results are given. Because the packets have size n \Delta l during
Phase 2 (which dominates the total time consumption), the transition between the various algorithm now
occurs for much larger r than in Table 1.
5.2 Intermixed Approach
In this section we present a two-dimensional analogue of algorithm circgos. The algorithm as described
below does not use the horizontal and vertical connections simultaneously. Such an algorithm is called
uni-axial. By applying the coloring technique of high-dim-gos 0 , the transfer time is halved.
The algorithm first creates a situation comparable to the one we find after Phase 2 of circgos. For
this, three routing phases are required:
Algorithm torgos(n, a, b)
1. Each PU i;j where (j \Gamma i) mod designated as a bridgehead. Note that there are a
bridgeheads in every row. In each bridgehead concentrate n=a packets from its row.
2. For ba=2c steps, send packets of size n=a along the rows among the bridgeheads in both directions,
such that afterwards, every bridgehead contains the complete data of its row.
3. For ba=2c steps, send packets of size n along the columns among the bridgeheads in both directions,
such that afterwards, every bridgehead contains a \Delta n data.
Now, each bridgehead in Row i, data from every Row i 0 where (i
This is the result of the diagonal way in which the bridgeheads were chosen. An example is given in

Figure

2. Thus, all data are available on the diagonals of every n=a \Theta n=a submesh. The algorithm
proceeds in log a rounds. In each round, the number of bridgeheads is increased by a factor of a.

Figure

2: Left: The bridgeheads in a two-dimensional torus for the case 3. After Phase 3,
each bridgehead in Row i, all data from every Row i 0 , where (i
bridgeheads from nine consecutive rows therefore know the complete data. Right: The bridgeheads (new
ones are drawn smaller) during the first round of Phase 4. Hereafter, each bridgehead in Row i knows
all data from every Row
Invariant 1 At the beginning of Round t, 1 - t - log a n, each PU holds n \Delta a t data, and all data are
available on the diagonals of all n=a t \Theta n=a t submeshes.
This implies that the gossiping has been completed when log a n. A more formal description of the
last phase is given below:
Algorithm torgos(n, a, b) (continued)
4. For repeatedly increase the number of bridgeheads by a factor of a by
inserting a \Gamma 1 new bridgeheads between any pair of two consecutive bridgeheads in every row.
a. The information from the old bridgeheads in a row is passed to the a \Gamma 1 new bridgeheads in
steps with packets of size m=(2 \Delta b \Gamma a
b. For ba=2c steps, send packets of size m along the columns among the bridgeheads (old as well as
new) in both directions, so that afterwards, every bridgehead contains a \Delta m data.
The three phases that operate along the rows are identical to those of circgos. Only Phase 3 and
Phase 4.b, which add the information of a row to a other rows, are new. The following analogue of
Lemma 5 is straightforward:
tg,f denote the number of time units needed for Phase f of torgos(n; a; b). Then
Proof: The time taken by Phase 1 is given in the proof of Lemma 5. In Phase 2, 3 and 4.b, there are
log a n+1 rounds in total, and each round consists of ba=2c routing steps. The size of the packets increases
from n=a until n 2 =a over the rounds. The transfer time is therefore bounded by ba=2c \Delta
a). The time taken by Phase 4.a is determined analogously.
Just as circgos, torgos constitutes a compromise between simplicity and performance. The routing
time will be somewhat smaller if the a-values and the corresponding b-values are chosen in dependency
of the growing size of the packets. But even the presented basic version of torgos performs fairly well.
In

Table

2 we compare the performance of all two-dimensional algorithms. It can be seen that torgos is
442 1482 5382 13182

Table

2: Comparison of the results obtained for gossiping on an n \Theta n torus. For every pair of values (n; r),
the number of time steps is given (from top to bottom) for Approach 1-1, Approach 2-1, Approach 2-2,
high-dim-gos 0 that circgos, and torgos. For the latter two, the values of (the second) a and b for
which the result was obtained are indicated.
always the most efficient algorithm, but for small r-values the difference with Approach 2-1 is marginal.
The performance of the variation of high-dim-gos 0 that utilizes circgos in both phases is better than
that of the simple approaches but nevertheless slightly disappointing, particularly if one considers that
this algorithm can choose its a and b values in each phase independently. Generally, we can conclude
that if one aims for simplicity, one should utilize Approach 2-1. If a slightly more involved algorithm is
acceptable, one should use torgos, which may be more than twice as fast.
6 Higher Dimensional Arrays
For the success of torgos it was essential that the packets were concentrated on diagonals at all times,
as formulated in Invariant 1. Starting in such a situation, the invariant could be efficiently reestablished
by copying horizontally (Phase 4.a), and adding together vertically (Phase 4.b).
The main problem in the construction of a gossiping algorithm for d-dimensional meshes is that it is
unclear how the concept of a diagonal can be generalizes. Once we have such a 'diagonal', we can perform
an analogue of torgos. In the following section we describe the appropriate notion of d-dimensional
diagonals. After that, we specify and analyze the gossiping algorithm for d - 3.
6.1 Generalized Diagonals
The property of a two-dimensional diagonal that must be generalized is the possibility of 'seeing' a full
and non-overlapping hyperplane, when looking along any of the coordinate axes. We will try to explain
what this means.
Let the unit-cube I d 2 R d be defined as I d = [0; 1i \Theta \Delta \Delta \Delta \Theta [0; 1i. When projecting the diagonal of
I 2 orthogonally on the x 0 -axes, we obtain the set [0; 1i \Theta 0; when projecting on the x 1 -axes, we obtain
0 \Theta [0; 1i. These projections are bijections (one-to-one mappings) from the diagonal to the sides of I 2 .
For algorithm torgos, this means that the information from diagonals can be replicated efficiently. A
diagonal behaves like a magical mirror: data received along one axis can be reflected along the other
axis. Not only in one direction, but in both directions. This requirement of problem-free copying between
diagonals in adjacent submeshes along all coordinate axes leads to the following
subset D of I d is called a d-dimensional diagonal if the orthogonal projections of D onto
any of the bounding hyperplanes of I d are bijective.
We will proof that the union of the following d sets satisfies the property of a d-dimensional diagonal:
Notice that D 0)g. On I 2 , the diagonal consists of f(0; 0)g as well as the points in f0 -
1g. The diagonals of I 2 and I 3 are illustrated in Figure 3. On a torus the d partial
hyperplanes are connected in a topologically interesting way. 110D

Figure

3: Diagonals of I 2 and I 3 . The bounding lines that belong (do not belong) to the considered sets
are drawn solid (dashed). The corner points of D 1 are no elements of it. Projecting I 3 downwards maps
bijectively on the ground plane.
Lemma
a diagonal of I d in the sense of Definition 1.
Proof: As the D i are completely symmetric, we can concentrate on the projection \Pi 0 along the x 0 -axis.
It is easy to check that for all
Clearly, these sets are all disjoint, so \Pi 0 is injective. On the other hand,
which implies the surjectivity of \Pi 0 .
In order to extend the definitions to d-dimensional n \Theta \Delta \Delta \Delta \Theta n cubes, one has to multiply all bounds
on every x i by n. Thus, the diagonal Dn can be defined concisely as
On grids, only the points with integral coordinates should be taken. An example is given in Figure 4.
So, we successfully defined d-dimensional diagonals. The reader is advised to obtain a full understanding
of the case 3. For us it was helpful to construct a model of paper (cardboard would have
1 It is easy to see that all d-subsets together form a closed d \Gamma 1-dimensional subspace of the d-dimensional torus. On
two-dimensional tori they constitute a circle and on three-dimensional tori a two-dimensional torus. Generally the diagonal
of a d-dimensional torus is a d \Gamma 1-dimensional torus, but a proof of this is beyond the scope of the paper.
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y

Figure

4: The diagonal of a 4 \Theta 4 \Theta 4 grid: 16 points, such that if they were occupied by towers in a
three-dimensional chess game, none of them could capture an other.
been even better). Such a model makes it easy to convince oneself that the required property, that looking
along a coordinate axis indeed gives a full but non-overlapping view of the hyperplanes, is satisfied.
Though we are not aware of any result in this direction, we are not sure that we are the first to define
this concept. Still we are very pleased with the utmost simplicity of Equation (4) and the elegance of the
proof of Lemma 8.
6.2 Details of the Algorithm
With the defined diagonals, we can now generalize torgos for gossiping on tori of arbitrary dimensions.
The algorithm is almost the same as before. With a few extra routing steps, the algorithm can also be
applied for meshes. Again, the presented algorithm is uni-axial. By applying the coloring technique of
high-dim-gos 0 , the transfer time can be reduced by a factor of d. By rows we mean one-dimensional
subspaces parallel to the x 0 -axis.
Algorithm cubgos(n, d, a, b)
1. In each row a PUs are designated as bridgeheads, namely the PUs which lie on the diagonal of
their n=a \Theta \Delta \Delta \Delta \Theta n=a submesh. Concentrate in each bridgehead n=a packets from their rows.
2. For ba=2c steps, send packets of size n=a along the rows among the bridgeheads in both directions,
such that afterwards, every bridgehead contains the complete data of its row.
3. Perform d \Gamma 1 round each consisting of ba=2c routing steps. In Round i, 1 d, packets of size
a are routed along the x i -axis among the bridgeheads in both directions, such that afterwards,
every bridgehead contains a i \Delta n data.
Now each bridgehead in Row data from every
Row
all data are available on the diagonal
of every n=a \Theta n=a submesh. Hereafter, log a further rounds are performed. In each round,
the number of bridgeheads is increased by a factor of a.
Invariant 2 At the beginning of Round t, 1 - t - log a n, each PU holds n \Delta a (d\Gamma1)\Deltat data, and all data
are available on the diagonal of every n=a t \Theta \Delta \Delta \Delta \Theta n=a t submesh.
When log a n, this implies that the gossiping has been completed. A more formal description of the
last phase is given below.
Algorithm cubgos(n, d, a, b) (continued)
4. For repeatedly increase the number of bridgeheads by a factor of a by
inserting a \Gamma 1 new bridgeheads between any pair of consecutive bridgeheads in every row.
a. The information from the old bridgeheads in a row is passed to the a \Gamma 1 new bridgeheads in
steps with packets of size m=(2 \Delta b \Gamma a
b. Perform d \Gamma 1 subphases each consisting of ba=2c routing steps. In Subphase i, 1
of size a are routed along the x i -axis among the bridgeheads (old as well as new) in both
directions. Afterwards, every bridgehead contains a
The following analogue of Lemma 7 is straightforward:
Lemma 9 Let T 0
cg,f denote the number of time units needed for Phase f of cubgos(n; d; a; b). Then
(a
log a
Denote the version of the algorithm that utilizes coloring of the packets in order to fully exploit the
all-port communication capability by cubgos 0 . Then we get
Theorem 4 Let T 0
cg 0 denote the number of time units taken by cubgos 0 (n; d; a; b). Then
log a n \Delta r:
Proof: In Lemma 9 the third expression dominates the other two by far.
9 280 ( 9,
90824

Table

3: Comparison of the results obtained for gossiping on a three-dimensional n \Theta n \Theta n torus. For
every pair of values (n; r), the number of time steps are given (from top to bottom) for application of
high-dim-gos 0 with the best choice from Approach 1 and Approach 2 (indicated), for high-dim-gos 0
that utilizes circgos in every phase, and for cubgos 0 . For the latter two, the values of (the last) a and
b are also indicated.
Thus, the transfer time is within a factor of a=(a \Gamma 1) from optimality for all d, and the start-up time
is within a factor of d\Deltaa=2\Deltalog a n
log 2\Deltad+1 n d ' a\Delta(log d+1)
2\Deltalog a
from optimality. This appears to be a really strong result.
From

Table

3 it can be seen that for some n and r, cubgos 0 is substantially faster than high-dim-gos 0 ,
even though the latter has much more freedom of choosing its parameters. Actually, if one is going to
apply high-dim-gos 0 , then one can just as well take the best of Approach 1 and Approach 2 in each of
the phases.
7 Experiments
To validate the efficiency of the developed algorithms, we implemented them on the Intel Paragon [2]. In
this section, the experimental results are presented.
System Description. The Paragon system used for the experimentation consists of 140 PUs, each
consisting of two 50MHz i860 XP microprocessors. One processor, called the message processor, is
dedicated to communication, so that the compute processor is released from message-passing operations.
Every PU is connected to a Mesh Routing Chip (MRC), and the MRCs are arranged in a 2-dimensional
mesh which is 14 nodes high and 10 nodes wide. The links can transfer data at a rate up to 175 MB/s
in both directions simultaneously.
The algorithms were implemented using the NX message-passing library. NX is the programming
interface supplied by Intel. Other communication layers for the Paragon, such as SUNMOS [9], achieve
higher bandwidth and lower latency than NX, but were not available.
Some features of the Paragon are particularly important in order to understand the performance of
the implemented algorithms, namely
ffl The MRCs implement dimension order wormhole routing, i.e., packets are first routed along the
rows to their destination columns and from there along the columns to their destinations. We
employed this fact to embed a circular array into the mesh topology of the Paragon.
ffl When a message enters its destination before the receive is posted, the OSF/1 operating system
buffers the message in a system buffer. When the corresponding receive is issued, the message is
copied from the system buffer to the application buffer. This buffering is very expensive and can be
avoided if the recipient first sends a zero-length synchronization message to the sender indicating
that it has posted the receive. All implementations make use of this mechanism.
ffl In previous experiments on the Paragon, we determined that the startup cost of a message transmission
under NX is about 150 -s. Short messages incur a somewhat lower startup cost than long
messages, because they are sent immediately whereas long messages wait until sufficient space is
available at the destination processor. The experiments also showed that the uni-directional transfer
rate from PU to MRC under NX is about 87 MB/s (11.5 ns per byte), whereas the bi-directional
transfer rate is approximately 44 MB/s. Furthermore, the bi-directional transfer rate between two
MRCs is 175 MB/s. Because of this, the topology of the Paragon can be viewed as a torus.
Modifications to the Algorithms. The implemented algorithms deviate slightly from the algorithms
described in the previous sections. This was done for two reasons. First, because every PU of the Paragon
is connected to an MRC and not directly to its (up to) 4 neighbors, we cannot assume the full-port
model in which a PU can send and receive a message in all 4 wind directions simultaneously. Second, as
mentioned above, the uni-directional transfer rate of the Paragon using NX is about 87 MB/s, whereas the
bi-directional transfer rate is approximately 44 MB/s. This shows that it is more accurate to assume that
a PU cannot send and receive simultaneously, although this is not a feature of the Paragon architecture
but a feature of NX.
We give two examples of how (the analyses of) the algorithms need to be modified in order to reflect
these communication characteristics of the Paragon. First, Approach 1 for gossiping on a circular array
of n PUs now consists of steps, and in each step every PU must send a message to one of its
neighbors and receive a message from its other neighbor. Since this cannot happen simultaneously, the
time consumption of Approach 1 is given by
Similarly, under the modified model it takes dlog 2 ne instead of dlog 3 ne steps to concentrate all data into
one PU and another dlog 2 ne steps to broadcast the data to every other PU. The time taken by Approach
2 is therefore approximately given by
ne
A detailed analysis of all algorithms under this model is omitted, because the modifications are rather
straightforward. Furthermore, the main purpose of this section is to show that the developed techniques
actually work in practice, and not that the performance model is accurate. A detailed performance model
should incorporate that short messages incur a lower startup cost than long messages, that the send and
receive overheads can differ significantly, etc. This is beyond the scope of this paper.
Time
per
byte
Message length (bytes)
Approach 1
Approach 2
Circgos

Figure

5: Performance of the gossiping algorithms on a circular array with 64 PUs.
An additional remark concerns the implementations of algorithm circgos and torgos. In the
implementations we used 3 parameters: a 1 , a 2 and k, where a 1 is the number of bridgeheads, a 2 is the
factor by which the number of bridgeheads is increased in every round, and n=k is the packet size during
Phase 3 (4.a) of circgos (torgos). In the descriptions of circgos and torgos, we have set a
2. For asymptotic analysis this is fine, but on such a moderate size platform rounding
errors may be introduced which can affect the execution times significantly.
Experimental Results. The circular array algorithms were implemented on the Paragon by embedding
a circular array into the mesh. Figure 5 compares the performance achieved by algorithm
on a circular array with 64 PUs with the performance achieved by Approach 1 and the
performance attained by Approach 2. Every data point measured for the implementation of algorithm
circgos is labeled with the values of a 1 , a 2 and k for which the result was obtained. In order to place
the data on a common scale, we divided the time taken by each algorithm by the message length m. The
total execution time is obtained by multiplying the time per byte by the message length.
It can be seen that algorithm circgos is always faster than Approach 2. For messages up to 256
bytes, the best results are obtained with a 1. With this set of parameters, the
behavior of circgos is almost the same as the behavior of Approach 2, except that it saves 1 startup and
the transmission of a packet of size l \Delta n=2 at the end of the concentration phase. When the message size
increases, the fastest results are obtained when the number of bridgeheads a 1 also increases, but a 2 and k
remain fixed. With these parameters, algorithm circgos first concentrates data in a few selected nodes
as in Approach 2, after that it circulates the packets around as in Approach 1, and finally it broadcasts
the data to all non-bridgeheads, again as in Approach 2. Other values for a 2 and k always performed
worse than a 1. When the message size increases beyond 16 KB, the best results are
obtained when a 64. For this value of a, algorithm circgos and Approach 1 behave identically,
as can be seen since the data points coincide.

Figure

6 shows the performance of 6 gossiping routines on an 8 \Theta 8 configuration of the Paragon: (1)
Approach 1-1, (2) Approach 2-2, (3) Approach 2-1, (4) algorithm torgos with parameters a
Approach 1-1 using black/white packets, and (6) the gossiping routine gcolx provided by
the NX message-passing library. The fifth algorithm implementation does not partition the packet in every
PU into a white and a black packet, but first performs a gossip in every 2 \Theta 2 submesh, after which each
colors its packet white, and each PU i;j where even colors its packet black.
This was done because of the one-port restriction. Furthermore, the first four algorithm implementations
do not employ the technique of interleaving horizontal and vertical messages. This was done because on
such a moderate size network one does not save many startups by using a concentrate/broadcast approach
instead of a store-and-forward approach. Moreover, if the PUs were divided into black and white PUs,
Time
per
byte
Message length (bytes)
Approach 1-1
Approach 2-2
Approach 2-1
Approach 1-1 w black/white nodes
gcolx
(a) Messages smaller than 1KB.1.52.53.54.51K 2K 4K 8K 16K 32K 64K
Time
per
byte
Message length (bytes)
Approach 1-1
Approach 2-2
Approach 2-1
Approach 1-1 w black/white nodes
gcolx
(b) Messages larger than 1KB.

Figure

Performance of the gossiping algorithms on a 2-dimensional mesh with 64 PUs.
the differences would almost vanish.
Because the differences between the various gossiping algorithms are rather small on this moderate
size machine, we divided the experimental data into results for messages smaller than 1KB and messages
larger than 1KB. Comparing Approach 1-1, 2-2, 2-1 and torgos(2; 2; 1), we find that torgos is the
fastest algorithm for messages up to 3KB. For larger messages, Approach 1-1 yields the best results. For
a message of 3KB, the ratio between the startup cost of the message transmission and the transmission
time of the message is about 4.2, and for such a small ratio Approach 1-1 turns out to be the fastest
gossiping algorithm. Furthermore, as was indicated in Section 6, Approach 2-2 and 2-1 have become
they never outperform the fastest of Approach 1-1 and torgos(2; 2; 1).
Comparing Approach 1-1 and torgos(2; 2; 1) with the gossiping routine gcolx supplied by NX,
one can see that gcolx only yields the best results when the message size is very small. For messages
larger than about 200 bytes, the fastest of our algorithm implementations always outperforms the vendor
supplied routine. The largest relative difference was measured for messages of 1.5KB. For this message
length, gcolx requires 3.96 -s/byte, whereas torgos(2; 2; 1) needs 3.04 -s/byte, which corresponds to
a performance improvement by a factor of about 1.3. We believe that this supports our claim that the
developed algorithms have practical relevance.
Also included in Figure 6 are the results obtained for an implementation of Approach 1-1 in which the
nodes are divided into white and black nodes, and in which the white nodes route their packets at all times
orthogonally to the black ones. It can be seen that except for very small packets, this implementation
always produces the best results. As stated before, this is due to the fact that on this moderate size
machine one does not save many startups by using a concentrate/broadcast approach instead of a store-
and-forward approach, especially when the nodes are split into white and black nodes. The results for this
algorithm are mainly included here to show that the idea of interleaving horizontal and vertical packets
can be used advantageously.
8 Conclusion
We presented gossiping algorithms for meshes of arbitrary dimensions. We optimized the trade-off between
contributions due to start-ups and those due to the bounded capacity of the connections. This
enabled us to reduce the time for gossiping in theory as well as practice for an important range of the
involved parameters. Furthermore, we presented an interesting generalization of a diagonal, which can
be applied to arbitrary dimensions. This seems to have wider applicability.

Acknowledgments

Computational support was provided by KFA J-ulich, Germany.



--R

'On the Efficiency of Global Combine Algorithms for 2-D Meshes with Wormhole Routing,' Journal of Parallel and Distributed Computing
'Intel Paragon XP/S - Architecture, Software Environment, and Performance,' Technical Report KFA-ZAM-IB-9409



Advanced Computer Architecture
'Randomized Multipacket Routing and Sorting on Meshes,' Algorith- mica
'Fast Gossiping for the Hypercube,' SIAM J.
'SUNMOS for the Intel Paragon: A Brief User's Guide

'A Survey of Wormhole Routing Techniques in Direct Networks,' IEEE Computer
'Circuit-Switched Broadcasting in Torus Networks,' IEEE Transactions on Parallel and Distributed Systems
'k-k Routing, k-k Sorting, and Cut-Through Routing on the Mesh,' Journal of Algorithms
'A Logarithmic Time Sort for Linear Size Networks,' Journal of the ACM
'Data Communications in Parallel Block Predictor-Corrector Methods for solving ODEs,' Techn.

'Bandwidth-Optimal Complete Exchange on Wormhole-Routed 2D/3D Torus Networks: A Diagonal-Propagation Approach,' IEEE Transactions on Parallel and Distributed Systems
--TR

--CTR
Michal Soch , Paval Tvrdk, Time-Optimal Gossip of Large Packets in Noncombining 2D Tori and Meshes, IEEE Transactions on Parallel and Distributed Systems, v.10 n.12, p.1252-1261, December 1999
Jop F. Sibeyn, Solving Fundamental Problems on Sparse-Meshes, IEEE Transactions on Parallel and Distributed Systems, v.11 n.12, p.1324-1332, December 2000
Ulrich Meyer , Jop F. Sibeyn, Oblivious gossiping on tori, Journal of Algorithms, v.42 n.1, p.1-19, January 2002
Francis C.M. Lau , Shi-Heng Zhang, Fast Gossiping in Square Meshes/Tori with Bounded-Size Packets, IEEE Transactions on Parallel and Distributed Systems, v.13 n.4, p.349-358, April 2002
Yuanyuan Yang , Jianchao Wang, Near-Optimal All-to-All Broadcast in Multidimensional All-Port Meshes and Tori, IEEE Transactions on Parallel and Distributed Systems, v.13 n.2, p.128-141, February 2002
Yuanyuan Yang , Jianchao Wang, Pipelined All-to-All Broadcast in All-Port Meshes and Tori, IEEE Transactions on Computers, v.50 n.10, p.1020-1032, October 2001
wormhole routing;mesh networks;torus networks;gossip;global communication