Methods and apparatus for data transfer optimization
Methods, apparatus and computer software product for optimization of data transfer between two memories includes determining access to master data stored in one memory and/or to local data stored in another memory such that either or both of the size of total data transferred and the number of data transfers required to transfer the total data can be minimized. The master and/or local accesses are based on, at least in part, respective structures of the master and local data.
1. A method of facilitating exchange of data between a first memory and a second memory, the method comprising:
receiving a mapping between a global data structure maintained in the first memory and a local data structure maintained in the second memory, the second memory being associated with a particular processor;
deriving an asynchronous bulk communication operation for transferring data between the global and local data structures, the asynchronous bulk communication operation comprising (i) access to the global data structure based on, at least in part, a structure one or more characteristics of the global data structure, and (ii) access to the local data structure based on, at least in part, one or more characteristics of the local data structure, for minimizing a parameter of a total data transfer between the first and second memories;
wherein a characteristic of the global data structure or a characteristic the local data structure comprises at least one dimension and a sequence of indices corresponding to each dimension; and
wherein the parameter comprises at least one of a number of data transfer operations required for the total data transfer, and a size of data to be transferred for the total data transfer.
2. The method of claim 1 , wherein the local data structure is based on, at least in part, a local memory compaction corresponding to a portion of a specified computation, the portion being designated to the particular processor.
3. The method of claim 2 , wherein the local memory compaction corresponds to a minimum total data size, the method further comprising selecting the local data structure such that:
a size of the local data structure is greater than the minimum total data size; and
at least one of: (i) the access to the global data structure comprises a first stride of a first constant value, and (ii) the access to the local data structure comprises a second stride of a second constant value.
4. The method of claim 1 , wherein data in the local data structure is at least one of processed or to be processed by the particular processor.
5. The method of claim 1 , wherein:
the parameter comprises a number of data transfer operations required for the total data transfer;
a data transfer size corresponding to one data transfer operation is no greater than the size of data to be transferred for the total data transfer; and
at least one of selecting the access to the global data structure or the access to the local data structure comprises selecting the data transfer size that minimizes the number of data transfer operations.
6. The method of claim 5 , further comprising selecting the data transfer size corresponding to one data transfer operation based on, at least in part, a capacity of a communication link between the first and second memories.
7. The method of claim 1 , wherein:
at least one of: (i) the first memory comprises a first set of memory banks, or (ii) the second memory comprises a second set of memory banks;
at least one of: (i) the access to the global data structure comprises a first stride of a first constant value, or (ii) the access to the local data structure comprises a second stride of a second constant value; and
at least one of: (i) selecting the access to the global data structure comprises selecting, based on at least in part, a number of banks in the first set and a size of a memory bank in the first set, the first stride such that consecutive data transfer operations correspond to distinct memory banks of the first set, or (ii) selecting the access to the local data structure comprises selecting, based on at least in part, a number of banks in the second set and a size of a memory bank in the second set, the second stride such that consecutive data transfer operations correspond to distinct memory banks of the second set.
8. The method of claim 1 , wherein:
the global data structure comprises at least one dimension;
the local data structure comprises at least one dimension; and
at least one dimension of the local data structure is smaller than a corresponding dimension of the global data structure.
9. The method of claim 1 , wherein:
the local data structure comprises at least one set of data elements; and
deriving the asynchronous bulk communication operation comprises computing: (i) a count representing a number of sets of data elements; and (ii) a size of each set of data elements.
10. The method of claim 9 , wherein computing the size of a set of data elements comprises determining a size of a data element.
11. The method of claim 9 , wherein computing at least one of the count or the size of a set of data elements is based on, at least in part, a capacity of a communication link between the first and second memories.
12. The method of claim 1 , wherein:
the local data structure comprises a plurality of sets of data elements;
the global data structure comprises a plurality of corresponding sets of data elements; and
deriving the asynchronous bulk communication operation comprises computing a stride representing a distance between a first set of data elements in the global data structure and a second set of data elements in the global data structure.
13. The method of claim 12 , wherein computing the stride is based on, at least in part, a dimension of the global data structure.
14. The method of claim 1 , wherein:
the local data structure comprises a plurality of sets of data elements;
the global data structure comprises a plurality of corresponding sets of data elements; and
deriving the asynchronous bulk communication operation comprises computing a stride representing a distance between a first set of data elements in the local data structure and a second set of data elements in the local data structure.
15. The method of claim 14 , wherein computing the stride is based on, at least in part, a dimension of the local data structure.
16. The method of claim 1 , wherein deriving the asynchronous bulk communication operation comprises determining at least one of: (i) a starting address in the first memory, and (ii) a starting address in the second memory.
17. The method of claim 1 , wherein
the global data structure comprises a first dimension and a second dimension;
the local data structure also comprises the first dimension and the second dimension; and
deriving the asynchronous bulk communication operation comprises generating: (i) a start address in the first memory, based on, at least in part, the first dimension, and (ii) a start address in the second memory, based on, at least in part, the second dimension, such that a set of data elements in the global data structure and a corresponding set of data elements in the local data structure are arranged in the first and second dimensions, respectively.
18. The method of claim 1 , further comprising transferring at least a portion of data from the first memory to the second memory according to the asynchronous bulk communication operation, thereby storing the data in the second memory.
19. The method of claim 1 , further comprising transferring data from the second memory to the first memory according to the asynchronous bulk communication operation, thereby storing at least a portion of the data in the first memory.
20. The method of claim 1 , wherein the step of deriving the asynchronous bulk communication operation is designated to a computer distinct from the processor.
21. The method of claim 20 , wherein the computer is configured to derive a sequence of asynchronous bulk communication operations, the sequence comprising the asynchronous bulk communication operation, and each operation in the sequence corresponding to a loop index and being further based on, at least in part, the loop index.
22. The method of claim 20 , wherein the computer is configured to derive a sequence of asynchronous bulk communication operations, the sequence comprising the asynchronous bulk communication operation, and each operation in the sequence: (i) corresponding to a distinct processor specified by a processor index, and (ii) being further based on, at least in part, the processor index.