Systems and methods for minimizing communications
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.
1. A system for allocating data structures to 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: select as a first data structure of a set of data structures, a data structure having a read-write ratio greater than a read-write threshold; compute a respective value of a memory access parameter for each data structure of the set of data structures; compute a first duplication factor for the first data structure by optimizing a function of a value of a memory access parameter corresponding to the first data structure, subject to a memory capacity constraint based on a number N of processing nodes, N being greater than one; and generate a first statement allocating different portions of the first data structure duplicated by the first duplication factor, across the plurality of processing nodes, wherein the first value of the memory access parameter, corresponding to the first data structure, comprises a first correction factor based on an association between the first data structure and a first processing node of 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: select as a second data structure, another data structure having a read-write ratio greater than the read-write threshold; 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 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 of computing first and second duplication factors, 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 of computing the first duplication factor before the operation of computing the second duplication factor; 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 of computing the second duplication factor before the operation of computing the first duplication factor.
7. A system for allocating data structures to 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; (b) compute a respective value of a memory access parameter for each data structure; (c) determine a respective duplication factor for each data structure by optimizing a function of 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; and (d) generate a statement allocating different portions of the data structure duplicated by each duplication factor, across the plurality of processing nodes, wherein to optimize the function, the processing unit is programmed to solve a mixed integer linear programming representation of the function and the memory capacity constraint, to minimize the function, or to maximize the function.
8. The system of claim 7 , wherein: the memory access parameter comprises a reduction in a number of remote accesses; and to optimize the function, the processing unit is programmed to maximize the function.
9. The system of claim 7 , wherein: the memory access parameter comprises a number of remote accesses: and to optimize the function, the processing unit is programmed to minimize the function.
10. The system of claim 7 , wherein a first respective value of the memory access parameter, corresponding to a first data structure, comprises a first correction factor based on an association between the first data structure and a first processing node.
11. The system of claim 7 , wherein the processing unit is further programmed to compute the read-write ratio of the first data structure.
12. The system of claim 7 , 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.
13. The system of claim 7 , 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.
14. The system of claim 7 , 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.