Scalable S-To-P Broadcasting on Message-Passing MPPs.
AbstractIn s-to-p broadcasting, s processors in a p-processor machine contain a message to be broadcast to all the processors, 1 sp. We present a number of different broadcasting algorithms that handle all ranges of s. We show how the performance of each algorithm is influenced by the distribution of the s source processors and by the relationships between the distribution and the characteristics of the interconnection network. For the Intel Paragon we show that for each algorithm and machine dimension there exist ideal distributions and distributions on which the performance degrades. For the Cray T3D we also demonstrate dependencies between distributions and machine sizes. To reduce the dependence of the performance on the distribution of sources, we propose a repositioning approach. In this approach, the initial distribution is turned into an ideal distribution of the target broadcasting algorithm. We report experimental results for the Intel Paragon and Cray T3D and discuss scalability and performance.
Introduction
The broadcasting of messages is a basic communication
operation on coarse-grained, message passing
massively parallel processors (MPPs). In the
standard broadcast operation, one processor broadcasts
a message to every other processor. Various
implementations of this operation for architectures
with different machine characteristics have been proposed
[5, 9, 12, 13, 14]. Another well-studied broadcasting
operation is the all-to-all broadcast in which
every processor broadcasts a message to every other
processor [3, 7, 8, 15]. Let p be the number of proces-
sors. Assume that s of the p processors, which we call
source processors, contain a message to be broadcast
to every other processor, 1 - s - p. In this paper
we present broadcasting algorithms that handle all
ranges of s. We report experimental results for s-to-
Research supported in part by ARPA under contract
DABT63-92-C-0022ONR. The views and conclusions contained
in this paper are those of the authors and should not
be interpreted as representing official policies, expressed or
implied, of the U.S. government.
broadcasting algorithms on the Intel Paragon and
discuss their scalability and performance.
In general, quantities influencing scalability, and
thus the choice of which algorithm gives the best per-
formance, include the number of processors, the message
sizes, and the number of source processors [10].
Our algorithms are scalable with respect to p, s, and
the message sizes; i.e., they maintain their speedup
as these parameters change. For s-to-p broadcast-
ing, other factors influence scalability as well. For
any fixed s, a particular algorithm exhibits a different
behavior depending where the s source processors
are located. Each algorithm has ideal distribution
patterns and distribution patterns giving poor
performance. Poor distribution patterns for one algorithm
can be ideal for another. Thus, the location
of the source processors and the relationship of these
locations to the size and dimensions of the architecture
effect the scalability of an algorithm. In order to
study these relationships to the fullest extent, we assume
that every processor knows the position of the
source processors and the size of the messages. This
implies synchronization occurs before the broadcasting

