Systems and methods for minimizing communications

Patent metadata

Field	Value
Publication number	US-10496304-B2
Application number	US-201614987216-A
Country	US
Kind code	B2
Filing date	Jan 4, 2016
Priority date	Jan 2, 2015
Publication date	Dec 3, 2019
Grant date	Dec 3, 2019

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 method for allocating data structures accesed by one or more tasks to be executed by a plurality of processing nodes, each processing node having a respective local memory, the method comprising performing by a processor steps of:
(a1) selecting 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 the distributed manner by the plurality of processing nodes;
(b1) computing a first duplication factor for the first data structure; and
(c1) generating a first statement allocating the first data structure duplicated by the first duplication factor, across the plurality of processing nodes.

2. The method of claim 1 , wherein the first duplication factor is 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 method of claim 2 , further comprising computing by the processor 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 method of claim 3 , further comprising computing by the processor 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 method of claim 1 , further comprising performing by the processor the steps of:
(a2) selecting as a second data structure, another data structure having a read-write ratio greater than the read-write threshold;
(b2) computing 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) generating a second statement allocating the second data structure duplicated by the second duplication factor, across the plurality of processing nodes.

6. The method of claim 5 , further comprising performing by the processor the steps of:
prior to performing the steps (b1) and (b2), comparing 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:
performing the step (Ill) before the step (b2); and
computing 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:
performing the step (b2) before the step (b1).

7. The method of claim 1 , further comprising computing by the processor the read-write ratio of the first data structure.

8. The method of claim 1 , further comprising computing by the processor the read-write threshold as a function of the number of processing nodes in the plurality of processing nodes.

9. The method of claim 1 , further comprising computing by the processor:
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 method of claim 1 , further comprising performing by the processor the steps of:
generating a local write statement for the first data structure, storing by a first processing node 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, generating a set of remote write statements for the first data structure, storing by the first processing node the data value in respective instances of the first data structure in respective local memories of the nodes in the set.

11. A method 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 method comprising performing by a processor steps of:
(a) selecting 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) designating 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) iterating in the order of the ordered set, each iteration comprising:
computing for a data structure corresponding to the iteration a duplication factor; and
generating a statement allocating the data structure duplicated by the duplication factor, across the plurality of processing nodes.

12. The method of claim 11 , wherein the duplication factor is based on, at least in part, a value of total available memory size of the plurality of processing nodes, the method further comprising, during a current iteration of the step (c) and prior to a next iteration:
updating by the processor, 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 method of claim 12 , further comprising computing by the processor, during a first iteration of the step (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 method of claim 11 , wherein in each iteration of the step (c), the duplication factor is 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 method 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 method comprising performing by a processor steps of:
(a) selecting 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) computing a respective value of a memory access parameter for each data structure; and
(c) determining a respective duplication factor for each data structure by optimizing a function of the respective duplication factors and the respective values of the memory access parameter, subject to a memory capacity constraint based on a number N of processing nodes, N being greater than one.

16. The method of claim 15 , wherein:
the memory access parameter comprises a reduction in a number of remote accesses; and
optimizing the function comprises maximizing the function.

17. The

Assignees

• Reservoir Labs Inc

Inventors

• Baskaran Muthu M
• 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

• G06F8/4441

  Reducing the execution time required by the program code · CPC title

• G06F3/0631 Primary

  by allocating resources to storage systems · CPC title

• G06F3/0638

  Organizing or formatting or addressing of data · CPC title

• G06F3/0604

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

• G06F8/453

  Data distribution · CPC title