Systems and methods for efficient determination of task dependences after loop tiling

1. A method for determining dependencies in a tiled loop nest, the method comprising performing by a processor configured as a compiler, the steps of:

receiving a program source code comprising an un-tiled loop nest;

obtaining: (i) a set of pre-tiling dependencies (D) corresponding to a statement in the un-tiled loop nest comprising a plurality of loop dimensions, and (ii) a tiling set (G) corresponding to a tiling scheme to be applied to the loop nest, the tiling scheme introducing at least one tiled dimension corresponding to at least one loop dimension of the loop nest;

generating based on, at least in part, the set of pre-tiling dependencies (D), a set of modified pre-tiling dependencies (A);

generating based on, at least in part, the tiling set (G), a set of compressed intra-tile dependencies (X);

compressing the set of modified pre-tiling dependencies (A) using the tiling set (G) to obtain a compressed set of modified pre-tiling dependencies (AG);

generating a set of post-tiling dependencies associated with the statement based on, at least in part, the compressed set and the set of compressed intra-tile dependencies (X); and

generating by the compiler, a schedule of operation of the statement according to the set of post-tiling dependencies, to facilitate parallelized execution of the program.

2. The method of claim 1 , wherein the tiling set (G) is represented as a matrix, each column of the matrix being associated with a respective loop dimension to be tiled.

3. The method of claim 2 , wherein the tiling set (G) comprises a diagonal matrix.

4. The method of claim 1 , wherein:

the set of pre-tiling dependencies comprises a first relation comprising a first loop index that is associated with a first loop dimension; and

generating the set of modified pre-tiling dependencies (A) comprises representing the first relation in a form: an expression of the first loop index greater than or equal to zero.

5. The method of claim 1 , wherein generating the set of modified pre-tiling dependencies (A) is performed independently of the tiling set (G).

6. The method of claim 1 , wherein generating the set of compressed intra-tile dependencies (X) is performed independently of the set of pre-tiling dependencies (D).

7. The method of claim 1 , wherein generating the set of post-tiling dependencies comprises performing a direct sum of the compressed set and the set of compressed intra-tile dependencies (X).

8. The method of claim 1 , wherein generating the set of post-tiling dependencies comprises:

determining a set of vertices associated with the set of compressed intra-tile dependencies (X); and

inflating at least one limit associated with the compressed set using at least one vertex in the set of vertices.

9. A system for determining dependencies in a tiled loop nest, 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 implement a compiler to:

receive a program source code comprising an un-tiled loop nest;

obtain: (i) a set of pre-tiling dependencies (D) corresponding to a statement in the un-tiled loop nest comprising a plurality of loop dimensions, and (ii) a tiling set (G) corresponding to a tiling scheme to be applied to the loop nest, the tiling scheme introducing at least one tiled dimension corresponding to at least one loop dimension of the loop nest;

generate based on, at least in part, the set of pre-tiling dependencies (D), a set of modified pre-tiling dependencies (A);

generate based on, at least in part, the tiling set (G), a set of compressed intra-tile dependencies (X);

compress the set of modified pre-tiling dependencies (A) using the tiling set (G) to obtain a compressed set of modified pre-tiling dependencies (AG);

generate a set of post-tiling dependencies associated with the statement based on, at least in part, the compressed set and the set of compressed intra-tile dependencies (X); and

generate by the compiler, a schedule of operation of the statement according to the set of post-tiling dependencies, to facilitate parallelized execution of the program.

10. The system of claim 9 , wherein the processing unit is programmed to represent the tiling set (G) as a matrix, each column of the matrix being associated with a respective loop dimension to be tiled.

11. The system of claim 10 , wherein the tiling set (G) comprises a diagonal matrix.

12. The system of claim 9 , wherein:

the set of pre-tiling dependencies comprises a first relation comprising a first loop index that is associated with a first loop dimension; and

to generate the set of modified pre-tiling dependencies (A), the processing unit is programmed to represent the first relation in a form: an expression of the first loop index greater than or equal to zero.

13. The system of claim 9 , wherein the processing unit is programmed to generate the set of modified pre-tiling dependencies (A) independently of the tiling set (G).

14. The system of claim 9 , wherein the processing unit is programmed to generate the set of compressed intra-tile dependencies (X) independently of the set of pre-tiling dependencies (D).

15. The system of claim 9 , wherein to generate the set of post-tiling dependencies, the processing unit is programmed to compute a direct sum of the compressed set and the set of compressed intra-tile dependencies (X).

16. The system of claim 9 , wherein to generate the set of post-tiling dependencies, the processing unit is programmed to:

determine a set of vertices associated with the set of compressed intra-tile dependencies (X); and

inflate at least one limit associated with the compressed set using at least one vertex in the set of vertices.