Collective Communication Optimization: Problem Statement and Use cases

3.1.1. Reliability

Traditional transport layer provides reliable transmission mechanisms, like TCP, QUIC, etc., only for point-to-point communication, and supports best-effort transmission services for multicast and broadcast communication. Therefore, in order to meet the requirement of reliable transmission, the implementations of collective operations like Bcast and AlltoAll are often based on point-to-point operations at hosts.¶

This leads to the waste of host CPU resources caused by repeated packaging and sending, while multiple identical data packets on the same path also constitute redundant traffic and exacerbate network load. To solve these problems, parallel computing networks need a reliable transmission mechanism suitable for collective operations, and cooperating with reasonable traffic engineering and congestion control mechanisms.¶

Collective communication optimization generally uses a network node like a switch to perform the collective operation like Reduce. The network node receives the data from multiple senders and computes the result based on the provided operator, e.g. SUM operator. There are two ways in terms of reliability to ensure the correctness of the collective operations.¶

The first one is to keep using the end-to-end reliability. The intermediate node that performs the 'Reduce' is not considered as an end point that participants in the traditional reliability guarantee. Refer to the figure below, Host 1 to 3 are workers for a Reduce operations, and Host 4 is the parameter server that collects the data from all the workers to perform a SUM computing. The transport session is established between each worker and the parameter server. Switch in the middle performs the in-network aggregation. In case there is any packet loss between any of the workers and switch or between switch and parameter server, end-to-end reliability mechanism like re-transmission would be triggered by end points. The intermediate switch releases the maintance burden of transport session and most of the state maintenance. Consider the scenarios where the data packet is small like in some of the high performance computing. The switch simply keeps a single packet from every worker until it can make the summation computing from all the workers. The state maintained is minimum. It should be considered how the reliability can be efficiently ensured in terms of the fast loss detection and signaling when an intermediate node plays a role. In addition to the reliability considerations, how to ensure the data to be aggregated at the correct intermediate node or nodes should be considered. Considering encryption scenarios, ubiquitous connection encryption (QUIC etc.) make it hard to employ performance enhancing functions.¶

The second one is to treat the intermediate switch as an end point. The reliability is guaranteed between the worker and switch and between switch and parameter server as two independent sessions. That would require the switch to support the full transport function which includes the session establishments and all the state maintenance. It is expected that the lighter transport session maintenance will bring more benefit. In addition, there should be fall back signaling to tolerate the faults. Considering encryption scenarios, If network devices are required to encrypt and decrypt data, it will require a lot of resources, maintain a large number of sessions, and also involve issues such as maintaining secret keys.¶

         +-----+
         |Pkt_1|
         +-----+
+------+
|Host_1+---------+
+------+         |
                 |
         +-----+ |                              +-------+
         |Pkt_2| |  +-------------------------+ |Pkt_Agg|
         +-----+ |  |                         | +-------+
+------+         |  |         Switch          |            +------+
|Host_2+---------+--> (In-Network Aggregation)+----------->|Host_4|
+------+         |  |                         |            +------+
                 |  +-------------------------+
         +-----+ |
         |Pkt_3| |
         +-----+ |
+------+         |
|Host_3+---------+
+------+

3.1.2. Semantic Gap Between Message and Packet

Collective operations offloading utilizes network devices to achieve low computational accuracy and high IO computing tasks, achieving optimization of collective operations. Collective communication optimization devices not only complete packet routing and forwarding, but also need to process transport layer messages. Therefore, the transport layer needs to complete the mapping mechanism between packets and messages, and complete the transmission layer message transmission. Existing transport layers cannot provide this function.¶

Message size will impact the performance of implementation of collective operations. The packet size usually has an upper bound, for example, the jumbo frame of Ethernet is 9.6kB, while message size dose not have limitation and it is determined by applications. For network devices, processing large size messages will incur a lot of overhead, reflected in deep buffer and its Serialization and Deserialization(SerDes) may have much pressure. In addition, it will also impact the message sending rate at the host and thus lower the end-to-end system performance. How to choose the appropriate message size and optimize its processing is still a problem.¶

       Host         Traditional        In-Network         Host
                  Network Devices   Network Devices
 +-------------+                                    +--------------+
 |             |                                    |              |
 | +---------+ |                                    | +----------+ |
 | |   App   | |                  +--------------+  | |   App    | |
 | +---------+ |                  |              |  | +----------+ |
 |             |                  |              |  |              |
++-------------+------------------+--------------+--+--------------++
||             |             Messages            |  |              ||
|| +---------+ |                  | +----------+ |  | +----------+ ||
|| |Transport| |                  | | Message  | |  | | Transport| ||
|| |  Layer  | |                  | |Processing| |  | |  Layer   | ||
|| +---------+ |                  | +----------+ |  | +----------+ ||
||             |                  |              |  |              ||
++-------------+------------------+--------------+--+--------------++
 |             |                  |              |  |              |
 |             | +--------------+ |              |  |              |
++-------------+-+--------------+-+--------------+--+--------------++
||             | |              | |              |  |              ||
|| +---------+ | |              | |              |  | +----------+ ||
|| | Network | | |            Packets            |  | |  Network | ||
|| |  Layer  | | |              | |              |  | |   Layer  | ||
|| |  (IB,   | | |              | |              |  | |   (IB,   | ||
|| | TCP/IP) | | | +----------+ | | +----------+ |  | |  TCP/IP) | ||
|| +---------+ | | |          | | | |          | |  | +----------+ ||
||             | | |          | | | |          | |  |              ||
|| +---------+ | | |  Packet  | | | |  Packet  | |  | +----------+ ||
|| |  Link   | | | |Forwarding| | | |Forwarding| |  | |   Link   | ||
|| |  Layer  | | | |          | | | |          | |  | |   Layer  | ||
|| |(IB Link,| | | |          | | | |          | |  | | (IB Link,| ||
|| |   Eth)  | | | +----------+ | | +----------+ |  | |    Eth)  | ||
|| +---------+ | |              | |              |  | +----------+ ||
||             | |              | |              |  |              ||
++-------------+-+--------------+-+--------------+--+--------------++
 +---------+---+ +-----+----+---+ +----+----+----+  +-----+--------+
           |           ^    |          ^    |             ^
           +-----------+    +----------+    +-------------+

3.1.3. Blocking and Non-blocking Communications

Parallel computing communication operators can be divided into two categories based on whether to wait for message feedback results before proceeding with the next step of computation: blocking and non-blocking. Blocking collective operations will experience process blocking until communication is completed. Non-blocking operations allow communication to be handled by the backend, and communication and computation can overlap. Parallel computing networks need to support two types of communication methods simultaneously, and for blocking communication, it is even more necessary to use methods such as in-network computing technology to to optimize collective communication performance.¶

3.2.1. In-Network Computing Primitives

After supporting collective operations offloading, collective communication library needs to be expanded to not only support end-to-end mode, but also end-to-network communication modes, whitch means suporting in-network processing/computing functions.¶

The implementation of the offloaded collective operations relies on the capabilities provided by physical network devices, known as in-network computing primitives. Currently, most online computing devices use programmable network devices such as P4(Programming Protocol-independent Packet Processors) and NPL(Network Programming Language). These programmable switches are not powerful enough to program non-trivial application-layer behavior. And their platforms are too heterogeneous to manage. We need to standardize the in-network computing primitives that network devices can provide, including data types, operations, etc. Based on the standard in-network computing primitives, we need to implement parallel in-network computing communication operators.¶

3.2.2. Topology Awareness

In data center, fat tree or CLOS topology is widely used. There are some full meshed network topology as well.¶

As the scale of parallel computing clusters continues to increase, it is difficult to achieve optimal transmission performance solely through automatic convergence of traditional routing protocols. It is necessary to cooperate with topology-aware algorithms to explore complex topologies, and complete path planning, traffic optimization, etc. However, existing topology-aware algorithms do not consider collective operations offloading scenarios and need to be modified to realize end-network cooperation, meeting the requirements of end-to-end path planning and traffic optimization.¶