Methods and apparatus for local memory compaction
View Patent ↗Methods, apparatus and computer software product for local memory compaction are provided. In an exemplary embodiment, a processor in connection with a memory compaction module identifies inefficiencies in array references contained within in received source code, allocates a local array and maps the data from the inefficient array reference to the local array in a manner which improves the memory size requirements for storing and accessing the data. In another embodiment, a computer software product implementing a local memory compaction module is provided. In a further embodiment a computing apparatus is provided. The computing apparatus is configured to improve the efficiency of data storage in array references. This Abstract is provided for the sole purpose of complying with the Abstract requirement rules. This Abstract is submitted with the explicit understanding that it will not be used to interpret or to limit the scope or the meaning of the claims.
1. A method for configuring a memory in a computing apparatus, the computing apparatus comprising at least one processor, the method comprising:
receiving program source code in a memory, the program source code comprising loop nests with arbitrary parametric affine iteration domain containing at least one array reference;
identifying during compilation, based on at least in part an analysis of the program source code, by the at least one processor and a local memory compaction module, inefficiencies in memory usage, the inefficiencies relating to at least one of access to and memory footprint of at least one array associated with the at least one array reference within the program source code;
allocating during the compilation of the program source code, by the processor and the local memory compaction module, at least one local array for accessing at least a fraction of data associated with the at least one array; and
mapping during the compilation, by the processor and the local memory compaction module, a portion of the at least one array to one of the at least one local array, wherein the memory size requirement of the at least one local array is smaller than the memory size requirements of the at least one array, such that the memory usage inefficiencies are reduced in compiled program source code.
2. The method of claim 1 , wherein the mapping further comprises:
partitioning a set of references to form sets of compatible references, the set of references accessing a portion of the at least one array;
determining a relation within the compatible references;
grouping compatible references based on the relation;
performing algebraic simplification on a group of compatible references; and
performing geometric rearrangement through re-indexing of the elements of the at least one local array.
3. The method of claim 2 , wherein the compatible references are references whose memory footprints overlap during the execution of a particular subset of loop iterations.
4. The method of claim 2 , wherein the determination further comprises identifying array references whose memory footprints overlap;
duplicating the identified references; and
associating each duplicate reference to disjoint subsets of the memory footprints.
5. The method of claim 1 , wherein identifying inefficiencies comprises identifying strides in the domain of array elements accessed through references, the method further comprising extracting a lattice of integer points within the domain, the lattice related to holes within the domain.
6. The method of claim 1 , wherein the accessed data set is arbitrarily complex.
7. The method of claim 2 , wherein the mapping produces a piecewise affine index function for at least one local array.
8. The method of claim 7 , wherein the mapping further comprises extracting at least one representative array reference from a set of references accessing a portion of the at least one array.
9. The method of claim 8 , wherein the at least one representative array reference is at least one representative access matrix, the mapping further comprising performing a Hermite factorization for each of the at least one representative access matrix and producing a piecewise affine index function from the factorization.
10. The method of claim 7 , wherein the mapping comprises performing the following at least once:
formulating a set of linear constraints by using the affine form of the Farkas lemma;
decomposing the linear constraints dimension by dimension to form resulting integer linear programming problems;
solving the resulting integer linear programming problems to compute the reindexing function, the linear part of the reindexing function being represented as a unimodular matrix; and
apply the reindexing to the at least one array.
11. The method of claim 7 , further comprising:
deriving a parallelepiped with minimal volume, the parallelepiped enclosing the domain of the data set accessed by the at least one local array;
deriving a finite prism of triangular base and of minimal volume enclosing the data footprint domain and comparing it to the parallelepiped with minimal volume;
partitioning the prism of triangular base into two prisms; and
rotating one of the prisms in such a way that the union of the rotated prism and the other prism has a smaller memory footprint than the enclosing parallelepiped.
12. The method of claim 1 , further comprising generating asynchronous communication and wait operations.
13. The method of claim 12 , wherein the generating asynchronous communication and wait operations further comprises using multi-buffering for overlapping communication and computation.
14. A computing apparatus comprising:
a memory;
at least one processor; and
a storage medium, the storage medium comprising a set of processor executable instructions that, when executed by the processor configure the computing apparatus to:
receive program source code in the memory, the program source code comprising loop nests with arbitrary parametric affine iteration domain containing at least one array reference;
identify during compilation, based on at least in part an analysis of the program source code, by the at least one processor, inefficiencies in memory usage, the inefficiencies relating to at least one of access to and memory footprint of at least one array associated with the at least one array reference within the program source code;
allocate, during the compilation of the program source code, at least one local array for accessing at least a fraction of data associated with the at least one array; and
map during the compilation, a portion of the at least one array to one of the at least one local array, wherein the memory size requirement of the at least one local array is smaller than the memory size requirements of the at least one array, such that the memory usage inefficiencies are reduced in compiled program source code.
15. The computing apparatus of claim 14 , wherein the configuration for mapping further comprises a configuration to:
partition a set of references to form sets of compatible references, the set of references accessing a portion of the at least one array;
determine a relation within the compatible references;
group compatible references based on the relation;
perform algebraic simplification on a group of compatible references; and
perform geometric rearrangement through re-indexing of the elements of the at least one local array.
16. The computing apparatus of claim 15 , wherein the compatible references are references whose memory footprints overlap during the execution of a particular subset of loop iterations.
17. The computing apparatus of claim 15 , wherein the configuration to determine a relation further comprises a determination to:
identify array references whose memory footprints overlap;
duplicate the identified references; and
associate each duplicate reference to disjoint subsets of the memory footprints.
18. The computing apparatus of claim 14 , wherein the configuration to identify inefficiencies comprises a configuration to identify strides in the domain of array elements accessed through references, and extract a lattice of integer points within the domain, the lattice related to holes within the domain.
19. The computing apparatus of claim 14 , wherein the accessed data set is arbitrarily complex.
20. The computing apparatus of claim 15 , wherein the configuration to map produces a piecewise affine index function for at least one local array.
21. The computing apparatus of claim 20 , wherein the configuration to map further comprises a configuration to extract at least one representative array reference from a set of references accessing a portion of the at least one array.
22. The computing apparatus of claim 21 , wherein the at least one representative array reference is at least one representative access matrix, the configuration to map further comprising a configuration to perform a Hermite factorization for each of the at least one representative access matrix and produce a piecewise affine index function from the factorization.
23. The computing apparatus of claim 20 , wherein the configuration to map comprises a configuration to perform the following at least once:
formulate a set of linear constraints by using the affine form of the Farkas lemma;
decompose the linear constraints dimension by dimension to form resulting integer linear programming problems;
solve the resulting integer linear programming problems to compute the reindexing function, the linear part of the reindexing function being represented as a unimodular matrix; and
apply the reindexing to the at least one array.
24. The computing apparatus of claim 20 , wherein the configuration further comprises a configuration to:
derive a parallelepiped with minimal volume, the parallelepiped enclosing the domain of the data set accessed by the at least one local array;
derive a finite prism of triangular base and of minimal volume enclosing the data footprint domain and comparing it to the parallelepiped with minimal volume;
partition the prism of triangular base into two prisms; and
rotate one of the prisms in such a way that the union of the rotated prism and the other prism has a smaller memory footprint than the enclosing parallelepiped.
25. The computing apparatus of claim 14 , wherein the configuration further comprises a configuration to generate asynchronous communication and wait operations.
26. The computing apparatus of claim 25 , wherein the configuration to generate asynchronous communication and wait operations further comprises a configuration to use multi-buffering for overlapping communication and computation.
27. A computer software product comprising a computer readable medium containing a set of processor executable instructions that when executed by a processor in a computing apparatus configure the computing apparatus to:
receive program source code in a memory within the computing apparatus, the program source code comprising loop nests with arbitrary parametric affine iteration domain containing at least one array reference;
identify, during compilation, based on at least in part an analysis of the program source code, by the at least one processor, inefficiencies in memory usage, the inefficiencies relating to at least one of access to and memory footprint of at least one array associated with the at least one array reference within the program source code;
allocate, during the compilation of the program source code, at least one local array for accessing at least a fraction of data associated with the at least one array; and
map during the compilation, a portion of the at least one array to one of the at least one local array, wherein the memory size requirement of the at least one local array is smaller than the memory size requirements of the at least one array, such that the memory usage inefficiencies are reduced in compiled program source code.
28. The computer software product of claim 27 , wherein the configuration to map further comprises a configuration to:
partition a set of references to form sets of compatible references, the set of references accessing a portion of the at least one array;
determine a relation within the compatible references;
group compatible references based on the relation;
perform algebraic simplification on a group of compatible references; and
perform geometric rearrangement through re-indexing of the elements of the at least one local array.
29. The computer software product of claim 28 , wherein the compatible references are references whose memory footprints overlap during the execution of a particular subset of loop iterations.
30. The computer software product of claim 28 , wherein the configuration to determine a relation further comprises a determination to:
identify array references whose memory footprints overlap;
duplicate the identified references; and
associate each duplicate reference to disjoint subsets of the memory footprints.
31. The computer software product of claim 28 , wherein the configuration to identify inefficiencies comprises a configuration to identify strides in the domain of array elements accessed through references, and extract a lattice of integer points within the domain, the lattice related to holes within the domain.
32. The computer software product of claim 27 , wherein the accessed data set is arbitrarily complex.
33. The computer software product of claim 28 , wherein the configuration to map produces a piecewise affine index function for at least one local array.
34. The computer software product of claim 33 , wherein the configuration to map further comprises a configuration to extract at least one representative array reference from a set of references accessing a portion of the at least one array.
35. The computer software product of claim 34 , wherein the at least one representative array reference is at least one representative access matrix, the configuration to map further comprises a configuration to perform a Hermite factorization for each of the at least one representative access matrix and produce a piecewise affine index function from the factorization.
36. The computer software product of claim 33 , wherein the configuration to map comprises a configuration to perform the following at least once:
formulating a set of linear constraints, the constraints being related to the data reindexing function by using the affine form of the Farkas lemma;
decompose the linear constraints dimension by dimension to form resulting integer linear programming problems;
solve the resulting integer linear programming problems to compute the reindexing function, the linear part of the reindexing function being represented as a unimodular matrix; and
apply the reindexing to the at least one array.
37. The computer software product of claim 33 , wherein the configuration further comprises a configuration to:
derive a parallelepiped with minimal volume, the parallelepiped enclosing the domain of the data set accessed by the at least one local array;
derive a finite prism of triangular base and of minimal volume enclosing the data footprint domain and comparing it to the parallelepiped with minimal volume;
partition the prism of triangular base into two prisms; and
rotate one of the prisms in such a way that the union of the rotated prism and the other prism has a smaller memory footprint than the enclosing parallelepiped.
38. The computer software product of claim 27 , wherein the configuration further comprises a configuration to generate asynchronous communication and wait operations.
39. The computer software product of claim 38 , wherein the configuration to generate asynchronous communication and wait operations further comprises a configuration to use multi-buffering for overlapping communication and computation.