In this paper we describe a number of different
broadcasting algorithms and investigate for each algorithm
its good and bad distribution patterns. We
characterize features of s-to-p broadcast algorithms
that perform well on a wide variety of source dis-
tributions. Some of our algorithms are tailored
towards meshes, others are based on architecture-independent
approaches. We show that algorithms
that
ffl exhibit a fast increase in the number of processors
actively involved in the broadcasting process
and
ffl increase the message length at these processors
as slowly as possible
give the best performance. We show that achieving
these two goals can be difficult for regular machine
sizes (i.e., machines whose dimensions are a power
of 2). This, in turn, implies that good or bad input
distributions cannot be characterized by the pattern
alone. The dimension of the machine plays a crucial
role as well. The performance obtained on ideal
distributions can vary greatly from that obtained on
poor distributions. We propose the approach of repositioning
sources to guarantee a good performance.
The basic idea is to perform a permutation to transform
the given distribution into an ideal distribution
for a particular algorithm which is then invoked to
perform the actual broadcast.
The paper is organized as follows. In Section 2
we describe the algorithms that do not reposition
their sources. In Section 3 we discuss different repositioning
approaches. Section 4 describes the different
source distributions we consider. In Section 5
we discuss performance and scalability of the proposed
algorithms on the Intel Paragon. Section 6
concludes.
Algorithms without Reposi-
tioning
In this section we describe s-to-p broadcasting algorithms
which do not reposition the sources. Our
first class of broadcast algorithms generalizes an efficient
1-to-p broadcasting approach. S-to-p broadcasting
could be done by having each one of the s
source processor initiate a 1-to-p broadcast. How-
ever, having the s broadcasting processes take place
without interaction is inefficient. Our approach is to
let each processor initiate a broadcast, but whenever
messages from different sources meet at a proces-
sor, messages are combined. Further broadcasting
steps proceed thus with larger messages. We use a
Binomial heap broadcasting tree [6, 9] to guide the
broadcasts.
In Algorithm Br Lin, we view the processors
of the mesh as forming a linear array (by using
a snake-like row-major indexing). The existence
of a linear array is not required and the approach
is architecture-independent. If processors P i and
both contain a message to be
broadcast, they exchange their messages and form
a larger message consisting of the original and the
received message. If only one of the processors contains
a message, it sends it to the other one. Then,
Algorithm Br Lin proceeds recursively on the first
p=2 and the last p=2 processors.
Algorithms Br Lin behaves differently for different
machine sizes. Whether the number of processors actively
involved in the broadcasting process increases,
depends on where the source processors are located.
For example, when the input distribution consists of
columns, the first log p=2 iterations introduce no new
sources. For meshes with an odd number of rows,
new sources are introduced in the case of column
distribution.
In order to study the use of only column links or
row links during a single iteration for arbitrary mesh
sizes, we introduce Algorithm Br xy. In Algorithm
Br xy, we first select either rows or columns. Assume
the rows were selected. We then view each row as
a linear array and invoke Algorithm Br Lin within
each row. After this, we invoke Algorithm Br Lin
within each column.
We consider two versions of Algorithm Br xy
which differ on how dimensions are selected. In Algorithm
Br xy source, the number of sources in the
rows and columns determine the order of the dimen-
sions. Recall that every processor knows the positions
of the sources. Every processor determines
, the maximum number of sources in a row,
and
, the maximum number of sources in a col-
umn. If the rows are selected and Algorithm
Br Lin is invoked on the rows. Otherwise,
the columns are selected first. A reason for choosing
the dimensions in this order is the following. When
the rows contain fewer elements, the broadcasting
done within the rows is likely to generate messages
of smaller size to be broadcast within the columns.
Assume sources are located in a few, say ff columns.
where r is the number
of rows of the mesh. First broadcasting in the
rows results in every processors containing ff messages
at the time the column broadcast starts.
For the sake of comparison, we also consider a version
of Algorithm Br xy which compares the dimensions
and broadcasts first along longer dimension.
Assume the mesh consists of r rows and c columns.
Algorithm Br xy dim selects the rows if r - c and
the columns if r ! c.
In the algorithms described so far processors issue
sends and receives to facilitate communication.
We do not make use of existing communication
operations generally available in communication libraries
[1, 2, 7]. S-to-p broadcasting can easily be
stated in terms of known communication operations.
We considered two such approaches. The first one,
Algorithm Xor, invokes an all-to-all personalized
exchange communication [7]. The second such approach
results in Algorithm 2-Step. This algorithm
performs the broadcast by invoking two regular communication
operations, one s-to-one followed by an
one-to-all operation. In the s-to-one communication,
processor receives the s messages from the source
processors. combines the s messages and initiates
an one-to-all broadcast.
3 Algorithms with Reposi-
tioning
On coarse-grained machines like the Paragon, sending
relatively short messages is cheap compared to
the cost of an entire s-to-p operation. At the same
time, experimental results show that the performance
of our s-to-p algorithms can differ by a factor
up to 2 for the same number of sources, depending
on where the sources are positioned. Each algorithm
has its own ideal source distribution. In this section
we consider the approach of repositioning the
sources and then invoking an s-to-p algorithm on its
ideal input distribution.
Algorithm Repos is invoked with one of the algorithms
described in the previous section. For the sake
of an example, assume it is Algorithm Br Lin. The
first step generates Br Lin's ideal input distribution
for s sources on the given machine size and machine
dimension. This is achieved by each source processor
sending its message to a processor determined by the
ideal distribution. We refer to the next section for
a discussion on ideal distributions. Whether it pays
to perform the redistribution depends on the quality
of the initial distribution of sources. We point out
that our current implementation of Algorithm Repos
does not check whether the initial distribution is
actually close enough to an ideal distribution. We
simply perform the repositioning.
Our second class of repositioning algorithms not
only repositions the sources, but also makes use
of the observation that the time for broadcasting
s=2 sources on a p=2-processor machine is less than
half of the time for broadcasting s sources on a p-processor
machine. Assume we partition the p processors
into a group G 1 consisting of p 1 processors
and into a group G 2 consisting of p 2 processors. The
partition of the processors into two groups is independent
of the position of the sources, and may depend
on the choice of the broadcasting algorithm invoked
on each processor group. After the broadcasting
within G 1 and G 2 is completed, every processor
in G 1 (resp. G 2 ) exchanges its data with a processor
in G 2 (resp. G 1 ). This communication step corresponds
to a permutation between the processors in
G 1 and G 2 .
We refer to Algorithm Part Lin as the algorithm
based on this principle and using Algorithm Br Lin
within the sub-machines. We refer to Algorithm
Part xy source as the algorithm based on this principle
and using Algorithm Br xy-source within the
sub-machines.
4 Source Distributions
In this section we discuss different patterns of source
distribution used in our experiments. Some of these
distributions exploit the strengths while other highlight
the weaknesses of the proposed algorithms.
Some are chosen because we expect them to be difficult
distributions for all algorithms. For the sake
of brevity, distributions may only be explained at an
intuitive level. Assume the machine is a mesh of size
with r - c and that processors are indexed
in row-major order. Let
c
e.
ffl Row and Column Distributions: In row distribution
source processors. These i
rows are spaced evenly. Every row, with the exception
of the last one, contains c source processors. For
mesh, R(30) has the source processors positioned
as shown in Figure 1. Column distribution
C(s) is defined analogously.
ffl Equal Distribution: In equal distribution E(s),
processor (1; 1) is a source processor and every dp=se-
th or bp=sc-th processor is a source processor. For
particular values of s, r, and c, E(s) can turn into
a row, column, or diagonal distribution, or exhibit a
rather irregular position of sources.
ffl Right and Left Diagonal Distributions: The right
diagonal distribution, Dr(s), has the s source processors
positioned on i diagonals. We include the diagonal
from (1; 1) to (r; r). The remaining
are spaced evenly (using modulo arithmetic), with
the last diagonal not necessarily filled with sources.
The left diagonal distribution Dl(s) has source processors
on the diagonal from (1; c) to (r; 1) and spaces
the remaining accordingly.
ffl Band Distribution: The band distribution B(s) is
similar to the right diagonal distribution. The right
diagonal distribution contains i diagonals, each having
width 1. The band distribution B(s) contains
r
e evenly distributed bands, each having width
d s
br
e.
ffl Cross Distribution: The cross distribution C(s)
corresponds to the union of a row and a column dis-
tribution, with the number of source processors in
the row distribution being roughly equal to the number
of processors in the column distribution.
ffl Square Block Distribution: In the square block
distribution, SB(s), the source processors are contained
in a square mesh of size d
se \Theta d
se.

