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

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.