Distributed physical processing of matrix sum operation

Patent metadata

Field	Value
Publication number	US-11010202-B2
Application number	US-201916533588-A
Country	US
Kind code	B2
Filing date	Aug 6, 2019
Priority date	Aug 6, 2019
Publication date	May 18, 2021
Grant date	May 18, 2021

Abstract

A specification of an operation to perform one or more element-wise sums of specified portions of a matrix is received. The specification of the operation is analyzed to select a type of processing load partitioning to be applied. Based on the selected type of processing load partitioning to be applied, processing required to perform the operation is partitioned across a plurality of physical processing elements in parallel. The partitioned processing is distributed to the physical hardware processing elements to perform in parallel the element-wise sums of the specified portions of the matrix.

First claim

What is claimed is:

1. A method, comprising:
receiving a specification of an operation to perform one or more element-wise sums of specified portions of a matrix;
analyzing the specification of the operation to select a type of processing load partitioning to be applied;
based on the selected type of processing load partitioning to be applied, partitioning processing associated with performing the operation across a plurality of physical processing elements in parallel, wherein:
partitioning the processing associated with performing the operation includes determining a size of each corresponding subset of the plurality of physical processing elements assigned to each corresponding partition of the matrix based proportionally on a number of matrix elements included in the corresponding partition of the matrix, and
each corresponding partition of the matrix is associated with a different output element of the operation; and

distributing the partitioned processing to the plurality of physical processing elements to perform in parallel the one or more element-wise sums of the specified portions of the matrix.

2. The method of claim 1 , further comprising producing one or more output elements associated with the operation.

3. The method of claim 1 , wherein the specification includes a first vector indicating indices of the matrix to be included in the operation.

4. The method of claim 3 , wherein the specification further includes a second vector indicating groupings of indices of the first vector.

5. The method of claim 1 , wherein analyzing the specification to select the type of processing load partitioning to be applied includes determining whether a computation metric value meets a specified threshold.

6. The method of claim 5 , wherein the computation metric value is based at least in part on computational work per output element of the operation.

7. The method of claim 6 , wherein in response to a determination that the computation metric value does not meet the specified threshold, the selected type of processing load partitioning to be applied is associated with assigning a specified portion of the physical processing elements to each group of indices associated with an entry in a lengths vector associated with the operation.

8. The method of claim 1 , wherein at least one of the physical processing elements is a field programmable gate array, an application specific integrated circuit, or a central processing unit.

9. The method of claim 1 , wherein partitioning the processing associated with performing the operation includes balancing computational workloads for a set of output elements of the operation across at least a portion of the physical processing elements.

10. The method of claim 1 , wherein partitioning the processing associated with performing the operation includes assigning each corresponding subset of the plurality of physical processing elements for each output element of the operation in proportion to a lengths vector value associated with each output element.

11. The method of claim 1 , wherein partitioning the processing associated with performing the operation includes grouping different sets of output elements of the operation such that the different sets require equal amounts of computational resources.

12. The method of claim 1 , wherein partitioning the processing associated with performing the operation utilizes at least one of the following partitioning algorithms: extended greedy algorithm, greedy heuristic, or Karmarkar-Karp heuristic.

13. The method of claim 1 , wherein distributing the partitioned processing to the physical processing elements includes using a network to access the physical processing elements.

14. The method of claim 1 , wherein the physical processing elements are communicatively connected via a computer network.

15. The method of claim 1 , wherein determining the size of each corresponding subset of the plurality of physical processing elements assigned to each corresponding partition of the matrix includes determining a corresponding value in a lengths vector that is part of the specification and that indicates a relative computational load of each corresponding partition of the matrix.

16. The method of claim 1 , wherein each corresponding subset of the plurality of physical processing elements assigned to each corresponding partition of the matrix includes a master processing element that handles coordination tasks.

17. A system, comprising:
a processor configured to:
receive a specification of an operation to perform one or more element-wise sums of specified portions of a matrix;
analyze the specification of the operation to select a type of processing load partitioning to be applied;
based on the selected type of processing load partitioning to be applied, partition processing associated with performing the operation across a plurality of physical processing elements in parallel, wherein:
the processor is configured to partition the processing associated with performing the operation including by being configured to determine a size of each corresponding subset of the plurality of physical processing elements assigned to each corresponding partition of the matrix based proportionally on a number of matrix elements included in the corresponding partition of the matrix, and
each corresponding partition of the matrix is associated with a different output element of the operation; and

distribute the partitioned processing to the plurality of physical processing elements to perform in parallel the one or more element-wise sums of the specified portions of the matrix; and

a memory coupled to the processor and configured to provide the processor with instructions.

18. A method, comprising:
receiving a specification of an operation to perform one or more element-wise sums of specified portions of a matrix;
analyzing the specification of the operation to select a type of processing load partitioning to be applied;
based on the selected type of processing load partitioning to be applied, partitioning processing associated with performing the operation across a plurality of physical processing elements in parallel, wherein partitioning the processing associated with performing the operation includes assigning computational tasks to the plurality of physical processing elements wherein assigning the computational tasks to the plurality of physical processing elements includes tasking each physical processing element of the plurality of physical processing elements with computing a partial contribution to each output sum of the operation; and
distributing the partitioned processing to the plurality of physical processing elements to perform in parallel the one or more element-wise sums of the specified portions of the matrix.

19. The method of claim 18 , further comprising accumulating the partial contributions computed by the plurality of physical processing elements for each output sum of the operation.

20. The method of claim 18 , wherein analyzing the specification to select the type of processing load partitioning to be applied includes determining whether a computation metric value meets a specified threshold.

Assignees

• Facebook Inc

Inventors

• Schatz Martin
• Firoozshahian Amin

Classifications

• Y02D10/00

  Energy efficient computing, e.g. low power processors, power management or thermal management · CPC title

• G06F9/505

  considering the load · CPC title

• G06F9/5061 Primary

  Partitioning or combining of resources · CPC title

• G06F9/5083 Primary

  Techniques for rebalancing the load in a distributed system · CPC title

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title