Tiling as a loop transformation technique

 

When targeting a data-parallel or SPMD style of programming, classical constraints in the literature to define tiles are the following:

Tiles are bounded

For scalability reasons, we want the number of points inside a tile to be bounded by a constant independent of the domain size.

Tiles are identical by translation

This constraint is imposed to allow for automatic code generation: a tile must be the image by a translation of any other one unless it crosses the computation domain boundaries.

Tiles are ``atomic''

Each tile is a unit of computation: all synchronization points are beginnings and ends of tiles. The order on tiles must be compatible with the order on nodes: one must thus avoid that two distinct tiles depend upon each other.

As already said, tiling is restricted to perfectly nested loops with uniform dependences, such as the following simple example: