TECHNICAL FIELD

The present disclosure relates to network devices. More specifically, the embodiments set forth below describe network devices configured to perform computations associated with multiple processors participating in a shared global memory system.

BACKGROUND

While many scientific applications rely on collective communication primitives, these primitives are also key to scalability in distributed machine learning/deep learning (ML/DL) training algorithms. For example, a training algorithm can be distributed among a plurality of graphics processing units (GPUs) or other parallel processing units configured to compute multiple results in parallel. Each GPU processes a batch of input samples on a model that is replicated across many GPUs. Once each GPU calculates the parameter updates, the parameters need to be collectively aggregated across all participating GPUs before the parameters are applied to local model parameters in a particular GPU.

A current solution can be implemented in a software library that provides implementations for the most common collective communication primitives, such as a broadcast primitive, an all-gather primitive, and reduction primitives. A reduction primitive is implemented in the software library by performing the reduction operation in a ring-scheme where each GPU sends a chunk of data to the next GPU in the ring. After one pass through the ring, each GPU holds a portion of the fully reduced result. Then, a second pass through the ring is required to distribute the reduction result so that every GPU holds the final reduction result.

However, although the bandwidth of the ring-scheme algorithm is sufficient, the latency is proportional to the number of GPUs. Furthermore, every step in the ring requires a costly synchronization mechanism in the form of a system-wide memory fence with a subsequent flag-write operation to signal data validity for the consumer. Measurements have shown that each synchronization can take multiple microseconds, especially limiting performance for small message sizes and larger scale. This limits the ability of the algorithm to scale with large ML/DL training applications because with every additional GPU added to the task, the compute load on each GPU decreases and communication latency quickly becomes a bottleneck. Thus. there is a need for addressing these issues and/or other issues associated with the prior art.

SUMMARY

A method, computer readable medium, and system are disclosed for implementing a pull mechanism associated with scalable, in-network computations for massively parallel shared memory processors. The pull mechanism refers to a technique for coordinating a computation among a plurality of processors in communication over a network, where at least a portion of the computation is off-loaded from the processors to one or more network devices.

In some embodiments, a method is described for performing in-network computations using a pull mechanism. The method is performed by a network device in communication with a plurality of endpoints via a network, and the method includes the steps of: receiving a pull request associated with a collective communication primitive; identifying one or more participating endpoints associated with the pull request; forwarding the pull request to each of the one or more participating endpoints via a multicast capability of the network device; for each response associated with the collective communication primitive received by the network device, combining a payload of the response with an intermediate result stored in an entry of a table maintained by the network device; and generating a pull response that is forwarded to at least one participating endpoint. A payload of the pull response includes the intermediate result calculated based on one or more responses associated with the collective communication primitive received at the network device from at least one participating endpoint.

In some embodiments, the network device comprises one of a switch, a router, or a network interface controller (NIC).

In some embodiments, the identifying step comprises: reading a network address from a header of the pull request, querying a multicast region table based on the network address, and identifying the one or more participating endpoints based on information included in a corresponding entry of the multicast region table. The multicast region table maps ranges of addresses in a shared global address space to multicast regions.

In some embodiments, each of the participating endpoints comprises a parallel processing unit and a memory coupled to the parallel processing unit. The memory in each participating endpoint stores an address translation table that maps network addresses in the shared global address space to a local address space for the participating endpoint.

In some embodiments, the table is stored in a cache unit of the network device. The method further includes the steps of: responsive to a cache miss based on the querying, allocating the entry in the cache unit for the pull request, and initializing the intermediate result in the entry to equal a value included in a payload of the pull request.

In some embodiments, the method further includes the steps of: determining that the cache unit is full, identifying a candidate entry in the cache unit based on an eviction policy, generating a partial response for the candidate entry, and evicting the candidate entry from the cache unit. The partial response includes an indication of at least one of the following: a number of participating endpoints that contributed to a partial result included in the partial response, or a list of endpoint identifiers for the number of participating endpoints that contributed to the partial result included in the partial response.

In some embodiments, at least one response received by the network device is received from a second network device. The payload of the at least one response includes an intermediate result corresponding to an in-network computation corresponding to one or more participating endpoints connected, either directly or indirectly, to the second network device.

In some embodiments, the pull request comprises a data unit conforming to an Ethernet frame, and wherein the Ethernet frame includes an Internet Protocol header.

In some embodiments, the payload of each response comprises a first format and the intermediate result is stored in a second format. A precision of the second format is greater than a precision of the first format. The formats can include integer, fixed-point, or floating-point formats having different bit widths.

In some embodiments, the collective communication primitive is associated with a reduction operation. A reduction operator is specified in at least one of the pull request or a multicast region table.

In some embodiments, a network device in communication with a plurality of endpoints via a network is described. The network device includes: a number of ports connected to the network; a memory storing a table; and logic. The logic can be included in one or more ports or, alternatively, be implemented externally to the ports and connected thereto. The logic is in communication with the memory and is configured to: receive a pull request associated with a collective communication primitive; identify one or more participating endpoints associated with the pull request; forward the pull request to each of the one or more participating endpoints via a multicast capability of the network device; for each response associated with the collective communication primitive received by the network device, combine a payload of the response with an intermediate result stored in an entry of a table in the memory; and generate a pull response that is forwarded to at least one participating endpoint. A payload of the pull response includes the intermediate result calculated based on one or more responses from at least one participating endpoint.

In some embodiments, the logic includes: a crossbar, and at least one arithmetic logic unit (ALU) configured to perform computations to calculate the intermediate result stored in the entry.

In some embodiments, the logic is configured to identify the one or more participating endpoints by: reading a network address from a header of the pull request, querying a multicast region table based on the network address, and identifying the one or more participating endpoints based on information included in a corresponding entry of the multicast region table. The multicast region table maps ranges of addresses in a shared global address space to multicast regions.

In some embodiments, the memory comprises a cache unit and the table is implemented in the cache unit. The logic further configured to: responsive to a cache miss based on the querying, allocate the entry in the cache unit for the pull request, and initialize the intermediate result in the entry to equal a value included in a payload of the pull request.

In some embodiments, the logic is further configured to evict a candidate entry from the cache unit based on an eviction policy.

In some embodiments, at least one response received by the network device is received from a second network device. The payload of the at least one response includes an intermediate result corresponding to an in-network computation corresponding to two or more participating endpoints connected, either directly or indirectly, to the second network device.

In some embodiments, the payload of each response comprises a first format and the intermediate result is stored in a second format. A precision of the second format is greater than a precision of the first format.

In some embodiments, the collective communication primitive is associated with a reduction operation. A reduction operator is specified in at least one of the pull request or a multicast region table.

In some embodiments, a non-transitory computer-readable media storing computer instructions is described. The instructions, when executed by one or more processors, cause the one or more processors to perform the steps of: receiving, at a network device, a pull request associated with a collective communication primitive; identifying one or more participating endpoints associated with the pull request; forwarding the pull request to each of the one or more participating endpoints via a multicast capability of the network device; for each response associated with the collective communication primitive received by the network device, combining a payload of the response with an intermediate result stored in an entry of a table; and generating a pull response that is forwarded to at least one participating endpoint. A payload of the pull response includes the intermediate result calculated based on one or more responses from at least one participating endpoint.

