title: $k$-ported vs. $k$-lane Broadcast, Scatter, and Alltoall Algorithms
authors: Jesper Larsson Träff
text: 
  
  
  
  
  
  k-ported k-lane Broadcast, Scatter, and Alltoall
    Algorithms
      Jesper Larsson Träff
  
  TU Wien, Faculty of Informatics, Institute of Computer Engineering 191-4
  
  Favoritenstrasse 16/3rd floor, 1040 Vienna, Austria
      December 30, 2023
  =======================================================================================================================================================
  
  
    In k-ported message-passing systems, a processor can
    simultaneously receive k different messages from k other
    processors, and send k different messages to k other processors
    that may or may not be different from the processors from which
    messages are received. Modern clustered systems may not have such
    capabilities. Instead, compute nodes consisting of n processors
    can simultaneously send and receive k messages from other nodes,
    by letting k processors on the nodes concurrently send and receive
    at most one message. We pose the question of how to design good
    algorithms for this k-lane model, possibly by adapting algorithms
    devised for the traditional k-ported model.
  
    We discuss and compare a number of (non-optimal) k-lane algorithms
    for the broadcast, scatter and alltoall collective operations (as
    found in, , MPI), and experimentally evaluate these on a small
    36× 32-node cluster with a dual OmniPath network (corresponding to
    k=2). Results are preliminary.
  
  
  
  
  § INTRODUCTION
  
  
  We pose the problem of designing good collective communication
  algorithms for modern high-performance clusters. By this pompous
  opener, we mean the following.  In k-ported message-passing systems,
  a processor can simultaneously receive k different messages from k
  other processors, and send k different messages to k other
  processors that may or may not be different from the processors from
  which messages are received. In this model, many standard collective
  communication operations (broadcast, allgather, reduction, scatter,
  etc.) have been studied, and for many operations, algorithms designed
  for one-ported (bidirectional, send-receive) communication extend
  nicely and close to
  optimally <cit.>.  Modern
  clustered systems may not have such strong capabilities per
  processor-core. Instead, compute nodes consisting of n processors
  can simultaneously send and receive k messages from other nodes, by
  letting k processors on the nodes concurrently send and receive at
  most one message. For instance, compute nodes may have several
  connections to the communication network, multiple network switches,
  and in general offer more off-node network bandwidth than can be
  saturated by a single processor-core on the compute node. We call such
  capabilities multi-lane, and the k-lane model allows
  k simultaneous communication operations per n-processor-core
  compute node, possibly concurrently with communication inside the
  compute node via shared memory.
  
  We examine two approaches to the design of good algorithms for
  k-lane systems. One is based on splitting the problem data across
  n process-cores and apply standard one-ported algorithms
  concurrently. This approach has been pursued in our previous
  work <cit.>. The other approach
  adapts k-ported algorithm to the k-lane model by additional
  communication on the compute nodes to distribute problem data to k
  node local processor-cores. We make the discussion concrete by
  describing initial algorithms for the broadcast, scatter and alltoall
  collective operations as found in the MPI operations ,
  and  <cit.>. We have implemented these
  algorithms and compare against standard k-ported
  algorithms <cit.> and the
  corresponding native MPI library implementations on a small, 36×
  32-core cluster with dual-switch communication network and different
  MPI libraries.
  
  Our experimental results so far are inconclusive. Efficiently
  exploiting k-lane communication seems to require also strong
  shared-memory support and efficient communication on the compute nodes
  as well as concurrent on- and off-node communication. Also, both
  algorithms and the implementations in MPI can be
  improved. Nevertheless, we think the k-lane model deserves further
  investigation towards better balancing on- and off-node
  communication capabilities for improved performance of collective
  communication operations.
  
  
  
  § ALGORITHMS
  
  
  
  We assume a high-performance computing system with p processor-cores
  located on N compute nodes, each with n processor-cores (on one or
  more sockets, which will play no role at the moment), such that
  p=Nn.  Each processor has a unique rank i, and ranks are
  consecutive, 0≤ i <p.
  
  We consider algorithms for broadcast (mostly for small data sizes),
  scatter and alltoall. In the broadcast operation, c data
  elements from a designated root processor r has to be disseminated
  to all p processors. In the scatter operation, the designated
  root processor has an individual block of data b_i to be
  communicated to each of the (other) processors with each block being
  of size c/p data elements. The gather operation is the dual
  of the scatter operation, and not treated further here. In the
  personalized alltoall operation each processor has an
  individual block of data of size c/p elements to be communicated to
  each of the (other) processors; equivalently, each processor has to
  receive a block of c/p elements from each of the (other) processors.
  In MPI, the regular broadcast, scatter and alltoall operations are
  performed by the collective operations , , and
  called on a communicator with p MPI
  processes <cit.>.
  
  
  
   §.§ Standard k-ported algorithms
  
  
  
  A straightforward divide and conquer approach leads to k-ported
  algorithms for both broadcast and scatter operations, see,
  , <cit.>.
  
  Let p be the number of processors, and let k, k≥ 1 be the
  number of communication ports per processor, which means that a
  processor can be involved in k send and receive operations at a
  time. Each processor i will maintain a range of processors [s,e-1]
  to which it belongs, 0≤ i<e, and a root processor r, s≤
  r<e also in the range. Initially, all processors start out with the
  same range [0,p-1] and r being the given root of the broadcast or
  scatter operation. In the divide step, each processor divides its
  range [s,e-1] into k+1 roughly equal-sized subranges
  [s_i,s_i+1-1], i=0,1,k, s_i<s_i+1, differing in size by at
  most one. The root processor r which belongs to one of the
  subranges, say [s_j,s_j+1-1] sends data to a new, local root r_i
  in each of the other subranges. For instance, r_i could be chosen as
  s_i (except for the range i=j). Each processor continues to the
  next divide step with the range [s_i,s_i+1-1] and local root
  r_i∈ [s_i,s_i+1-1] to which it belongs.  A processor terminates
  when its range consists only of the processor itself, at which point
  at the latest it will have become a local root and received data from
  some other processor.
  
  For the broadcast algorithm, a (local) root processor always sends all
  (the same) c data elements to the new subroots. For the scatter
  algorithm, the root sends the data blocks [b_s_ib_s_i+1…
    b_s_i+1-1] to the local root r_i of subrange [s_i,s_i-1-1].
  
  Obviously, these algorithms take log_k+1p communication
  rounds.  Broadcast in each round sends c data elements, while
  scatter sends c elements in total over all communication rounds.
  Thus, this k-ported broadcast algorithm is only good for small
  element counts c, since broadcast can be done in O(log p+c)
  rounds and communication time by other, different
  algorithms <cit.>. The scatter algorithm sends
  the total number of data elements c only once from the root
  processor, and is thus round and message size optimal.
  
  For the alltoall operation, the straightforward algorithm does
  p/k communication rounds, in each of which each processor
  sends its k blocks of data to the k “next” processors and
  receives its blocks from the “previous” k-processors. This
  algorithm is message size optimal in the sense that each block is sent
  and received exactly once. Message-combining algorithms and
  implementations <cit.> can reduce the number of
  communication rounds (to log_k+1 p) at the cost of
  sending and receiving more than c data elements.
  
  
  
   §.§ k-lane algorithms: Approach problem splitting
  
  
  A straight-forward approach to exploit multi-lane communication
  capabilities is to split the collective communication problem to be
  solved on c data elements into n (similar) independent subproblems
  to be solved on c/n data elements. The splitting is performed
  concurrently on one, more, or all of the N compute
  nodes. With k-lane communication capabilities, the n independent
  subproblems on c/n data elements can ideally be solved with a
  speed-up of a factor of k. The overall speed-up is determined by
  this, and the amount of work and time to be spent in the splitting of
  the c element problem on the compute nodes.
  
  Concretely, for the broadcast problem, the compute node at which the
  designated broadcast root r is residing splits the c data elements
  over the n processors on the node into blocks of n/c elements (one
  block per processor) by a scatter operation on the node. After that,
  n concurrent broadcast operations each on N processors on
  different nodes are performed. To complete, on all nodes, the blocks of
  c/n elements need to be collected together to a block of c
  elements which must be distributed to all processors on the node. This
  is a collective allgather operation. Assuming optimal algorithms for
  all component operations (scatter on root node, broadcast between
  nodes, allgather on compute nodes), this algorithm has an overhead
  penalty by the final allgather operations (extra communication rounds,
  extra data communication on the compute nodes). A scatter algorithm,
  in contrast, following the same idea, is optimal in terms of
  communication rounds and data communicated. First, a scatter operation
  is done on the node on which the designated root processor r resides
  into n scatter problems of c/n data elements.  These n scatter
  problems are solved concurrently over the N nodes, leaving each
  processor with a data block of c/(nN)=c/p data elements. Assuming
  standard (optimal, one-ported) logarithmic round scatter algorithms for the
  component problems, the total number of communication rounds is
  log n+log N≤log p+1, which is
  at most one round off from optimal. The amount of data leaving the
  root node is c-c/N.
  
  The alltoall operation can also be implemented with this approach by
  combining blocks to the same node into larger blocks of n c/p = c/N
  data elements. This is done by concurrent alltoall operations on all
  compute nodes, followed by n independent alltoall operations over
  the N nodes. Thus, the complete data is communicated twice.
  
  These algorithms are called full-lane algorithms
  in <cit.> where they are described
  in full detail with experimental results. The aim is a speed-up of a
  factor of k on systems utilizing k physical lanes instead of just
  one physical lane. Whether this is possible depends on the speed-up of
  the part of the algorithms that is performed on the compute nodes.
  
  
  
   §.§ k-lane algorithms: Approach k-ported algorithm reuse
  
  
  Another approach to designing good algorithms for multi-lane systems is
  to adapt and reuse algorithms designed for multi-ported systems. The
  idea is that send and receive operations to and from k other
  processors by a single processor is split among k processors on a
  compute node that together perform the communication operations of a
  single, k-ported processor. This in most cases entails (additional)
  communication on the nodes to split and assemble larger data blocks.
  
  For (non-pipelined) tree algorithms as often used for broadcast (for
  small problem sizes) and scatter, we propose a construction that makes
  use of standard k-ported algorithms. We exemplify with
  broadcast. Let r be the root processor.  We let r send data first
  to k-1 non-root processors on the same node, for instance by an
  efficient broadcast algorithm for the communication capabilities of
  the node. Now, k processors on the root node have the data, and can
  in the following step concurrently send data to k other nodes. This
  is done using the pattern of the k-ported algorithm, with each
  processor taking the role of one port, and sending data to, say, the
  first processor of a new node. The first time a processor on a
  non-root node receives data, it first broadcasts the data to k other
  processors on the node, which then continue as in the k-ported
  algorithm. The number of steps of the k-lane algorithm derived in
  this way from a k-ported algorithm is at most twice that of the
  k-ported algorithm, if we count the node local broadcast over k
  processors as one step. Finally, to complete the broadcast, each of
  the k local root processors on each of the compute nodes, broadcast
  their data block to n/k (disjoint) processors on the node. The
  k-lane scatter algorithm can be adopted in the same way. A receiving
  processor on a node scatters to k-1 processors which then
  concurrently do the k send operations of a single processor in the
  k-ported algorithm to processors on other nodes.
  
  For alltoall, a k-lane algorithm could look as follows: In N-1
  communication rounds, all n processors on a compute node
  concurrently send their n data blocks to processors on the “next”
  node and receive their n data blocks from processors on the
  “previous” node. In a final round, all processors on each compute
  node exchanges their blocks with the other processors on the node
  (on-node, local alltoall). The communication in a round is done in n
  steps in such a way that in each step the n processors on a node
  send and receive from different processors. This algorithm will in
  each of the N-1 rounds utilize the full off-node communication
  bandwidth possible with k lanes.
  
  
  
   §.§ A k-lane model
  
  
  What can be expected from algorithms designed as outlined above? For
  the broadcast and scatter problems, both approaches entail
  communication on the compute nodes, as well as k- or n-way
  concurrent communication between nodes. For n-way communication
  between nodes, we can possibly and realistically assume,
  see <cit.>, that bandwidth is
  equally shared among the processors, that is a k/n-way increase
  (with k) per processor. In order for a k-lane algorithm to exhibit
  a k-fold speed-up, the part of the problem solved on the nodes must
  also be sped up by a factor of k. Whether this is possible also
  depends on the communication performance and the communication
  capabilities on the compute nodes.
  
  Communication between processors on the same node is typically via
  shared memory. How much communication can the shared memory sustain?
  Can all processors communicate at the same time achieving the same
  (memory) bandwidth as when only one processor is reading and writing
  from and to the memory? Is compute node communication like a fully
  connected network with some number k' of simultaneous communication
  ports? How large is k' compared to the number of lanes k? Can
  communication on the node and off the node be done simultaneously? Is
  the bandwidth (and latency) for off-node communication much different
  from the shared-memory bandwidth for node local communication (often,
  they are in the same ballpark)? Experimental work is needed to
  determine reasonable assumptions; the results in
  Section <ref> may provide some useful information.
  
  Another way to pose the question is: What would be required from the
  node local communication, bandwidth and capability wise, in order to
  make it possible to design algorithms with a provable speed-up of k?
  
  
  
  § IMPLEMENTATIONS
  
  
  We have implemented the k-ported algorithms, the full-lane
  algorithms, and the adapted k-lane algorithms described in
  Section <ref> in MPI. The code is available from the
  author.
  
  To perform k-ported communication, we post k non-blocking MPI send
  and/or receive operations, followed by an , and assume that
  the MPI library will be able to use the available ports for the
  processor effectively. For the adapted k-ported algorithms, the
  compute node local broadcast and scatter operations are done by the
  available and operations. The adapted broadcast
  implementation does a full to all processors on the node
  when a block of data is received by the local root, and not a k-way
  broadcast followed by k n/k-way broadcasts. This could,
  theoretically (depending on model and implementation), slow down the
  implementation. 
  
  
  
  § EXPERIMENTAL RESULTS
  
  
  
  
  
  We have conducted a number of experiments, comparing the algorithms
  against each other and against the native MPI library implementations
  of , and on current, standard MPI
  libraries. The results listed here have been collected on our own
  small 36× 32-core cluster described in
  Table <ref>. This systems has powerful, multi-lane,
  off-node communication capabilities: Each of the two sockets on the
  shared-memory compute nodes has a connection to an own OmniPath
  network (dual-network). Thus, at least two processors (or MPI
  processes), possibly more, can at the same time communicate with
  processors (or processes) on other nodes at the same cost as when only
  one processor (or process) is communicating. For the MPI
  implementations, we assume that processes are placed alternatingly on
  the two sockets, such that, , MPI processes with rank 0 and rank 1
  are place on different sockets, and each close to the network
  interface on the corresponding socket.
  
  All experiments have been conducted on the full system with N=36
  (nodes) and n=32 (processor-cores per node). For the k-ported and
  the adapted k-lane implementations, we have used k=1,2,3,4,5,6 for
  the number of virtual lanes. We have used three different MPI
  libraries, namely , , and .
  
  
  
   §.§ Compute node network performance, N=1,n=32 N=32,n=1
  
  
  An initial experiment illustrates the differences in capabilities
  between communication on the compute nodes and between compute
  nodes. We perform an alltoall operation on p=32 MPI processes,
  either all on a single compute node (N=1, n=32), or on N=32
  compute nodes with one MPI process on each (N=32,n=1). We use either
  the k-ported alltoall implementation described in
  Section <ref> or the native MPI library
  implementation. For the k-ported experiment, we choose
  k=32 which just means that each MPI process posts k=32
  non-blocking send and receive operations over p/k
  communication rounds. As the broadcast experiments will show
  (Section <ref>), this performs better than
  using blocking send-receive operations.
  
  The count c is the number of data elements per process. Data
  elements are here .  For the running times (in μ-seconds,
  measured with and ), we report both average and
  minimum time of the slowest process over repetitions with
  initial, not measured warm-up repetitions.
  
  The results with in are shown in
  Table <ref> and
  Table <ref>.
  
  
  
  
  
  The results with in are shown
  Table <ref> and
  Table <ref>.
  
  
  
  
  
  The results with are shown in
  Table <ref> and
  Table <ref>.
  
  
  
  
  
  For all three MPI libraries, the difference between alltoall on the
  node and across nodes is considerable, but also varies greatly between
  the libraries, most dramatically for the k-ported alltoall
  implementations for where the difference is about a
  factor of 10 for larger problems. Also, the simple k-ported
  implementation with n=32 non-blocking MPI send and receive
  operations is in most cases (considerably) better for alltoall
  communication on a compute note than the MPI library native
  collective.
  
  
  
  
  
   §.§ Broadcast
  
  
  
  We compare the k-lane and the k-ported broadcast implementations
  against the full-lane implementation, and the native for the
  three different MPI libraries, and try with k=1,2,3,4,5,6 virtual
  lanes.  The count c is the number of data elements per process. Data
  elements are here . For the running times (in μ-seconds,
  measured with and ), we report both average and
  minimum time of the slowest process over repetitions with
  initial, not measured warm-up repetitions.
  
  The broadcast results with are shown in
  Table <ref>, Table <ref>,
  Table <ref>, Table <ref> and
  Table <ref>.
  The results for the k-lane algorithms are disappointing. The
  completion overall (for all/most counts) increase with the number of
  lanes used for off-node communication. The k-ported algorithm is for
  all k better than the k-lane algorithm, for large counts by a
  factor of more than 2. The best algorithm here is the full-lane
  algorithm, which outperforms the native by a factor of
  about 5 for the largest counts.
  
  
  
  
  
  
  
  
  
  
  
  The broadcast results with are shown in
  Table <ref>,
  Table <ref>,
  Table <ref>,
  Table <ref> and
  Table <ref>. The results are qualitatively
  similar to those for the library, with again the
  full-lane algorithm being considerably better than . For
  , is terrible for small c, and needs to be
  repaired or tuned better (algorithm selection).
  
  
  
  
  
  
  
  
  
  
  
  The broadcast results with are shown in
  Table <ref>,
  Table <ref>,
  Table <ref>,
  Table <ref> and
  Table <ref>.
  From the k-lane algorithm perspective this MPI library gives the
  most interesting performance results. The running time decrease with
  increasing k, with overall best performance for k=5,6. In absolute
  terms, the k-ported algorithm performs much better, though, for
  large counts, but performance seems largely independent of the chosen
  k. Also here, the full-lane implementations performs the best, but
  the difference to the native is smaller than for the other
  libraries. is by far the best for small c.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Scatter
  
  
  We compare the k-lane and the k-ported scatter implementations
  against the full-lane implementation, and the native for
  the three different MPI libraries, and try with k=1,2,3,4,5,6
  virtual lanes.  The count c is the number of data elements per
  process. Data elements are here .  For the running times (in
  μ-seconds, measured with and ), we report
  both average and minimum time of the slowest process over repetitions with initial, not measured warm-up repetitions.
  
  The scatter results with are shown in
  Table <ref>, Table <ref>,
  Table <ref>, Table <ref>
  and Table <ref>. The k-lane results are
  disappointing, with slightly increasing running times with increasing
  k. The k-ported algorithm fare better, with small, but significant
  decreases in running times with increasing k. This is contradictory
  to our expectations. Both algorithms are significantly better,
  though, than both full-lane algorithm and .
  
  
  
  
  
  
  
  
  
  
  
  The scatter results with are shown in
  Table <ref>,
  Table <ref>,
  Table <ref>,
  Table <ref> and
  Table <ref>.
  The results are comparable to the results with .
  
  
  
  
  
  
  
  
  
  
  
  The scatter results with are shown in
  Table <ref>,
  Table <ref>,
  Table <ref>,
  Table <ref> and
  Table <ref>.  The results are comparable to
  the results with and .
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Alltoall
  
  
  We compare the k-lane with k=32 and the k-ported alltoall with
  k=1,2,3,4,5,6 implementations against the full-lane implementation,
  and the native for the three different MPI libraries.
  The count c is the number of data elements per process. Data
  elements are here .  For the running times (in μ-seconds,
  measured with and ), we report both average and
  minimum time of the slowest process over repetitions with
  initial, not measured warm-up repetitions.
  
  In the k-lane algorithm where all processors on a node send to all
  processors on another “next” node and receives from all processors
  on a different “previous” node, k is not a parameter in the
  implementation. There is therefore only one experiment in the tables
  for the k-lane algorithms.
  
  The alltoall results with are shown in
  Table <ref>, Table <ref>,
  Table <ref> and
  Table <ref>. The k-lane algorithm is always
  significantly better than the k-ported algorithm. The results with
  the k-ported algorithm shows significantly decreasing running times
  with increasing k, which simply means a larger number of concurrent,
  non-blocking send and receive operations. The results clearly show
  that more non-blocking send-receive operations (up to some limit) is
  beneficial to avoid delays. The number of non-blocking operations is
  bounded by the small constant k. The best algorithm for small
  problem sizes is the full-lane algorithm, which is also significantly
  better than .
  
  
  
  
  
  
  
  
  
  The alltoall results with are shown in
  Table <ref>,
  Table <ref>,
  Table <ref> and
  Table <ref>. The results are similar to
  the results with .
  
  
  
  
  
  
  
  
  
  The alltoall results with are shown in
  Table <ref>,
  Table <ref>,
  Table <ref> and
  Table <ref>.  The results are similar to
  the results with and .
  
  
  
  
  
  
  
  
  
  
  
  
  
  § CONCLUSION
  
  
  This note discussed the k-lane communication model in which k
  processors on a compute node can communicate simultaneously without
  communication degradation, and raise the question of how to design
  algorithms for standard, collective operations that can exploit these
  capabilities. The k-lane model is different from the often used,
  more powerful k-ported model, in which each processor can at
  a time be involved in up to k communication operations. Different
  approaches to designing good k-lane algorithms for broadcast,
  scatter and alltoall were explored. Another, possible approach using
  dynamic programming to construct optimal trees as in
  <cit.> was not discussed here.
  Unfortunately, the results so far are inconclusive, with rarely any
  definite advantage over standard k-ported implementations, even for
  k=1. The results, as is often the case, however, show many instances
  where the native MPI library implementations of the collective
  operations (, , ) can easily be
  improved, and sometimes quite considerably.  We think it
  deserves to explore the k-lane model further.
  
  plain
   
  
  