Systems and methods for minimizing communications

Patent metadata

Field	Value
Publication number	US-11068178-B2
Application number	US-201916700331-A
Country	US
Kind code	B2
Filing date	Dec 2, 2019
Priority date	Jan 2, 2015
Publication date	Jul 20, 2021
Grant date	Jul 20, 2021

Abstract

A system for allocation of one or more data structures used in a program across a number of processing units takes into account a memory access pattern of the data structure, and the amount of total memory available for duplication across the several processing units. Using these parameters duplication factors are determined for the one or more data structures such that the cost of remote communication is minimized when the data structures are duplicated according to the respective duplication factors while allowing parallel execution of the program.

First claim

What is claimed is:

1. A system for allocating data structures accessed by one or more tasks to be executed by a plurality of processing nodes, each processing node having a respective local memory, the system comprising:
a first processor; and
a first memory in electrical communication with the first processor, the first memory comprising instructions which, when executed by a processing unit comprising at least one of the first processor and a second processor, and in electronic communication with a memory module comprising at least one of the first memory and a second memory, program the processing unit to:
(a1) select as a first data structure, a data structure having a read-write ratio greater than a read-write threshold, the read-write ratio corresponding to read-write operations in the one or more tasks to be executed in a distributed manner by the plurality of processing nodes;
(b1) compute a first duplication factor for the first data structure; and
(c1) generate a first statement allocating the first data structure duplicated by the first duplication factor, across the plurality of processing nodes.

2. The system of claim 1 , wherein the processing unit is programmed to compute the first duplication factor based on, at least in part, at least one of: (i) a number of the plurality of processing nodes, (ii) the read-write ratio of the first data structure, (iii) a first value of total available memory size of the plurality of processing nodes, and (iv) a size of the first data structure.

3. The system of claim 2 , wherein the processing unit is further programmed to compute the first value of the total available memory size using a sum of memory capacity of each processing node in the plurality of processing nodes.

4. The system of claim 3 , wherein the processing unit is further programmed to compute another value of the total available memory size based on, at least in part, the first value, the first duplication factor, and the size of the first data structure.

5. The system of claim 1 , wherein the processing unit is further programmed to:
(a2) select as a second data structure, another data structure having a read-write ratio greater than the read-write threshold;
(b2) compute a second duplication factor for the second data structure, the second duplication factor being based on, at least in part, at least one of: (i) the number of the plurality of processing nodes, (ii) the read-write ratio of the second data structure, (iii) a second value of total available memory size of the plurality of processing nodes, and (iv) a size of the second data structure; and
(c2) generate a second statement allocating the second data structure duplicated by the second duplication factor, across the plurality of processing nodes.

6. The system of claim 5 , wherein the processing unit is further programmed to:
prior to performing operations (b 1) and (b2), compare the read-write ratio of the first data structure with the read-write ratio of the second data structure;
if the read-write ratio of the first data structure is greater than the read-write ratio of the second data structure:
perform the operation (b1) before the operation (b2); and

compute the second value of the total available memory size based on, at least in part, both the first duplication factor and the size of the first data structure; and
otherwise:
perform the operation (b2) before the operation (b1).

7. The system of claim 1 , wherein the processing unit is further programmed to compute the read-write ratio of the first data structure.

8. The system of claim 1 , wherein the processing unit is further programmed to compute the read-write threshold as a function of the number of processing nodes in the plurality of processing nodes.

9. The system of claim 1 , wherein the processing unit is further programmed to compute:
a correction factor representing an average local access to the first data structure by at least one processing node in the plurality of processing nodes; and
the read-write threshold as a function of the number of processing nodes in the plurality of processing nodes and the correction factor.

10. The system of claim 1 , wherein the processing unit is further programmed to:
generate a local write statement for the first data structure that allows a first processing node to store a data value in an instance of the first data structure in local memory of the first processing node; and
for a set of processing nodes in the plurality of processing nodes, a cardinality of the set depending on the first duplication factor, generate a set of remote write statements for the first data structure, allowing the first processing node to store the data value in respective instances of the first data structure in respective local memories of the nodes in the set.

11. A system for allocating data structures accessed by one or more tasks to be execute by a plurality of processing nodes, each processing node having a respective local memory, the system comprising:
a first processor; and
a first memory in electrical communication with the first processor, the first memory comprising instructions which, when executed by a processing unit comprising at least one of the first processor and a second processor, and in electronic communication with a memory module comprising at least one of the first memory and a second memory, program the processing unit to:
(a) select a set of data structures, each data structure having a read-write ratio greater than a read-write threshold, each read-write ratio corresponding to read-write operations in the one or more tasks to be executed in a distributed manner by the plurality of processing nodes;
(b) designate a rank to each data structure according the read-write ratio thereof, and ordering the set of data structures according to the ranks; and
(c) iterate in the order of the ordered set, wherein in each iteration the processing unit is programmed to:
compute for a data structure corresponding to the iteration a duplication factor; and
generate a statement allocating the data structure duplicated by the duplication factor, across the plurality of processing nodes.

12. The system of claim 11 , wherein the processing unit is further programmed to:
compute the duplication factor based on, at least in part, a value of total available memory size of the plurality of processing nodes; and
during a current iteration of the operation (c) and prior to a next iteration, update the value of the total available memory size based on, at least in part, the size of the data structure corresponding to the current iteration and the duplication factor associated with the data structure.

13. The system of claim 12 , wherein the processing unit is further programmed to compute, during a first iteration of the operation (c), the value of the total available memory size using a sum of memory capacity of each processing node in the plurality of processing nodes.

14. The system of claim 11 , wherein:
in each iteration of the operation (c), the processing unit is programmed to compute the duplication factor based on, at least in part, at least one of: (i) a number of the plurality of processing nodes, (ii) the read-write ratio of the data structure corresponding to the iteration, (iii) a size of the data structure, and (iv) a value of total available memory size of the plurality of processing nodes.

15. A system for allocating data structures accessed by one or more tasks to be executed by a plurality of processing nodes, each processing node having a respective local memory, the system comprising:
a first proce

Assignees

• Reservoir Labs Inc

Inventors

• Baskaran Muthu Manikandan
• Henretty Thomas
• Johnson Ann
• Konstantinidis Athanasios
• Langston M H
• Mcmahon Janice O
• Meister Benoit J
• Mountcastle Paul D
• Naqvi Aale
• Pradelle Benoit
• Ramananandro Tahina
• Tavarageri Sanket
• Lethin Richard A

Classifications

• Y02D10/00

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

• G06F8/4432 Primary

  Reducing the energy consumption · CPC title

• G06F8/453

  Data distribution · CPC title

• G06F3/0604

  Improving or facilitating administration, e.g. storage management · CPC title

• G06F3/0671

  In-line storage system · CPC title