Methods and apparatus for data transfer optimization

Patent metadata

Field	Value
Publication number	US-9858053-B2
Application number	US-201414181201-A
Country	US
Kind code	B2
Filing date	Feb 14, 2014
Priority date	Feb 8, 2008
Publication date	Jan 2, 2018
Grant date	Jan 2, 2018

Abstract

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.

First claim

What is claimed is:

1. A method of facilitating exchange of data between a first memory and a second memory, the method comprising:
deriving a data transfer operation for transferring a plurality of data elements, the data transfer operation lacking a specification of an iterator, and comprising: (a) a first data access specification describing source locations of the plurality of data elements in a first memory, (b) a number of data elements to be transferred in the data transfer operation, and (c) a second data access specification describing destination locations of the plurality of data elements in a second memory, by: (i) generating the first data access specification based on, at least in part, a structure of the plurality of data elements in the first memory and the number of data elements to be transferred, and (ii) generating the second data access specification based on, at least in part, a structure of the plurality of data elements in the second memory and the number of data elements to be transferred, for minimizing a parameter of a total data transfer of the group of data elements.

2. The method of claim 1 , wherein at least one of the structure of the plurality of data elements in the first memory and the structure of the plurality of data elements in the second memory comprises at least one dimension and a sequence of indices corresponding to each dimension.

3. The method of claim 1 , 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.

4. The method of claim 1 , wherein the plurality of data elements is based on, at least in part, a local memory compaction corresponding to a portion of a specified computation, the portion being designated to a processor associated with the memory.

5. The method of claim 4 , wherein the local memory compaction corresponds to a minimum total data size, the method further comprising selecting the second plurality of data elements such that:
a size of the plurality of data elements is greater than the minimum total data size; and
at least one of: (i) the first data access specification comprises a first stride of a constant value, and (ii) the second data access specification comprises a second stride of a constant value.

6. The method of claim 1 , wherein the plurality of data elements is at least one of processed and to be processed by the processor.

7. 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 generating the first data access specification and the second data access specification comprises selecting the data transfer size that minimizes the number of data transfer operations.

8. The method of claim 7 , 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.

9. The method of claim 1 , wherein:
at least one of: (i) the first memory comprises a first set of memory banks, and (ii) the second memory comprises a second set of memory banks;
at least one of: (i) the first data access specification comprises a first stride of a constant value, and (ii) the second data access specification comprises a second stride of a constant value; and
at least one of: (i) generating the first data access specification 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, and (ii) generating the second data access specification 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.

10. The method of claim 1 , wherein:
the structure of the plurality of data elements comprises at least one dimension;
the structure of the plurality of data elements comprises at least one dimension; and
at least one dimension of the structure of the plurality of data elements is smaller than a corresponding dimension of the structure of the plurality of data elements.

11. The method of claim 1 , wherein:
the plurality of data elements comprises at least one set of data elements; and
deriving the data transfer operation comprises computing: (i) a count representing a number of sets of data elements; and (ii) a size of each set of data elements.

12. The method of claim 11 , wherein computing the size of a set of data elements comprises determining a size of a data element.

13. The method of claim 11 , wherein computing at least one of the count and 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.

14. The method of claim 1 , wherein:
the plurality of data elements comprises a plurality of sets of data elements;
the plurality of data elements comprises a plurality of corresponding sets of data elements; and
deriving the data transfer operation comprises computing a first stride representing a distance between a first set of data elements in the plurality of data elements and a second set of data elements in the plurality of data elements.

15. The method of claim 14 , wherein computing the first stride is based on, at least in part, a dimension of a structure of the plurality of data elements.

16. The method of claim 1 , wherein:
the plurality of data elements comprises a plurality of sets of data elements;
the plurality of data elements comprises a plurality of corresponding sets of data elements; and
deriving the data transfer operation comprises computing a second stride representing a distance between a first set of data elements in the plurality of data elements and a second set of data elements in the plurality of data elements.

17. The method of claim 16 , wherein computing the second stride is based on, at least in part, a dimension of a structure of the plurality of data elements.

18. The method of claim 1 , wherein deriving the data transfer operation comprises determining at least one of: (i) a start address in the first memory, and (ii) a starting address in the second memory.

19. The method of claim 1 , wherein
the plurality of data elements comprises a first dimension and a second dimension;
the plurality of data elements also comprises the first dimension and the second dimension; and
deriving the data transfer 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 plurality of data elements and a corresponding set of data elements in the plurality of data elements are arranged in the first and second dimensions, respectively.

20. The method of claim 1 , further comprising transferring at least a portion of the plurality of data elements from the first memory to the second memory according to the data transfer operation, thereby storing the plurality of data elements in the s

Assignees

• Reservoir Labs Inc

Inventors

• Lethin Richard A
• Leung Allen K
• Meister Benoit J
• Wohlford David E

Classifications

• G06F8/443 Primary

  Optimisation · CPC title

• G06F12/023

  Free address space management · CPC title