Figure

shows three of the above distributions for
30. The remainder of this section describes how
the algorithms handle different distributions. The
Row
l l l l l l l l l l
l
l l l l l l l l l
l l l l l l l l l l
Cross
l m
l m
l
l
l
l
l
l l l l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
Diagonal
l
l
l
l
l
l
l
l
l
l
l
l

Figure

1: Placement of source processors in row, cross, and right diagonal distributions on a
machine.
performance of the algorithms on these distributions
is discussed in the next section.
Consider first Algorithm Br xy source. One expects
row and column distributions to be ideal source
distributions. Algorithm Br xy source will choose
the first dimension so that the number of source
processors is increased as fast as possible, while the
message length increases as slowly as possible. How-
ever, not all row and column distributions are equally
good. For example, in R(20) on a mesh of size 10\Theta10,
the first and the sixth row contain the source processors
and thus the first iteration does not increase the
number of source processors. Having the 20 sources
positioned in the first and the seventh row eliminates
this. This is an important observation for the
algorithms generating ideal distributions. It shows
that the machine dimension effects the ideal distribution
of sources. The diagonal distribution places
the same number of sources in each row and col-
umn. One would expect Algorithm Br xy source to
perform quite well on diagonal distributions. The
performance of Algorithm Br xy source on the equal
distribution will vary. Cross, square block, and band
distributions should be considerably more expensive
since the source positions may not allow a fast increase
in the number of sources.
The behavior of Algorithm Br Lin on these source
distributions is quite different. First, neither row
or column distribution are ideal distributions for
Br Lin. For an even number of rows, an iteration
achieves no increase in the number of sources on
the column distribution. Consider the row distri-
bution. When the number of rows is a power of 2,
Algorithm Br Lin is actually identical to Algorithm
Br xy source. When the number of rows is odd, communication
in an iteration occurs between processors
not in the same column and congestion will increase.
The equal distribution can turn into a row or a column
distribution and will thus not be ideal either.
The behavior of the algorithm on the left and the
right diagonal distribution can differ (no such difference
exists for Algorithm Br xy source). On a machine
of size 10 \Theta 10, Dr(10) experiences no increase
in the number of sources in the first iteration (since
processor P 50 lies on the diagonal). For other machine
sizes, the right diagonal distribution may not
experience such disadvantage. The left diagonal distribution
is least sensitive towards the size of the
machine and it achieves the desired properties of an
efficient broadcasting algorithm. The remaining distributions
appear to be difficult distributions.
Finally, Algorithm Br xy dim suffers the obvious
drawbacks when the selection of the dimension is
done according to the size of the dimensions and not
according to the number of sources. The ideal distribution
for Algorithm Br xy dim will either be a row
or a column distribution, depending on the dimensions

