All reduce across multiple reconfigurable dataflow processors
A method for a reconfigurable computing system includes receiving a compute graph for execution on multiple RDPs interconnected with a ring network having R interconnected RDPs. A compute graph with a node specifying a reduction operation for a first and second tensor is detected. The detected compute graph node is partitioned into a compute subgraph corresponding to an RDP of the R interconnected RDPs. A first node is inserted into the compute subgraph that specifies a partial reduction operation for producing a partial reduction result corresponding to a shard of the first tensor and a shard of the second tensor. A second node is inserted for communicating the partial reduction result to an adjacent RDP. A third node is inserted that specifies a reduction operation for producing a total reduction result. A fourth node is inserted for communicating the total reduction result to at least one other RDP.
1 . A computing system, the system comprising:
a host computer comprising a graph optimization module configured to conduct a method comprising:
receiving a compute graph for execution on multiple reconfigurable dataflow processors RDPs, the multiple RDPs being interconnected with a ring network, the ring network having R interconnected RDPs, including a first RDP, and a second RDP adjacent to the first RDP in the ring network, wherein R is an integer value;
detecting a node of the compute graph that specifies a reduction operation for a first tensor and a second tensor;
partitioning the node of the compute graph into a compute subgraph corresponding to the first RDP;
inserting a first inserted node into the compute subgraph that specifies a partial reduction operation for producing a partial reduction result corresponding to a shard of the first tensor and a shard of the second tensor;
inserting a second inserted node into the compute subgraph for communicating the partial reduction result to the second RDP;
inserting a third inserted node into the compute subgraph that specifies a reduction operation for producing a total reduction result for the first tensor and the second tensor; and
inserting a fourth inserted node into the compute subgraph for communicating the total reduction result to the first RDP.
2 . The system of claim 1 , wherein the partial reduction operation comprises a General Matrix Multiplication GeMM operation.
3 . The system of claim 2 , wherein the GeMM operation has a GeMM meta-pipeline stage latency.
4 . The system of claim 1 , wherein the first tensor is sharded to generate R distinct shards of the first tensor, and wherein the second tensor has B distinct slices of the second tensor, each B distinct slice of the second tensor is sharded to generate R distinct shards of the second tensor, each R distinct shard of the second tensor is tiled to generate more than one distinct tiles of the second tensor, and such that a compute unit within an RDP of the R interconnected RDPs receives a distinct tile of the second tensor.
5 . The system of claim 3 , wherein communicating a partial reduction result to the second RDP results in an inter-chip latency for the partial reduction result.
6 . The system of claim 5 , wherein the inter-chip latency for the partial reduction result is less than the GeMM meta-pipeline stage latency.
7 . The system of claim 4 , wherein the RDPs comprise a grid of compute units and a grid of memory units interconnected with a switching array, each compute unit comprising an array of arithmetic units organized into I lanes and J meta-pipeline stages, wherein I is an integer value greater than one, and wherein J is an integer value greater than one.
8 . The system of claim 7 , wherein each distinct shard of the first tensor comprises M distinct rows and each distinct tile of the second tensor comprises N distinct columns, such that each different lane of the I lanes receives a corresponding M distinct row and each different stage of the J meta-pipeline stages sequentially receives a corresponding N distinct column, wherein M is an integer value greater than one, and wherein N is an integer value greater than one.
9 . A computer implemented method, the method comprising:
receiving a compute graph for execution on multiple reconfigurable dataflow processors RDPs, the multiple RDPs being interconnected with a ring network, the ring network having R interconnected RDPs, including a first RDP, and a second RDP adjacent to the first RDP in the ring network, wherein R is an integer value;
detecting a node of the compute graph that specifies a reduction operation for a first tensor and a second tensor;
partitioning the node of the compute graph into a compute subgraph corresponding to the first RDP;
inserting a first inserted node into the compute subgraph that specifies a partial reduction operation for producing a partial reduction result corresponding to a shard of the first tensor and a shard of the second tensor;
inserting a second inserted node into the compute subgraph for communicating the partial reduction result to the second RDP;
inserting a third inserted node into the compute subgraph that specifies a reduction operation for producing a total reduction result for the first tensor and a second tensor; and
inserting a fourth inserted node into the compute subgraph for communicating the total reduction result to the first RDP.
10 . The method of claim 9 , wherein the partial reduction operation comprises a General Matrix Multiplication GeMM operation.
11 . The method of claim 10 , wherein the GeMM operation has a GeMM meta-pipeline stage latency.
12 . The method of claim 9 , wherein the first tensor is sharded to generate R distinct shards of the first tensor, and wherein the second tensor has B distinct slices of the second tensor, each B distinct slice of the second tensor is sharded to generate R distinct shards of the second tensor, each R distinct shard of the second tensor is tiled to generate more than one distinct tiles of the second tensor, and such that a compute unit within an RDP of the R interconnected RDPs receives a distinct tile of the second tensor.
13 . The method of claim 11 , wherein communicating a partial reduction result to the second RDP results in an inter-chip latency for the partial reduction result.
14 . The method of claim 13 , wherein the inter-chip latency for the partial reduction result is less than the GeMM meta-pipeline stage latency.
15 . The method of claim 12 , wherein the RDPs comprise a grid of compute units and a grid of memory units interconnected with a switching array, each compute unit comprising an array of arithmetic units organized into I lanes and J meta-pipeline stages, wherein I is an integer value greater than one, and wherein J is an integer value greater than one.
16 . The method of claim 15 , wherein each distinct shard of the first tensor comprises M distinct rows and each distinct tile of the second tensor comprises N distinct columns, such that each different lane of the I lanes receives a corresponding M distinct row and each different stage of the J meta-pipeline stages sequentially receives a corresponding N distinct column, wherein M is an integer value greater than one, and wherein N is an integer value greater than one.
17 . A computer program product comprising a computer readable storage medium having program instructions embodied therewith, wherein the computer readable storage medium is not a transitory signal per se, wherein the program instructions are executable by a processor to cause the processor to conduct a method comprising:
receiving a compute graph for execution on multiple reconfigurable dataflow processors RDPs, the multiple RDPs being interconnected with a ring network, the ring network having R interconnected RDPs, including a first RDP, and a second RDP adjacent to the first RDP in the ring network, wherein R is an integer value;
detecting a node of the compute graph that specifies a reduction operation for a first tensor and a second tensor;
partitioning the node of the compute graph into a compute subgraph corresponding to the first RDP;
inserting a first inserted node into the compute subgraph that specifies a partial reduction operation for producing a partial reduction result corresponding to a shard of the first tensor and a shard of the second tensor;
inserting a second inserted node into the compute subgraph for communicating the partial reduction result to the second RDP;
inserting a third inserted node into the compute subgraph that specifies a reduction operation for producing a total reduction result for the first tensor and a second tensor;
inserting a fourth inserted node into the compute subgraph for communicating the total reduction result to the first RDP;
generating a file for execution by the RDPs; and
saving the file in a memory of a host computer.
18 . The system of claim 1 , wherein a file is generated for execution by the RDPs, and the file is saved in a memory of the host computer.
19 . The method of claim 9 , wherein a file is generated for execution by the RDPs, and the file is saved in a memory of a host computer.