On optimal tiling of iteration spaces

The distributed memory architecture for parallel processing has the advantages of high levels of flexibility and scalability. However, due to the higher communication startup cost in these machines, frequent communication is very expensive. Tiling is a technique for the extraction of parallelism which groups the iterations into blocks called ´tiles´ such that a sequential traversal of the tiles covers the entire iteration space. The size of the tile is very important in determining the efficiency of execution: the larger the tile size the lower the communication cost, and vice versa. In this paper, a method for determining the optimal tile size for tiling 2D iteration spaces of a DOACROSS loop nest is presented The results reported are based on a wavefront execution of the tiles.