5 Experimental Results
In this section we report performance results for the
broadcasting algorithms on the Intel Paragon.
We consider machine sizes from 4 to 256 processors
and message sizes from 32 bytes to 16K bytes.
We study the performance over a whole spectrum of
source numbers ranging from 1 to p and a representative
selection of source distributions. In this paper
we report only the performance for the case when
all source processors broadcast messages of the same
length. In our experiments, using different length
messages did not influence the performance of the
algorithms. In particular, for a given algorithm a
good distribution remains a good distribution when
the length of messages varies. Throughout this sec-
tion, we use L to denote the size of the messages at
source processors.
Most implementation issues follow in a straightforward
way from the descriptions given in the previous
sections. We point out that we do not synchronize
globally after each iteration or after one dimension
has been handled. In all our algorithms, as soon as
a processor has all relevant data, it continues.
5.1 Performance of Algorithms without
Repositioning
In the following we first study the scalability of the
five algorithms described in Section 2 for standard
scalability parameters such as machine size, number
of source processors, and message length. We then
consider other relevant parameters, including the distribution
of the source processors, the dimension of
the machine, and the interaction of the dimension
of the machine and the source processor distribution
with respect to a particular algorithm. We show that
these parameters have a significant impact on the
performance.
Xor
Br_Lin
Br_xy_source
100103050Number of Sources
Time
(msec)

Figure

