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

Patent metadata

Field	Value
Publication number	US-10095434-B2
Application number	US-201614987223-A
Country	US
Kind code	B2
Filing date	Jan 4, 2016
Priority date	Jan 2, 2015
Publication date	Oct 9, 2018
Grant date	Oct 9, 2018

Abstract

A compilation system can compile a program to be executed using an event driven tasks (EDT) system that requires knowledge of dependencies between program statement instances, and generate the required dependencies efficiently when a tiling transformation is applied. To this end, the system may use pre-tiling dependencies and can derive post-tiling dependencies via an analysis of the tiling to be applied.

First claim

What is claimed is:

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.

Assignees

• Reservoir Labs Inc

Inventors

• Baskaran Muthu M
• Henretty Thomas
• Johnson Ann
• Konstantinidis Athanasios
• Langston M H
• Mcmahon Janice O
• Meister Benoit J
• Mountcastle Paul D
• Naqvi Aale
• Pradelle Benoit
• Ramananandro Tahina
• Tavarageri Sanket
• Lethin Richard A

Classifications

• G06F8/4441

  Reducing the execution time required by the program code · CPC title

• G06F3/0671

  In-line storage system · CPC title

• G06F3/0631 Primary

  by allocating resources to storage systems · CPC title

• G06F3/0604

  Improving or facilitating administration, e.g. storage management · CPC title

• G06F8/453

  Data distribution · CPC title