Systems and methods for scalable hierarchical polyhedral compilation
AssigneeQUALCOMM Technologies, Inc.
InventorsMuthu Manikandan Baskaran, Benoit J. Meister, Benoit Pradelle
Life of this patent
Estimating the term…
Abstract
A system for compiling programs for execution thereof using a hierarchical processing system having two or more levels of memory hierarchy can perform memory-level-specific optimizations, without exceeding a specified maximum compilation time. To this end, the compiler system employs a polyhedral model and limits the dimensions of a polyhedral program representation that is processed by the compiler at each level using a focalization operator that temporarily reduces one or more dimensions of the polyhedral representation. Semantic correctness is provided via a defocalization operator that can restore all polyhedral dimensions that had been temporarily removed.
Claims20
A method for optimizing execution of a program by a processing system comprising a hierarchical memory having a plurality of memory levels, the method comprising:
- (a) for each memory level in at least a subset of memory levels in the plurality of memory levels focalizing a loop dimension of a selected loop nest within a program, the loop nest having a nesting level of N, N being greater than 1, focalizing comprising:
- selecting, as the loop dimension being focalized, a dimension in which memory accesses are piecewise uniformly generated references (PUGRs) or a dimension in which memory accesses are uniformly generated references (UGRs);
- removing an iterator corresponding to a loop index associated with the loop dimension being focalized, reducing the nesting level to N−1;
- in the loop nest having the reduced nesting level, at least one of:
- (i) removing from a loop condition at another loop dimension of the selected loop nest a subcondition corresponding to the loop index;
- and
- (ii) removing from a memory access expression of an operand, a reference to the loop index;
- and
- storing the loop index and associated focalization information for that memory level;
- and
- (b) for each focalized dimension, defocalizing that dimension by:
- adding an iterator based on a reintroduced loop index associated with the loop dimension being defocalized;
- and
- at least one of:
- updating a loop condition at another loop dimension of the selected loop nest based on the stored focalization information associated with the loop dimension being defocalized;
- and
- updating the memory access expression of the operand based on the reintroduced loop index and the stored focalization information.
A system for facilitating optimized execution of a program by a processing system comprising a hierarchical memory having a plurality of memory levels, 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) for each memory level in at least a subset of memory levels in the plurality of memory levels, focalize a loop dimension of a selected loop nest within a program, the loop nest having a nesting level of N, N being greater than 1, wherein to focalize the loop dimension the instructions program the processing unit to:
- select, as the loop dimension being focalized, a dimension in which memory accesses are piecewise uniformly generated references (PUGRs) or a dimension in which memory accesses are uniformly generated references (UGRs);
- remove an iterator corresponding to a loop index associated with the loop dimension being focalized, reducing the nesting level to N−1;
- in the loop nest having the reduced nesting level, at least one of:
- (i) remove from a loop condition at another loop dimension of the selected loop nest a subcondition corresponding to the loop index;
- and
- (ii) remove from a memory access expression of an operand, a reference to the loop index;
- and
- store the loop index and associated focalization information for that memory level;
- and
- (b) for each focalized dimension, defocalize that dimension, wherein to defocalize the dimension the instructions program the processing unit to:
- add an iterator based on a reintroduced loop index associated with the loop dimension being defocalized;
- and
- at least one of:
- update a loop condition at another loop dimension of the selected loop nest based on the stored focalization information associated with the loop dimension being defocalized;
- and
- update the memory access expression of the operand based on the reintroduced loop index and the stored focalization information.
Dependencies are inferred from the claim text.