2: Performance of algorithms when the number
of sources varies from 1 to 100, assuming
and equal distribution on a
The communication operations invoked in Algorithms
Xor and 2-Step use the implementations described
in [7]. In particular, the all-to-all exchange
algorithm views the exchanges as consisting of p permutations
and it uses the exclusive-or on processor
indices to generate the permutations. The most efficient
Paragon implementation of an one-to-all communication
views the mesh as a linear array and applies
the communication pattern used in Algorithm
Br Lin; i.e., processor P i
exchanges a message with
and then the one-to-all communication is performed
within each machine half. We did not expect
Algorithms Xor and 2-Step to give good per-
formance. Xor simply exchanges too many messages
and Algorithm 2-Step creates unnecessary communication
bottlenecks. However, we did want to see
their performance against the other proposed algorithms
to show the disadvantage of using existing
communication routines in a brute-force way.

Figure

2 shows the performance of the five algo-
rithms. From this figure it is apparent that Algorithms
2-Step and Xor are not efficient. In particu-
lar, for more than 4 sources, Algorithm 2-Step suffers
congestion at the node which receives all the
messages. Algorithm Xor is inherently inefficient
because of the large number of sends issued by the
source processors. For Algorithm 2-Step, the rate of
increase in the execution time is steeper than the increase
in number of sources. This is due to the fact
that as the number of source processors increases,
the bottleneck processor in Algorithm 2-Step receives
more messages in the first step and sends out more
data in the second step. However, in the case of Algorithm
Xor, with the increase in number of source
processors, the increase in the number of sources is
more distributed among all processors.
Xor
Br_Lin
Br_xy_source
Message Length (in bytes)
Time
(msec)

Figure

3: Performance of algorithms when L varies
from 32 bytes to 16K keeping s =30 on a
machine with right diagonal distribution.
Xor
Br_Lin
Br_xy_source
Machine Size
Time
(msec)

Figure

4: Performance of algorithms when the machine
size varies, assuming having approximately
sources in a right diagonal distribution

The bandwidth of the network is high enough to
handle this type of increased communication volume
better. The performance of the other three algo-
rithms, Br Lin, Br xy source, and Br xy dim scales
linearly with the increase in number of sources. Depending
on the number of sources and how the equal
distribution places sources in the machine, the performance
of these algorithms differs slightly.

Figure

3 shows the performance for a right diagonal
distribution with when the message size
changes. As already stated, the diagonal distributions
place the same number of sources in the rows
and columns. Once again, regardless of how small
a message size, Algorithms 2-Step and Xor perform
poorly. The almost flat curve up to a message size of
1K for Algorithm Xor further supports our observation
related to Figure 2. The other three algorithms
experience little increase in the time until
bytes. Then we see a linear increase.

Figure

4 shows the behavior of the five algorithms
when the machine size varies from 4 to 256 processor.
Algorithm Xor is as good as any other algorithm for
small machine sizes (4 to 16 processors). This feature
is also observed when the number of sources is close
to p for small machine sizes.
The first three figures give the impression that algorithms
Br Lin, Br xy source, and Br xy dim give
the same performance. However, this is not true.
In the following we show that different distributions
and different machine sizes effect these algorithms in
different ways.
Br_Lin
Br_xy_source
row dia blk cro6789
Distributions
Time
(msec)

Figure

5: Performance of three algorithms on a 10x10
machine with assuming different source distributions
with

Figure

5 shows the performance for
using different distribution patterns. The figure
confirms the discussion given in Section 4 with respect
to ideal and difficult distributions. Algorithm
Br xy source gives roughly the same performance on
the first 4 distributions, but for the square block and
cross distribution we see a considerable increase in
time. We point out that the same performance on
the first 4 distributions for Br xy source is not true in
general. However, the row and the column distribution
show up as ideal distributions. Square block and
cross distributions require more time for all three al-
gorithms. As expected, Algorithm Br Lin performs
best on them. This is due to the fact that in Algorithm
Br Lin sources can spread to different rows
and columns in the first few iterations, thus utilizing
the links more efficiently. On the other hand, for the
square block distribution, Algorithms Br xy source,
Br xy dim have only few columns and rows available
to generate new sources. The big increase in Algorithm
Br xy dim for the row distribution indicates
the importance of choosing the right dimension first.
Br_Lin
Br_xy_source
407.58.59.510.511.5Number of Sources
Time
(msec)

Figure

Performance of three algorithms on a 10x10
machine with a right diagonal distribution. The total
message size is kept at 80K and the number of sources
varies.

Figure

6 shows the performance of the three algorithms
when the total message size (i.e., the sum of
the message sizes in the source processors) is fixed.
An interesting aspect of the performance curves is
that if the data is spread among a larger number
of sources, the broadcast operation is accomplished
faster. For example the 80K size, data spread among
5 sources takes approximately 11.4 msec using Algorithm
Br xy source. However, the same amount of
data spread among 40 sources to begin with takes
only 7.3 msec. This plot highlights our claim made
earlier that for a given amount of data more number
of sources involved in broadcasting yield faster
execution times.
Time

Figure

7: Performance of Algorithm Br Lin when
and the dimensions vary, assuming equal
distribution. Three source sizes are shown and
4K in all the cases.

Figure

7 shows the performance of three algorithms
when the dimensions of the machine
vary. It demonstrates that performance is related
to the size the dimensions. For the same number
of sources, message size, and number of pro-
cessors, a distribution gives different performance
(hence is considered good or bad) depending on the
dimension of machine. For a small number of sources
(for example the machine dimensions may
not affect the performance. For a large number
of sources, machine dimensions impact the performance
considerably more. It seems like an anomaly
to have faster performance for
The reason lies in the distribution and the number
of rows. When the equal distribution
tends to place the source processors within columns.
This does not allow a fast increase in the number of
sources. On the other hand, for the source
processors are, with the exception of size 4 \Theta 30, positioned
along diagonals.
5.2 Performance of Algorithms with
Repositioning
Algorithms Br xy source and Br Lin exhibit good
performance for a variety of source distributions and
machine dimensions. However, each algorithm has
source distributions which exhibit the algorithm's
weaknesses. In addition, the relationship between
source distribution and machine dimension can result
in a performance loss. The algorithm cannot
change the machine dimension, but the problems
arising from the source distribution can be avoided
by performing a repositioning. In Section 3 we described
a repositioning and a partitioning approach.
We next discuss the performance of the repositioning
approach using Algorithm Br xy source. We use
the row distribution as the ideal source distribution
for Br xy source. Similar results hold for the repositioning
algorithm using Br Lin with the left diagonal
distribution as the ideal source distribution.
Let Algorithm Repos xy source be the repositioning
algorithm invoking Br xy source. In this algorithm
we first perform a permutation to redistribute
source processors according to the row distribution.
We generate a row distribution that positions the
rows so that the number of new sources increases as
fast as possible (the exact position of the rows depends
on the number of rows of the mesh). The cost
of the permutation depends on s, where the s source
processors are located, and the message length.
In

Figure

8 we show the percentage difference between
Algorithms Repos xy source and Br xy source
on four input distributions when the number of
sources increases from 16 to 192. The machine size
is and the message size is 6K bytes. Repositioning
pays for all distributions except the band
distribution. Repositioning for the band distribution
costs up to 6:5% more. Translating this into
actual time, when s is less than 150, Repos xy source
-10103050Number of Sources
Percentage
Difference
o- equal
+- cross
*- band
x- blk

Figure

8: The difference between Repos xy source
and Br xy source on different input distributions for
a machine with varying the number
of sources.
costs between 1 and 2 msec more. For
repositioning costs 7.5 msec more, indicating that
repositioning is expensive for large source numbers.
The repositioning approach results in a significant
gain for the cross and square block distributions. In
terms of actual time, the gain for repositioning on
the cross distributions lies between 13 and 31 msec.
A gain of 13 msec is observed when
for all other source numbers the gain lies between 20
and 31 msec.
The conclusion of our experimental study is that
repositioning pays (i.e., the cost of the initial permutation
is less than the gain resulting from working
with an ideal source distribution) unless:
ffl the number of sources is large (s ? p=2 appears
to be the breakpoint), or
ffl the number of processors is small (for p - 16,
there appears to be little difference between the
algorithms and different source distributions),
or
ffl the message length is small (i.e., less that 1K).
Clearly, if the input distribution is close to an ideal
distribution, it does not pay to reposition. However,
none of our algorithms tries to analyze the input dis-
tribution. The effect of the message length on the
repositioning is illustrated in Figure 9. The figure
shows the percentage difference for the same four
distributions on a 16 \Theta 16 machine and 75 sources
when the message length increases. For a message
size of less than 1K, repositioning pays only for the
cross distribution. As the message size increases, the
benefit of repositioning increases for all distributions.
Not surprisingly, for large message length, the gain
tapers off and decreases for some distributions.
In Section 3 we also proposed to combine the repositioning
with a partitioning approach. We first generate
an ideal source distribution and then create two
Message Length
Percentage
Difference
o- equal
+- cross
*- band
x- blk

Figure

9: The difference between Repos xy source
and Br xy source on different input distributions for
a machine with varying the message
length.
broadcasting problems, each on one half of the ma-
chine. Let Algorithm Part xy source be such a partitioning
algorithm using Br xy source within each
machine half. We have compared Part xy source
against the performance of Repos xy source and
Br xy source. Our results showed that for the Intel
Paragon the partitioning approach hardly ever gives
a better performance than repositioning alone. The
reason lies in the cost of the final permutation. The
exchange of long messages done in the final step dominates
the performance and eliminates the gain obtained
from broadcasting on smaller machines. The
performance of partitioning algorithms could be different
for machines of other characteristics, but we
conjecture that for other currently available MPPs
the outcome will be the same.
6 Conclusions
We described different s-to-p broadcasting algorithms
and analyzed their scalability and performance
on the Intel Paragon. We showed that the
performance of each algorithm is influenced by the
distribution of the source processors and a relationship
between the distribution and the dimension of
the machine. Each algorithm has ideal distributions
and distributions on which the performance
degrades. To reduce the dependence of the performance
on the input distribution we proposed a repositioning
approach. In this approach the given distribution
is turned into an ideal distribution of the target
broadcasting algorithm. We have also compiled
and run our programs under MPI environment, using
MPI point-to-point message passing primitives.
We have observed a performance loss of 2 to 5% in
every implementation.



--R

"CCL: A Portable and Tunable Collective Communication Library for Scalable Parallel Computers,"
"Interprocessor Collective Communication Library,"
"Multiphase Complete Exchange on a Circuit Switched Hypercube,"
"Benchmarking the CM-5 Multicomputer,"
"On the Design and Implementation of Broadcast and Global Combine Operations Using the Postal Model,"
Introduction to Algorithms
"Communication Operations on Coarse-Grained Mesh Architectures,"
"An Architecture for Optimal All-to-All Personalized Communication,"
"Opti- mal Broadcast and Summation in the LogP Model,"
Introduction to Parallel Computing
"Multicast in Hypercube Multiprocessors,"
"Performance Evaluation of Multicast Wormhole Routing in 2D- Mesh Multicomputers,"
"Optimum Broadcasting and Personalized Communication in Hypercubes,"
"Many-to- Many Communication With Bounded Traffic,"
"All-to-all Communication on Meshes with Wormhole Routing,"
--TR

--CTR
Yuh-Shyan Chen , Chao-Yu Chiang , Che-Yi Chen, Multi-node broadcasting in all-ported 3-D wormhole-routed torus using an aggregation-then-distribution strategy, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.9, p.575-589, September 2004
scalability;message-passing MPPs;broadcasting;communication operations